Quantum Chebyshev's Inequality and Applications
arXiv:1807.06456 · doi:10.4230/LIPIcs.ICALP.2019.69
Abstract
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 of order in the multi-pass streaming model with updates (turnstile model). We design a -pass quantum streaming algorithm with memory satisfying a tradeoff of , whereas the best classical algorithm requires . Then, we study the problem of estimating the number of edges and the number of triangles given query access to an -vertex graph. We describe optimal quantum algorithms that perform and 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.
arXiv comment27 pages; v3: better presentation, lower bound in Theorem 4.3 is new
References in corpus (13)
- Quantum speedup of Monte Carlo methods
- Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
- Optimal Quantum Measurements of Expectation Values of Observables
- Quantum communication complexity of symmetric predicates
- Pseudorandom States, Non-Cloning Theorems and Quantum Money
- Speed-up via Quantum Sampling
- Optimal Algorithms for Testing Closeness of Discrete Distributions
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Quantum Speed-up for Approximating Partition Functions
- Quantum algorithms for testing properties of distributions
- An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
- A simpler sublinear algorithm for approximating the triangle count
- Quantum algorithm for exact Monte Carlo sampling