CoChat
Sign Up
Cited by 1,413Quantum Computing Algorithms and ArchitectureQuantum Mechanics and ApplicationsQuantum Information and Cryptography

Quantum random walks: An introductory overview

Open access
Kempe, J·2003·Contemporary Physics
DOI 10.1080/00107151031000110776
Open this paper in CoChat — free accountOpen PDF

Abstract

This article aims to provide an introductory survey on quantum random walks.Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks.We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context.We will mention recent developments in this new area and outline some open questions. God does not play dice.

AI snapshot

Written from the paper’s full text.

TL;DR

This review introduces quantum random walks, contrasting them with classical random walks and surveying physical intuition, algorithmic uses, implementation proposals, and decoherence. It argues that quantum walks can spread quadratically faster and can produce polynomial-versus-exponential hitting-time separations on certain graphs.

Key findings

  • In discrete-time quantum walks on a line, interference makes the position variance grow as \(T^2\) rather than the classical linear \(T\), so typical distance scales like \(T\) instead of \(\sqrt{T}\); the distribution is not Gaussian and can be asymmetric depending on the coin and initial state.
  • For a Hadamard walk with an absorbing boundary at position 0 starting from \(|\uparrow\rangle\otimes|1\rangle\), the absorption probability is \(2/\pi \approx 0.63662\), leaving an escape probability of about \(0.36338\); a classical one-dimensional walk absorbs with probability 1.
  • On an \(N\)-cycle, the quantum mixing time is bounded by roughly \(N\log N/\epsilon^3\), nearly quadratically faster than the classical \(N^2\); on the hypercube, discrete quantum mixing is at least \(d^{3/2}/\epsilon\) and the continuous quantum walk does not converge to the uniform distribution, while quantum hitting from one corner to the opposite is polynomial in \(d\) versus classical exponential.
  • Continuous-time quantum walk on glued binary trees yields an exponential oracle separation: Childs et al. solve a graph-traversal oracle problem with polynomially many quantum queries, whereas classical algorithms require exponentially many.

Methods

  • Review/survey article; no primary experimental or numerical data are collected. It builds intuition from the Aharonov–Davidovich–Zagury example, then formalizes discrete-time and continuous-time quantum walk models.
  • Synthesizes cited literature on quantum walks on lines, circles, hypercubes, glued trees, and general graphs; covers computer science background, quantum circuits, physical implementation proposals (ion trap, cavity QED, optical lattice), and decoherence studies.
  • Main analysis is conceptual and mathematical: definitions of coin, shift, unitary evolution, asymptotic variance, mixing and hitting times, and comparisons to classical Markov chains; most proofs are omitted.

Limitations

  • The paper states many open questions: the relationship between discrete- and continuous-time models remains unclear; many graphs (e.g., the symmetric group) are unstudied; stationary distributions can depend on the initial state for even cycles; and rapid hitting appears tied to graph symmetry.
  • The paper states that it omits most proofs and aims at intuition, so it is not a source for detailed derivations.
  • Evident from the text: as an introductory overview, it reports no new experiments or primary data; some cited results are numerical, unpublished, or proposals not yet implemented.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1080/00107151031000110776

Cites

29 of 29 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 88 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning

    The walk starting in |↑>⊗|0 has a drift to the right, exactly opposite to the walk starting in |↓>⊗|0.

    “we see that the walk starting in | ↑ ⊗ |0 has a drift to the right side, exactly opposite to the walk in Eq. ( 16).”
    Quote in the paperNot a substantial claim
  • Findingnone given

    If the initial spin state is a superposition, application of the translation operator U induces a superposition of positions.

    “Application of the translation operator U will induce a superposition of positions”
    Quote in the paperSubstantial claim
  • Findingnone given

    The Hadamard coin is balanced: after one iteration and measurement of the coin in the standard basis, each direction is obtained with probability 1/2.

    “Measuring the coin state in the standard basis gives each of {| ↑ ⊗ |1 , | ↓ ⊗ | -1 } with probability 1/2.”
    Quote in the paperNot a substantial claim
  • Findingnone given

    The quantum walk probability distribution starts to differ from the classical distribution from T = 3 on.

    “Note that this distribution starts to differ from the classical distribution from T = 3 on.”
    Quote in the paperNot a substantial claim
  • Findingcitation

    The continuous-time quantum walk penetrates the glued trees from root to root exponentially faster than the classical walk.

    “We have seen that the continuous time quantum walk penetrates the glued trees from root to root exponentially faster than the classical walk.”
    Quote in the paperSubstantial claim
  • May combine two claims. 28
  • Classified as probably not a substantial claim. 16
  • The quote only partly states this claim. 1

  • May combine two claims.

    Findingnone given

    The quantum random walk on the line with initial state |↓>⊗|0 is asymmetric with a drift to the left.

    “Furthermore the quantum random walk is asymmetric with a drift to the left.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    With a rotated measurement, the displacement in one case can be made much larger than l, so in rare cases the particle jumps much further than l.

    “We have the effect that even though our translation operation displaces only by l, in some (rare) cases the particle will jump much further than l.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The initial wave packet width ∆x is much larger than the step length l, allowing the approximation exp(±iP l)|ψ x0 ≈ (I ± iP l)|ψ x0.

  • May combine two claims.

    Findingcitation

    The DFT coin transforms each direction into an equally weighted superposition of directions, so after measurement each direction is equally likely with probability 1/d.

    “Clearly the unitary DF T -coin [59] transforms each direction into an equally weighted superposition of directions such that after measurement each of them is equally likely to be obtained (with probability 1/d).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [59] 59. Such a labeling allows to color the edges of a graph (with colors 1, 2, . . . , d) such that the colors of the incident edges of a vertex are all different. It is a well known fact from graph theory that every graph of maximum degree d can be consistently edge-colored with at most d + 1 colors. In the case of the d-dimensional hypercube only d colors are needed.

      Not checked in the free run.

  • May combine two claims.

    Findingreasoning

    If after one step the spin is measured in the S_z basis, the particle is localized around x0+l with probability |α↑|^2 or around x0-l with probability |α↓|^2.

    “If at this point we decide to measure the spin in the S z basis, the particle will be either in the state | ↑ ⊗ |ψ x0-l , localized around x 0 + l with probability p ↑ = |α ↑ | 2 or in the state | ↓ ⊗ |ψ x0-l , localized around x 0 -l with probability p ↓ = |α ↓ | 2 .”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingnone given

    The coin Y = 1/√2 [[1,i],[i,1]] treats |↑> and |↓> in the same way and does not bias the walk, independently of its initial coin-state.

    “It is not hard to see that this coin treats | ↑ and | ↓ in the same way and does not bias the walk, independently of its initial coin-state.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingreasoning

    For a spin-1/2 particle, if the spin is initially |↑>, application of U shifts the particle right by l; if the spin is initially |↓>, application of U shifts it left by l.

    “if the spin of the particle is initially in the state | ↑ , so that its wave-function is of the form | ↑ ⊗ |ψ ↑ x0 , then application of U transforms it to | ↑ ⊗ |ψ ↑ x0-l and the particle will be shifted to the right by l.If the spin of the particle is in the state | ↓ , i.e. the total wavefunction is given by | ↓ ⊗ |ψ ↓ x0 , then the translation operator will transform it to | ↓ ⊗ |ψ ↓ x0+l and”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingreasoning

    For a classical random walk with one absorbing boundary at 0 starting at 1, the probability to ever get absorbed is p = 1.

    “It is well known that the probability p to ever get absorbed by the wall in the origin is p = 1.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingnone given

    In the purely quantum case, the variance scales as σ^2 ∼ T^2, whereas in the classical case σ^2 ∼ T.

    “In the purely quantum case we have seen that σ 2 ∼ T 2 , whereas in the classical case σ 2 ∼ T .”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Aharonov, Davidovich and Zagury's 1993 work first coined the term 'quantum random walk'.

    “Their work for the first time coins the term 'quantum random walk'.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [5] 5. Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Phys. Rev. A, 48(2):1687-1690, 1993.

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    The post-selection effect is strikingly different from any classical behavior; quantum mechanics allows post-selection of events that cannot be observed classically.

    “This is strikingly different from any classical behavior.Quantum mechanics allows us to post-select events that cannot be observed classically.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    The limiting distribution of the quantum walk on the line does not approach a Gaussian, and its variance is not linear in the number of steps T.

    “In particular we will see that the limiting distribution of the walk on the line will not approach a Gaussian and the variance σ 2 will not be linear in the number of steps T .”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Classical random walks form one of the cornerstones of theoretical computer science.

    “Classical random walks form one of the cornerstones of theoretical computer science [30,31].”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites [30] 30. C. Papadimitriou. Computational Complexity. Addison Wesley, Reading, Massachusetts, 1994.

      Not checked in the free run.

    • cites [31] 31. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    For different initial states and distances to the boundary, the numerical absorption probability changes, but the escape probability is non-zero and finite in all cases.

    “This behavior is general: for different initial states and distance to the boundary the numerical value for the absorption probability p quantum changes, but the escape probability is non-zero and finite in all cases.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation

    In the theory of classical Markov chains, many connections between the discrete and continuous time model can be made, and many quantities of interest, such as mixing times and absorption probability, have similar behavior in both cases.

    “In the theory of classical Markov chains many connections between the discrete and continuous time model can be made and many of the quantities of interest, like mixing times (see Sec. IV B) and absorption probability, have similar behavior in both cases [26].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [26] 26. D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. preprint available at http://stat-www.berkeley.edu/users/aldous/book.html.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    The speed of propagation of the random walk on the infinite homogeneous line is linear in time T; there are constants a<b such that when T is in [an,bn], the probability to measure the walk a distance 2n+1 from the starting point is of order 1/sqrt(n).

    “It can be seen that the speed of propagation of the random walk on the infinite homogeneous line is linear in the time T .In other words there are constants a < b such that when T ∈ [an, bn] then the probability to measure the walk a distance 2n + 1 from the staring point (i.e. at the root of the right tree starting from the root of the left tree) is of order 1/ √ n.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [27] 27. A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D.A. Spielman. Exponential algorithmic speedup by quantum walk, 2002. lanl-report quant-ph/0209131.

      Not checked in the free run.

    • The authors state this as an assumption: In the continuous time random walk model, transitions can occur at all times and the jumping rate from a vertex to its neighbor is a fixed, time-independent constant gamma.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    If G is connected and non-bipartite, then the distribution of the random walk converges to a stationary distribution pi independent of the initial distribution p0.

    “If G is connected and non-bipartite, then the distribution of the random walk, p T = M T p 0 converges to a stationary distribution π which is independent of the initial distribution p 0 .”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [36] 36. W. Feller. An Introduction to Probability Theory and its Applications. John Wiley, New York, 1968.

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    The classical simple random walk on the hypercube has high symmetry: all vertices of the same Hamming weight have the same weight in the probability distribution, allowing reduction to a biased random walk on the line.

    “This implies that all vertices of same Hamming weight have the same weight in the probability distribution of the random walk.This allows us to 'cumulate' all the vertices of same Hamming weight into a single vertex and to reduce the symmetric random walk on the hypercube to a biased random walk on the line”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    The quantum Hadamard walk with an absorbing boundary in |0, starting in |↑>⊗|1, has a non-vanishing escape probability; the absorption probability is p_quantum = 2/π ≈ 0.63662, giving escape probability ≈ 0.36338.

    “Careful analysis [12,16] shows that the quantum Hadamard walk with absorbing boundary in |0 , starting in the state | ↑ ⊗ |1 has a non-vanishing probability to escape.The probability to be absorbed at |0 turns out to be p quantum = 2/π ≈ 0.63662, which gives an escape probability of ≈ 0.36338.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [12] 12. A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. One-dimensional quantum walks. In Proc. 33th STOC, pages 60-69, New York, NY, 2001. ACM.

      Not checked in the free run.

    • cites [16] 16. E. Bach, S. Coppersmith, M. Goldschen, R. Joynt, and J. Watrous. One-dimensional quantum walks with absorbing boundaries, 2002. Lanl-archive quant-ph/0207008.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    Numerical studies indicate that the discrete time random walk on G_n using the 3-dimensional Grover coin at degree-3 vertices and the 2-dimensional one at degree-2 vertices shows extremely similar behavior to its continuous counterpart, and can be reduced to a discrete time walk on the line on which the walk propagates in linear time.

    “Numerical studies [29] indicate that this discrete time random walk shows an extremely similar behavior to its continuous counterpart.In particular it is possible to reduce the walk to a discrete time walk on the line on which the walk propagates in linear time.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [29] 29. N. Shenvi and J. Kempe. unpublished.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    As algorithmic tools, classical random walks have been applied to central problems such as estimation of the volume of a convex body, approximation of the permanent of a matrix, and discovery of satisfying assignments for Boolean formulae.

    “As algorithmic tools, they have been applied to a variety of central problems [32], such as estimation of the volume of a convex body [33], approximation of the permanent of a matrix [34], and discovery of satisfying assignments for Boolean formulae [35].”
    Quote in the paperNot a substantial claim0 of 3 sources checked
    • cites [32] 32. A. Sinclair. Algorithms for Random Generation and counting, a Markov Chain approach. Birkhauser press, 1993.

      Not checked in the free run.

    • cites [33] 33. M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1-17, Jan- uary 1991.

      Not checked in the free run.

    • cites [34] 34. M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial- time approximation algorithm for the permanent of a ma- trix with non-negative entries. In Proc. 33th STOC, pages 712-721, New York, NY, 2001. ACM.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    The quantum random walk has variance scaling as σ^2 ∼ T^2, so the expected distance from the origin is of order T; it propagates quadratically faster than the classical walk.

    “By contrast it can be shown that the quantum random walk has a variance that scales with σ 2 ∼ T 2 , which implies that the expected distance from the origin is of order σ ∼ T -the quantum walk propagates quadratically faster!”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [12] 12. A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. One-dimensional quantum walks. In Proc. 33th STOC, pages 60-69, New York, NY, 2001. ACM.

      Not checked in the free run.

    • Rests on an assumption: The classical symmetric random walk on the line after T steps has variance σ^2 = T, so the expected distance from the origin is of order √T.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Classical random walks provide a general paradigm for sampling and exploring an exponentially large set of combinatorial structures by using a sequence of simple, local transitions.

    “They provide a general paradigm for sampling and exploring an exponentially large set of combinatorial structures (such as matchings in a graph), by using a sequence of simple, local transitions [32].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [32] 32. A. Sinclair. Algorithms for Random Generation and counting, a Markov Chain approach. Birkhauser press, 1993.

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    The choice of coin operator can have a serious impact on the shape of the resulting distribution, and this effect is amplified in higher dimensions or on graphs of higher valence.

    “We have already seen that even in the simple case of a walk on the line the choice of the coin operator can have a serious impact on the shape of the resulting distribution, and this effect is only amplified in higher dimensions (see [19] for examples of the effects of various coins on a two-and three-dimensional grid) or on graphs of higher valence (degree).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [19] 19. T.D. Mackay, S.D. Bartlett, L.T. Stephenson, and B.C. Sanders. Quantum walks in higher dimensions. J. Phys. A: Math. Gen., 35:2745, 2002.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    Any classical random walk approaches a stationary distribution independent of its initial state; the classical random walk loses its memory.

    “Recall that any classical random walk approaches a stationary distribution independent of its initial state (Sec.IV B) -the classical random walk looses its memory.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [36] 36. W. Feller. An Introduction to Probability Theory and its Applications. John Wiley, New York, 1968.

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    With the Cesaro limit definitions, c_t converges to a stationary distribution; the result is true for all finite graphs.

    “With these definitions in place it is not very hard to see that c t converges to a stationary distribution.We will show this below for the Hadamard walk on the circle [11] -also to give an idea about the kind of calculations involved in these types of problems -but the result is true for all finite graphs.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11] 11. D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani. Quantum walks on graphs. In Proc. 33th STOC, pages 50-59, New York, NY, 2001. ACM.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    The exponential hitting time on both the hypercube and glued trees seems to depend crucially on the symmetry of these graphs.

    “Another observation is that the exponential hitting time on both hypercube and glued trees seems to depend crucially on the symmetry of these graphs.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Travaglione and Milburn [42] suggest an ion-trap based implementation of the random walk on a line.

    “For instance Travaglione and Milburn [42] suggest an ion-trap based implementation of the random walk on a line.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [42] 42. B.C. Travaglione and G.J. Milburn. Implementing the quantum random walk. Phys. Rev. A, 65:032310, 2002.

      Not checked in the free run.

  • May combine two claims. The quote only partly states this claim.

    Interpretationreasoning

    In the quantum case, the mixing time is determined by all |lambda_k - lambda_l|, unlike the classical case where it is governed only by the second largest eigenvalue.

    “All of these sums over pairs of eigenvalues enter Eq. ( 40), and so the mixing time is determined by all |λ k -λ l |.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    The quantum random walk cannot converge to a stationary distribution because all transformations are unitary and reversible, so the walk can never lose its recollection of the initial state.

    “This cannot be true for the quantum random walk.All transformations are unitary and hence reversible, therefore the walk can never lose its recollection of the initial state and therefore it does not converge to a stationary distribution.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    A quantum computer can emulate any classical computation efficiently; quantum computers are at least as strong as classical computers.

    “In particular this implies that a quantum computer can emulate any classical computation efficiently: quantum computers are at least as strong as their classical brothers.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Sanders et al. [43] propose a quantum electrodynamics device implementation of the random walk in an optical cavity traversed by an atom.

    “Another recent suggestion by Sanders et al. [43] puts the random walk into a quantum electrodynamics device.The physical system is an optical cavity traversed by an atom.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [43] 43. B.C. Sanders, S.D. Bartlett, B. Tregenna, and P.L. Knight. Quantum quincunx in cavity quantum electro- dynamics, 2002. arXive eprint quant-ph/0207028.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    The quantum walk mixes at most quadratically faster than the classical walk; exponential speed-up is not possible in all but possibly very contrived cases.

    “As shown by Aharonov et al. [11] the quantum walk mixes at most quadratically faster [71].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11] 11. D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani. Quantum walks on graphs. In Proc. 33th STOC, pages 50-59, New York, NY, 2001. ACM.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    For the simple random walk on an N-circle, the mixing time is quadratic, M_epsilon ~ N^2 log(1/epsilon).

    “It is well known that for the simple random walk on an N -circle, the mixing time is quadratic, M ǫ ∼ N 2 • log(1/ǫ).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [36] 36. W. Feller. An Introduction to Probability Theory and its Applications. John Wiley, New York, 1968.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    For a d-regular graph, the limiting probability distribution is uniform over the nodes of the graph.

    “For a d-regular G (all nodes have the same degree d), the limiting probability distribution is uniform over the nodes of the graph.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [36] 36. W. Feller. An Introduction to Probability Theory and its Applications. John Wiley, New York, 1968.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    Kendon and Tregenna's numerical studies show that decoherence can improve both convergence to uniform and reliability of hitting.

    “Kendon and Tregenna's [48] numerical studies also show that decoherence can improve both convergence to uniform and reliability of hitting.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [48] 48. V. Kendon and B. Tregenna. Decoherence is useful in quantum walks, 2002. Lanl-arXive quant-ph/0209005.

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    Numerical studies of the quantum-to-classical transition have been executed for the circle, line and hypercube by Kendon and Tregenna, and analytical expressions for the walk on the line with coin decoherence have been obtained by Brun et al.

    “Numerical studies of this transition from quantum to classical have been executed for the circle, line and hypercube by Kendon and Tregenna [48] and extensive analytical expressions for the walk on the line with decoherence of the coin-space have been obtained by Brun et al. [49][78].”
    Quote in the paperNot a substantial claim0 of 3 sources checked
    • cites [48] 48. V. Kendon and B. Tregenna. Decoherence is useful in quantum walks, 2002. Lanl-arXive quant-ph/0209005.

      Not checked in the free run.

    • cites [49] 49. T.A. Brun, H.A. Carteret, and A. Ambainis. The quan- tum to classical transition for random walks, 2002. LANL preprint quant-ph/0208195.

      Not checked in the free run.

    • cites [78]

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    In the Sanders et al. proposal, the focus is to implement the random walk with existing present-day technology in a microwave cavity.

    “The focus of this proposal is to implement the random walk with existing present day technology in a microwave cavity.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [43] 43. B.C. Sanders, S.D. Bartlett, B. Tregenna, and P.L. Knight. Quantum quincunx in cavity quantum electro- dynamics, 2002. arXive eprint quant-ph/0207028.

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    In the fresh-coin transition, quantum coherences between coin degrees of freedom cannot interfere, so the walk behaves like the classical walk.

    “This does not allow the quantum coherences between the coin degrees of freedom to ever interfere and hence the walk behaves like the classical walk.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [49] 49. T.A. Brun, H.A. Carteret, and A. Ambainis. The quan- tum to classical transition for random walks, 2002. LANL preprint quant-ph/0208195.

      Not checked in the free run.

    • cites [51] 51. T.A. Brun, H.A. Carteret, and A. Ambainis. Quan- tum walks driven by many coins, 2002. LANL preprint quant-ph/0210161.

      Not checked in the free run.

  • Classified as probably not a substantial claim.

    Interpretationnone given

    The paper has presented several striking differences between quantum and classical random walks concerning their distribution, mixing and hitting properties.

    “We have presented several rather striking differences in the behavior of these walks as compared to their classical counterparts concerning their distribution, their mixing and hitting properties.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisereasoning

    The fresh-coin transition induces a very different variance behavior: it stays quadratic in T for a whole range of coin-spaces and becomes linear only in the limit of one new coin per time step.

    “It turns out that this way to transition from quantum to classical induces a very different behavior of the variance σ 2 : it stays quadratic in T for a whole range of coin-spaces to become linear only in the limit of one new coin per time step.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [49] 49. T.A. Brun, H.A. Carteret, and A. Ambainis. The quan- tum to classical transition for random walks, 2002. LANL preprint quant-ph/0208195.

      Not checked in the free run.

    • cites [51] 51. T.A. Brun, H.A. Carteret, and A. Ambainis. Quan- tum walks driven by many coins, 2002. LANL preprint quant-ph/0210161.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    The first exponential separation relative to an oracle, based on the quantum Fourier transform, was given in 1997 by Bernstein and Vazirani.

    “[75] Note that this is not the first exponential separation relative to an oracle.The first such separation -based on the quantum Fourier Transform -has been given in 1997 by Bernstein and Vazirani [41].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [41] 41. E. Bernstein and U. Vazirani. Quantum complexity the- ory. SIAM Journal on Computing, 26:1411, 1997.

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Aharonov et al. suggested observing a quantum random walk effect in the optical cavity setting.

    “[77] Aharonov et al. [5], when pointing out a first 'quantum random walk effect' in the original 1993 work (see Sec. II), already suggested to observe it in the optical cavity setting.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [5] 5. Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Phys. Rev. A, 48(2):1687-1690, 1993.

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    The Sanders et al. proposal allows controlled decoherence to be introduced into the cavity, enabling study of the decrease in phase diffusion with noise.

    “Another upshot of this proposal is that controlled decoherence can be introduced into the cavity.This allows to study the decrease in phase diffusion (transition from a linear spread σ ∼ T in the quantum case to a classical spread σ ∼ √ T ) with noise (see also Sec.VI).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [43] 43. B.C. Sanders, S.D. Bartlett, B. Tregenna, and P.L. Knight. Quantum quincunx in cavity quantum electro- dynamics, 2002. arXive eprint quant-ph/0207028.

      Not checked in the free run.

43 of 43

  • The paper relies on this without support.

    The classical symmetric random walk on the line after T steps has variance σ^2 = T, so the expected distance from the origin is of order √T.

    “As mentioned before the classical symmetric random walk on the line after T steps has a variance σ 2 = T , so the expected distance from the origin is of order σ = √ T .”

  • The paper relies on this without support.

    The classical random walk on the line has a limiting distribution approaching a Gaussian with mean zero and variance σ^2 = T, and on the circle it approaches the uniform distribution.

    “Its limiting distribution on the line (for large number of iterations T ) approaches a Gaussian distribution with mean zero and variance σ 2 = T .On the circle this distribution approaches the uniform distribution”

  • The paper relies on this without support.

    The classical distribution is peaked around the origin and drops off exponentially several standard deviations away from the origin.

    “This is again in stark contrast to the classical case in which the distribution is peaked around the origin and drops off exponentially several standard deviations σ away from the origin.”

  • The authors state this as an assumption.

    The initial wave packet width ∆x is much larger than the step length l, allowing the approximation exp(±iP l)|ψ x0 ≈ (I ± iP l)|ψ x0.

    “If the width ∆x of the initial wave packet is much larger than the step length l we can approximate exp(±iP l)|ψ x0 ≈ (I ± iP l)|ψ x0 .”

  • The authors state this as an assumption.

    In the continuous time random walk model, transitions can occur at all times and the jumping rate from a vertex to its neighbor is a fixed, time-independent constant gamma.

    “To make the process continuous in time we can assume that transitions can occur at all times and the jumping rate from a vertex to its neighbor is given by γ, a fixed, time-independent constant.”

  • The authors state this as an assumption.

    Interaction with a larger environment induces decoherence, which in turn makes the world classical.

    “Usually it is assumed that interaction with a larger environment induces decoherence, which in turn makes the world classical.”
6 of 6

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Quantum walks provide an ideal framework for emulation due to their rich dynamics.

    “Quantum walks [5,6]-an extension of the classical random walk into the quantum world-provide an ideal framework for emulation due to their rich dynamics [7][8][9].”

    From Two-photon quantum walks in an elliptical direct-write waveguide array (2011) · cites this paper as [6]

  • For proper initial conditions, the DTQW walker spreads symmetrically with a nearly constant probability distribution except for two peaks at x±=±ct, beyond which the probability quickly goes to zero.

    “for proper initial conditions the walker spreads out symmetrically, with a nearly constant probability distribution save for two peaks located at x ± = ± ct (where c = 1 / √ 2 for the 'Hadamard walk' [2]), beyond which the probability quickly goes to zero.”

    From Relativistic quantum walks (2006) · cites this paper as [2]

  • The standard deviation of the DTQW walker's position grows linearly in time, unlike the classical random walk.

    “the standard deviation of the walker's position grows linearly in time ((∆ x ) t ∼ t ), in clear distinction to the classical random walk ((∆ x ) t ∼ t 1 / 2 )”

    From Relativistic quantum walks (2006) · cites this paper as [2]

  • Thermal noise in stationary non-equilibrium systems may support the existence of quantum coherence and entanglement.

    “early work in quantum information science, for example, has shown that thermal noise in stationary non-equilibrium systems may in fact support the existence of quantum coherence and entanglement [4, 5].”

    From Vibrations, quanta and biology (2013) · cites this paper as [5]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Measured down-spin position disagrees with the preceding state

    Minor

    Equation (2) places the down-spin component at x0+l, but the subsequent description places that same outcome at x0−l.

1 of 1

Cites

Flagged first, then by citations

Research works printed but not linked: 16

  1. [2]2. R.J. Hughes, D.M. Alde, P. Dyer, G.G. Luther, G.L. Morgan, and M. Schauer. Quantum cryptography. Con- temp. Phys., 36(3):149-163, May-June 1995.
  2. [11]11. D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani. Quantum walks on graphs. In Proc. 33th STOC, pages 50-59, New York, NY, 2001. ACM.
  3. [17]17. C. Moore and A. Russell. Quantum walks on the hy- percube. In J.D.P. Rolim and S. Vadhan, editors, Proc. RANDOM 2002, pages 164-178, Cambridge, MA, 2002. Springer.
  4. [20]20. T. Yamasaki, H. Kobayashi, and H. Imai. An analysis of absorbing times of quantum walks. In C. Calude, M.J. Dinneen, and F. Peper, editors, Unconventional Models of Computation, Third International Conference, UMC 2002, Kobe, Japan, October 15-19, 2002, Proceedings, volume 2509 of Lecture Notes in Computer Science, pages 315-330. Springer, 2002.
  5. [26]26. D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. preprint available at http://stat-www.berkeley.edu/users/aldous/book.html.
  6. [27]27. A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D.A. Spielman. Exponential algorithmic speedup by quantum walk, 2002. lanl-report quant-ph/0209131. · arXiv
  7. [30]30. C. Papadimitriou. Computational Complexity. Addison Wesley, Reading, Massachusetts, 1994.
  8. [31]31. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  9. [37]37. L. Lovasz and P. Winkler. Mixing times. In D. Aldous and J. Propp, editors, Microsurveys in Discrete Proba- bility, volume 41 of DIMACS Series on Disc. Math. and Theoret. Comp. Sci., pages 85-134. AMS, 1998.
  10. [40]40. D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge, 2003. to ap- pear in Proc. 35th STOC (ACM, New York, NY).
  11. [41]41. E. Bernstein and U. Vazirani. Quantum complexity the- ory. SIAM Journal on Computing, 26:1411, 1997.
  12. [43]43. B.C. Sanders, S.D. Bartlett, B. Tregenna, and P.L. Knight. Quantum quincunx in cavity quantum electro- dynamics, 2002. arXive eprint quant-ph/0207028. · arXiv
  13. [47]47. M.O. Scully and M.S. Zubairy. Quantum Optics. Cam- bridge University Press, New York, 1997.
  14. [49]49. T.A. Brun, H.A. Carteret, and A. Ambainis. The quan- tum to classical transition for random walks, 2002. LANL preprint quant-ph/0208195. · arXiv
  15. [50]50. T.A. Brun, H.A. Carteret, and A. Ambainis. Quan- tum random walks with decoherent coins, 2002. LANL preprint quant-ph/0210180. · arXiv
  16. [51]51. T.A. Brun, H.A. Carteret, and A. Ambainis. Quan- tum walks driven by many coins, 2002. LANL preprint quant-ph/0210161. · arXiv

Cited by

Sorted by citations

Related

Authors
Kempe, J.
Affiliations
Université Paris-Sud (FR)
Corresponding author
Kempe, J
ORCID
Kempe, J
Venue
Contemporary Physics
Publisher
Informa UK Limited
Published
2003-07
Volume
44
Issue
4
Pages
307-327
ISSN
  • 0010-7514 (ISSN-L)
  • 1366-5812
DOI
10.1080/00107151031000110776
OpenAlex
W2160185408
Cited by
1,413
References
29
Citations by year
2026: 66 · 2025: 64 · 2024: 77 · 2023: 85 · 2022: 76 · 2021: 74 · 2020: 82 · 2019: 76 · 2018: 75 · 2017: 68 · 2016: 77 · 2015: 66 · 2014: 69 · 2013: 70 · 2012: 69
FWCI
32.30
Type
journal article
Language
en
Open access
Locations
  • Contemporary Physics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Defense Advanced Research Projects Agency
  • U.S. Air Force
  • Advanced Research Projects Agency
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
quantum walks, classical random walks, quantum information, quantum computing applications, open problems

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-11.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-11.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review