Open Access

ARTICLE

Analysis and Experimental Demonstration of Amplitude Amplification for Combinatorial Optimization

Daniel Koch^1,*, Brian Pardo², Kip Nieman²

1 Air Force Research Lab, Information Directorate, Rome, NY, USA
2 National Academy of Sciences, Washington, DC, USA

* Corresponding Author: Daniel Koch. Email:

Journal of Quantum Computing 2026, 8, 75-100. https://doi.org/10.32604/jqc.2026.079392

Received 20 January 2026; Accepted 13 May 2026; Issue published 26 June 2026

Abstract

Quantum Amplitude Amplification (QAA), the generalization of Grover’s algorithm, is capable of yielding optimal solutions to combinatorial optimization problems with high probabilities. In this work we extend the conventional 2-dimensional mathematical representation of Grover’s (marked and non-marked orthogonal collective states) to oracle operators which encode cost functions, such as those shown in previous studies with QUBO (Quadratic Unconstrained Binary Optimization). We show that unconstrained linear cost functions (no quadratic or higher terms) are a special case whereby the symmetry of the system leads to an exact formula for determining optimal oracle parameter settings, the first known case for non-Grover QAA. Using simulations of problem sizes up to 40 qubits we demonstrate QAA’s algorithmic performance using our derived equation for oracle parameter values across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with a first-of-its-kind experimental demonstration of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, with and without error mitigation techniques from the respective hardware vendors. In addition to the first ever 5-qubit Grover’s experimental demonstration on a trapped ion system, we show that the observed probabilities of each basis state agree with theoretical predictions for the full range of free parameter values in the oracle and diffusion operators.

---

Keywords

---