Quantum Chebyshev’s inequality and applications
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.