Hamoudi, Yassine ;
Magniez, Frédéric
Quantum Chebyshev's Inequality and Applications
Abstract
In this paper we provide new quantum algorithms with polynomial speedup 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 >= 3 in the multipass streaming model with updates (turnstile model). We design a Ppass quantum streaming algorithm with memory M satisfying a tradeoff of P^2 M = O~(n^{12/k}), whereas the best classical algorithm requires P M = Theta(n^{12/k}). Then, we study the problem of estimating the number m of edges and the number t of triangles given query access to an nvertex graph. We describe optimal quantum algorithms that perform O~(sqrt{n}/m^{1/4}) and O~(sqrt{n}/t^{1/6} + m^{3/4}/sqrt{t}) queries respectively. This is a quadratic speedup 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 dependence is quadratic. Our algorithm subsumes a previous result of Montanaro [Montanaro, 2015]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [Brassard et al., 2002] and of previous quantum algorithms for the mean estimation problem. We show that this speedup is optimal, and we identify another common model of quantum sampling where it cannot be obtained. Finally, we develop a new technique called "variabletime amplitude estimation" that reduces the dependence of our algorithm on the sample preparation time.
BibTeX  Entry
@InProceedings{hamoudi_et_al:LIPIcs:2019:10645,
author = {Yassine Hamoudi and Fr{\'e}d{\'e}ric Magniez},
title = {{Quantum Chebyshev's Inequality and Applications}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {69:169:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10645},
URN = {urn:nbn:de:0030drops106458},
doi = {10.4230/LIPIcs.ICALP.2019.69},
annote = {Keywords: Quantum algorithms, approximation algorithms, sublineartime algorithms, Monte Carlo method, streaming algorithms, subgraph counting}
}
2019
Keywords: 

Quantum algorithms, approximation algorithms, sublineartime algorithms, Monte Carlo method, streaming algorithms, subgraph counting 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 