A fast quantum mechanical algorithm for estimating the median. Quantum Physics e-Print archive

Consider the problem of estimating the median of N items to a precision ε, i.e. the estimate µ should be such that, with a large probability, the number of items with values smaller than µ is less than and those with values greater than µ is also less than. Any classical algorithm to do this will need at least samples. Quantum mechanical systems can simultaneously carry out multiple computations due to their wave like properties. This paper gives an step algorithm for the above problem.