The quantum query complexity of approximating the median and related statistics

Let X = (z,, , z,-,) be a sequence of n numbers. For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):. We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle. We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2. We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121. Thus, the lower bound we obtain is essentially optimal. The upper and the lower bound both hold in the comparison tree model as well.