On the quantum black-box complexity of approximating the mean and the median

Preprint
Publisher Website
Google Scholar
  • 29 April 1998
Abstract
Let f : {0,1,...,n-1} --> {0,1} be a boolean function which is equal to 1 at exactly (1+ delta)n/2 points of the domain, where delta is either equal to 0 or to epsilon, for some 0 < epsilon <= 1. Consider the problem of deciding whether delta = epsilon or delta = 0, given an oracle for such a function f. We show that any quantum algorithm that solves this problem with any constant probability greater than 1/2 must make Omega(1/epsilon) calls to the oracle for f. The abstract problem defined above can readily be reduced to the problem of approximating the mean or the median of a set of numbers to within epsilon, thereby implying a lower bound of Omega(1/epsilon) for these two problems as well.

This publication has 0 references indexed in Scilit: