What is a quantum walk and what is it researched for?
Status as of: September 7, 2026.
A quantum walk is the quantum analogue of a random walk: a walker moves over the nodes of a graph, but instead of picking one path at random it spreads as a wave over every path at once, and the paths interfere. As of September 7, 2026, quantum walks carry some of the cleanest proven speedups in quantum computing — including one of the field's few provable exponential separations — and they can, in principle, run any quantum program. What nobody has is a measured end-to-end advantage on a commercial problem. Rosetta Q runs a quantum walk inside its own research engine, and at equal budget it currently loses to its classical rival (Fisher p = 0.095, not significant). This post defines the object, lists what is proven with a source per row, and prints our own scoreboard — including the losing side of it.
What is a quantum walk?
A quantum walk is a walk on a graph in which the walker's position is a quantum state. Two standard families exist. In the discrete-time walk, each step applies a quantum "coin" operation and a conditional shift, so the walker moves in superposition of directions. In the continuous-time quantum walk (CTQW), introduced by Farhi and Gutmann in 1998, there are no steps at all: the graph's connectivity matrix is used as the Hamiltonian, and the walker's amplitude flows along the edges continuously under the Schrödinger equation.
The measurable difference from a classical random walk is how fast the walker spreads. On a line, a classical walker diffuses: its standard deviation grows like the square root of time. A quantum walker moves ballistically: the standard deviation grows linearly with time. That quadratic gap in spread — plus interference, which can concentrate amplitude on the vertex you care about — is the raw material of every quantum-walk algorithm.
Faster spreading on a line is physics, and it is proven. Whether it pays for anything is a separate question, and the rest of this post keeps the two apart.
Where is a quantum-walk advantage actually proven?
In the query model — and the flagship result is one of the few provable exponential separations in quantum computing. In 2003, Childs, Cleve, Deotto, Farhi, Gutmann and Spielman took two binary trees glued back-to-back through a random cycle and showed that a continuous-time quantum walk crosses from the entrance to the exit efficiently, while any classical algorithm — not just the known ones: any — needs exponentially many queries. The separation is proven, not conjectured. The catch that defines the whole field: the graph is an oracle, a black box you pay to consult, and the speedup counts consultations.
| Result | Speedup | Model | Year | Source |
|---|---|---|---|---|
| Glued-trees traversal | Exponential, proven against any classical algorithm | Query (oracle) | 2003 | Childs et al., STOC 2003, arXiv:quant-ph/0209131 |
| Element distinctness | O(n^2/3) queries, later shown optimal | Query | 2004-2007 | Ambainis, SIAM J. Comput. 37, 210, arXiv:quant-ph/0311001 |
| Spatial search | O(√n) on suitable graphs | Query | 2004 | Childs & Goldstone, Phys. Rev. A 70, 022314 |
| Universality | Any quantum circuit compiles to a walk on some graph | Model equivalence | 2009 | Childs, Phys. Rev. Lett. 102, 180501 |
| Random hierarchical graphs | Superpolynomial to exponential, generalizing glued trees | Query (oracle) | 2025 | Balasubramanian, Li & Harrow, Commun. Math. Phys., arXiv:2307.15062 |
Three notes on that table. First, element distinctness — deciding whether a list contains a repeated item — is where quantum walks beat plain Grover search (our Grover post covers why quadratic is the generic ceiling): Ambainis' walk over sets of queried items gets it done in about n to the two-thirds queries. Second, universality (2009) means quantum walks are not a niche trick: any quantum computation can be phrased as a walk on some graph, so "quantum walk computer" is a full model of quantum computing, not a special-purpose gadget. Third, the family is still growing: the 2025 result by Balasubramanian, Li and Harrow — published in Communications in Mathematical Physics — extends the glued-trees separation to a broad class of random hierarchical graphs. The theory side of this ledger is alive and well.
The fine print the marketing versions drop: every row above lives in the query model. Nobody hands you a business dataset as an oracle. When the graph arrives as explicit data, loading it costs at least its size — the same wall we documented in our QRAM post — and strong classical algorithms are back in the race. Between "proven in the query model" and "wins on your data, end to end" sits the gap where, so far, every applied quantum-walk claim we know of has stalled. Our catalog of proven quantum advantages counts the survivors by class; quantum walks appear on the theory side only.
What has Rosetta Q measured with its own quantum walk?
We run one, and it currently loses — and publishing that number is the point. The RQ-Engine, our internal research pipeline for predicting allosteric sites on proteins, has an experimental arm that uses continuous-time quantum walks as propagators over residue-contact graphs: the protein becomes a graph, the walk explores it, and the arm scores candidate pockets by how amplitude settles.
Measured, under budget parity against classical propagators on the same graphs: the sealed run RQ-EXP-QMARGIN-001 gave Fisher p = 0.095 — not significant — with 1 of 86 proteins individually significant. The arm's latest re-measure (2026-08-14) gave p = 0.0741 and 0.0921 on two independent seeds: still no crossing. The verdict as of today is plain: on our problem, at equal budget, the classical mathematics wins. The walk re-races every time the model changes, and every version so far has lost.
This is not "quantum walks are useless." It is one honest, dated data point in a field short of them — a negative with a seal on it. Rosetta Q keeps this marker public for the same reason our advantaged-solve marker sits at zero: a ledger that only records wins is not a ledger. A walk that only wins in the query model is, for now, a beautiful theorem.
Why hasn't 28 years of theory become a product?
Because the proven wins are query-model wins, and the hardware runs so far are physics demonstrations. Both halves of that sentence have sources. On hardware, quantum walks have actually been implemented at respectable scale:
| Platform | What was demonstrated | What it was not | Source |
|---|---|---|---|
| Superconducting, 62 qubits | Programmable 2D quantum walks on an 8x8 lattice | A solve of any problem past a classical baseline | Science, May 2021, DOI 10.1126/science.abg7812 |
| Superconducting, 12 qubits | Strongly correlated multi-particle walks | Same | Science, 2019, DOI 10.1126/science.aaw1611 |
| Photonic 3D chip | Multi-photon walks on a three-dimensional graph | Same | Light: Science & Applications, 2024 |
A 2024 field review (Qiang, Ma & Song, Intelligent Computing) is upbeat and honest at once: "remarkable progress" in implementations, applications explored "from algebraic and optimization problems to quantum Hamiltonian and biochemical process simulations" — and a closing section on the challenges standing between that and a practical machine. That framing matches what we measure from our side of the bench.
What would move the verdict, in our reading: a workload whose graph is naturally oracle-like — enormous, implicit, cheap to consult locally, expensive to hold as data — plus hardware deep enough to run the walk under error correction, plus a classical baseline fought at equal budget. That last clause is the one our own experiment enforces, and it is the one that most published walk applications skip.
What we know / what we don't know
What we know. The definition and the ballistic-vs-diffusive scaling are textbook physics (Farhi & Gutmann, 1998). The query-model separations in the table are proven theorems, each with its paper and year, and one of them is exponential against any classical algorithm. Universality (2009) makes walks a full model of quantum computing. On our own bench: p = 0.095 at budget parity, 1 of 86 proteins significant, two seeds, sealed and dated.
What we don't know. Whether any commercial workload maps onto the oracle setting tightly enough for a glued-trees-style advantage to survive contact with real data — none has, measured, to date. Whether our own arm loses because quantum walks carry no usable signal for allosteric structure, or because our graph construction and features are wrong — we cannot distinguish those two yet, and we say so. Whether the 2025 hierarchical-graphs family moves closer to natural problem structure or remains a mathematical object. And what a quantum walk at error-corrected scale will cost end to end, because nobody has priced one.
Sources
- Farhi & Gutmann, "Quantum computation and decision trees," Phys. Rev. A 58, 915 (1998) — arxiv.org/abs/quant-ph/9706062 (accessed 2026-09-07)
- Childs, Cleve, Deotto, Farhi, Gutmann & Spielman, "Exponential algorithmic speedup by a quantum walk," STOC 2003 — arxiv.org/abs/quant-ph/0209131 (accessed 2026-09-07)
- Ambainis, "Quantum walk algorithm for element distinctness," SIAM J. Comput. 37, 210 (2007) — arxiv.org/abs/quant-ph/0311001 (accessed 2026-09-07)
- Childs & Goldstone, "Spatial search by quantum walk," Phys. Rev. A 70, 022314 (2004) — arxiv.org/abs/quant-ph/0306054 (accessed 2026-09-07)
- Childs, "Universal computation by quantum walk," Phys. Rev. Lett. 102, 180501 (2009) — arxiv.org/abs/0806.1972 (accessed 2026-09-07)
- Balasubramanian, Li & Harrow, "Exponential speedups for quantum walks in random hierarchical graphs," Commun. Math. Phys. (2025) — arxiv.org/abs/2307.15062 (accessed 2026-09-07)
- "Quantum walks on a programmable two-dimensional 62-qubit superconducting processor," Science (2021) — science.org/doi/10.1126/science.abg7812 (accessed 2026-09-07)
- "Strongly correlated quantum walks with a 12-qubit superconducting processor," Science (2019) — science.org/doi/10.1126/science.aaw1611 (accessed 2026-09-07)
- "Multi-particle quantum walks on 3D integrated photonic chip," Light: Science & Applications (2024) — nature.com/articles/s41377-024-01627-7 (accessed 2026-09-07)
- Qiang, Ma & Song, "Review on Quantum Walk Computing: Theory, Implementation, and Application," Intelligent Computing 3:0097 (2024) — arxiv.org/abs/2404.04178 (accessed 2026-09-07)
Related on this ledger: our proven-advantage catalog, what QRAM is and why loading data is the silent bottleneck, what Grover really gives you, and what an advantaged solve is.
Rosetta Q publishes verdicts with raw, reproducible data. This is educational content, not a product claim, and not investment advice. The p-values quoted for our own experiment are internal measurements, sealed and dated; the raw run artifacts are internal, which means this scoreboard does not yet meet the radical-reproducibility standard we demand of others — we note that as our own debt. All external results are cited from their original papers, accessed 2026-09-07.