2025-11-19T10:13:14.160303

On the Optimal Rate of Convergence for Translation-Invariant 1D Quantum Walks

Hinrichs, Mittenbühler
We study the convergence rate of translation-invariant discrete-time quantum dynamics on a one-dimensional lattice. We prove that the cumulative distributions function of the ballistically scaled position $\mathbb X(n)/{n}$ after $n$ steps converges at a rate of $n^{-1/3}$ in the Lévy metric as $n\to\infty$. In the special case of step-coin quantum walks with two-dimensional coin space, we recover the same convergence rate for the supremum distance and prove optimality.
academic

On the Optimal Rate of Convergence for Translation-Invariant 1D Quantum Walks

Basic Information

  • Paper ID: 2511.13409
  • Title: On the Optimal Rate of Convergence for Translation-Invariant 1D Quantum Walks
  • Authors: Benjamin Hinrichs, Pascal Mittenbühler
  • Classification: math-ph (Mathematical Physics), math.MP, quant-ph (Quantum Physics)
  • Publication Date: November 17, 2025 (arXiv preprint)
  • Institution: Universität Paderborn
  • Paper Link: https://arxiv.org/abs/2511.13409

Abstract

This paper investigates the convergence rate of translation-invariant discrete-time quantum dynamics on one-dimensional lattices. The authors prove that after n steps, the cumulative distribution function of the ballistically scaled position X(n)/n converges at a rate of n^(-1/3) in the Lévy metric. For the special case of step-coin quantum walks with two-dimensional coin space, the authors recover the same convergence rate in the supremum distance (Kolmogorov metric) and establish its optimality.

Research Background and Motivation

Research Problem

This paper aims to establish a Berry-Esseen type theorem for quantum walks, i.e., a quantized central limit theorem error bound. Specifically, it studies the precise rate at which the position distribution of one-dimensional quantum walks converges to the asymptotic distribution.

Problem Significance

  1. Theoretical Importance: Quantum walks are quantum analogues of classical random walks and have received widespread attention since their introduction. While various weak convergence results (analogous to the central limit theorem) exist, global error bounds have been lacking, contrasting sharply with the celebrated Berry-Esseen theorem in the classical setting.
  2. Application Value: Quantum walks have important applications in quantum computing (e.g., search algorithms) and experimental implementations. Precise convergence rates are crucial for estimating computational errors.
  3. Phenomenological Difference: Classical random walks exhibit convergence rate n^(-1/2), while this paper finds quantum walks converge at rate n^(-1/3), which is slower. This is caused by the special behavior of the ballistic propagation wavefront region.

Limitations of Existing Methods

  1. Lack of Global Error Bounds: Except for recent work CJWW25 (proving exponential decay outside the convex hull of the propagation region), global error bounds for quantum walks have not been studied.
  2. Insufficient Local Estimates: ST12 only provides local error bounds outside a thin layer near the wavefront.
  3. Metric Selection: Since the cumulative distribution function may not be differentiable everywhere, the supremum metric is not entirely appropriate; more suitable metrics (such as the Lévy metric) are needed.

Core Contributions

  1. General Upper Bound in Lévy Metric (Theorem 2.1): For general translation-invariant one-dimensional lattice quantum dynamics, under mild assumptions, the cumulative distribution function converges at rate n^(-1/3) in the Lévy metric.
  2. Optimality for Step-Coin Quantum Walks (Theorem 2.2): For step-coin quantum walks with two-dimensional coin space:
    • Upper bound of n^(-1/3) in supremum distance (Kolmogorov metric)
    • Optimality of this rate (matching lower bound)
  3. Generalized Esseen-Zolotarev Type Inequality (Theorem 3.1): A new inequality is established connecting the Lévy metric with characteristic functions, serving as a key technical tool for proving the main results.
  4. Fine Analysis of Wavefront Region: Through careful analysis of transition probabilities in the wavefront region (boundary of the propagation region), combined with asymptotic expansions of Airy functions and oscillatory sum estimates, the optimal convergence rate is obtained.

Detailed Methodology

Task Definition

Input:

  • Initial density matrix ρ (quantum state)
  • Number of time steps n
  • Translation-invariant time evolution operator W

Output:

  • Position cumulative distribution function F^ρ_(x) = tr(ρ1_{(-∞,x]}(X_n)), where X_n = W^(-n)XW^n/n

Objective: Quantify the distance between F^ρ_ and the asymptotic distribution F^ρ_V, where V is the velocity operator.

Overall Architecture

The proof consists of two main parts:

Part One: General Theory (Theorem 2.1)

Establishes convergence rate in Lévy metric through a generalized Esseen inequality.

Key Steps:

  1. Generalized Zolotarev Inequality (Theorem 3.1): For cumulative distribution functions F, G and arbitrary ε∈(0,1], L(F,G)≤ε+ε−2Cmax⁡(sup⁡λ∈(0,1]∣F^(λ)−G^(λ)λ∣,sup⁡λ∈(1,∞)∣F^(λ)−G^(λ)λ2∣)\mathcal{L}(F,G) \leq \varepsilon + \varepsilon^{-2}C\max\left(\sup_{\lambda\in(0,1]}\left|\frac{\hat{F}(\lambda)-\hat{G}(\lambda)}{\lambda}\right|, \sup_{\lambda\in(1,\infty)}\left|\frac{\hat{F}(\lambda)-\hat{G}(\lambda)}{\lambda^2}\right|\right)
  2. Characteristic Function Estimates (Theorem 3.3): For all n∈ℕ and λ∈ℝ, ∣F^Xnρ(λn)−F^Vρ(λ)∣≤∣λ∣2nsup⁡k,p∣ωk′′(p)∣+∣λ∣n(tr(∣X∣ρ)+∑ksup⁡p∥Πk′(p)∥)\left|\hat{F}^{\rho}_{X_n}\left(\frac{\lambda}{n}\right) - \hat{F}^{\rho}_V(\lambda)\right| \leq \frac{|\lambda|^2}{n}\sup_{k,p}|\omega_k''(p)| + \frac{|\lambda|}{n}\left(\text{tr}(|X|\rho) + \sum_k\sup_p\|\Pi_k'(p)\|\right)
  3. Optimal Choice: Selecting ε = n^(-1/3) yields L(F^ρ_, F^ρ_V) ≤ Cn^(-1/3).

Part Two: Precise Analysis for Step-Coin Quantum Walks (Theorem 2.2)

Region Decomposition Strategy: The position space is divided into three regions for separate analysis:

  1. Smooth Interior Region |x| < |a| - r
  2. Wavefront Region |x| ≈ |a|
  3. Outside Propagation Region |x| > |a|

Technical Innovations

1. Smoothing Technique (Lemma 3.2)

Smoothing via convolution with triangular density:

\left(\frac{2n}{\varepsilon}\right)^2\left(\frac{\varepsilon}{2n}-|x|\right), & |x| \geq \frac{\varepsilon}{2n} \\ 0, & \text{else} \end{cases}$$ Characteristic function: $$\hat{\Theta}_{\varepsilon}^n(\lambda) = \left(\frac{\sin(\varepsilon\lambda/2n)}{\varepsilon\lambda/2n}\right)^n$$ Choosing n=3 achieves optimal balance. #### 2. Stationary Phase Analysis in Wavefront Region Using results from [ST12], transition probabilities can be expressed as: $$p_n(\phi; \pm\lfloor n|a|\rfloor \mp k) = (1+(-1)^{n+k})\left(n^{-2/3}s^2\left(\frac{k}{n}\right)\text{Ai}^2\left(\pm n^{2/3}p\left(\frac{k}{n}\right)\right) + n^{-4/3}q^2\left(\frac{k}{n}\right)\text{Ai}'^2\left(\pm n^{2/3}p\left(\frac{k}{n}\right)\right)\right) + O(n^{-4/3})$$ where Ai is the Airy function and p, q, s are smooth functions. #### 3. Oscillatory Sum Estimates (Appendix A) Key Lemma (Proposition A.3): For p∈C² satisfying p(0)=0, p'(0)=α>0, $$\left|\sum_{k=\lfloor n^{1/3}\rfloor}^{\lfloor rn\rfloor}\sin\left(\frac{4}{3}np\left(\frac{k}{n}\right)^{3/2}\right)\right| \leq Cn^{1/2}$$ This is proved by decomposing the sum into k∈[n^(2/3), rn] (applying Lemma A.1) and k∈[n^(1/3), n^(2/3)] (applying Lemma A.2). #### 4. Leading Term Extraction (Proposition 4.10) Decomposing transition probabilities as: $$p_n(\phi, -\lfloor n|a|\rfloor + k) = n^{-1}\sigma_{C,\phi}\left(\frac{k}{n}\right) + \text{OSC}_n\left(\frac{k}{n}\right)$$ where oscillatory terms satisfy: $$\sum_{k=\lfloor n^{1/3}\rfloor}^{\lfloor rn\rfloor}\text{OSC}_n\left(\frac{k}{n}\right) = O(n^{-1/3})$$ ### Mathematical Framework **Hilbert Space**: H = ℓ²(ℤ; K), where K is a local Hilbert space. **Translation Invariance**: Time step operator W commutes with right shift operator T; after Fourier transform: $$(FWF^*\psi)(p) = \hat{W}(p)\psi(p)$$ **Spectral Assumption**: $$\hat{W}(p) = \sum_{k\in I}e^{i\omega_k(p)}\Pi_k(p)$$ where ω_k∈C²(𝕋;ℝ), Π_k∈C¹(𝕋;B(H)). **Velocity Operator**: $$FVF^*(p) = \sum_{k\in I}\omega_k'(p)\Pi_k(p)$$ ## Experimental Setup ### Theoretical Verification Framework This is purely theoretical work with no numerical experiments. Verification is completed through rigorous mathematical proofs. ### Specific Setup for Step-Coin Quantum Walks **Coin Operator**: $$C = e^{i\theta}\begin{pmatrix} a & b \\ -b & a \end{pmatrix}, \quad |a|^2 + |b|^2 = 1$$ **Step Operator**: S(ψ₁⊕ψ₂) = Tψ₁⊕T^(-1)ψ₂ **Time Step Operator**: W = SC **Initial State**: ρ = |δ₀φ⟩⟨δ₀φ|, where φ∈ℂ² ### Asymptotic Distribution (Proposition 4.1) Density function: $$\sigma_{C,\phi}(x) = \begin{cases} \frac{|b|(1+\lambda_C(\phi)x)}{\pi(1-x^2)\sqrt{|a|^2-x^2}}, & |x| < |a| \\ 0, & \text{else} \end{cases}$$ where λ_C(φ) = |φ₂|² - |φ₁|² + |a|^(-2)(ab̄φ₁φ̄₂ + āb φ̄₁φ₂). ## Experimental Results ### Main Theoretical Results #### Theorem 2.1 (General Upper Bound) Under mild regularity assumptions (ω_k∈C², Π_k∈C¹), for any density matrix ρ satisfying tr(|X|ρ)<∞, there exists a constant C>0 such that: $$\mathcal{L}(F^{\rho}_{X_n}, F^{\rho}_V) \leq Cn^{-1/3}$$ #### Theorem 2.2 (Optimality) For step-coin quantum walks with two-dimensional coin space, assuming all elements of C are nonzero and initial state is a finite sum of orthogonal projections, there exist C₁, C₂>0 such that: $$C_1n^{-1/3} \leq \|F^{\rho}_{X_n} - F^{\rho}_V\|_{\infty} \leq C_2n^{-1/3}$$ ### Key Technical Results #### Lemma 4.7 (Lower Bound) There exists C>0 such that for all n∈ℕ: $$\min\{F_n(\phi; -n|a|), 1-F_n(\phi; n|a|)\} \geq Cn^{-1/3}$$ This directly gives the lower bound for supremum norm, since F^φ_V(-|a|) = 0. #### Lemma 4.9 (Upper Bound Outside Wavefront) $$F_n(\phi; -n|a| + n^{1/3}) = O(n^{-1/3}), \quad 1-F_n(\phi; n|a| - n^{1/3}) = O(n^{-1/3})$$ #### Proposition 4.11 (Upper Bound in Wavefront Region) There exist r>0 and C>0 such that for all r'≤r: $$|F_n(\phi; \pm n|a|\mp nr') - F^{\phi}_V(\pm|a|\mp r')| \leq Cn^{-1/3}$$ ### Comparison with Classical Case | Property | Classical Random Walk | Quantum Walk | |----------|----------------------|--------------| | Scaling | X_n/√n | X_n/n | | Convergence Rate | n^(-1/2) | n^(-1/3) | | Propagation | Diffusive | Ballistic | | Asymptotic Distribution | Gaussian | Non-Gaussian (with cusps) | ### Physical Interpretation (Remark 2.3) Reasons for slower convergence in quantum walks: 1. **Ballistic Wavefront**: Most information concentrates in the ballistically propagating wavefront region 2. **Non-smoothness**: F^ρ_V develops non-differentiable cusps at support boundaries ±|a| 3. **Boundary Dominance**: Approximation error is dominated by boundary behavior ## Related Work ### Central Limit Theorems for Quantum Walks - **Konno (2002, 2005)**: First weak limit theorems for quantum walks - **Grimmett, Janson, Scudo (2004)**: Weak convergence results - **Ahlbrecht et al. (2011)**: Asymptotic evolution of random-coin quantum walks - **Sunada & Tate (2012)**: Asymptotic behavior of 1D quantum walks, providing fine analysis of wavefront region - **Suzuki (2016), Wada (2020)**: Position-dependent and long-range quantum walks ### Error Bound Research - **Berry (1941), Esseen (1945)**: Classical Berry-Esseen theorem, n^(-1/2) convergence rate - **Fainleib (1968), Bentkus & Götze (1996)**: Improvements to Berry-Esseen theorem - **Zolotarev (1971)**: Lévy metric estimates - **Bobkov (2016)**: Survey on Fourier-Stieltjes transforms and distribution closeness - **Cedzich et al. (2025)**: Exponential tail estimates for quantum lattice dynamics ### Unique Contributions of This Paper 1. **First Global Error Bound**: Fills the gap in Berry-Esseen type theorems for quantum walks 2. **Optimal Rate**: Proves n^(-1/3) is tight 3. **New Technical Tools**: Generalized Esseen-Zolotarev inequality applicable to broader settings ## Conclusions and Discussion ### Main Conclusions 1. **General Result**: Translation-invariant one-dimensional quantum dynamics converges to asymptotic distribution at rate n^(-1/3) in Lévy metric. 2. **Optimality**: For step-coin quantum walks, n^(-1/3) is the optimal convergence rate in supremum distance (upper and lower bounds match). 3. **Quantum vs Classical**: Quantum walks (n^(-1/3)) converge slower than classical random walks (n^(-1/2)), which is an essential characteristic of ballistic propagation and wavefront effects. ### Limitations 1. **Lower Bound in Lévy Metric** (Remark 2.4): For step-coin quantum walks, only proved: $$n^{-2/3-\varepsilon} \lesssim \mathcal{L}(F^{\rho}_{X_n}, F^{\rho}_V) \lesssim n^{-1/3}$$ Matching lower bound requires finer analysis of the wavefront sector. 2. **Initial State Restrictions**: Theorem 2.2 requires initial state to be a finite sum of orthogonal projections and coin operator elements to be nonzero. 3. **Dimension Limitation**: Results apply only to one-dimensional systems. 4. **Translation Invariance**: Assumes time step operator is translation-invariant, excluding many physically relevant non-uniform systems. ### Future Directions 1. **Non-Translation-Invariant Walks**: Extension to non-uniform quantum walks, more common in physical applications. 2. **Higher-Dimensional Systems**: Study convergence rates for quantum walks on two-dimensional and higher-dimensional lattices. 3. **Lower Bounds in Lévy Metric**: Improve lower bounds in Theorem 2.1, proving optimality in Lévy metric. 4. **More General Initial States**: Relax restrictions on initial states, considering mixed states and more general density matrices. 5. **Computational Error Estimates**: Apply results to error analysis of quantum algorithms and experimental implementations of quantum computing. 6. **Nonlinear Effects**: Consider convergence properties of interacting quantum walks. ## In-Depth Evaluation ### Strengths #### 1. Important Theoretical Breakthrough - **Fills a Gap**: First global error bound for quantum walks, resolving a long-standing open problem - **Proves Optimality**: Not only provides upper bound but also proves lower bound, establishing n^(-1/3) as tight - **Reveals Essential Difference**: The difference in quantum vs classical convergence rates (n^(-1/3) vs n^(-1/2)) reflects deep physical properties of quantum systems #### 2. Technical Innovation - **Generalized Esseen Inequality**: Theorem 3.1 is an important generalization of classical results, applicable to non-differentiable cumulative distribution functions - **Region Decomposition Strategy**: Cleverly decomposes problem into smooth and wavefront regions, applying different techniques appropriately - **Oscillatory Sum Estimates**: Appendix A's oscillatory sum estimation technique has independent value and applicability to other problems #### 3. Rigorous Mathematical Arguments - **Complete Proof Chain**: From general theory to specific models, logic is clear and steps are complete - **Detailed Error Analysis**: Precise order estimates for each error term - **Airy Function Asymptotics**: Fully utilizes special function theory combined with stationary phase method #### 4. Clear Exposition - **Reasonable Structure**: Presents general results first, then delves into specific models - **Physical Intuition**: Remark 2.3 excellently explains why quantum walks converge slower - **Technical Details**: Appendix provides complete technical proofs without affecting main text readability ### Weaknesses #### 1. Completeness of Results - **Lower Bound in Lévy Metric**: Theorem 2.1 lacks matching lower bound; optimality proven only in special cases - **Gap**: The gap between n^(-2/3-ε) and n^(-1/3) noted in Remark 2.4 needs to be filled #### 2. Scope of Applicability - **Restrictive Assumptions**: - Translation invariance excludes many physically relevant models (disordered systems, quasiperiodic systems) - One-dimensional restriction makes direct application to higher-dimensional quantum walks difficult - Initial state restrictions (finite sum of orthogonal projections) are quite strong #### 3. Practical Considerations - **Constant Dependence**: While O(n^(-1/3)) is proved, constant C may be large; practical applications require more precise estimates - **Numerical Verification**: Lacks numerical experiments verifying theoretical predictions, especially for finite n behavior #### 4. Technical Limitations - **Complex Wavefront Analysis**: Proof of Proposition 4.10 relies on deep results from [ST12], high technical threshold - **Airy Function Dependence**: Analysis highly depends on special properties of Airy functions; generalization to other models may be difficult ### Impact #### 1. Theoretical Contribution - **Foundational Result**: Establishes important foundation for quantum walk theory, analogous to Berry-Esseen theorem's role in classical probability - **Methodology**: Generalized Esseen inequality and region decomposition strategy may inspire research on other quantum systems - **Cross-Disciplinary Impact**: Connects quantum information, mathematical physics, and probability theory #### 2. Application Value - **Quantum Algorithms**: Provides theoretical basis for error analysis of quantum search algorithms, etc. - **Experimental Guidance**: Helps estimate number of steps needed for experimental quantum walk implementations - **Computational Complexity**: Provides insight into understanding sources of quantum computational advantage #### 3. Reproducibility - **Theoretically Verifiable**: Proofs are complete and rigorous, verifiable by peers - **Technically Traceable**: Sufficient citations and explanations of techniques used, facilitating understanding and generalization - **Open Problems**: Clearly identifies unresolved issues (e.g., Lévy metric lower bounds), guiding future research ### Applicable Scenarios #### 1. Theoretical Research - Asymptotic theory of quantum walks - Quantum central limit theorems - Quantum information propagation theory - Non-equilibrium quantum statistical mechanics #### 2. Quantum Algorithm Design - Convergence analysis of quantum search algorithms - Graph algorithms based on quantum walks - Quantum sampling algorithms #### 3. Experimental Physics - Optical quantum walk experiments - Quantum walks in cold atom systems - Topological quantum walks #### 4. Numerical Simulation - Error estimation for quantum dynamics simulations - Accuracy assessment of finite-time approximations ## In-Depth Analysis of Technical Highlights ### 1. Choice of Lévy Metric Advantages of Lévy metric over supremum metric: - **Adaptability**: More friendly to non-differentiable cumulative distribution functions - **Weakened Conditions**: Does not require pointwise continuity - **Equivalence to Weak Convergence**: Lévy metric quantifies weak convergence Definition (Equation 2.4): $$\mathcal{L}(F,G) := \sup_{x\in\mathbb{R}}\inf\{\varepsilon>0: F(x-\varepsilon)-\varepsilon \leq G(x) \leq F(x+\varepsilon)+\varepsilon\}$$ Key Property (Equation 2.5): $$\mathcal{L}(F,G) \leq \|F-G\|_{\infty}$$ ### 2. Cleverness of Smoothing Lemma Lemma 3.2 uses convolution smoothing: $$\mathcal{L}(F,G) - \mathcal{L}(F*H, G*H) \leq \max\{\varepsilon, 1-H(\varepsilon/2)+H(-\varepsilon/2)\}$$ Choosing n=3 triangular density convolution achieves balance: - Sufficient smoothness (enabling Fourier inversion) - Controlled support (making error terms manageable) - Computable characteristic function ### 3. Physical Picture of Wavefront Region At x≈±|a|: - **Density Function Singularity**: σ_{C,φ}(x)∼(|a|²-x²)^(-1/2) diverges as x→±|a| - **Airy Function Appearance**: Transition probabilities involve Ai(±n^(2/3)p(k/n)), reflecting oscillatory behavior - **Scale Separation**: - Macroscopic scale: O(n) (total steps) - Mesoscopic scale: O(n^(2/3)) (wavefront width) - Microscopic scale: O(n^(1/3)) (wavefront internal structure) ### 4. Elegant Treatment of Oscillatory Sums Proof of Proposition A.3 demonstrates harmonic analysis techniques: - **Region I** (k∈[n^(2/3), rn]): Monotonicity + Lemma A.1 → O(n^(1/3)) - **Region II** (k∈[n^(1/3), n^(2/3)]): Second derivative control + Lemma A.2 → O(n^(1/2)) - **Combination**: O(n^(1/3)) + O(n^(1/2)) = O(n^(1/3)) This region decomposition reflects how oscillation frequency varies with k. ## Open Problems and Research Perspectives ### Short-Term Tractable Problems 1. **Lévy Metric Lower Bound**: Using techniques similar to Proposition 4.10, may prove L(F_{X_n}, F_V) ≥ Cn^(-1/3) 2. **Numerical Verification**: Implement quantum walk simulations to verify theoretical predictions of constants 3. **More General Coins**: Generalize to higher-dimensional coin space K=ℂ^d ### Medium-Term Challenging Problems 1. **Two-Dimensional Quantum Walks**: Expected convergence rate may differ; requires new techniques 2. **Weakly Disordered Systems**: Study how small perturbations affect convergence rate 3. **Interacting Quantum Walks**: Effects of nonlinear interactions ### Long-Term Open Problems 1. **Non-Translation-Invariant Systems**: Quasiperiodic and random potential cases 2. **Topological Quantum Walks**: How topological invariants affect convergence 3. **Continuous-Time Limit**: Relationship with continuous-time quantum walks ## Key References 1. **[ST12]** T. Sunada and T. Tate. Asymptotic behavior of quantum walks on the line. J. Funct. Anal., 2012. - Provides precise asymptotic expansion of transition probabilities in wavefront region 2. **[Kon05]** N. Konno. A new type of limit theorems for the one-dimensional quantum random walk. J. Math. Soc. Japan, 2005. - Gives explicit expressions for asymptotic distributions 3. **[Zol71]** V. M. Zolotarev. Estimates of the difference between distributions in the Lévy metric. 1971. - Inspiration for generalized Esseen inequality in this paper 4. **[CJWW25]** C. Cedzich et al. Exponential Tail Estimates for Quantum Lattice Dynamics. To appear in Ann. Henri Poincaré, 2025. - Recent work on error bounds for quantum walks 5. **[Ber41, Ess45]** A. C. Berry (1941), C.-G. Esseen (1945). Classical Berry-Esseen theorem - Classical prototype for quantum analogue in this paper --- **Summary**: This is a high-quality mathematical physics paper solving an important problem in quantum walk theory, establishing a Berry-Esseen type theorem and proving the optimal convergence rate n^(-1/3). Technically rigorous and innovative, theoretically profound, providing foundational tools for error analysis in quantum information and quantum computing. Main limitations are scope (one-dimensional, translation-invariant) and completeness of certain results (Lévy metric lower bounds). Future work can extend in multiple directions with broad research prospects.