In An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance Brassard presents a quantum algorithm for finding the mean output of a function

$F(1,..,N) \implies [0,1]$

in time $O(1/\text{error})$. The paper implies that an equivalent classical algorithm would take $O(1/\text{error}^2)$ (actually it gives results for error in terms of time, but no matter).

The classical algorithm is not actually given but I assume it would just be repeated sampling from $F$ with error properties depending on the sample mean formula $\sigma_\bar{F}=\sigma_F/\sqrt{n}$. The validity of $\sigma_\bar{F}$ therefore does not depend on the distribution of $F$, although if we are interested in the distribution of $\bar{F}$ then the distribution of $F$ becomes important.

Does Brassard's mean1 algorithm differ at all from the classical counterpart in its dependence on distribution of $F$? i.e. the distribution does not matter so far as $\sigma_\bar{F}$ is concerned but is important if we are interested in the distribution of the mean?

  • 1
    $\begingroup$ I looked at the paper by Brassard et al and I think it is strange that Brassard does not mention the equivalent classical algorithm for the mean. A maths paper should always be crystal clear not leave the reader assuming something. $\endgroup$ – Learner Feb 8 '19 at 2:01
  • 1
    $\begingroup$ I was thinking , Brassard's paper you mention is unrefereed paper on ArXiv maybe the final refereed paper does mention the exact choice or exact algorithm of how the mean is classically computed? $\endgroup$ – Learner Feb 8 '19 at 2:04
  • $\begingroup$ Hmm. Where did it get published in the end I wonder? quick search is unsuccessful. $\endgroup$ – Sideshow Bob Feb 8 '19 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.