REVIEW 3 major objections 5 minor 29 references
Classification of coined quantum walks on the line and comparison to correlated classical random walks
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read One angle classifies every symmetric coined quantum walk on the line, and corrected closed-form amplitudes make finite-step predictions exact.
desk verdict Useful extension of Konno's classification, but Theorem 3's surjectivity proof has a sign gap that needs fixing before the paper's main claims are fully established. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing device is the reduction of a coin setup to the handful of quantities that actually enter the spatial distribution: the squared amplitudes $|\alpha|^2,|\beta|^2,|a|^2,|b|^2$ and the overlap term $\kappa=2\cos(\theta)\sin(\theta)\cos(\varphi)\sin(\varphi)\cos(\xi-\phi_2)$, as given in [22, Lemma 3]. The canonical family of Theorem 2 is obtained by enforcing the symmetry conditions $|\alpha|=|\beta|=1/\sqrt2$ and $\kappa=0$, which leaves only $\theta$ free. For the exact amplitudes, the paper applies the spatial Fourier transform to the walk operator, reducing $n$ steps to the $n$-th power of a $2\times2$ matrix, and evaluates those powers with the Fibonacci–Horner decomposition coming from the Cayley–Hamilton theorem. The same matrix-power machinery, with the unitary coin replaced by a doubly stochastic transition matrix, yields the correlated classical formulas.
What would settle it
Run the walk for a small fixed number of steps, say $n=3$, with a generic non-symmetric coin such as Hopf coordinates $\theta=\pi/4$, $\phi_1=0.3$, $\phi_2=0.1$ and initial state $\varphi=\pi/3$, $\xi=1.2$, and compare the Lemma 5 amplitudes with a direct matrix multiplication of $W(C)^3$ applied to $|0\rangle|\gamma\rangle$; any difference beyond rounding error would falsify the corrected closed-form expression, and since the classification feeds on the same distribution formula, it would also undercut Theorems 2--4.
Extended reading notes
Core claim
On its own terms, the paper claims that the spatial probability distribution $p_{\mathcal C}(j,n)$ is the correct equivalence invariant for a coin setup $\mathcal C=(C,|\gamma\rangle)$, and that modulo this invariant the symmetric walks are classified by $\theta\in[0,\pi/2]$. Theorem 2 establishes the bijection $\theta\mapsto(\cos(\theta)(|\uparrow\rangle\langle\uparrow|+|\downarrow\rangle\langle\downarrow|)+\sin(\theta)(|\uparrow\rangle\langle\downarrow|-|\downarrow\rangle\langle\uparrow|),\ (|\uparrow\rangle+i|\downarrow\rangle)/\sqrt{2})$. Theorem 3 shows every walk is distributionally equivalent to one with $\phi_1=0$ and parameter triples in $[0,\pi/2]\times[0,\pi]\times[0,\pi/2]$, and Theorem 4 gives a bijective description of the limiting densities $f_{\mathcal C}(x)=\frac{\sqrt{1-|a|^2(1-\lambda_{\mathcal C}x)}}{\pi(1-x^2)\sqrt{|a|^2-x^2}}$ with $\lambda_{\mathcal C}=\cos(2\varphi)+\sin(2\varphi)\tan(\theta)\cos(\xi)$. Lemma 5 provides corrected exact amplitudes $\alpha_j(n)$ and $\beta_j(n)$ for arbitrary $n$, and Lemma 6 gives the analogous joint probabilities for the correlated classical walk. The variance analysis concludes that every non-trivial quantum walk spreads quadratically in $n$, while correlated classical walks spread linearly except at full correlation, where the two models coincide.
Load-bearing premise
The classification takes as given the previously published formulas for the spatial distribution and limiting density of a general coined walk; if those formulas carry hidden assumptions about the coin or initial state, the parametrizations will not cover all walks.
Editorial extensions
If this is right
- For symmetric walks, the full history of spatial probabilities is encoded in the single angle $\theta$; two symmetric setups with the same $\theta$ are indistinguishable by position measurements at every time step.
- Beyond symmetry, every coined walk is captured by three real parameters $(\varphi,\xi,\theta)$ in the stated ranges, so classification questions reduce to a three-dimensional parameter space.
- The limiting distribution of any non-trivial walk is fixed by the pair $(\theta,\lambda_{\mathcal C})$, and the paper's counterexample with $\theta=1.2$, $\varphi_1=0.2$, $\varphi_2=1.0$ shows that equal limiting distributions do not imply equal finite-time distributions.
- Variance scales as $\Omega(n^2)$ for every non-trivial quantum walk; the only exception is the $\theta=\pi/2$ case, which oscillates, while the correlated classical walk scales linearly for $\delta\in(-1,1)$.
- The corrected amplitudes make exact finite-time predictions available for arbitrary coins and initial states, replacing the earlier expression that contained an error.
Reading between the lines
- Beyond the paper: because Theorem 2 is bijective, the same $\theta$ family could serve as an experimental benchmark: any measured symmetric walk distribution can be mapped to a $\theta$ value and tested against the exact amplitudes of Lemma 5.
- Beyond the paper: the surjective parametrization of Theorem 3 and the bijective limiting parametrization of Theorem 4 give an outer and an inner bound for the open problem of a bijective classification of all walks; a natural next step is to seek a minimal injective parameter domain interpolating between the two.
- Beyond the paper: the classical counterpart is built from one doubly stochastic transition matrix; replacing it with more general Markov transition matrices should produce non-symmetric classical limiting distributions and would allow a direct test of how much of the quantum asymmetry is genuinely non-classical.
- Beyond the paper: the closed-form amplitudes could be differentiated to yield the full characteristic function and all moments, giving a parameter-free derivation of higher cumulants beyond the variance.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies discrete-time coined quantum walks on the line with arbitrary SU(2) coins and arbitrary initial coin states. Its main results are: Theorem 1 characterizes the initial coin states that produce spatially symmetric walks; Theorem 2 gives a bijective parametrization of symmetric walks modulo the equivalence relation of having identical position distributions at all times; Theorem 3 gives a surjective parametrization of all walks modulo the same equivalence; and Theorem 4 gives a bijective parametrization of the limiting distributions of all non-trivial walks. The paper also derives closed-form amplitude expressions for quantum walks (Lemma 5) and for correlated classical random walks (Lemma 6), and compares the variance growth and limiting distributions of the two models.
Significance. If the theorems are correct, the classification is a useful and fairly complete structural description of one-dimensional coined quantum walks, consolidating and extending Konno's exact distribution formulas. The corrected finite-time amplitude formulas address a concrete error in the literature and are used in the paper's counterexamples and edge-case analyses. The comparison with correlated classical random walks is conceptually valuable, and the paper provides code and data on GitHub, which is a practical strength. However, the current manuscript contains two load-bearing proof errors in the classification theorems and omits the key final step of the inverse Fourier transform in Lemmas 5 and 6; these points need to be repaired before the central claims can be certified.
major comments (3)
- [IV.1, Proof of Theorem 3] The surjectivity proof is invalid as written. The reduction sets θ=ϱ(θ_C) and ξ=ξγ (or π−ξγ), but the interference term κ=cosθ sinθ cosφ sinφ cos(ξ−ϕ2) is not preserved by this map. If θ_C lies in (π/2,π) or (3π/2,2π), then cosθ sinθ changes sign under ϱ, and the prescribed ξ-transformation does not compensate. A concrete counterexample to the construction is θ_C=2π/3, φ=π/4, ξ=0: the original setup has κ<0, while the representative (θ,ξ)=(π/3,0) has κ>0; indeed the one-step probabilities are p(1)=(2−√3)/4 and p(−1)=(2+√3)/4 for the original, and these two values are interchanged for the constructed representative. Additionally, for ξγ>π the map ξ↦π−ξγ sends the parameter outside [0,π] and changes the sign of cosξ; the intended reduction appears to be 2π−ξγ or an equivalent phase shift. The surjectivity claim may be salvageable by choosing ξ̃ with cosξ̃=sign(cosθ_C sinθ_C)cos(ξγ−ϕ2), but the proof as it stands does not establish Theorem 3. I also note an inconsistency in the definition of κ: the proof of Theorem 2 uses aαbβ+aαbβ = 2cosθ sinθ cosφ sinφ cos(ξ−ϕ2), while the proof of Theorem 3 defines κ without the factor 2 and then states its range as [−1/4,1/4]; these two conventions cannot both be correct, and the discrepancy should be fixed.
- [IV.1, Proof of Theorem 2] The injectivity argument contains an algebraic error. From |a|^{2(n−1)}(|b|²+|a|²)/2 with |a|=cosθ and |b|=sinθ, one obtains cos^{2(n−1)}(θ)/2, since |b|²+|a|²=1. The displayed chain then incorrectly simplifies this to cos²(θ)/2. That equality is false for every n>1 and would make p(n,n) independent of n, which is not the case. Since this identity is used to prove injectivity of the parametrization θ↦[setup], the proof as written is not valid. The claim can be repaired by evaluating p(n,n) at n=2 (giving cos²θ/2, which is injective on [0,π/2]), but the current text must be corrected.
- [IV.2, Lemmas 5 and 6] The paper explicitly omits the final inverse Fourier transform calculation for both Lemma 5 and Lemma 6, stating only that the result follows from applying the identity ∫ dk/(2π) e^{ikx}=δ(x) multiple times. These lemmas are presented as corrections of [21] and are subsequently used for counterexamples and edge-case variance computations, so the omitted derivation is load-bearing for the closed-form contribution. The authors should include the full final calculation, or at least a detailed and complete appendix derivation, so that the claimed corrected formulas can be independently verified.
minor comments (5)
- [Lemma 5] The notation 'cosh(θ)' and 'cosh+1(θ)' should be written as cos^h(θ) and cos^{h+1}(θ); in standard notation cosh denotes the hyperbolic cosine, which is clearly not intended here.
- [Section VI] The condition '|α| = |β|2 = 1/2' should read '|α|² = |β|² = 1/2'.
- [Figures 1 and 2] The legend label 'θ = π 2' should be 'θ = π/2'.
- [References] Reference [20] is dated 1995, but the cited paper by Gillis appeared in 1955.
- [Lemma 6] In the statement of Lemma 6, the component β_j(n) is written as β_j(t) in the displayed formula; the argument should be n consistently.
Circularity Check
No circularity: the classification theorems are derived from independent external results by Konno, and the amplitude formulas follow a direct Fourier/Fibonacci-Horner calculation rather than assuming the target result.
full rationale
The paper's central claims are explicitly built on external prior work, not on its own conclusions: the authors state in Section I that they 'primarily build on Konno's work,' and Theorems 1-4 use Konno's independently established Theorem 1, Theorem 6, and Lemma 3 as the input facts. The classification arguments then solve algebraic constraints on the parameters |α|^2, |β|^2, |a|^2, |b|^2, and κ that Konno's Lemma 3 identifies as the only distribution-relevant data; this is a derivation from an external result, not a self-referential reduction. Lemma 5 is obtained by Fourier transform and Fibonacci-Horner decomposition, and the paper explicitly corrects rather than assumes the earlier result of Jayakody and Cohen; the sentence 'The outcome then indeed establishes Lemma 5' follows an omitted final integral calculation, which is a proof gap but not a circular use of the claimed formula. No parameters are fitted to the target distributions, and no uniqueness theorem from the present authors is imported to force a choice. The reader's skeptic concern about Theorem 3 - that replacing θ by ϱ(θ) may flip the sign of cos(θ)sin(θ) and that the prescribed transformation of ξ need not restore the interference term κ - is a potential mathematical correctness flaw in the surjectivity proof, not an instance of circularity under the hard rules. Therefore no circular step is identified.
Assumptions & free parameters
assumptions (4)
- domain assumption Konno's Lemma 3 gives the full spatial distribution after n steps as a function only of |α|², |β|², |a|², |b|², and aαbβ + conjugate.
- domain assumption Konno's Theorem 1 gives the limiting density f_C(x) for non-trivial coins as stated in [22].
- domain assumption The walk starts in a product state |0>⊗|γ> and evolves by the unitary T(1⊗C); global phases are irrelevant to probabilities.
- standard math Cayley-Hamilton theorem and the Fibonacci-Horner decomposition for 2x2 matrix powers.
Cite this review
Pith. "Pith review of Classification of coined quantum walks on the line and comparison to correlated classical random walks." pith.science (2026). https://pith.science/paper/T2HMUAEA
@misc{pith2026250723524,
author = {Pith},
title = {Pith review of: Classification of coined quantum walks on the line and comparison to correlated classical random walks},
year = {2026},
howpublished = {\url{https://pith.science/paper/T2HMUAEA}},
note = {Machine review of arXiv:2507.23524}
}
read the original abstract
We present a comprehensive classification of one-dimensional coined quantum walks on the infinite line, focusing on the spatial probability distributions they induce. Building on prior results, we identify all initial coin states that lead to symmetric quantum walks for arbitrary coins, and provide a bijective parametrisation of all symmetric quantum walks modulo distributional equivalence. Extending beyond the symmetric case, we also give a surjective parametrisation of all coined quantum walks under the same equivalence relation and a bijective parametrisation modulo equivalence of the walks' limiting distributions. Furthermore, we derive corrected closed-form expressions for the walk amplitudes, resolving inaccuracies in previous literature, and generalise the approach to the correlated classical random walk. This unified framework enables a direct comparison between quantum and classical dynamics. Additionally, we discuss the asymptotic scaling of variances for both models, identifying quadratic spreading as a hallmark of non-trivial quantum walks and contrasting it with the linear behaviour of classical walks, except at the extremal points of maximal correlation. Finally, we compare the limiting distributions arising from quantum walks with the ones in the classical case.
Figures
Reference graph
Works this paper leans on
-
[21]
D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in Proceedings of the Thirty-Third Annual ACM Sympo- sium on Theory of Computing , STOC ’01 (Association for Computing Machinery, New York, NY, USA, 2001) p. 50–59
work page 2001
-
[1]
Classification Our main three theorems can be compactly proven with the aid of Konno’s previous work [22]. Therein, Konno derives closed-form expressions for the spatial probability distributions after each application of the walk operator, utilising the path integral approach pio- neered in [16] for the Hadamard walk. Konno uses those expressions to dete...
-
[2]
Closed-form expressions We follow the established framework of Fourier anal- ysis for the quantum walk as an alternative to the path integral approach. This technique has first been applied by Nayak and Vishwanath [23] to the Hadamard walk and is also suitable for more general quantum walks (see also [16]). The Fourier analysis allows us to retrace the n-...
-
[3]
Shenvi, J
N. Shenvi, J. Kempe, and K. B. Whaley, Phys. Rev. A 67, 052307 (2003)
2003
-
[4]
The dynamics are, of course, trivial and we obtain |ψn⟩ = 1√ 2 (i |−n⟩ ⊗ |↓⟩+ |n⟩ ⊗ |↑⟩) with induced spatial probability distributions p(C,|γ⟩)(j, n) = ( δj,−n + δj,n)/2. These distribu- tions clearly have a variance ofσ2 = n2, that is they also follow the asymptotic quadratic trend of the non-trivial quantum walks. Second, let θ = π/2. Again by Theorem ...
-
[5]
Either with the aid of Lemma 5 or by direct calculation, one verifies that |ψn⟩ = 1√ 2 ( |0⟩ ⊗(|↑⟩ + i |↓⟩), if n even, (|−1⟩ ⊗ |↓⟩+ i |1⟩ ⊗ |↑⟩), if n odd, resulting in spatial probability distributions of the form p(C,|γ⟩)(j, n) = ( δj,0, if n even, δ|j|,1/2, if n odd. The variances of these very simple probability distribu- tions oscillate between0 (fo...
-
[6]
Kempe, Contemp
J. Kempe, Contemp. Phys.44, 307 (2003)
2003
-
[7]
Schöning, in40th Annual Symposium on Foundations of Computer Science (Cat
U. Schöning, in40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) (1999) pp. 410–414
work page 1999
Show all 29 references
-
[8]
Cedzich, T
C. Cedzich, T. Geib, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner, and R. F. Werner, Ann. Henri Poincaré19, 325 (2018)
2018
-
[9]
Ambainis, Int
A. Ambainis, Int. J. Quantum Inf.01, 507 (2003)
2003
-
[10]
Magniez, A
F. Magniez, A. Nayak, J. Roland, and M. Santha, in Proceedings of the Thirty-Ninth Annual ACM Sympo- sium on Theory of Computing , STOC ’07 (Association for Computing Machinery, New York, NY, USA, 2007) p. 575–584
2007
-
[11]
Kitagawa, M
T. Kitagawa, M. S. Rudner, E. Berg, and E. Demler, Phys. Rev. A82, 033429 (2010)
2010
-
[12]
J. K. Asbóth, B. Tarasinski, and P. Delplace, Phys. Rev. B 90, 125143 (2014)
2014
-
[13]
Farhi and S
E. Farhi and S. Gutmann, Phys. Rev. A58, 915 (1998)
1998
-
[14]
Štefaňák, T
M. Štefaňák, T. Kiss, and I. Jex, Phys. Rev. A78, 032306 (2008)
2008
-
[15]
Mohseni, P
M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru- Guzik, J. Chem. Phys.129, 174106 (2008)
2008
-
[16]
A. C. Oliveira, R. Portugal, and R. Donangelo, Phys. Rev. A74, 012312 (2006)
2006
-
[17]
C. M. Chandrashekar, Discrete-Time Quantum Walk - Dynamics and Applications (2010), arXiv:1001.5326 [quant-ph]
2010 arXiv
-
[18]
Konno, Quantum Inf
N. Konno, Quantum Inf. Process.1, 345 (2002)
2002
-
[19]
Aharonov, L
Y. Aharonov, L. Davidovich, and N. Zagury, Phys. Rev. A 48, 1687 (1993)
1993
-
[20]
who derived an alternative, more compact expres- sion. Lemma 6. Let q0 = ( α, β) be an arbitrary probability distribution over {↑, ↓}, i.e. 0 ≤ α, β≤ 1 with α = 1 − β. Let δ ∈ [−1, 1] parametrise the velocity transition matrix (5) and let rn be the probability distribution ove...
-
[22]
Ambainis, E
A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing , STOC ’01 (Association for Computing Machinery, New York, NY, USA, 2001) p. 37–49
2001
-
[23]
Feller, An introduction to probability theory and its applications, Vol
W. Feller, An introduction to probability theory and its applications, Vol. 2 (John Wiley & Sons, 1991)
1991
-
[24]
Goldstein, Q
S. Goldstein, Q. J. Mech. Appl. Math.4, 129 (1951)
1951
-
[25]
Gillis, Math
J. Gillis, Math. Proc. Camb. Philos. Soc.51, 639 (1995)
1995
-
[26]
M. N. Jayakody and E. Cohen, Eur. Phys. J. D77, 193 (2023)
2023
-
[27]
Konno, J
N. Konno, J. Math. Soc. Japan57, 1179 (2005)
2005
-
[28]
Nayak and A
A. Nayak and A. Vishwanath, Quantum Walk on the Line (2000), arXiv:quant-ph/0010117
2000 arXiv
-
[29]
Taher, M
R. Taher, M. Mouline, and M. Rachidi, Electron. J. Lin- ear Algebra15 (2006)
2006
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.