Quantum Chebyshev's Inequality and Applications

Understand

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 $F_k$ of order $k \geq 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 $P^2 M = \tilde{O}(n^{1-2/k})$, whereas the best classical algorithm requires $P M = \Theta(n^{1-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.