A fast quantum mechanical algorithm for estimating the median

Lov K. Grover

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 b…