Does anyone know the solution of Exercise 6.14 of Nielsen and Cheung:
Prove that any classical counting algorithm with a probability at least 3/4 for estimating $M$ correctly to within an accuracy $c \sqrt{M}$ for some constant $c$ and for all values of $M$ must make $\Omega(N)$ oracle calls.
The same result is also stated in Mosca's phd thesis in Table 2.5 but with no references where this is proved.
Mosca's phd thesis cites
Ran Canetti, Guy Even, and Oded Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters, 1995.
and
Goldreich, Oded. "A sample of samplers: A computational perspective on sampling." Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, Berlin, Heidelberg, 2011. 302-332.
but from those I see a complexity of $\Omega(M)$ not $\Omega(N)$
