Quantum Walk on the Line

Ashvin Vishwanath; Ashwin Nayak

REVIEW

Quantum Walk on the Line

Ashwin Nayak, Ashvin Vishwanath

Quantum Physics · Submitted 31 Oct 2000 · 23 references

Pith's verdict: The line-distribution result is solid and genuinely new; the circle-mixing headline is asserted in a sentence rather than derived, and the general-walk claims rest on an unpublished companion.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on October 29, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/0010117 (version 1)

Pith IDZP5SDISX, Pith's permanent record of this paper and its review

CitationAshvin Vishwanath, Ashwin Nayak. "Quantum Walk on the Line." arXiv:quant-ph/0010117 (2000). https://pith.science/paper/ZP5SDISX

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Worth your time, but read it as two papers: a solid one about the line, and a promissory note about the circle and about general graphs. The solid part is real. The exact Fourier solution (Eqs. 4–7) is checkable by hand, the stationary-phase work in Appendix B is textbook-clean, and splitting the distribution into a slow piece plus a fast oscillating piece is the right move. The check that p(alpha) = (1-alpha)/(pi|omega''|) integrates to 1 via |omega''| = dalpha/dk is the kind of step that makes an asymptotic result trustworthy rather than decorative, and the moment table matching simulation at t=80 backs it up. Meyer had the closed form; nobody had extracted the distribution from it, and that is the contribution. Now the soft spots. The abstract's headline [abstract:s3] is the circle corollary, and it gets one sentence in Section 4: 'immediate.' It isn't. Parity is the first problem: on an even cycle the walk never leaves its parity class, so total variation distance to uniform over all sites is bounded below by 1/4 at every t. Footnote 2 allows delta < 1, so this is survivable, but the Section 3.3 bound delta = 1 - beta*c cannot be the operative circle bound without saying so. Second, footnote 2 defines the mixing time as independent of initial state, and the whole analysis is for (1,0)^T; Appendix D's symmetric-state P_slow is a different expression. Plausible, unshown. Your worry about P_fast concentrating does not land: Eq. 8 bounds it pointwise at the same O(1/t) scale as P_slow, so it cannot concentrate mass beyond a constant factor. The 'straightforward calculation' in Section 3.3 is thin, but the conclusion it reaches is right. The theta-family section leans on [16], listed as in preparation. They flag the space limitation themselves, so it is not a hidden gap, but a referee should ask what is actually proved there versus gestured at. Send it out. It is a founding paper and the line result stands on its own; the referee's job is to make them write Sections 3.3 and 4 properly.

Referee report

Major objections (4)

[§3.3 and §4] The step from the line to the circle is carried by one sentence in §4 (''The linear time mixing for the circle is immediate'') and by the un-derived counting argument in §3.3 (''a straightforward calculation shows''). Two concrete obstructions are not addressed. (i) On an even cycle the Hadamard walk preserves parity, so the total-variation distance to uniform over all n sites is bounded below by 1/2 for every t, independent of how far the walk has spread; the paper's δ-mixing definition (fn. 2) permits δ < 1, so this is survivable, but the bound δ = 1 - βc in §3.3 cannot be the operative bound on the circle without saying so explicitly. (ii) fn. 2 defines the δ-mixing time as ''independent of the initial state'', yet the entire analysis is for the single initial chirality (1,0)^T; Appendix D's Eq. 31 shows P_slow differs for the symmetric initial condition, so uniformity over initial states is plausible but not shown. In addition, §1 attributes O(n log n) circle mixing to [1] (a personal communication), which is weaker than the linear claim made here; the paper should reconcile the two notions of mixing or explain the discrepancy.
[§3.3] There is a factor-of-two inconsistency in the load-bearing mixing argument. The text states that ''P(α,t) is at most 1/√2 t within the interval'', but Eq. 10 together with the caption of Figure 3 (''P_slow is scaled by a factor of 2 because it has support on the odd points as well'') implies that the typical probability at an occupied (even) site is 2 P_slow ≈ √2/t, not 1/(√2 t). The counting argument and the resulting ℓ1 bound 2(1 - βc) need to be redone with the correct per-site normalisation; as written the sentence also reads as an upper bound where the argument requires a lower bound. The qualitative conclusion (a constant δ < 1) survives, but the stated constants do not.
[§1, Appendix B, Appendix D] Several load-bearing claims are deferred to reference [16], listed as ''In preparation, October 2000'': the reduction to a one-parameter family of walks (§1 and Appendix D), the transition-region analysis around α = ±1/√2 (Appendix B), and the finite-line mixing (§4). Appendix D's assertion that every θ ∉ {0, π} mixes in linear time is presented as part of this paper's contribution but is not proved here. Either include the key steps or mark these results explicitly as unproved in this manuscript, so the reader can tell which claims are established and which are cited.
[Abstract and §3.1] The abstract's ''almost uniformly distributed'' overstates the pointwise behaviour. Eq. 8 shows the probability oscillates with O(1) relative amplitude (the cos² terms range over [0, 1]), so P oscillates between roughly zero and twice its mean; the uniform description applies to the coarse-grained P_slow, not to P pointwise. The abstract should say ''uniform on average'' or ''coarse-grained'', and §3.3 should state precisely which notion of uniformity the mixing argument establishes.

Minor objections (6)

[§2.1] The sentence ''Here L and R refer to the 'right' and 'left' chirality states'' reverses the labels; L is left and R is right throughout the rest of the paper.
[Eq. 18 vs Eq. 35] At θ = π/2 these two equations give different values of k_α for the same α (for example α = 0.5), indicating a sign-convention mismatch between Appendix B (where α = -ω'_k, Eq. 15) and Appendix D (where Eq. 32 sets α = +ω'_k). Probabilities are unaffected because ω''_{kα} is even in α, but the reader cannot use both definitions as written; fix the convention and cross-reference it.
[§1] The phrase ''the analogously defined walk on the or the circle'' is garbled and should be corrected.
[Figures 2, 3, 5] The figures have no axis titles; label the vertical axis ''probability'' and state the value of t in each caption. The captions do correctly note that only even points are plotted.
[Eq. 8] The quantities k_α and φ(α) are defined only later, in Appendix B (Eqs. 18–19); define them or cross-reference at first use so Eq. 8 is self-contained.
[Abstract] ''Unbiased'' refers to the walk rules, not to the realised distribution: the (1,0)^T initial state gives ⟨α⟩ = -0.293, as the paper itself notes. Point the reader to the formal definition in Appendix D.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

A quantum walk spreads itself almost flat across its whole reachable range in $t$ steps, so the matching walk on a circle mixes in time linear in its size rather than quadratic.

The reading

Classical random walks are the engine behind a large family of algorithms, and the paper asks what happens to the walk itself when the coin toss is replaced by a quantum operation. The authors define a walk on the integer line in which a particle carries a two-valued 'chirality' (left or right), has that chirality rotated by a Hadamard transformation at each step, and then moves one site in whichever direction the rotated chirality indicates. Solving the resulting two-component recurrence exactly in Fourier space and then applying stationary-phase asymptotics, they find that after $t$ steps the position distribution is spread almost evenly over the interval $[-t/√2, t/√2]$, with the probability falling off faster than any inverse power of $t$ outside it. The consequence the authors draw is that the same walk wrapped onto a circle of $n$ sites is already close to uniform after a number of steps linear in $n$, where the classical walk needs quadratic time. If that holds, the standard recipe of 'simulate a Markov chain and sample from it' has a quantum analogue that reaches its stationary-looking distribution quadratically sooner, at least in one dimension.

What carries the argument

The load-bearing device is the Fourier-space diagonalisation of the one-step operator combined with the method of stationary phase. Translational invariance makes the walk a multiplication by a $2×2$ unitary $M_k$ in momentum space, so the $t$-step wave function is just $M_k^t$ applied to the initial chirality, which is written out in closed form in Equations 4 and 5. Inverting the transform leaves integrals of the form $∫ g(k) e^{iφ(k,α)t} dk$ with $φ(k,α) = -(ω_k + αk)$, and the stationary points $±k_α$ of $φ$ — fixed by $∂φ/∂k = 0$, i.e. $ω'_{k_α} + α = 0$ — supply the $t^{-1/2}$ amplitude in the bulk, the endpoints $k = 0, π$ supply the $t^{-1/3}$ frontier peaks, and the absence of stationary points outside supplies the fast decay. The identity $|ω''_{k_α}| = dα/dk_α$ is what converts the sum over lattice sites into a Riemann integral and lets the authors show $p(α) = t P_{slow}(α,t)$ normalises to one.

Extended reading notes

Core claim

The paper establishes that the Hadamard walk — a quantum particle on $Z$ whose chirality is Hadamard-rotated and then translated one step left or right — has an almost uniform position distribution over $[-t/√2, t/√2]$ after $t$ steps. The exact solution comes from diagonalising the $2×2$ unitary $M_k = e^{ik}M_+ + e^{-ik}M_-$ that advances the Fourier-transformed wave function by one step; its eigenvalues are $e^{∓iω_k}$ with $ω_k$ defined by $ω_k = k/√2$ to leading order, and inverting the Fourier transform turns each amplitude into an oscillatory integral. The method of stationary phase then shows three regimes: exponential-type decay beyond $|α| > 1/√2$ where $α = n/t$, a $t^{-1/3}$ peak of width $O(t^{1/3})$ exactly at the two frontiers $α = ±1/√2$, and a $t^{-1/2}$ bulk in between. In the bulk the probability splits into a non-oscillating part $P_{slow}(α,t) = (1-α)/(π t |ω''_{k_α}|)$ and a rapidly oscillating part, and the slow part is a genuine probability density on $[-1/√2, 1/√2]$ that integrates to one and reproduces the simulated moments ($⟨α⟩ = -1 + 1/√2$, $⟨|α|⟩ = 1/2$, $⟨α^2⟩ = 1 - 1/√2$). The authors then argue that a constant fraction of the sites in the bulk carry probability at least a constant over $√2 t$, which bounds the total variation distance from uniform by a constant below one.

Load-bearing premise

The step from 'the bulk probability is about $1/(√2 t)$ per site' to '$δ$-close to uniform for a constant $δ < 1$' rests on the Section 3.3 sentence that 'a straightforward calculation shows' a constant fraction of sites carry at least a constant over $√2 t$, and the circle-mixing statement is then called 'immediate' in Section 4 without a written proof; the authors also state that for lack of space they cannot give full details of the general-walk analysis, deferring them to a paper in preparation.

Editorial extensions

If this is right

The same walk defined on a circle of $n$ sites mixes to within constant total variation distance of uniform in time linear in $n$, against quadratic time for the classical symmetric walk.
Almost all the probability stays inside $[-t/√2, t/√2]$: the mass outside, including the two frontier peaks, is only $O(t^{-1/3})$, so the effective speed of the quantum walk is $1/√2$ sites per step.
A one-parameter family of unbiased quantum walks, $U_θ = e^{i(θ/2)σ_y}$, reproduces the same qualitative picture for every $θ$ except the degenerate $θ = 0$ and $θ = π$, where the particle either travels in one direction forever or zig-zags among at most three sites.
For the general family the distribution is near-uniform on $[-\cos(θ/2), \cos(θ/2)]$, with mean absolute position $⟨|α|⟩ = 1 - θ/π$, so the Hadamard case $θ = π/2$ sits at the widest spread.
The asymptotic formulas agree with direct simulation at $t = 80$ and $t = 100$, which the authors take as a hint that the analysis is usable for small quantum systems and not only in the large-$t$ limit.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The quadratic-to-linear gain here is a statement about spreading, not about algorithmic speed-up: to turn it into an algorithm one needs a way to extract a sample from the near-uniform distribution, and the paper does not address readout or the cost of preparing the required initial chirality.
Because the bulk probability per site scales as $1/t$, distinguishing the walk's output from uniform requires only polynomially many samples, which is the regime in which a quantum sampler could plausibly beat classical Markov chain Monte Carlo on graphs with the same translation symmetry.
The technique generalises to any graph whose walk operator is diagonalised by a Fourier-type transform — Cayley graphs of abelian or finite groups are the natural next target, and the paper names them as the promising class.
The authors' notion of mixing is closeness to uniform at a single time, not convergence to a stationary distribution; since a unitary process is recurrent, the average-over-time definition used by the concurrently cited work is the one that survives in the long run, and the two definitions could give different answers on graphs without the line's symmetry.

Original abstract

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,816 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.14 · human participants 0.01 · controlled comparison 0.40 · randomized assignment 0.02 · states quantitative result 0.96 · compares with prior results 0.96 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs.	background 0.94	0.15	0.02	asserted 0.65
s1	We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''.	contribution 0.98	0.91	0.04	asserted 0.85
s2	We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)].	result 1.00	0.93	0.36	asserted 1.00
s3	This implies that the same walk defined on the circle mixes in_linear_ time.	interpretation 0.84	0.87	0.35	asserted 0.99
s4	This is in direct contrast with the quadratic mixing time for the corresponding classical walk.	interpretation 0.82	0.44	0.24	asserted 1.00
s5	We conclude by indicating how our techniques may be applied to more general graphs.	future work 1.00	0.30	0.10	hedged possibility 0.98

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** The dynamics of the Hadamard walk. In (a) we begin at time t with a particle in chirality state “right” or “left”. The result of the Hadamard transformation is shown in (b), the particle is now in an equal superposition of “left” and “right” chirality states (with the amplitudes indicated) and then moves accordingly (c) to generate the state at time t + 1. We begin by considering the quantum walk in one dimension. Recall that a classical particle doing a random walk on the integer lattice chooses, at every time step, a random direction (“left” or “right”) to move in, and moves to…

**Figure 2.** A comparison of two probability distributions, one obtained from a computer simulation of the Hadamard walk, and the other from from an asymptotic analysis of the walk. The number of steps in the walk was taken to be 100. Only the probability at the even points is plotted, since the odd points have probability zero. ψL(n,t) = 1 + (−1)n+t 2 Z π −π dk 2π (1 + cos k √ 1 + cos2 k ) e−i(ωkt+kn) (6) ψR(n,t) = 1 + (−1)n+t 2 Z π −π dk 2π e ik √ 1 + cos2 k e −i(ωkt+kn) (7) Notice that the amplitudes vanish for even n (respectively, odd n) at odd t (even t), as we would expe

**Figure 3.** A comparison of the distributions P and Pslow for t = 100. Only the probability at the even points is plotted, and Pslow is scaled by a factor of 2 because it has support on the odd points as well. The calculation of moments is further simplified by the following observation. Let p(α) = tPslow(α,t). Then p is a probability density function over the interval between ∓1/ √ 2. It is clearly non-negative, and we show below that it integrates to 1. This observation allows us to approximate the sums in the moment calculations by a Riemann integral, and the error so introduced is again a…

**Figure 4.** A table of moments calculated with the approximation by the density function p(α), which are compared with computer simulation results with t = 80. We claim that there is a constant δ < 1 such that at time t, P is δ-close to the uniform distribution on the integer points between ∓t/√ 2. We emphasise that for classical symmetric random walk, the corresponding mixing time is quadratic in t. In order to show that the Hadamard walk is “mixed” at time t (in the sense described above), it suffices to show that a constant fraction β > 0 of the points in the said interval have probability…

**Figure 5.** The probability distribution obtained from a computer simulation of the Hadamard walk with a symmetric initial condition. The number of steps in the walk was taken to be 100. Only the probability at the even points is plotted, since the odd points have probability zero. C Justification for approximations made in section 3 In calculating the moments of the probability distribution P(α,t) obtained by observing a particle doing the Hadamard walk, we made two approximations. First, we decomposed P into a slowly varying, nonoscillating part Pslow and a quickly oscillating part Pfast. We…

Figures reproduced from arXiv:quant-ph/0010117 by the authors.

References

Works cited (23)

[16]

Ashwin Nayak and Ashvin Vishwanath. In preparation, Oc tober 2000

View on Pith 2000
[1]

Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Personal communication, October 2000

View on Pith 2000
[2]

Andris Ambainis and John Watrous. Personal communicati on, October 2000

View on Pith 2000
[3]

Carl M. Bender and Steven A. Orszag. Advanced Mathematical Methods for Scientists and Engineer s. International Series in Pure and Applied Mathematics. McGr aw-Hill, Inc., New York, 1978

View on Pith 1978
[4]

Norman Bleistein and Richard A. Handelsman. Asymptotic Expansions of Integrals . Holt, Rinehart and Winston, New York, 1975

View on Pith 1975
[5]

Persi Diaconis. Group Representations in Probability and Statistics , volume 11 of Lecture Notes- Monograph Series. Institute of Mathematical Statistics, Hayward, Californ ia, 1988

View on Pith 1988
[6]

Martin Dyer, Alan Frieze, and Ravi Kannan. A random polyn omial-time algorithm for approximating the volume of convex bodies. Journal of the ACM , 38(1):1–17, January 1991

View on Pith 1991
[7]

H. Dym and H. P. McKean. Fourier Series and Integrals , volume 14 of Probability and Mathematical Statistics. Academic Press, New York, 1972

View on Pith 1972
[8]

Lov K. Grover. A fast quantum mechanical algorithm for da tabase search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computi ng, pages 212–219, Philadelphia, Pennsylvania, 22–24 May 1996

View on Pith 1996
[9]

Mark Jerrum and Alistair Sinclair. Approximating the pe rmanent. SIAM Journal on Computing , 18(6):1149–1178, December 1989

View on Pith 1989
[10]

Mark Jerrum and Alistair Sinclair. The Markov chain Mon te Carlo method: An approach to approxi- mate counting and integration. In Dorit S. Hochbaum, editor , Approximation Algorithms for NP-hard Problems, chapter 12, pages 482–520. PWS Publishing, Boston, 1996

View on Pith 1996
[11]

Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A poly nomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Technical Report TR00-079, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier .de/eccc/, 2000. 11

View on Pith 2000
[12]

L´ aszl´ o Lov´ asz and Ravi Kannan. Faster mixing via average conductance. In Proceedings of the Thirty- First Annual ACM Symposium on Theory of Computing , Atlanta, Georgia, 1–4 May 1999. ACM

View on Pith 1999
[13]

David A. Meyer. From quantum cellular automata to quant um lattice gases. Journal of Statistical Physics, 85:551–574, 1996

View on Pith 1996
[14]

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

View on Pith 1995
[15]

Ashwin Nayak, Leonard Schulman, and Umesh Vazirani. Un published, 1997

View on Pith 1997
[17]

Christos H. Papadimitriou. On selecting a satisfying t ruth assignment. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science , pages 163–169, San Juan, Puerto Rico, 1–4 October 1991. IEEE Computer Society

View on Pith 1991
[18]

Dana Randall and David Wilson. Sampling spin conﬁgurat ions of an ising system. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorith ms, pages S959–960, Baltimore, Maryland, 17–19 January 1999

View on Pith 1999
[19]

Uwe Sch¨ oning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceed- ings of the 40th Annual Symposium on Foundations of Computer Science, New York City, NY, 17–19 October 1999. IEEE Computer Society

View on Pith 1999
[20]

Peter W. Shor. Polynomial-time algorithms for prime fa ctorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484–1509, October 1997

View on Pith 1997
[21]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474– 1483, October 1997

View on Pith 1997
[22]

John Watrous. Quantum simulations of classical random walks and gndirected graph connectivity. In Proceedings of the Annual IEEE Conference on Computational Complexity, pages 180–187, Atlanta, Georgia, USA, 4–6 May 1999. A Technical background In this section, we give details of the concepts and results f rom mathematical analysis that we use in the paper...

View on Pith 1999
[23]

At these points, φ has a stationary point of order 2 atk =π, 0, respectively, as may readily be veriﬁed. Using the method of stationary phase, we thus get the following leading term for I at these points: I( 1√2,t ) ∼ g(π)3π √2 Γ(1/3)[ 6t]1/3 cos( π√2t + π6) I(− 1√2,t ) ∼ g(0)6π √ 3 2 Γ(1/3) [ 6 t ]1/3 . Finally, we turn to the interval of most interest t...

View on Pith

Forward citations

Cited by 12 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Geometry of Transport in Quantum Walks and Parrondo's Paradox
quant-ph 2026-09 accept novelty 7.0 of 10

Parrondo's paradox in quantum walks is equivalent to the composite transport vector lying outside the convex cone generated by the individual transport vectors.
Restart and first detection in a lackadaisical quantum walk with flat-band localization
quant-ph 2026-09 accept novelty 7.0 of 10

The response of a lackadaisical quantum walk to random restart depends sharply on whether the initial state has overlap with a localized flat band, producing different power-law scaling for the restart-site occupation.
Ergodicity in discrete-time quantum walks
math-ph 2026-03 unverdicted novelty 7.0 of 10

In one dimension, ergodicity of homogeneous discrete-time quantum walks is equivalent to the absolutely continuous spectrum of the walk operator.
Discrete-time quantum walks with energy-dependent coins
quant-ph 2026-09 accept novelty 6.0 of 10

A family of homogeneous discrete-time quantum walks is constructed from the energy-dependent scattering amplitudes of four types of point interactions, yielding analytically tractable connections between transmission,...
Robust Genuine Multipartite Entanglement in Two Walker Quantum Walks
quant-ph 2026-08 conditional novelty 6.0 of 10

In an open two-walker discrete-time quantum walk, genuine multipartite entanglement rapidly approaches the theoretical maximum of 1/2 for all four Bell states and for a broad family of coin operators, except near the ...

Show 7 more citing papers

A Probabilistic Representation for Multi-State Discrete-time Quantum Walks
quant-ph 2026-07 conditional novelty 5.0 of 10

Three-state discrete-time quantum walks on Z admit an exact Monte Carlo representation via Poisson-driven classical processes that converges to multi-state Dirac PDEs.
Self-Trapping Bounds for Continuous-Time Nonlinear Quantum Walks on Path and Cycle Graphs
quant-ph 2026-05 unverdicted novelty 5.0 of 10

Nonlinear continuous-time quantum walks on paths and cycles can be trapped at the initial site to arbitrary fidelity by choosing the cubic nonlinearity coefficient, unlike spreading linear walks.
Quantum percolation in quasicrystals using continuous-time quantum walk
quant-ph 2019-08 conditional novelty 5.0 of 10

Continuous-time quantum walks on Penrose and Ammann-Beenker quasicrystals show stronger localization and faster loss of percolation with disorder than on a square lattice.
Controlled dynamics of a multi-component discrete-time quantum walker
quant-ph 2026-08 conditional novelty 4.0 of 10

For a three-state quantum walk with a pairwise-coupling SU(3) coin (angles β, γ, with α fixed at π/4), spreading stays ballistic for all couplings while the speed and left-right asymmetry vary in structured ways acros...
Classification of coined quantum walks on the line and comparison to correlated classical random walks
quant-ph 2025-07 conditional novelty 4.0 of 10

Coined quantum walks on the line are classified modulo distributional equivalence by a few angles, and their closed-form amplitudes are corrected and linked to classical correlated walks.
Response to glassy disorder in coin on spread of quantum walker
quant-ph 2021-11 unverdicted novelty 4.0 of 10

Glassy disorder in the coin of a 1D discrete-time quantum walk inhibits ballistic spread while keeping it faster than classical diffusion, with slow or fast falloff and mid-strength inflection points depending on the ...
Investigation of Continuous-Time Quantum Walk Via Modules of Bose-Mesner and Terwilliger Algebras
quant-ph 2006-03 conditional novelty 4.0 of 10

The paper reformulates continuous-time quantum walks on association schemes using Bose-Mesner and Terwilliger algebras, giving spectral formulas for transition amplitudes that depend only on the relation class of the ...

How later papers used it

90 later papers cite it

Evidence: substantial. 90 of the citing papers share no author with it, and 16 of those carry a confident label from Pith's citation classifier.

Pith read 29 of the 149 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

6 later papers by other authors are listed below: 6 used its method or tool.

Uses its method or tool 6 of 14 papers with this label

Approximated the single particle probability distribution according to this paper and replaced the sum by an integral.

Interference Phenomena in Quantum Information (2010) · 0.95 · paraphrased: the licence does not allow quoting
Used the method introduced in this paper to obtain the amplitudes of the quantum walk with memory on a cycle and represented its time evolution using the Fourier transform.

Quantum walks with memory on cycles (2013) · 0.96 · paraphrased: the licence does not allow quoting
Following another work and this paper, considered the basis state of the particle as a product state of the chirality and position basis states.

An Effective Hamiltonian Approach to Quantum Random Walk (2015) · 0.81 · paraphrased: the licence does not allow quoting
Used path integration from this paper to obtain the solution for the quantum part of the walk.

Controlling and reversing the transition from classical diffusive to quantum ballistic transport in a quantum walk by driving the coin (2012) · 0.97 · paraphrased: the licence does not allow quoting
Following the analysis given in another work, transformed the state vector in this paper to momentum space.

Closed-form expressions for the probability distribution of quantum walk on a line (2023) · 0.99 · paraphrased: the licence does not allow quoting
Used this paper for the inverse Fourier transform.

Quantum Corralling (2021) · 0.82 · paraphrased: the licence does not allow quoting

How the literature uses it

91 arXiv papers cite this in 149 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 69 sentences without a confident label

Uses its method or tool 13 papers

As described in [ref] , this can be done using the method of steepest descent, where we examine the time-oscillatory portion of [ref] and [ref], which is [equation] where we have defined [equation] From the analysis of [ref] , the part we care about is the movement of the peak in probability (e.g., the leading right peak in Figure [ref]).

Quantum Walk on the Line through Potential Barriers · Analysis with Potential Barriers · 1.00
Concerning the quantum walk, in Appendix [ref] we approximate the single particle probability distribution according to [ref] and replace the sum in ([ref]) by integral.

Interference Phenomena in Quantum Information · Meeting problem for distinguishable particles · 0.95
In order to obtain the expression for the amplitudes of the quantum walk with memory on cycle we use the method introduced in [ref] and represent time evolution of the walk using the Fourier transform [equation] From the above we get a recursive relation for the time evolution in the Fourier basis [equation] where [equation]

Quantum walks with memory on cycles · Fourier analysis · 0.96

Compares with it 3 papers

Eq (8) in [ref] ), where one obtains a common factor $1+(-1)^t+tα$, reflecting the parity properties of the QW: for even (odd) $t$, the probability distribution vanishes at odd (even) sites.

Asymptotic properties of the Dirac quantum cellular automaton · Stationary phase method · 0.99
This method is in fact stronger than the stationary point method from [ref] and [ref] , where the authors use it to study the asymptotics of the resulting probability distribution from coin operators with real eigenvalues.

Quantum Walks on the Line with Phase Parameters · Contributions · 0.96
The paper [ref] asked the same question but had a different approach.

Ergodicity in discrete-time quantum walks · Coins with nonzero entries · 0.95

Cites it as background 51 papers

In the literature of discrete quantum walk [ref] , the Kitaev model [ref] for quantum wire is one of the simplest systems that supports these topological phases, which are identified as Majorana boundary modes [ref] .

Field Induced Oscillation of Two Majorana Modes for a finite Quantum Wire · Introduction · 0.95
Background on QWs Discrete-time QWs embody a widely studied type of interaction between a two-dimensional “coin” degree of freedom, and a high-dimensional “walker” one [ref] .

Entanglement transfer, accumulation and retrieval via quantum-walk-based qubit-qudit dynamics · Background · 1.00
Both continuous [ref] and discrete [ref] models of QW have been formulated, which exhibit properties that are qualitatively different from the classical analog [ref] .

Quantum walks on embedded hypercubes · Introduction · 0.88

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [16]

Ashwin Nayak and Ashvin Vishwanath. In preparation, Oc tober 2000

View on Pith 2000

[2] [1]

Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Personal communication, October 2000

View on Pith 2000

[3] [2]

Andris Ambainis and John Watrous. Personal communicati on, October 2000

View on Pith 2000

[4] [3]

Carl M. Bender and Steven A. Orszag. Advanced Mathematical Methods for Scientists and Engineer s. International Series in Pure and Applied Mathematics. McGr aw-Hill, Inc., New York, 1978

View on Pith 1978

[5] [4]

Norman Bleistein and Richard A. Handelsman. Asymptotic Expansions of Integrals . Holt, Rinehart and Winston, New York, 1975

View on Pith 1975

[6] [5]

Persi Diaconis. Group Representations in Probability and Statistics , volume 11 of Lecture Notes- Monograph Series. Institute of Mathematical Statistics, Hayward, Californ ia, 1988

View on Pith 1988

[7] [6]

Martin Dyer, Alan Frieze, and Ravi Kannan. A random polyn omial-time algorithm for approximating the volume of convex bodies. Journal of the ACM , 38(1):1–17, January 1991

View on Pith 1991

[8] [7]

H. Dym and H. P. McKean. Fourier Series and Integrals , volume 14 of Probability and Mathematical Statistics. Academic Press, New York, 1972

View on Pith 1972

[9] [8]

Lov K. Grover. A fast quantum mechanical algorithm for da tabase search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computi ng, pages 212–219, Philadelphia, Pennsylvania, 22–24 May 1996

View on Pith 1996

[10] [9]

Mark Jerrum and Alistair Sinclair. Approximating the pe rmanent. SIAM Journal on Computing , 18(6):1149–1178, December 1989

View on Pith 1989

[11] [10]

Mark Jerrum and Alistair Sinclair. The Markov chain Mon te Carlo method: An approach to approxi- mate counting and integration. In Dorit S. Hochbaum, editor , Approximation Algorithms for NP-hard Problems, chapter 12, pages 482–520. PWS Publishing, Boston, 1996

View on Pith 1996

[12] [11]

Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A poly nomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Technical Report TR00-079, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier .de/eccc/, 2000. 11

View on Pith 2000

[13] [12]

L´ aszl´ o Lov´ asz and Ravi Kannan. Faster mixing via average conductance. In Proceedings of the Thirty- First Annual ACM Symposium on Theory of Computing , Atlanta, Georgia, 1–4 May 1999. ACM

View on Pith 1999

[14] [13]

David A. Meyer. From quantum cellular automata to quant um lattice gases. Journal of Statistical Physics, 85:551–574, 1996

View on Pith 1996

[15] [14]

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

View on Pith 1995

[16] [15]

Ashwin Nayak, Leonard Schulman, and Umesh Vazirani. Un published, 1997

View on Pith 1997

[17] [17]

Christos H. Papadimitriou. On selecting a satisfying t ruth assignment. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science , pages 163–169, San Juan, Puerto Rico, 1–4 October 1991. IEEE Computer Society

View on Pith 1991

[18] [18]

Dana Randall and David Wilson. Sampling spin conﬁgurat ions of an ising system. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorith ms, pages S959–960, Baltimore, Maryland, 17–19 January 1999

View on Pith 1999

[19] [19]

Uwe Sch¨ oning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceed- ings of the 40th Annual Symposium on Foundations of Computer Science, New York City, NY, 17–19 October 1999. IEEE Computer Society

View on Pith 1999

[20] [20]

Peter W. Shor. Polynomial-time algorithms for prime fa ctorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484–1509, October 1997

View on Pith 1997

[21] [21]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474– 1483, October 1997

View on Pith 1997

[22] [22]

John Watrous. Quantum simulations of classical random walks and gndirected graph connectivity. In Proceedings of the Annual IEEE Conference on Computational Complexity, pages 180–187, Atlanta, Georgia, USA, 4–6 May 1999. A Technical background In this section, we give details of the concepts and results f rom mathematical analysis that we use in the paper...

View on Pith 1999

[23] [23]

At these points, φ has a stationary point of order 2 atk =π, 0, respectively, as may readily be veriﬁed. Using the method of stationary phase, we thus get the following leading term for I at these points: I( 1√2,t ) ∼ g(π)3π √2 Γ(1/3)[ 6t]1/3 cos( π√2t + π6) I(− 1√2,t ) ∼ g(0)6π √ 3 2 Γ(1/3) [ 6 t ]1/3 . Finally, we turn to the interval of most interest t...

View on Pith