Frederic Magniez, Université Paris Diderot
We describe a new quantum paradigm, that we call Quantum Chebyshev’s inequality, to approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependency is quadratic. To illustrate this method, we apply it to the approximation of frequency moments in the multi-pass streaming model, and to the approximation of the number of edges and triangles in the quantum graph query access model. This new paradigm is based on a refinement of the Amplitude Estimation algorithm, and of previous quantum algorithms for the mean estimation problem. It is optimal and it subsumes a previous result of Montanaro.
Joint work with Yassine Hamoudi.