1999/01/19 by Edward Farhi, Farhi, Edward, Jeffrey Goldstone +5
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/9901059
19 pages, LaTeX, amssymb,amsmath packages; email to [email protected]
arxiv created 1999/01/19 · openalex publication_date 1999/01/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.