1996/07/29 by Lov K. Grover, Grover, Lov K. · 3 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9607024
14 pages, single postscript file
arxiv created 1996/07/29 · openalex publication_date 1996/07/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider the problem of estimating the median of N items to a precision epsilon, i.e., the estimate should be such that, with a high probability, the number of items, with values both smaller than and larger than this estimate, is less than N*(1+epsilon)/2. Any classical algorithm to do this will need at least O(1/epsilon2) samples. Quantum mechanical systems can simultaneously carry out multiple computations due to their wave like properties. This paper describes an O(1/epsilon) step algorithm for the above estimation.