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 representation of Grover's (orthogonal collective states) to oracles which encode cost functions such as QUBO, and show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings. Using simulations of problem sizes up to 40 qubits we demonstrate QAA's algorithmic performance across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with experimental demonstrations of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, showing that the observed probabilities of each basis state match our equations as a function of varying the free parameters in the oracle and diffusion operators.
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 representation of Grover's (orthogonal collective states) to oracles which encode cost functions such as QUBO, and show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings. Using simulations of problem sizes up to 40 qubits we demonstrate QAA's algorithmic performance across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with experimental demonstrations of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, showing that the observed probabilities of each basis state match our equations as a function of varying the free parameters in the oracle and diffusion operators.
Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is well-positioned for combinatorial optimization and is particularly promising for Quadratic Unconstrained Binary Optimization (QUBO) problems. QAA is appealing due to its ability to drive the quantum system to a target state, yielding the globally optimal solution with probability over 90+%. However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity, which is further compounded by unresolved algorithmic challenges regarding the choice of free parameters. In this study, we address these issues by utilizing a realistic traffic flow QUBO problem to investigate the implementation of QAA as a heuristic solver. Specifically, allowing the diffusion operator parameter to take non-π values expands the capabilities of QAA. This unlocks a new multiple-shot, low-iteration strategy that aims for a high cumulative probability rather than maximizing the probability of a single basis state. Using 25-qubit simulations, our results demonstrate that heuristic QAA addresses two of the main challenges cited in previous studies. Firstly, heuristic QAA works even at a single iteration, reducing circuit depth by orders of magnitude compared to standard QAA. And secondly, we show that the problem-dependent parameters necessary for reaching optimal algorithmic performance can be reliably approximated with minimal upfront classical computing overhead.
We investigate the use of amplitude amplification on the gate-based model of quantum computing as a means for solving combinatorial optimization problems. This study focuses primarily on quadratic unconstrained binary optimization (QUBO) problems, which are well-suited for qubit superposition states. Specifically, we demonstrate circuit designs which encode QUBOs as ‘cost oracle’ operations UC, which distribute phases across the basis states proportional to a cost function. We then show that when UC is combined with the standard Grover diffusion operator Us, one can achieve high probabilities of measurement for states corresponding to optimal and near optimal solutions while still only requiring O(π42N/M) iterations. In order to achieve these probabilities, a single scalar parameter ps is required, which we show can be found through a variational quantum–classical hybrid approach and can be used for heuristic solutions.
We propose an algorithm using a modified variant of amplitude amplification to solve combinatorial optimization problems via the use of a subdivided phase oracle. Instead of dividing input states into two groups and shifting the phase equally for all states within the same group, the subdivided phase oracle changes the phase of each input state uniquely in proportion to their objective value. We provide visualization of how amplitudes change after each iteration of applying the subdivided phase oracle followed by conventional Grover diffusion in the complex plane. We then show via numerical simulation that for normal, skew normal, and exponential distribution of objective values, the algorithm can be used to amplify the probability of measuring the optimal solution to a significant degree independent of the search space size. In the case of skew normal and exponential distributions, this probability can be amplified to be close to unity, making our algorithm near deterministic. We then modify our algorithm in order to demonstrate how it can be extended to a broader set of objective value distributions. Finally, we discuss the speedup compared to classical schemes using the query complexity model, and show that our algorithm offers a significant advantage over these classical approaches.
We study an oracle operation, along with its circuit design, which combined with the Grover diffusion operator boosts the probability of finding the minimum or maximum solutions on a weighted directed graph. We focus on the geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by Gaussian distributions. We then demonstrate how an oracle that encodes these distributions can be used to solve for the optimal path via amplitude amplification. And finally, we explore the degree to which this algorithm is capable of solving cases that are generated using randomized weights, as well as a theoretical application for solving the Traveling Salesman problem.
We present a family of quantum amplitude amplification algorithms that interleave ordinary Grover rotations with tunable weak measurements in loops. A successful measurement yields the target state and stops the algorithm, while after a failure, the loop resumes from the post-measurement state without restarting. We express the leading costs in expected Grover iterations as p→0. For a known target probability p, an exact weak measurement-conditioned loop for states near the angle π/4 uses (π/8+1/4+o(1))/p iterations, improving on the standard Grover constant π/4 and on optimised restart Grover, and matching the corresponding infimum in our continuous-angle analysis. When only a lower bound 0<p0≤p<1/2 is available, a discrete Lyapunov equation gives the exact expected oracle cost for every fixed measurement strength and a closed-form optimal strength. Using the strength selected from p0, the expected number of Grover iterations is at most 221(p1+p01), where the expected cost decreases as the actual p increases, and gives the leading constant 1/2 at the promise boundary p=p0. For completely unknown p, we identify measurement strength κ(t)=Θ(1/t) as the critical scale within the regular schedules considered here and analyse κb(t)=min{1/2,b/t}. For each fixed b>2, we rigorously derive a closed-form Gamma-function expression C(b) giving (C(b)/2+o(1))/p expected iterations. Numerical minimisation of this explicit expression gives b≈5.2 and C(b)/2≈1.01. The results show that weak measurements preserve the Θ(1/p) search scale while adding an explicit fixed-point control mechanism and provable oracle savings.