Pathfinding Using Grover Search Could Need 440k Gates For 262,144 Routes – Quantum Zeitgeist

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.
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.
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.
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
See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
As a quantum scientist exploring the frontiers of physics and technology. My work focuses on uncovering how quantum mechanics, computing, and emerging technologies are transforming our understanding of reality. I share research-driven insights that make complex ideas in quantum science clear, engaging, and relevant to the modern world.
Quantum computing’s breakthroughs, deals, and research, delivered straight to your inbox.
Read by quantum researchers, engineers, developers, and business professionals worldwide.
The Quantum Ecosystem
Explore the Quantum Navigator
A living directory of the global quantum industry, plus public quantum stocks and the investors funding them.
Counts as of October 2026
Disclaimer: All material, including information from or attributed to Quantum Zeitgeist or individual authors of content on this website, has been obtained from sources believed to be accurate as of the date of publication. However, Quantum Zeitgeist makes no warranty of the accuracy or completeness of the information and Quantum Zeitgeist does not assume any responsibility for its accuracy, efficacy, or use. Any information on the website obtained by Quantum Zeitgeist from third parties has not been reviewed for accuracy.
Copyright 2019 to 2026 The Quantum Zeitgeist website is owned and operated by Hadamard LLC, a Wyoming limited liability company.
To provide the best experiences, we and our partners use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us and our partners to process personal data such as browsing behavior or unique IDs on this site and show (non-) personalized ads. Not consenting or withdrawing consent, may adversely affect certain features and functions.
Click below to consent to the above or make granular choices. Your choices will be applied to this site only. You can change your settings at any time, including withdrawing your consent, by using the toggles on the Cookie Policy, or by clicking on the manage consent button at the bottom of the screen.

source
This is a newsfeed from leading technology publications. No additional editorial review has been performed before posting.

Leave a Reply