Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Technical Summary: Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Problem Statement
The paper investigates the existence of Uniform Average Mixing (UAM) for continuous-time quantum walks on connected, non-complete strongly regular graphs (SRGs). UAM is defined by the existence of a Borel probability measure $\mu$ on $[0, \infty)$ such that the time-averaged mixing matrix equals the uniform matrix $\frac{1}{n}J$, where $n$ is the number of vertices. Specifically, the study seeks to determine which SRGs admit such a law and to characterize the nature of these laws (e.g., whether they can be realized by bounded densities, finite atomic measures, or single observation times). The work addresses the spectral-moment viewpoint of quantum walk averages, a topic previously posed as an open problem in the literature.

Methodology
The author employs a spectral moment approach, reducing the infinite-dimensional problem of finding a time law to a finite-dimensional moment problem.

1. Spectral Reduction: Utilizing the algebraic structure of SRGs (specifically the identity $A^2 = (\lambda - \nu)A + (k - \nu)I + \nu J$), the mixing matrix $M(t)$ is expressed in terms of three cosine moments corresponding to the graph's restricted eigenvalues.
2. Affine Constraints: The condition for UAM is shown to be equivalent to satisfying two affine constraints on these three moments, defining a "moment line" in $\mathbb{R}^3$.
3. Geometric and Algebraic Tools:
   • Carathéodory-type Theorems: The author utilizes refinements of Carathéodory's theorem to prove that any averaged mixing matrix can be realized by at most two observation times (atoms), regardless of the original time law.
   • Moment Problems: For graphs with non-integral spectra, the author constructs explicit bounded, compactly supported time densities using Fejér polynomials and Gram matrix inversion. For integral spectra, they derive necessary and sufficient conditions using finite Toeplitz and Hankel semidefinite matrices.
   • Complex Hadamard Matrices: A key step involves linking the existence of a point on the moment line with a positive semidefinite Gram matrix to the existence of complex Hadamard matrices within the Bose–Mesner algebra of the graph. This allows for a classification of parameter sets without relying on prior classification theorems or computer calculations.

Key Contributions and Results

• Reduction to Two Times: The paper proves that for any connected, non-complete SRG, if a UAM law exists, it can be realized by a discrete measure with at most two atoms (observation times). This simplifies the search for UAM to checking specific pairs of times.
• Explicit Constructions:
  • For SRGs with non-integral restricted eigenvalues (conference graphs of non-square order), the author constructs an explicit bounded probability density supported on a finite interval $[0, T]$.
  • For integral spectra, a finite semidefinite criterion (Toeplitz/Hankel form) is provided to determine existence.
• Complete Classification: The paper determines all SRGs admitting UAM. Apart from graphs with Instantaneous Uniform Mixing (IUM) and conference graphs of non-square order, UAM is admitted only by:
  1. Graphs (or their complements) with parameters $(4\theta^2 + 4\theta + 2, 2\theta^2 + \theta, \theta^2 - 1, \theta^2)$ for $\theta \ge 1$.
  2. Graphs (or their complements) with parameters $(4\theta^2 - 1, 2\theta^2, \theta^2, \theta^2)$ for $\theta \ge 2$.
  • The Petersen graph and its complement are identified as the smallest members of these families.
• Density vs. Atoms: A dichotomy is established: a graph with UAM admits a bounded time density if and only if it does not admit instantaneous uniform mixing. If IUM exists, the UAM law must be concentrated on a discrete set.
• Correction of Previous Work: The paper corrects the classification of Instantaneous Uniform Mixing on SRGs by Godsil, Mullin, and Roy. It identifies that their sign conditions incorrectly excluded the halved 5-cube (which mixes uniformly at $t=\pi/4$) and incorrectly included parameters $(36, 14, 4, 6)$, for which no UAM law exists. The corrected classification relies on the divisibility of $n$ by 16 and the existence of specific Hadamard matrices.

Significance and Claims
The paper claims to provide a complete, self-contained classification of strongly regular graphs admitting uniform average mixing. Its significance lies in:

• Unification: It unifies the study of UAM with the theory of complex Hadamard matrices in the Bose–Mesner algebra, offering a short, elementary proof of Chan's classification of such matrices in this context.
• Exactness: It provides exact, non-asymptotic criteria (finite semidefinite conditions) for the integral spectrum case and explicit constructions for the non-integral case.
• Resolution of Open Problems: It answers specific open problems regarding the rationality of mixing times and the spectral conditions for IUM within the class of SRGs.
• Methodological Rigor: The classification is derived without reliance on computer calculations or prior classification theorems, using only elementary inequalities and moment theory.

The author emphasizes that the results are definitive for the class of connected, non-complete SRGs, establishing precise boundaries between graphs that admit continuous densities, those requiring discrete atomic laws, and those that admit no uniform average mixing at all.