Solving multi-constrained path finding problems traditionally relied heavily on classical methods like dynamic programming which require 18,754 labels on a specific instance; however, two quantum approaches, Grover search and decoded quantum interferometry (DQI), offer potential advantages. Grover searches for a complex network of 136 arc qubits demands approximately 4.4 × 105 Toffoli gates, while DQI achieves approximation ratios unmatched by current polynomial-time classical algorithms for certain problem structures. This investigation determines whether quantum computers can efficiently solve multi-constrained path finding, a challenge for traditional computing methods.

DQI demonstrated an ability to exceed current polynomial-time classical algorithms when applied to specific network structures; notably those involving staged fabrics and power-of-index weights. These findings help pinpoint areas where near-term quantum devices may offer advantages in tackling complex optimisation problems. Finding a path meeting multiple requirements, such as delay or cost limits, is a notoriously difficult problem for computers; it’s considered weakly NP-complete, meaning finding an exact solution quickly becomes impossible as the network grows larger.

Grover search works by essentially searching through many possibilities at once, like flipping all coins simultaneously instead of one at a time, hoping the right combination appears more frequently. However, even with this speedup, implementing Grover search requires substantial operations; their largest test instance demanded approximately 440,000 Toffoli gates, basic building blocks controlling information flow within a quantum computer, compared to just 18,754 labels for classical dynamic programming. This raises the question of where these new methods truly excel over existing techniques, which is explored in detail below.

Encoding Valid Paths via Ancilla Free State Preparation

David Awschalom and his colleagues focused their approach around crafting a specific quantum ‘state preparation’, building the initial conditions for effective algorithm execution. This technique constructs a superposition representing every possible path through a directed acyclic graph (DAG) without needing extra helper qubits called ‘ancilla.

The resulting state carefully encodes information about valid paths while simultaneously creating an error-detecting code within the quantum system itself; this feature is linked to the structure of the network being explored. They employed Grover search on DAGs with up to 136 arc qubits, exploring 262,144 possible paths using a method requiring approximately 4.4 × 105 Toffoli gates for their largest instance, classical dynamic programming required 18,754 labels on that same problem size.

Quantum advantage in multi-constrained pathfinding

A threshold has been crossed in multi-constrained path finding: previously, exact solutions became computationally impossible as network complexity increased due to the weakly NP-complete nature of the challenge. The team demonstrated this by achieving results with only about 74 evaluations on an instance comprising 136 arc qubits and 262,144 paths, a substantial reduction compared to the 18,754 labels needed for classical dynamic programming at the same scale. This performance also proved favourable when contrasted against uniform sampling which required around 31,800 attempts.

Grover search needs O(sqrt(N/M)) oracle calls for M good paths among N total paths; however, classical meet-in-the-middle matches this exponent in the worst case, with known quantum algorithms utilising quantum memory performing better still. Analysis revealed that decoded quantum interferometry (DQI) could express solutions efficiently within certain parameters, though a classical Boltzmann sampler matched its performance on larger instances. Simulations verified these findings alongside two small binary tests run on IBM Heron processors which retained 67 % and 15% of the ideal gain over uniform sampling.

Toffoli Gate Reduction Remains Key to Practical Quantum Pathfinding

Their Grover search approach demonstrably reduces computational demands compared to classical dynamic programming for specific network configurations; however, reliance on approximately 440,000 Toffoli gates raises an important question: can this gate count be realistically reduced through circuit optimisation. The authors acknowledge that other quantum algorithms utilising quantum memory may offer superior scaling but require hardware beyond current capabilities while also introducing complexities in maintaining qubit coherence. Optimising these circuits remains vital work despite the substantial number of gates required even for moderately sized problems.

This research demonstrated a Grover search approach to finding paths within networks that satisfy multiple criteria, achieving results comparable to classical meet-in-the-middle techniques in some cases, though other quantum approaches with memory may perform better. The study also showed decoded quantum interferometry (DQI) could outperform existing algorithms for specific network types involving staged fabrics or power-of-index weights; small binary instances run on IBM Heron processors retained between 15% and 67% of ideal performance gains over standard sampling methods.

👉 More information
🗞 On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry
✍️ Dmitrii Chemodanov
🧠 ArXiv: https://arxiv.org/abs/2611.15794

More like this