A fast quantum mechanical algorithm for estimating the median

Abstract

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/epsilon^2) 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.

14 pages, single postscript file

Cited by in corpus (11)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Computation in Quantum-Hall Systems
• Quantum Computation
• Dynamic Grover Search: Applications in Recommendation systems and Optimization problems
• An Introduction to Quantum Game Theory
• The quantum query complexity of approximating the median and related statistics
• Speedup of iterated quantum search by parallel performance
• Design of gates for quantum computation: the three-spin XOR gate in terms of two-spin interactions
• Theoretical Analyses of Quantum Counting against Decoherence Errors
• Quantum Information Processing with Single Photons
• Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm