The quantum query complexity of approximating the median and related statistics

Ashwin Nayak, Felix Wu

Let X = (x_0,...,x_{n-1})$ be a sequence of n numbers. For ε> 0, we say that x_i is an ε-approximate median if the number of elements strictly less than x_i, and the number of elem…