Quantum Mechanical Square Root Speedup in a Structured Search Problem

Edward Farhi, Sam Gutmann

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…