# Quantum Chebyshev's Inequality and Applications

arXiv: https://arxiv.org/abs/1807.06456 · HTML: https://mlsanity.com/paper/1807.06456/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2018.

## Built on by (most cited first, 10 of 10)

- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models](https://mlsanity.com/paper/2510.08462/) (2025)
- [Quantum speedup of non-linear Monte Carlo problems](https://mlsanity.com/paper/2502.05094/) (2025)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)

## Abstract (arXiv)

In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we consider the approximation of the frequency moments Fk of order k ≥ 3 in the multi-pass streaming model with updates (turnstile model). We design a P-pass quantum streaming algorithm with memory M satisfying a tradeoff of P2 M = tildeO(n1-2/k), whereas the best classical algorithm requires P M = Theta(n1-2/k). Then, we study the problem of estimating the number m of edges and the number t of triangles given query access to an n-vertex graph. We describe optimal quantum algorithms that perform tildeO(√n/m1/4) and tildeO(√n/t1/6 + m3/4/√t) queries respectively. This is a quadratic speed-up compared to the classical complexity of these problems. For this purpose we develop a new quantum paradigm that we call Quantum Chebyshev's inequality. Namely we demonstrate that, in a certain model of quantum sampling, one can 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. Our algorithm subsumes a previous result of Montanaro [Mon15]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [BHMT02] and of previous quantum algorithms for the mean estimation problem. We show that this speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. For our applications, we also adapt the variable-time amplitude amplification technique of Ambainis [Amb10] into a variable-time amplitude estimation algorithm.