Quantum Mechanical Square Root Speedup in a Structured Search Problem

Abstract

An unstructured search for one item out of N can be performed quantum mechanically in time of order square root of N whereas classically this requires of order N steps. This raises the question of whether square root speedup persists in problems with more structure. In this note we focus on one example of a structured problem and find a quantum algorithm which takes time of order the square root of the classical time.

6 pages, REVTeX; correspondence to farhi@mitlns.mit.edu