{ "id": "epmpqzxtyg", "slug": "quantum-walk", "title": "Quantum walk", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] } ], "excerpt": "A quantum walk is the quantum-mechanical counterpart of a classical random walk, coming in discrete-time and continuous-time forms and powering quantum algorithms for search and graph problems.", "snippet": "A quantum walk is the quantum-mechanical counterpart of a classical random walk, coming in discrete-time and continuous-time forms and powering quantum algorithms for search and graph problems.", "node": "technology.computing.ai.algorithms", "markdown": "# Quantum walk\n\nA quantum walk is the quantum-mechanical counterpart of a classical random walk: a particle whose position on a graph evolves by unitary, coherent dynamics rather than by probabilistic transitions. It comes in two main formulations, the discrete-time quantum walk, which evolves in steps, and the [continuous-time quantum walk](https://www.edgepedia.org/continuous-time-quantum-walk), which evolves under a Hamiltonian.[1](https://spj.science.org/doi/10.34133/icomputing.0097) Quantum walks supply algorithmic tools for search, sampling, and graph problems, from exponential oracle separations to quadratic speedups for Markov-chain search.[1](https://spj.science.org/doi/10.34133/icomputing.0097) • [2](https://arxiv.org/pdf/0810.0312)\n\n| Key fact | Statement |\n|---|---|\n| Two formulations | Discrete-time walks evolve step by step; continuous-time walks evolve under a Hamiltonian[1](https://spj.science.org/doi/10.34133/icomputing.0097) |\n| Continuous-time law | \\( i\\,d/dt\\,q(t) = Hq(t) \\), with \\( H \\) an \\( N \\times N \\) Hermitian matrix whose entry \\( H_{jk} \\) is nonzero exactly when vertices \\( j \\) and \\( k \\) are connected[2](https://arxiv.org/pdf/0810.0312) |\n| Coined step | On a \\( d \\)-regular graph, one step is \\( U = S \\cdot (C \\otimes I) \\), a coin toss followed by a conditional shift[3](https://arxiv.org/pdf/quant-ph/0012090) |\n| First dedicated paper | Aharonov, Davidovich, and Zagury, Physical Review A 48, 1687 (1993)[4](https://ar5iv.labs.arxiv.org/html/1201.4780) |\n| Exponential separation | On the glued-trees graph the continuous-time walk traverses from entrance to exit in time linear in \\( n \\), while classical walks need exponentially many steps[5](https://dl.acm.org/doi/10.1145/780542.780552) |\n| Element distinctness | \\( O(N^{2/3}) \\) quantum queries versus \\( \\Omega(N) \\) classically[6](https://www.ias.edu/sites/default/files/math/csdm/03-04/aambainis_quantum_walk_algorithm_for_element.pdf) |\n| Hardware scale | Discrete-time walks on graphs with up to 17 nodes and 20 edges run on 40 superconducting qubits with Hellinger fidelity above 87% over 7 steps[7](https://www.nature.com/articles/s41534-026-01332-w) |\n\n## How it works\n\nA continuous-time quantum walk on an undirected graph with \\( N \\) vertices assigns a complex amplitude to each vertex and evolves under the [Schrödinger equation](https://www.edgepedia.org/schrodinger-equation) \\( i\\,d/dt\\,q(t) = Hq(t) \\), where \\( H \\) is Hermitian and supported on the edges; the adjacency matrix or the Laplacian are the standard choices.[2](https://arxiv.org/pdf/0810.0312) Published conventions differ on sign: one recent paper writes the generator as \\( H = \\gamma(A - D) \\), with hopping rate \\( \\gamma \\), adjacency matrix \\( A \\), and degree matrix \\( D \\),[8](https://www.nature.com/articles/s41534-025-01165-z) while work on welded trees uses \\( H = -A \\).[9](https://link.springer.com/article/10.1007/s00220-025-05370-x)\n\nBecause the evolution is unitary and reversible, a quantum walk converges to no stationary distribution; the limiting behavior is instead described by the time-averaged probability distribution.[3](https://arxiv.org/pdf/quant-ph/0012090) A discrete-time walk on a lattice cannot be translation-invariant without extra structure: a particle moving left and right in superposition with equal amplitudes at each step is physically impossible in general, which motivates the coin degree of freedom.[4](https://ar5iv.labs.arxiv.org/html/1201.4780) Enlarging the state space with a coin, or equivalently walking on directed edges, removes this obstruction.[2](https://arxiv.org/pdf/0810.0312)\n\n## How it is done\n\nAn algorithmic quantum walk is not run as a physical walking particle; a physical walk is not an efficient way to compute the walk's own evolution.[10](https://ar5iv.labs.arxiv.org/html/2004.01329) The practitioner instead encodes the graph's vertices into qubits, for example an \\( N = 2^n \\)-vertex hypercube walk into \\( n \\) qubits, prepares an initial state, and applies either the step operator \\( U \\) repeatedly or Hamiltonian evolution for a chosen time.[10](https://ar5iv.labs.arxiv.org/html/2004.01329) For continuous-time dynamics on succinctly specified Hamiltonians, applying phase estimation to a suitable discrete-time walk simulates evolution for time \\( t \\) using \\( O(t) \\) operations.[2](https://arxiv.org/pdf/0810.0312) In the quantum setting the measurement is performed only once, at the end of the evolution.[11](https://mediatum.ub.tum.de/doc/1323917/document.pdf) Efficient circuit implementations of continuous-time walks exist only for selected graph classes, such as the glued tree, complete graph, complete bipartite graph, star graph, and [circulant graphs](https://www.edgepedia.org/circulant-graph) with few nonzero eigenvalues; sampling single-particle walks on exponentially large circulant graphs is believed classically intractable and has been demonstrated with bulk optics.[1](https://spj.science.org/doi/10.34133/icomputing.0097)\n\n## Origin\n\nThe first paper with quantum walks as its main topic was published in 1993: Y. Aharonov, L. Davidovich, and N. Zagury, \"Quantum random walks,\" in [Physical Review A](https://www.edgepedia.org/physical-review-a), which defined the walk as the counterpart of classical random walks for particles that cannot be precisely localized.[12](https://doi.org/10.1103/physreva.48.1687) • [4](https://ar5iv.labs.arxiv.org/html/1201.4780) Edward Farhi and Sam Gutmann introduced the continuous-time walk in \"Quantum computation and decision trees\" (Physical Review A, 1998).[13](https://doi.org/10.1103/physreva.58.915) Dorit Aharonov, Andris Ambainis, Julia Kempe, and [Umesh Vazirani](https://www.edgepedia.org/umesh-vazirani) formulated the coined walk on graphs with \\( U = S \\cdot (C \\otimes I) \\) and its mixing-time theory in \"Quantum Walks On Graphs\" (arXiv, 2000).[3](https://arxiv.org/pdf/quant-ph/0012090) Andrew M. Childs, Edward Farhi, and Sam Gutmann gave an example of exponentially shorter quantum propagation in 2002 (Quantum Information Processing).[14](https://doi.org/10.1023/a:1019609420309) Andris Ambainis proposed the element-distinctness walk algorithm in 2003 (arXiv).[15](https://doi.org/10.48550/arxiv.quant-ph/0311001) Andrew M. Childs and [Jeffrey Goldstone](https://www.edgepedia.org/jeffrey-goldstone) introduced continuous-time spatial search in 2004 (Physical Review A).[16](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.70.022314) Andris Ambainis, Julia Kempe, and Alexander Rivosh published \"Coins make quantum walks faster\" in 2005,[17](https://doi.org/10.5555/1070432.1070590) and Frédéric Magniez, Miklós Sántha, and Márió Szegedy applied walks to triangle finding the same year.[18](https://doi.org/10.5555/1070432.1070591) Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha gave the general Markov-chain search theorem in \"Search via Quantum Walk\" (arXiv, 2006).[19](https://doi.org/10.48550/arxiv.quant-ph/0608026) Andrew M. Childs proved universal computation by quantum walk in 2009 (Physical Review Letters).[20](https://doi.org/10.1103/physrevlett.102.180501) Tianen Chen and Yun Shang introduced a hybrid model unifying the discrete and continuous walks in 2025 (npj Quantum Information).[8](https://www.nature.com/articles/s41534-025-01165-z)\n\n## Variants\n\nThe main variants are discrete-time (coined) walks, continuous-time walks, Szegedy walks, staggered walks, discontinuous walks, and nonunitary models.[1](https://spj.science.org/doi/10.34133/icomputing.0097) The coined model pairs a walker with a coin system, evolving in the space \\( H_p \\otimes H_c \\) under a coin operator and a conditional shift.[4](https://ar5iv.labs.arxiv.org/html/1201.4780) The Szegedy walk quantizes a classical discrete-time [Markov chain](https://www.edgepedia.org/markov-chain) and yields faster search for a marked vertex.[1](https://spj.science.org/doi/10.34133/icomputing.0097) The staggered model is a coinless discrete-time variant whose evolution operator is built by partitioning the vertex set into tessellations and moving the walker with the associated reflection operators.[21](https://content.e-bookshelf.de/media/reading/L-11619099-7b5971185a.pdf) • [1](https://spj.science.org/doi/10.34133/icomputing.0097) Known interconversion results connect these frameworks: any Szegedy walk is equivalent to a 2-tessellable staggered walk on the line graph of a bipartite graph, and a coin-based walk with flip-flop shift can be cast into the Szegedy or staggered model only when the coin operator is an orthogonal reflection.[1](https://spj.science.org/doi/10.34133/icomputing.0097)\n\n## Applications\n\nThe glued-trees result constructed an oracular problem solvable exponentially faster by a continuous-time quantum walk than by any classical algorithm; its authors noted it was, as far as they knew, the first algorithmic speedup based on either walk type.[5](https://dl.acm.org/doi/10.1145/780542.780552) The state-of-the-art welded-tree algorithm takes \\( O(n) \\) queries and \\( O(n^2) \\) time, whereas classical algorithms require \\( 2^{\\Omega(n)} \\) queries under a reasonable oracle model.[9](https://link.springer.com/article/10.1007/s00220-025-05370-x) For element distinctness, the walk on the [Johnson graph](https://www.edgepedia.org/johnson-graph) of \\( r \\)-element subsets achieves \\( O(N^{2/3}) \\) queries, improving the earlier \\( O(N^{3/4}) \\) algorithm and matching the known lower bound; classically sorting requires \\( \\Omega(N) \\) queries, and \\( k \\)-distinctness takes \\( O(N^{k/(k+1)}) \\) queries.[6](https://www.ias.edu/sites/default/files/math/csdm/03-04/aambainis_quantum_walk_algorithm_for_element.pdf)\n\nFor unstructured search, applying the search Hamiltonian for a time \\( t_f \\simeq \\pi\\sqrt{N}/2 \\) produces the marked state with high probability, an \\( O(\\sqrt{N}) \\) speedup that is provably optimal for that problem.[10](https://ar5iv.labs.arxiv.org/html/2004.01329) On spatial graphs the speedup depends on dimension: full \\( \\sqrt{N} \\) speedup on a \\( d \\)-dimensional periodic lattice for \\( d > 4 \\), time of order \\( N \\, \\mathrm{poly}(\\log N) \\) for \\( d = 4 \\), and no substantial speedup for \\( d < 4 \\).[16](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.70.022314) The general Markov-chain search theorem states that for a reversible ergodic chain with spectral gap \\( \\delta \\) and marked-set measure \\( \\epsilon \\), the search cost is \\( S + \\sqrt{1/\\epsilon} \\cdot (\\sqrt{1/\\delta} \\cdot U + C) \\), where \\( S \\), \\( U \\), and \\( C \\) are the setup, update, and check costs; the Szegedy framework uses quadratically fewer walk steps than the classical search algorithm, and quantum fast-forwarding implements \\( t \\) walk steps in \\( O(\\sqrt{t}) \\) calls.[22](https://www.math.uwaterloo.ca/~anayak/papers/NRS.pdf) • [23](https://homepages.cwi.nl/~jeffery/notes/week3.pdf) Quantum walks also yield an optimal algorithm for evaluating balanced binary game trees, and the fastest published triangle-finding algorithms, with exponent \\( 5/4 \\) in the number of vertices, are built on the walk search framework.[2](https://arxiv.org/pdf/0810.0312) • [22](https://www.math.uwaterloo.ca/~anayak/papers/NRS.pdf)\n\nOn the implementation side, a fully programmable silicon photonic processor simulated walk dynamics on graphs with up to 400 vertices, showing exponentially faster hitting and quadratically faster mixing than classical walks.[1](https://spj.science.org/doi/10.34133/icomputing.0097) On superconducting hardware, walks on biological network motifs with up to 17 nodes and 20 edges ran on 40 qubits with Hellinger fidelity above 87% over 7 steps, and experimentally obtained walk dynamics on a protein-protein-interaction network were applied to prioritizing disease-associated genes.[7](https://www.nature.com/articles/s41534-026-01332-w)\n\n## Limitations and alternatives\n\nEncoding overhead is the main practical cost: dense graph encodings require prohibitively deep circuits on noisy hardware, which recent work addresses with symmetry-sector encoding that trades circuit depth for qubit number, plus symmetry-respecting postselection as noise mitigation.[7](https://www.nature.com/articles/s41534-026-01332-w) A no fast-forwarding theorem holds: in general a Hamiltonian cannot be simulated for time \\( t \\) using a number of walk steps sublinear in \\( t \\).[2](https://arxiv.org/pdf/0810.0312) Decoherence returns discrete-time walks to classical random processes through loss of coherence.[11](https://mediatum.ub.tum.de/doc/1323917/document.pdf) For unstructured search the speedup is only quadratic, and quadratic is the best possible.[10](https://ar5iv.labs.arxiv.org/html/2004.01329) Even the glued-trees speedup is narrower than it first appears: a classical walk with polynomial memory run for \\( O(n^2) \\) steps certainly reaches the exit vertex, so the naive quantum walk offers no great advantage there and the separation requires the modified construction.[11](https://mediatum.ub.tum.de/doc/1323917/document.pdf) In some tasks classical or hybrid methods win outright: for the spin glass ground state problem the best known classical algorithm beats the pure quantum walk algorithm, while a hybrid discrete-time walk-classical algorithm beats both.[10](https://ar5iv.labs.arxiv.org/html/2004.01329)\n\n## References\n\n1. [Quantum Walk Computing: Theory, Implementation, and Application (Intelligent Computing, 2024; also arXiv:2404.04178)](https://spj.science.org/doi/10.34133/icomputing.0097)\n2. [Quantum walks and the simulation of Hamiltonian dynamics (Childs, Commun. Math. Phys. 294, 581-603, 2010; arXiv:0810.0312)](https://arxiv.org/pdf/0810.0312)\n3. [Quantum walks on graphs (Aharonov, Ambainis, Kempe, Vazirani, STOC 2001; quant-ph/0012090)](https://arxiv.org/pdf/quant-ph/0012090)\n4. [Quantum walks: a comprehensive review (Venegas-Andraca, Quantum Information Processing 11(5), 2012)](https://ar5iv.labs.arxiv.org/html/1201.4780)\n5. [Exponential algorithmic speedup by a quantum walk (Childs, Cleve, Deotto, Farhi, Gutmann, Spielman, STOC'03)](https://dl.acm.org/doi/10.1145/780542.780552)\n6. [Quantum walk algorithm for element distinctness (Ambainis)](https://www.ias.edu/sites/default/files/math/csdm/03-04/aambainis_quantum_walk_algorithm_for_element.pdf)\n7. [Experimental implementation of a discrete-time quantum walk on biological networks | npj Quantum Information (2026)](https://www.nature.com/articles/s41534-026-01332-w)\n8. [A hybrid quantum walk model unifying discrete and continuous quantum walks | npj Quantum Information (2025)](https://www.nature.com/articles/s41534-025-01165-z)\n9. [Exponential Speedups for Quantum Walks in Random Hierarchical Graphs | Communications in Mathematical Physics (2025)](https://link.springer.com/article/10.1007/s00220-025-05370-x)\n10. [How to Compute Using Quantum Walks (Kendon)](https://ar5iv.labs.arxiv.org/html/2004.01329)\n11. [Quantum walks: a tutorial (Reitzner, Nagaj, Bužek)](https://mediatum.ub.tum.de/doc/1323917/document.pdf)\n12. [Y. Aharonov, L. Davidovich, N. Zagury (1993). Quantum random walks. Physical Review A.](https://doi.org/10.1103/physreva.48.1687)\n13. [Edward Farhi, Sam Gutmann (1998). Quantum computation and decision trees. Physical Review A.](https://doi.org/10.1103/physreva.58.915)\n14. [Andrew M. Childs, Edward Farhi, Sam Gutmann (2002). An Example of the Difference Between Quantum and Classical Random Walks. Quantum Information Processing.](https://doi.org/10.1023/a:1019609420309)\n15. [Ambainis, Andris (2003). Quantum walk algorithm for element distinctness. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.quant-ph/0311001)\n16. [Spatial search by quantum walk (Childs & Goldstone, Phys. Rev. A 70, 022314, 2004)](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.70.022314)\n17. [Andris Ambainis, Julia Kempe, Alexander Rivosh (2005). Coins make quantum walks faster. .](https://doi.org/10.5555/1070432.1070590)\n18. [Frédéric Magniez, Miklós Sántha, Márió Szegedy (2005). Quantum algorithms for the triangle problem. .](https://doi.org/10.5555/1070432.1070591)\n19. [Magniez, Frédéric and colleagues (2006). Search via Quantum Walk. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.quant-ph/0608026)\n20. [Andrew M. Childs (2009). Universal Computation by Quantum Walk. Physical Review Letters.](https://doi.org/10.1103/physrevlett.102.180501)\n21. [Quantum Walks and Search (Portugal, 2nd ed., sample)](https://content.e-bookshelf.de/media/reading/L-11619099-7b5971185a.pdf)\n22. [Quantum Analogues of Markov Chains (Nayak, Richter, Santha survey chapter)](https://www.math.uwaterloo.ca/~anayak/papers/NRS.pdf)\n23. [Week 3: Quantum Walk Algorithms (Jeffery, lecture notes)](https://homepages.cwi.nl/~jeffery/notes/week3.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/quantum-walk", "markdown_url": "https://www.edgepedia.org/quantum-walk.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Quantum walk\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-walk. Edgepedia Community License 1.0.", "credit_md": "\"[Quantum walk](https://www.edgepedia.org/quantum-walk)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/quantum-walk](https://www.edgepedia.org/quantum-walk). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Quantum walk\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-walk. Edgepedia Community License 1.0.", "speakable": "A quantum walk is the quantum-mechanical counterpart of a classical random walk, coming in discrete-time and continuous-time forms and powering quantum algorithms for search and graph problems." }