Spectral characterization of the uniform theta graph $Θ(t,2)$ and classification of 6-periodic Grover walks

• URL: http://arxiv.org/abs/2609.08315v1
• Date: Tue, 08 Sep 2026 06:37:31 GMT
• Title: Spectral characterization of the uniform theta graph $Θ(t,2)$ and classification of 6-periodic Grover walks
• Abstract summary: We characterize the uniform theta graph $(t,2)$ by the spectrum of its normalized adjacency matrix.<n>We also investigate the periodicity of Grover walks on nonregular graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize the uniform theta graph $Θ(t,2)$ by the spectrum of its normalized adjacency matrix, or equivalently, by the spectrum of its normalized Laplacian matrix. We also investigate the periodicity of Grover walks on nonregular graphs, which is closely related to the eigenvalues of the normalized adjacency matrix and those of the time evolution matrix of the Grover walk. We show that the Dutch windmill graph $D_n^{(t)}$ is $2n$-periodic and that the uniform theta graph $Θ(t,n)$ is $(2n+2)$-periodic. Furthermore, we completely determine the connected $6$-periodic graphs and prove that they are precisely $D_3^{(t)}$ with $t \geq 2$ and $Θ(t,2)$ with $t \geq 1$.

Related papers

• Schur States, Average Mixing, and Counting Trees on Line Graphs' CTQW [0.0]
  We introduce a family of complex-valued edge weights on a finite simple graph $G$ arising from a continuous-time quantum walk on the line graph $ellG$.<n>We identify a structural mechanism -- the $-2$ eigenspace of $ellG$ -- providing uniform commutative states beyond the regular case.
  arXiv  Detail & Related papers  (2026-05-03T16:31:26Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Mesoscopic Fluctuations and Multifractality at and across Measurement-Induced Phase Transition [46.176861415532095]
  We explore statistical fluctuations over the ensemble of quantum trajectories in a model of two-dimensional free fermions.<n>Our results exhibit a remarkable analogy to Anderson localization, with $G_AB$ corresponding to two-terminal conductance.<n>Our findings lay the groundwork for mesoscopic theory of monitored systems, paving the way for various extensions.
  arXiv  Detail & Related papers  (2025-07-15T13:44:14Z)
• Strongly regular and strongly walk-regular graphs that admit perfect state transfer [0.0]
  We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs.<n>We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph $K_2,2 and the complete graph $K_2,2,2.
  arXiv  Detail & Related papers  (2025-06-03T07:10:06Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Quantum walks on join graphs [0.0]
  We explore the behaviour of a continuous quantum walk on a weighted join graph having the adjacency matrix or Laplacian matrix as its associated Hamiltonian. We characterize strong cospectrality, periodicity and perfect state transfer (PST) in a join graph. We demonstrate that the bound $frac2|V(X)|$ is tight for infinite families of graphs.
  arXiv  Detail & Related papers  (2023-12-12T00:33:30Z)
• $ε$-Uniform Mixing in Discrete Quantum Walks [0.0]
  We study whether the probability distribution of a discrete quantum walk can get arbitrarily close to uniform. We establish a characterization of this phenomenon on regular non-bipartite graphs in terms of their adjacency eigenvalues and eigenprojections.
  arXiv  Detail & Related papers  (2023-11-30T18:43:38Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
  arXiv  Detail & Related papers  (2023-07-02T05:03:38Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07:50Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• The average search probabilities of discrete-time quantum walks [0.0]
  We first show that, for a regular graph, the spectrum of the transition matrix is determined by the weighted adjacency matrix of an augmented graph. We then consider the average search probability on a distance regular graph, and find a formula in terms of the adjacency matrix of its subgraph. In particular, for any family of (1) complete graphs, or (2) strongly regular graphs, or (3) distance regular graphs of a fixed parameter $d$, varying valency $k$ and varying size $n$, the average search probability approaches $1/4$ as the valency goes to infinity.
  arXiv  Detail & Related papers  (2021-08-22T18:53:22Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$.<n>Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
  arXiv  Detail & Related papers  (2021-04-06T15:34:14Z)
• Anharmonic oscillator: a solution [77.34726150561087]
  The dynamics in $x$-space and in $(gx)-space corresponds to the same energy spectrum with effective coupling constant $hbar g2$. A 2-classical generalization leads to a uniform approximation of the wavefunction in $x$-space with unprecedented accuracy.
  arXiv  Detail & Related papers  (2020-11-29T22:13:08Z)
• Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
  We propose a fast general metric learning framework that is entirely projection-free. We replace the PD cone constraint in the metric learning problem with possible linear constraints per distances. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes.
  arXiv  Detail & Related papers  (2020-06-15T23:15:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.