Quantum Walks, QAOA and Annealing: The Evidence For and Against Advantage

Updated 2026-10-11 | 4 min read | QUANTUM (QNT) community

Three different kinds of claim

Optimization is the use case executives hear about most and the one where evidence is thinnest. To keep it straight, separate three kinds of statement: a proof (mathematically guaranteed under stated rules), a benchmark (a measured win against named classical rivals), and a hope (it might work at scale). The sections below sort each technique.

Quantum walks: a proof, on a made-up problem

A classical random walk wanders a graph by coin flips. A quantum walk lets the wanderer take all paths at once so the waves interfere, spreading faster in some graphs. Per the reference below, quantum walks give exponential speedup for some oracular problems, citing Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003). Their abstract says they design a black-box problem solved exponentially faster by a quantum computer using a continuous-time quantum walk, and prove no classical algorithm can solve it with high probability in subexponential time. That is a real proof of a gap.

The catch is the word "constructed." The problem was designed so the walk shines, and it is not a practical task. Polynomial speedups for natural problems are known too: element distinctness (Ambainis, 2007), triangle finding (Magniez, Santha and Szegedy, 2005) and NAND tree evaluation (Farhi, Goldstone and Gutmann, 2008). The reference also notes Grover search can be viewed as a quantum walk. So walks are best-proven where least practical, and modestly useful, in the polynomial sense, where practical. See also the Grover limit.

QAOA: promising shape, no proven exponential win

The quantum approximate optimization algorithm, proposed by Farhi, Goldstone and Gutmann in 2014, alternates a cost step and a mixing step with tunable angles, loosely inspired by adiabatic evolution. Because it uses shallow circuits, it was a candidate for noisy machines (see variational circuits and barren plateaus). The scorecard from the reference below:

• For: it briefly had a better approximation ratio than any known polynomial-time classical algorithm on one specific problem. A 2020 estimate said a 420-qubit, 500-constraint circuit would take at least a century to simulate classically.
• Against: the early advantage was overtaken in 2015 when Barak and coauthors proposed a better classical algorithm. No exponential speedup is proven for combinatorial optimization, and provable results resemble Grover's, at most modest polynomial. A 2023 study found depth above 11 required for scalable advantage on MaxCut.

A broader search summary I read describes the field as having narrow theoretical results for special problem families, shallow circuits or weak baselines, and no demonstrated practical speedup. Treat vendor claims accordingly, and compare against the best classical solver, not a naive one. For finance applications specifically see the portfolio reality check.

Decoded quantum interferometry: a fresh lead

Jordan and coauthors published "Optimization by Decoded Quantum Interferometry" in Nature (volume 646, 2025). It turns an optimization problem into a decoding problem using the quantum Fourier transform. As reported on Google Research's page, for an algebraic problem of fitting polynomials over finite fields it achieves superpolynomial speedup over known classical algorithms. For unstructured max-XORSAT it beats general heuristics such as simulated annealing on a built instance, but a tailored classical solver can outperform it, so the broad question remains open. The authors themselves describe superpolynomial advantage for optimization as largely open.

Annealing: strong empirical claim, narrow scope

Quantum annealers search for low-energy states by slowly evolving a physical system. A D-Wave paper (King and coauthors, Science 388, 2025) reported that annealing processors produce samples matching Schrodinger-equation dynamics of spin glasses, and that leading approximate classical methods, tensor networks and neural networks among them, could not match accuracy in a reasonable time. Read it carefully: it compares against specific approximate methods, the claim is hedged ("may remain out of reach"), and the task is simulating a physical quench, not solving a business optimization problem. See annealing vs gate model and the basics.

Bottom line

Proof: quantum walks on a constructed problem, plus DQI on a structured one. Benchmark: annealing on spin dynamics. Hope: QAOA and most business optimization. Caution is not pessimism, since the research is productive, but a speedup for your supply chain has not been shown. Not financial advice, and the QNT memecoin is independent of Quantinuum Ltd.

Sources and further reading

• Wikipedia: quantum walk
• Childs et al.: Exponential algorithmic speedup by quantum walk (arXiv)
• Wikipedia: quantum approximate optimization algorithm
• arXiv: Optimization by Decoded Quantum Interferometry
• King et al.: Beyond-classical computation in quantum simulation (arXiv, Science 2025)

Reported as of 2026-10-09. Theory results are proven only under the stated assumptions, and experimental claims and classical rebuttals keep changing, so check the primary papers. Nothing here is financial advice and nothing here predicts the price of any asset. The QNT memecoin is independent of Quantinuum Ltd, the real company, and of every lab and researcher named on this page.

Frequently asked questions

Share on X

Keep reading

• Annealing vs Gate Model for Optimization: Which Quantum Approach Helps Real Businesses?
  D-Wave style quantum annealers and gate-model machines from IBM, IonQ and Quantinuum aim at optimization differently. Here is what each does, what the benchmarks say, and how to stay fair.
• Quantum Portfolio Optimization: A Reality Check With Real Optimism
  Portfolio optimization is the most-hyped quantum finance idea. Here is what QAOA, annealing and benchmarking efforts like QOBLIB really show in 2026.
• Variational Quantum Circuits and Barren Plateaus, Explained
  How variational quantum circuits train like neural networks, why barren plateaus make them hard to scale, and what researchers are doing about it.

All Quantum computing guides | Back to top | Search the site

Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary