2026-07-29T07:07:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13704 2024-03-06T10:52:42Z ddc:004 open_access

Quantum Approximate Counting with Nonadaptive Grover Iterations Venkateswaran, Ramgopal O'Donnell, Ryan quantum approximate counting Grover search 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ramgopal Venkateswaran and Ryan O'Donnell 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.59 urn:nbn:de:0030-drops-137048 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.59 eng https://creativecommons.org/licenses/by/4.0/legalcode