alphaFeedback

WorksMathematics

Growing-time trace fluctuations and self-averaging form factors of Grover walks on random lifts

AI contributions
Not recorded for this paper
View details

Abstract

We prove a functional central limit theorem for trace statistics of Grover walks on random NN-lifts of a fixed finite connected simple dd-regular graph, d≥3d\geq3. All observations are computed from the same random lift. The squared centred traces, divided by their observation times, have averages converging in probability to a degree-dependent constant. Their partial sums, centred at this constant and divided by the square root of the window length, converge to Brownian motion. For a window of length MM beginning at t≥1t\geq1, it suffices that M→∞M\to\infty and R4(d−1)R/N→0R^4(d-1)^R/N\to0, where R=t+MR=t+M. The initial time may remain fixed, with no further restriction on M/tM/t. Convergence holds jointly with fixed low-degree polynomial trace statistics; their limiting vector is independent of the Brownian motion. For non-bipartite bases, we also identify Gaussian trace limits at fixed time offsets. Under common initial-time normalisation, subtracting a deterministic growth profile gives an explicit Brownian time change when M/tM/t has a finite limit. Bipartite bases retain the same averaged constant and have twice the Brownian variance rate. The proof combines a growing-dimensional Poisson approximation, a uniform bilinear Chebyshev-energy estimate, a time-decaying Poisson–Gaussian coupling, and a Gaussian quadratic-array theorem. Separate moment estimates give expectation-centred versions under an additional sufficient condition.

Introduction and main results

Can averaging a dependent sequence of trace statistics on one random graph produce a law of large numbers and a functional central limit theorem? We study this question for Grover walks on random lifts of a fixed regular base. An NN-lift replaces each base vertex by a fibre of NN copies and joins adjacent fibres by independent uniformly random perfect matchings. The graph is sampled once; every observation is then computed from the same graph by varying the power of its Grover operator. Thus increasing the observation window does not provide independent samples of graphs.

The trace of a power sums contributions from all eigenphases. The expectation of its squared mean-centred trace is the connected spectral form factor. For a non-bipartite base, the squared centred trace divided by its observation time has a nondegenerate limit at a single growing time. Averaging the observation-time-normalised squared traces instead recovers an explicit deterministic value. This question of temporal self-averaging has also been studied for quantum graphs and random-matrix ensembles [4, 6, 12, 15, 22, 31].

Our main result describes the cumulative averaging error by a Brownian limit while the number of sheets and the observation window grow simultaneously. The initial time may remain fixed: within the stated logarithmic cutoff range, the window need not be short relative to its initial time. The limit is joint with fixed low-degree polynomial trace statistics and is independent of their limiting Poisson structure. Bipartite and non-bipartite bases have the same averaged limit, but the Brownian variance rate doubles in the bipartite case. Dividing all observations by a common initial time instead leaves a deterministic growth profile and, on proportional windows, a nonconstant variance rate.

Theorem 1.1 gives the functional limit and Theorem 1.2 the law of large numbers. Corollaries 1.3 and 1.4 describe the common-time normalisation. The subsequent fixed-offset theorem identifies the fluctuations that remain at a single time. Both exact mean centring and a centring computable from the base and the number of sheets are available. All trace observables use the full Grover spectrum.

Main contributions. The proof requires uniform estimates because both the number of cycle lengths and the number of observations increase. A fixed-dimensional cycle limit or a stationary Gaussian approximation at fixed time offsets alone would not control the cumulative error. Theorem 4.1 provides a total-variation error of order R4qR/NR^4q^R/N, where q=d−1q=d-1, for the entire cycle-count vector up to the cutoff RR. Theorem 6.4 evaluates the bilinear Chebyshev energy with a bounded remainder at all positive observation times. Proposition 10.1 retains time decay in a simultaneous Poisson–Gaussian coupling. Theorem 10.2 then gives an invariance principle for Gaussian quadratic arrays with a product bound on the covariance error, rather than exact stationarity. These estimates allow the initial observations to have nonvanishing covariance errors while their cumulative contribution becomes negligible. The exact trace identity in Section 2 and separate finite-lift moment bounds connect these arguments to the stated trace statistics.

Model and observables

Let B=(V,E)B=(V,E) be a fixed finite connected simple dd-regular graph, where d≥3d \ge3. Set

q=d−1,n0=∣V(B)∣,m0=∣E(B)∣,rd=2qd,αd=arccos⁡rd.q=d-1,\qquad n_0=\lvert V(B)\rvert,\qquad m_0=\lvert E(B)\rvert,\qquad r_d=\frac{2\sqrt{q}}{d},\qquad\alpha_d=\arccos r_d.

Thus 0<rd<10<r_d<1 and 0<αd<π/20<\alpha_d<\pi/2. Choose an orientation for each base edge and assign independent uniform permutations of [N]={1,…,N}[N]=\{1,\ldots,N\} to the oriented edges. Traversal in the reverse direction uses the inverse permutation. For an oriented edge e=(u,v)e=(u,v) with permutation σe\sigma_e, join (u,a)(u,a) to (v,σe(a))(v,\sigma_e(a)) for every a∈[N]a\in[N]. This defines the random NN-lift GNG_N; we do not condition on connectedness. We write SN\mathfrak{S}_N for the symmetric group on [N][N]. Constants CBC_B may change from line to line and depend only on the fixed base, unless further dependence is indicated by subscripts.

For a finite simple dd-regular graph GG, let AGA_G be its adjacency matrix and D(G)D(G) its directed-edge set. Write o(e),t(e)o(e),t(e) for the initial and terminal vertices of a directed edge, and eˉ\bar e for its reversal. We use InI_n for the n×nn\times n identity matrix and 1\mathbf{1} for the all-ones column vector of the dimension indicated by the surrounding formula; MTM^{\mathsf T} and M∗M^* denote transpose and conjugate transpose. The untwisted Grover matrix is

(UG)e,f=2d1{t(f)=o(e)}−1{e=fˉ}.(U_G)_{e,f}=\frac{2}{d}\mathbf{1}_{\{t(f)=o(e)\}}-\mathbf{1}_{\{e=\bar f\}}.

It is real and orthogonal: it is the product of the arc-reversal involution and the direct sum of the local reflections (2/d)11∗−Id(2/d)\mathbf{1}\mathbf{1}^{*}-I_d, each acting on the dd arcs terminating at a vertex. We use the centred real trace

AN(s)=Tr⁡UGNs−E[Tr⁡UGNs],s∈Z≥0,\mathcal{A}_N(s)=\operatorname{Tr}U_{G_N}^{s}-\mathbb{E}[\operatorname{Tr}U_{G_N}^{s}],\qquad s\in\mathbb{Z}_{\geq0},

and the connected form factor with no matrix-dimension normalisation,

FNc(s)=E[∣AN(s)∣2]=E[∣Tr⁡UGNs∣2]−∣E[Tr⁡UGNs]∣2.\mathcal{F}^{\mathrm{c}}_N(s)=\mathbb{E}[|\mathcal{A}_N(s)|^2]=\mathbb{E}[|\operatorname{Tr}U_{G_N}^{s}|^2]-|\mathbb{E}[\operatorname{Tr}U_{G_N}^{s}]|^2.

The symbols P\mathbb{P} and E\mathbb{E} refer to the probability law or coupling under consideration. For quantities defined from GNG_N, expectations are over the random covering permutations. The auxiliary Poisson and Gaussian laws are specified when they are introduced. Throughout, the full Grover spectrum is retained.

For any graph GG, let HGH_G denote its directed-edge non-backtracking matrix. For the base,

(HB)e,f=1{t(e)=o(f), f≠eˉ}.(H_B)_{e,f}=\mathbf{1}\{t(e)=o(f),\ f\ne\bar{e}\}.

The trace Tr⁡HGk\operatorname{Tr}H_G^k counts rooted, oriented cyclically non-backtracking closed walks: the non-backtracking condition is imposed also on the transition from the last edge to the first. A matrix is primitive if all entries of some positive integer power are positive. Under our standing regularity assumptions, HBH_B is primitive exactly when BB is non-bipartite; see Lemma 7.1. The time-averaging results below cover both bipartite and non-bipartite bases. Define

Γd(h)=2π∫αdπ−αdcos⁡(hθ) dθ,h∈Z.(1)\Gamma_d(h)=\frac{2}{\pi}\int_{\alpha_d}^{\pi-\alpha_d}\cos(h\theta)\,\mathrm{d}\theta,\qquad h\in\mathbb{Z}. \tag*{(1)}

The variance coefficient and the period are

cd=Γd(0)=4πarcsin⁡(2d−1d),pB={1,B is not bipartite,2,B is bipartite.c_d=\Gamma_d(0)=\frac{4}{\pi}\arcsin\left(\frac{2\sqrt{d-1}}{d}\right),\qquad p_B=\begin{cases} 1,& B\text{ is not bipartite},\\ 2,& B\text{ is bipartite}. \end{cases}

The set Id=[αd,π−αd]∪[−π+αd,−αd]I_d=[\alpha_d,\pi-\alpha_d]\cup[-\pi+\alpha_d,-\alpha_d] is the limiting dispersive Grover band, and Γd\Gamma_d is the Fourier transform of π−11Id\pi^{-1}\mathbf{1}_{I_d}. Hence cd=∣Id∣/π=2∣Id∣/(2π)c_d=|I_d|/\pi=2|I_d|/(2\pi): it is the orthogonal-class ramp slope 22 multiplied by the fraction of the quasi-energy circle occupied by the band. By Lemma 7.1, pBp_B is the period of HBH_B. For a cutoff RR, write

τN,R=R4qR/N,δN,R=R5qR/N.\tau_{N,R}=R^4q^R/N,\qquad\delta_{N,R}=R^5q^R/N.

The quantity τN,R\tau_{N,R} controls the cycle approximation in total variation; δN,R\delta_{N,R} controls covariance errors. The fixed polynomial trace statistics YN,kY_{N,k} and their limits YkY_k are defined in § 2. We use WW for standard Brownian motion. Probability metrics and path-space conventions are specified at the end of this section.

Time averaging on one lift

We distinguish two choices of centring and two choices of time normalisation. Set

AN0(s)=AN(s),AN∗(s)=Tr⁡UGNs−mN(s),\mathcal{A}_N^0(s)=\mathcal{A}_N(s),\qquad \mathcal{A}_N^*(s)=\operatorname{Tr}U_{G_N}^{s}-m_N(s),

where mN(s)m_N(s) is the explicit finite sum defined in § 9.1. The superscripts 00 and ∗* distinguish exact mean centring and this explicit centring. The superscripts 00 and ∗* are labels, not powers or adjoints. For ⋆∈{0,∗}\star\in\{0,*\}, define

F^N,t,M♮,⋆=1M∑h=0M−1AN⋆(t+h)2t+h,F^N,t,M⋆=1Mt∑h=0M−1AN⋆(t+h)2.\widehat{\mathcal{F}}_{N,t,M}^{\natural,\star} =\frac{1}{M}\sum_{h=0}^{M-1}\frac{\mathcal{A}_N^\star(t+h)^2}{t+h}, \qquad \widehat{\mathcal{F}}_{N,t,M}^{\star} =\frac{1}{Mt}\sum_{h=0}^{M-1}\mathcal{A}_N^\star(t+h)^2.

Every summand is evaluated on the same random lift. The symbol ♮ means that each squared trace is divided by its own observation time. The cumulative error for this normalisation is

ZN,t,M♮,⋆(u)=1M∑h=0⌊Mu⌋−1{A^N⋆(t+h)2t+h−cd},0≤u≤1,\mathcal{Z}^{\natural,\star}_{N,t,M}(u)=\frac{1}{\sqrt{M}}\sum_{h=0}^{\lfloor Mu\rfloor-1}\left\{\frac{\widehat{A}^{\star}_{N}(t+h)^{2}}{t+h}-c_d\right\},\qquad0\le u\le1,

Empty sums are zero. Each process is right-continuous and constant between consecutive points u=j/Mu=j/M; its polygonal interpolation is linear between consecutive grid values.

References

  1. [1]J. Akahori, N. Konno, Y. Mukai, N. Nagata, I. Sato, R. Suzuki, and Y. Tamura. Exact new-sector computation and finite-size spectral statistics of Grover walks on random graph lifts. Physica Scripta, 101:395202, 2026. doi:10.1088/1402-4896/aea8eb.DOI
  2. [2]A. D. Barbour. Stein’s method and Poisson process convergence. J. Appl. Probab., 25A:175–184, 1988. URL: https://user.math.uzh.ch/barbour/pub/Barbour/PoissonProcessConvergence.pdf, doi: 10.2307/3214155.DOI
  3. [3]H. Bass. The Ihara–Selberg zeta function of a tree lattice. International Journal of Mathematics, 3(6):717–797, 1992. doi:10.1142/S0129167X92000357.DOI
  4. [4]G. Berkolaiko, H. Schanz, and R. S. Whitney. Leading Off-Diagonal Correction to the Form Factor of Large Graphs. Physical Review Letters, 88(10):104101, 2002. doi:10.1103/PhysRevLett.88.104101.DOI
  5. [5]C. Bordenave and B. Collins. Eigenvalues of random lifts and non-backtracking eigenvalues of random permutation matrices. Annals of Mathematics, 190:811–875, 2019. URL: https://arxiv.org/abs/1801.00876, arXiv:1801.00876, doi:10.4007/annals.2019.190.3.3.
  6. [6]G. Cipolloni, L. Erdős, and D. Schröder. On the spectral form factor for random matrices. Communications in Mathematical Physics, 401:1665–1700, 2023. doi:10.1007/s00220-023-04692-y.DOI
  7. [7]B. Collins and M. Nagatsuu. Weingarten calculus for centered random permutation matrices. Algebraic Combinatorics, 9:465–479, 2026. URL: https://alco.centre-mersenne.org/articles/10.5802/alco.480/, doi:10.5802/alco.480.DOI
  8. [8]I. Dumitriu, T. Johnson, S. Pal, and E. Paquette. Functional limit theorems for random regular graphs. Probability Theory and Related Fields, 156:921–975, 2013. URL: https://arxiv.org/abs/1109.4094, arXiv:1109.4094, doi:10.1007/s00440-012-0447-y.
  9. [9]I. Dumitriu and Y. Zhu. Global eigenvalue fluctuations of random biregular bipartite graphs. Random Matrices: Theory and Applications, 12(3):2350004, 2023. URL: https://arxiv.org/abs/2008.11760, arXiv:2008.11760, doi:10.1142/S2010326323500041.
  10. [10]J. Friedman and D.-E. Kohler. The Relativized Second Eigenvalue Conjecture of Alon. Preprint, 2014. URL: https://arxiv.org/abs/1403.3462, arXiv:1403.3462.
  11. [11]S. Gnutzmann and A. Altland. Spectral correlations of individual quantum graphs. Physical Review E, 72:056215, 2005. arXiv:nlin/0508009, doi:10.1103/PhysRevE.72.056215.DOI
  12. [12]S. Gnutzmann and U. Smilansky. Quantum Graphs: Applications to Quantum Chaos and Universal Spectral Statistics. Advances in Physics, 55(5–6):527–625, 2006. doi:10.1080/00018730600908042.DOI
  13. [13]Y. Gong, W. Li, and S. Liu. Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions. Mathematische Nachrichten, 298:3417–3439, 2025. URL: https://arxiv.org/abs/2406.05759, arXiv:2406.05759, doi:10.1002/mana.70046.
  14. [14]C. Greenhill, S. Janson, and A. Ruciński. On the number of perfect matchings in random lifts. Combinatorics, Probability and Computing, 19:791–817, 2010. URL: https://arxiv.org/abs/0907.0958, arXiv:0907.0958, doi:10.1017/S0963548309990654.
  15. [15]F. Haake, H.-J. Sommers, and J. Weber. Fluctuations and ergodicity of the form factor of quantum propagators and random unitary matrices. Journal of Physics A, 32:6903–6913, 1999. arXiv:chao-dyn/9906024, doi:10.1088/0305-4470/32/40/301.DOI
  16. [16]L. Hanany and D. Puder. Word Measures on Symmetric Groups. Int. Math. Res. Not. IMRN, (11):9221–9297, 2023. doi:10.1093/imrn/rnac084.DOI
  17. [17]T. Johnson. Exchangeable pairs, switchings, and random regular graphs. Electronic Journal of Combinatorics, 22:P1.33, 2015. URL: https://arxiv.org/abs/1112.0704, arXiv:1112.0704, doi:10.37236/4659.
  18. [18]T. Johnson and S. Pal. Cycles and eigenvalues of sequentially growing random regular graphs. The Annals of Probability, 42:1396–1437, 2014. URL: https://arxiv.org/abs/1203.1113, arXiv:1203.1113, doi:10.1214/13-AOP864.
  19. [19]F. Kong and H. Wang. A functional Breuer–Major theorem with Poisson noise. Preprint, 2025. URL: https://arxiv.org/abs/2510.26216v1, arXiv:2510.26216v1.
  20. [20]N. Konno, H. Mitsuhashi, H. Morita, and I. Sato. The trace formula with respect to the Grover matrix of a graph. Linear and Multilinear Algebra, 70(10):1963–1979, 2022. doi:10.1080/03081087.2020.1779173.
  21. [21]N. Konno and I. Sato. On the relation between quantum walks and zeta functions. Quantum Information Processing, 11:341–349, 2012. doi:10.1007/s11128-011-0250-1.DOI
  22. [22]T. Kottos and U. Smilansky. Periodic Orbit Theory and Spectral Statistics for Quantum Graphs. Annals of Physics, 274(1):76–124, 1999. doi:10.1006/aphy.1999.5904.DOI
  23. [23]N. Linial and D. Puder. Word maps and spectra of random graph lifts. Random Structures & Algorithms, 37:100–135, 2010. URL: https://arxiv.org/abs/0806.1993, arXiv:0806.1993, doi:10.1002/rsa.20304.
  24. [24]A. Maltsev and M. Osman. Mesoscopic linear statistics for two ensembles of quantum graphs. Preprint, 2026. URL: https://arxiv.org/abs/2607.02356v1, arXiv:2607.02356v1.
  25. [25]Y. Maoz. Smooth linear eigenvalue statistics on random covers of compact hyperbolic surfaces—a central limit theorem and almost sure RMT statistics. Israel Journal of Mathematics, 2026. Published online 6 April 2026. URL: https://arxiv.org/abs/2310.18663v3, arXiv:2310.18663v3, doi:10.1007/s11856-026-2907-6.
  26. [26]F. Naud. Random Covers of Compact Surfaces and Smooth Linear Spectral Statistics. Annales Henri Poincaré, 27:347–373, 2026. arXiv:2209.07941, doi:10.1007/s00023-025-01551-5.DOI
  27. [27]A. Nica. On the number of cycles of given length of a free word in several permutations. Random Structures & Algorithms, 5:703–730, 1994. doi:10.1002/rsa.3240050506.DOI
  28. [28]I. Nourdin and D. Nualart. The functional Breuer–Major theorem. Probab. Theory Related Fields, 176:203–218, 2020. doi:10.1007/s00440-019-00917-1.DOI
  29. [29]I. Oren, A. Godel, and U. Smilansky. Trace Formulae and Spectral Statistics for Discrete Laplacians on Regular Graphs (I). Journal of Physics A: Mathematical and Theoretical, 42(41):415101, 2009. doi: 10.1088/1751-8113/42/41/415101.DOI
  30. [30]I. Oren and U. Smilansky. Trace formulae and spectral statistics for discrete Laplacians on regular graphs (II). Journal of Physics A, 43:225205, 2010. arXiv:1003.1445, doi:10.1088/1751-8113/43/22/225205.DOI
  31. [31]R. E. Prange. The Spectral Form Factor Is Not Self-Averaging. Physical Review Letters, 78(12):2280–2283, 1997. doi:10.1103/PhysRevLett.78.2280.DOI
  32. [32]D. Puder and T. Zimhoni. Local statistics of random permutations from free products. International Mathematics Research Notices, 2024(5):4242–4300, 2024. URL: https://arxiv.org/abs/2203.12250, arXiv: 2203.12250, doi:10.1093/imrn/rnad207.
  33. [33]E. Rio. Upper bounds for minimal distances in the central limit theorem. Ann. Inst. H. Poincaré Probab. Statist., 45(3):802–817, 2009. doi:10.1214/08-AIHP187.DOI
  34. [34]A. Röllin. On the optimality of Stein factors. In Probability Approximations and Beyond, volume 205 of Lecture Notes in Statistics, pages 61–72. Springer, 2012. arXiv:0706.0879v3, doi:10.1007/978-1-4614-1966-2_5.DOI
  35. [35]Z. Rudnick and I. Wigman. Almost Sure GOE Fluctuations of Energy Levels for Hyperbolic Surfaces of High Genus. Annales Henri Poincaré, 26:2279–2291, 2025. doi:10.1007/s00023-025-01552-4.DOI
  36. [36]I. Sato, T. Komatsu, N. Konno, and H. Mitsuhashi. Konno–Sato theorem for a covering of a graph. Letters in Mathematical Physics, 115:77, 2025. doi:10.1007/s11005-025-01960-x.DOI
  37. [37]G. K. Tanner. From Quantum Graphs to Quantum Random Walks. In F. Khanna and D. Matrasulov, editors, Non-Linear Dynamics and Fundamental Interactions, volume 213 of NATO Science Series II: Mathematics, Physics and Chemistry, pages 69–87. Springer, Dordrecht, 2006. arXiv:quant-ph/0502424, doi:10.1007/1-4020-3949-2_6.
  38. [38]X. Yu. Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts. Preprint, 2026. URL: https://arxiv.org/abs/2608.28539v2, arXiv: 2608.28539v2.

Paper details

vlnc:W_9guptw6g
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Not recorded for this paper · View statement →

Looking for related papers…
Contents