LIPIcs.STACS.2021.59.pdf
- Filesize: 0.61 MB
- 12 pages
Document
Quantum Approximate Counting with Nonadaptive Grover Iterations
Authors
-
Part of:
Volume:
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-03-10
File
Document Identifiers
Acknowledgements
The authors would like to thank Scott Aaronson and Patrick Rall for helpful communications.
Cite As Get BibTex
Ramgopal Venkateswaran and Ryan O'Donnell. Quantum Approximate Counting with Nonadaptive Grover Iterations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.59
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Quantum complexity theory
Keywords
- quantum approximate counting
- Grover search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity in Algorithms, pages 24-32. SIAM, 2020.
-
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493-505, 1998.
-
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
- Paul Burchard. Lower bounds for parallel quantum counting, 2019. URL: http://arxiv.org/abs/1910.04555.
- Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude estimation, 2020. URL: http://arxiv.org/abs/1912.05559.
-
Lov Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212-219, 1996.
- Kouhei Nakaji. Faster amplitude estimation, 2020. URL: http://arxiv.org/abs/2003.02417.
-
Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 384-393, 1999.
-
Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation without phase estimation. Quantum Information Processing, 19(2):75, 2020.
-
Chu-Ryang Wei. Simpler quantum counting. Quantum Information and Computation, 19(11&12):0967-0983, 2019.