# Does Brassard's algorithm for calculating the mean make implicit assumptions on distribution?

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?

• 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. – Learner Feb 8 at 2:01
• 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? – Learner Feb 8 at 2:04
• Hmm. Where did it get published in the end I wonder? quick search is unsuccessful. – Sideshow Bob Feb 8 at 14:38