1997/11/18 by Edward Farhi, Farhi, Edward, Sam Gutmann +1 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9711035
6 pages, REVTeX; correspondence to [email protected]
arxiv created 1997/11/18 · openalex publication_date 1997/11/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.