Limitations of quantum counting, nested quantum search and amplitude amplification and their potential to solve discrete optimization problems
- 11 December 2025
- journal article
- Published by The Royal Society in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 383 (2310)
Abstract
Several quantum algorithms have been proposed for solving discrete optimization problems. In this paper, we focus on the quantum counting algorithm (QCB) of Brassard G, Høyer P, Tapp A. 1998 Quantum counting. In Automata, languages and programming (eds KG Larsen, S Skyum, G Winksel), pp. 820–831. Berlin Heidelberg, Berlin, Heidelberg: Springer. (doi:10.1007/BFb0055105), the nested quantum search algorithm of Cerf NJ, Grover LK, Williams CP. 2000 Nested quantum search and structured problems. Phys. Rev. 61. (doi:10.1103/physreva.61.032303), and amplitude amplification. We discuss potential limitations of these quantum algorithms and investigate how they can be used to solve discrete optimization problems. Our goal is to provide a set of practical guidelines that can help researchers to effectively implement Grover-based quantum algorithms. This article is part of the theme issue ‘Quantum theory and topology in models of decision making (Part 2)’.Keywords
This publication has 12 references indexed in Scilit:
- Discrete optimization: A quantum revolution?European Journal of Operational Research, 2024
- Challenges and opportunities in quantum optimizationNature Reviews Physics, 2024
- Iterative quantum amplitude estimationnpj Quantum Information, 2021
- Amplitude estimation without phase estimationQuantum Information Processing, 2020
- Algorithms for quantum computation: discrete logarithms and factoring2002
- Quantum amplitude amplification and estimation2002
- Nested quantum search and structured problemsPhysical Review A, 2000
- Grover’s quantum searching algorithm is optimalPhysical Review A, 1999
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Quantum counting1998