Authors: Daniel Koch, Brian Pardo, Kip Nieman (Air Force Research Laboratory)

---

Combinatorial optimisation problems frequently challenge classical computing resources, driving exploration into quantum solutions. Daniel Koch, Brian Pardo, and Kip Nieman, all from the Air Force Research Laboratory, have investigated the potential of Quantum Amplitude Amplification (QAA) to efficiently find optimal solutions. Their research extends the conventional framework of Grover’s algorithm to oracles encoding cost functions, such as those found in Quadratic Unconstrained Binary Optimisation (QUBO) problems, and importantly reveals an exact formula for parameter settings with linear cost functions. Through simulations and experimental demonstrations on both IBMQ and IonQ platforms, the team validates QAA’s performance across a range of problem sizes, showcasing its ability to achieve Grover‑like performance particularly close to the global optimum and confirming the accuracy of their theoretical predictions.

This work establishes that linear cost functions possess a unique symmetry allowing for the derivation of an exact formula to determine optimal oracle parameter settings, streamlining the process of finding solutions. Simulations involving up to 40 qubits demonstrated QAA’s performance across all possible solutions, noting a performance closely resembling Grover’s algorithm when identifying solutions near the global optimum.

The study unveils a novel approach to QAA by utilizing cost oracles, quantum operators that apply phases proportional to the cost of each solution, offering a potentially more efficient circuit implementation compared to traditional Grover oracles. Researchers meticulously analyzed the algorithmic performance using simulations, demonstrating peak probabilities and required iterations for identifying solutions across a range of problem sizes. Experiments were then conducted on both IBMQ superconducting qubits and IonQ trapped‑ion qubits, validating the theoretical predictions by showing that observed probabilities align with the equations governing the oracle and diffusion operators. This represents the first experimental demonstration of generalized QAA employing cost oracles, marking a crucial step towards practical quantum optimisation.

The breakthrough reveals a method for precisely controlling the parameters within QAA, enabling researchers to tailor the algorithm to specific optimisation problems. The team successfully implemented and tested QAA on quantum hardware from two leading providers, IBMQ and IonQ, varying free parameters within the oracle and diffusion operators to observe corresponding changes in basis‑state probabilities. These experimental results, conducted on systems up to 5 qubits and incorporating noise‑mitigation techniques, confirm the accuracy of the derived equations and the viability of the generalized QAA approach. The work opens avenues for developing more efficient quantum algorithms for tackling real‑world optimisation challenges in fields such as logistics, finance, and materials science.

The research establishes a clear connection between the structure of cost functions and the optimal configuration of QAA parameters. Specifically, the study proves that linear cost functions allow for the precise calculation of oracle settings, simplifying the implementation of the algorithm and potentially improving its performance. Simulations up to 40 qubits demonstrate that as problem size increases, the algorithm’s ability to identify globally optimal solutions approaches the efficiency of Grover’s algorithm, a benchmark for quantum search. This work pioneered a method for determining optimal oracle parameter settings, demonstrating that linear cost functions possess a unique symmetry allowing for exact formulaic prediction. The detailed analysis revealed a convergence towards Grover‑like performance as problem complexity increased.

To validate theoretical predictions, the study harnessed both IBMQ superconducting qubits and IonQ trapped‑ion qubits for experimental demonstrations of generalized QAA. The team engineered a system where the probabilities of each basis state were measured and directly compared to equations derived from their model, varying free parameters within both the oracle and diffusion operators. Experiments employed alternating oracle and diffusion operations, each governed by adjustable parameters, allowing for precise control over the quantum state evolution. This approach enables a detailed examination of how parameter settings influence the probability distribution across possible solutions.

A key methodological innovation lies in the development of cost oracles, inspired by the phase‑separator operator in the Quantum Approximate Optimisation Algorithm (QAOA), but designed for enhanced circuit efficiency. Unlike traditional Grover oracles requiring complex N‑Toffoli gates, these cost oracles offer a streamlined implementation. The research demonstrated that a fixed diffusion parameter of π can achieve high probabilities—exceeding 90%—of measuring optimal solutions. Furthermore, the study established an exact formula for predicting optimal oracle parameter settings specifically for linear cost functions, a significant advancement in simplifying QAA implementation.

Grover‑Like Performance in Complex Quantum Searches

Scientists achieved a significant breakthrough in quantum amplitude amplification (QAA), extending the conventional two‑dimensional representation of Grover’s algorithm to oracles encoding complex cost functions like those found in QUBO problems. The research demonstrates that linear cost functions represent a unique case, allowing the derivation of an exact formula to determine optimal oracle parameter settings. Simulations up to 40 qubits measured algorithmic performance across all potential solutions, focusing on the similarity to Grover‑like performance for solutions approaching the global optimum. Experiments revealed that peak probabilities and iterations required to identify globally optimal solutions increasingly resemble Grover’s algorithm as problem size grows.

The work details the first experimental demonstration of generalized QAA utilizing cost oracles, conducted on both IBMQ and IonQ platforms. Measurements confirm that the observed probabilities of each basis state align with theoretical predictions as the free parameters within the oracle and diffusion operators are varied. Simulations using up to 40 qubits showed high measurement probabilities—exceeding 90%—when employing a diffusion parameter setting of π. The study introduces a generalized framework for cost oracles, extending the traditional Grover oracle by defining collective states based on cost‑function evaluations.

Researchers formulated a cost oracle (U_C(p_s)) described by

[

U_C(p_s),|Z_i\rangle = e^{i,C(Z_i),p_s},|Z_i\rangle,

]

where (C(Z_i)) is the cost function value for bit string (Z_i) and (p_s) is the phase scale. This generalisation allows oracles with more than two unique phases, expanding QAA’s applicability to a broader range of combinatorial optimisation problems. The diffusion operator (U_s(\theta)) was implemented using a standard construction, effectively acting as a mixer within the QAA framework. Further experiments on up to five qubits varied the free parameter in either the oracle or diffusion operator and compared measured basis‑state probabilities with predicted theoretical values. These tests, performed on both IBMQ and IonQ systems with and without vendor‑implemented noise mitigation, validate the theoretical framework and demonstrate the feasibility of generalized QAA on current quantum hardware. For linear cost functions, an exact equation determines optimal oracle‑parameter settings, offering a significant refinement to quantum amplitude amplification techniques. Simulations involving up to 40 qubits confirm that the performance of these cost oracles is comparable to that of Grover oracles, while also revealing a broader range of potential solutions. Experimental implementations on both IBMQ and IonQ platforms show observed probabilities aligning with the equations derived for generalized QAA.

The study acknowledges limitations in determining optimal oracle parameter settings for more complex, non‑linear problems such as QUBO, identifying this as an area for future investigation. Researchers suggest exploring methods such as the Grover‑Mixer QAOA approach, pre‑computing optimal operator settings to enhance efficiency, and considering alternative hardware implementations beyond gate‑based models, such as photonic integrated circuits. Current experimental results demonstrate the ability to implement this approach with up to five qubits, and the authors note that substantial technological advancements will be necessary to significantly increase this number in the near future.

---

Reference

Analysis and Experimental Demonstration of Amplitude Amplification for Combinatorial Optimization – arXiv: 2601.10473