1998/12/18 by Edward Farhi, E. Farhi, Farhi, E. +8 · 13 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Computability, Logic, AI Algorithms #Computation #Computer science #Discrete mathematics #FOS: Physical sciences #Geometry #Limit (mathematics) #Mathematical analysis #Mathematics #Physics #Point (geometry) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum computer #Quantum mechanics #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9812057
published in arXiv (Cornell University) (Cornell University) · 5 pages
arxiv created 1998/12/18 · openalex publication_date 1998/12/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the problem of inserting a new item into an ordered list of N-1 items. The length of an algorithm is measured by the number of comparisons it makes between the new item and items already on the list. Classically, determining the insertion point requires log N comparisons. We show that, for N large, no quantum algorithm can reduce the number of comparisons below log N/(2 loglog N).