Self-Tuning Quantum Algorithm Cracks Constrained Shortest Path Problem With Fewer Resources

Quantum computers promise to transform how humanity tackles some of the hardest computational puzzles, but a stubborn practical question has long stood in the way: how deep should a quantum circuit be? Researchers at the Qatar Center for Quantum Computing at Hamad Bin Khalifa University, together with a colleague at Hurghada University in Egypt, have now unveiled an elegant answer. In a study published in Quantum Machine Intelligence, they introduce the Dynamic Depth Quantum Approximate Optimization Algorithm, or DDQAOA, a variant of one of the most celebrated quantum optimization methods that decides for itself how many circuit layers it needs, growing only when the evidence demands it.

The Quantum Approximate Optimization Algorithm, known as QAOA, has become the workhorse of near-term quantum optimization. It works as a hybrid quantum-classical dance: a quantum processor prepares a candidate state, a classical optimizer tunes the circuit’s angles, and the two repeat until a good solution emerges. The catch is that QAOA’s performance hinges on a parameter called depth, denoted p, which counts how many alternating layers of problem and mixing operations the circuit contains. Deeper circuits generally produce better answers, but they demand more two-qubit gates, more classical optimization effort, and more tolerance of hardware noise. Until now, practitioners had to guess this depth in advance, with no reliable guidance.

Guessing wrong is costly in both directions. A circuit that is too shallow is underparameterized and cannot represent a high-quality solution, particularly as problems grow denser and more constrained. A circuit that is too deep burns scarce quantum resources on layers that add nothing, a serious problem on today’s noisy intermediate-scale quantum devices where every additional two-qubit gate multiplies the chance of error. The research team, led by Rakesh Saini with co-authors Nora Mohamed, Saif Al-Kuwari and Ahmed Farouk, set out to eliminate this guesswork entirely by letting the algorithm discover its own depth.

DDQAOA begins modestly, with a single QAOA layer, and monitors the optimization as it proceeds. The algorithm tracks the expectation value of the problem’s cost function, the quantity that measures how good the current quantum state is. When improvement stalls, the algorithm does not give up; instead it concludes that the current depth has exhausted its expressive capacity and adds one more layer. Two complementary convergence checks guard against false alarms. The first detects a plateau by verifying that the best energy has not improved beyond a small tolerance over a patience window of fifty iterations. The second examines the variance of recent energy values, distinguishing genuine convergence from mere oscillations around a local minimum. Only when one of these conditions is satisfied does the depth increase.

Crucially, when a new layer is added, the algorithm does not start its optimization from scratch. Building on the INTERP parameter-transfer protocol developed by Zhou and colleagues in 2020, DDQAOA interpolates the optimized parameters from the shallower circuit to seed the deeper one. For the transition from one to two layers, the team applies transfer coefficients of 1.2 for the cost angle gamma and 0.8 for the mixer angle beta, values motivated by the structure of adiabatic quantum evolution. For deeper transitions, the method constructs smooth interpolants, switching from linear interpolation to cubic splines once four or more layers are available. This warm-starting places each new optimization inside the basin of attraction of a good solution, dramatically accelerating convergence.

To test their method rigorously, the researchers turned to the Constrained Shortest Path Problem, an NP-hard challenge that asks for the cheapest route between two points in a network while respecting a limit on resource consumption, such as fuel or time. This problem is far more than an academic curiosity: it appears as a building block in air-cargo route planning, flight scheduling, airline crew pairing, and aircraft tail assignment. The team encoded the problem as a Quadratic Unconstrained Binary Optimization formulation, folding the source, target, flow-conservation and resource constraints into penalty terms, and then converted the result into an Ising Hamiltonian whose ground state encodes the optimal path.

The benchmark was substantial: 100 randomly generated problem instances each at the 10-qubit and 16-qubit scales, plus 20 additional instances requiring 22 qubits on complete five-node graphs. Against fixed-depth QAOA baselines at depths 3, 5, 10 and 15, DDQAOA delivered striking results. At 10 and 16 qubits it outperformed every fixed-depth baseline, achieving median approximation ratios of roughly 0.97 and 0.99 respectively, with the smallest variability of any method. At 22 qubits it matched the best deep circuits, statistically indistinguishable from depth-10 QAOA and within 0.1 percent of depth-15, while attaining the highest median success probability of all methods tested.

The resource savings are where the approach truly shines. Because CNOT gates are the dominant source of noise on real quantum hardware, cumulative two-qubit gate usage is the currency of practical quantum optimization. Standard QAOA at depth 15, which achieved results close to DDQAOA, consumed 217 percent, 159.3 percent and 315 percent more CNOT gates at the 10-, 16- and 22-qubit scales respectively. Measured per circuit, DDQAOA used 3.17, 2.59 and 4.15 times fewer cumulative CNOTs than the deepest baseline across the three problem sizes. The algorithm’s gate count grows stepwise, from a single layer’s worth of gates up to the depth-10 equivalent, allocating quantum resources only as the optimization landscape requires.

Perhaps the most scientifically satisfying finding concerns the parameters themselves. In fixed-depth QAOA, the optimized gamma and beta angles typically show no discernible pattern across layers. DDQAOA, by contrast, consistently produced monotonically increasing gamma values and beta values converging toward zero, exactly the structure predicted by adiabatic theory, in which the cost Hamiltonian’s influence grows and the mixer’s fades as the system approaches the ground state. Across 100 diverse problem instances, with the classical optimizer free to deviate after initialization, this adiabatic signature emerged reliably, suggesting the interpolation strategy guides the search toward structured, physically meaningful solution manifolds rather than random corners of parameter space.

The authors are careful to note the limits of the current work. All experiments ran on classical simulators using the PennyLane framework with the Adam optimizer, and the success probabilities, while far above the random-guessing baseline of one over two to the power N, remain small in absolute terms because sampling the exact ground state among exponentially many bitstrings is an inherently stringent criterion. Future work will target larger instances and validation on real quantum hardware, where noise resilience and connectivity constraints will provide the ultimate test. Still, by removing the need to choose circuit depth in advance while matching or beating hand-tuned deep circuits at a fraction of the gate cost, DDQAOA offers a practical, NISQ-aware route to applying quantum optimization to genuinely constrained industrial problems, and a compelling demonstration that sometimes the best way to go deep is to earn each layer.

Subject of Research: A dynamic-depth variant of the quantum approximate optimization algorithm for solving the NP-hard constrained shortest path problem on near-term quantum devices.

Article Title: Dynamic depth quantum approximate optimization algorithm for solving constrained shortest path problem

Article References: Saini, R., Mohamed, N., Al-Kuwari, S., & Farouk, A. (2026). Dynamic depth quantum approximate optimization algorithm for solving constrained shortest path problem. Quantum Machine Intelligence, 8(2), Article 104. https://doi.org/10.1007/s42484-026-00442-0

Image Credits: AI Generated

DOI: 10.1007/s42484-026-00442-0

Keywords: quantum computing, QAOA, DDQAOA, constrained shortest path problem, combinatorial optimization, NISQ devices, circuit depth, parameter transfer, Ising Hamiltonian, QUBO, adiabatic evolution, CNOT gates