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.ESA.2019.16
URN: urn:nbn:de:0030-drops-111370
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11137/
Go to the corresponding LIPIcs Volume Portal

Belovs, Aleksandrs

Quantum Algorithms for Classical Probability Distributions

pdf-format:
LIPIcs-ESA-2019-16.pdf (0.4 MB)

Abstract

We study quantum algorithms working on classical probability distributions. We formulate four different models for accessing a classical probability distribution on a quantum computer, which are derived from previous work on the topic, and study their mutual relationships.
Additionally, we prove that quantum query complexity of distinguishing two probability distributions is given by their inverse Hellinger distance, which gives a quadratic improvement over classical query complexity for any pair of distributions.
The results are obtained by using the adversary method for state-generating input oracles and for distinguishing probability distributions on input strings.

BibTeX - Entry

@InProceedings{belovs:LIPIcs:2019:11137,
  author =	{Aleksandrs Belovs},
  title =	{{Quantum Algorithms for Classical Probability Distributions}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{16:1--16:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11137},
  URN =		{urn:nbn:de:0030-drops-111370},
  doi =		{10.4230/LIPIcs.ESA.2019.16},
  annote =	{Keywords: quantum query complexity, quantum adversary method, distinguishing probability distributions, Hellinger distance}
}

Keywords: quantum query complexity, quantum adversary method, distinguishing probability distributions, Hellinger distance
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

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