License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.69
URN: urn:nbn:de:0030-drops-106458
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10645/
Go to the corresponding LIPIcs Volume Portal

Hamoudi, Yassine ; Magniez, Frédéric

Quantum Chebyshev's Inequality and Applications

pdf-format:
LIPIcs-ICALP-2019-69.pdf (0.6 MB)

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 F_k 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 P^2 M = 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. 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 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 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 speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. Finally, we develop a new technique called "variable-time 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:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10645},
  URN =		{urn:nbn:de:0030-drops-106458},
  doi =		{10.4230/LIPIcs.ICALP.2019.69},
  annote =	{Keywords: Quantum algorithms, approximation algorithms, sublinear-time algorithms, Monte Carlo method, streaming algorithms, subgraph counting}
}

Keywords: Quantum algorithms, approximation algorithms, sublinear-time algorithms, Monte Carlo method, streaming algorithms, subgraph counting
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI