License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.59
URN: urn:nbn:de:0030-drops-137048
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13704/
Go to the corresponding LIPIcs Volume Portal

Venkateswaran, Ramgopal ; O'Donnell, Ryan

Quantum Approximate Counting with Nonadaptive Grover Iterations

pdf-format:
LIPIcs-STACS-2021-59.pdf (0.6 MB)

Abstract

Approximate Counting refers to the problem where we are given query access to a function f : [N] → {0,1}, and we wish to estimate K = #{x : f(x) = 1} to within a factor of 1+ε (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with O(min (√{N/ε}, √{N/K} / ε) queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve O(√{N/ε}) query complexity, which is tight.

BibTeX - Entry

@InProceedings{venkateswaran_et_al:LIPIcs.STACS.2021.59,
  author =	{Venkateswaran, Ramgopal and O'Donnell, Ryan},
  title =	{{Quantum Approximate Counting with Nonadaptive Grover Iterations}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13704},
  URN =		{urn:nbn:de:0030-drops-137048},
  doi =		{10.4230/LIPIcs.STACS.2021.59},
  annote =	{Keywords: quantum approximate counting, Grover search}
}

Keywords: quantum approximate counting, Grover search
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

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