Quantum random walks on d-regular graphs with Haar-random coin operators

Technical Summary: Quantum Random Walks on d-Regular Graphs with Haar-Random Coin Operators

Problem Statement
The paper investigates discrete-time quantum random walks (QRWs) on $d$-regular undirected connected simple graphs. Standard QRWs utilize a fixed unitary coin operator (e.g., Hadamard or Grover) to induce interference, leading to ballistic spreading ($\sigma^2 \propto t^2$) distinct from classical random walks ($\sigma^2 \propto t$). Open quantum walks, which introduce decoherence, typically revert to classical diffusive behavior. This work addresses a specific variant: a QRW where the coin operator is not fixed but is independently drawn from a uniform distribution over the unitary group $U(d)$ with respect to the Haar measure at every iteration. The central question is how this "Haar-random" coin affects the dynamics, specifically whether the resulting averaged channel leads to complete depolarization (erasing all initial state information) or if specific structures allow for the persistence of initial state information despite the decoherence.

Methodology
The authors construct the walk on a bipartite Hilbert space $\mathbb{C}^d \otimes \mathbb{C}^N$, where $d$ represents the coin space (degree of the graph) and $N$ represents the vertex space.

1. Model Definition: The walk is defined by the iteration of a unitary operator $\hat{U} = \Lambda_S (\hat{C} \otimes \hat{I}_N)$, where $\Lambda_S$ is a controlled shift operator determined by the graph's edge labeling functions $w(j, v)$, and $\hat{C}$ is the coin operator.
2. Haar-Random Coin: Instead of a fixed $\hat{C}$, the coin operator $\hat{V}$ is chosen independently at each step $t$ from the Haar measure $\mu_H$ on $U(d)$.
3. Averaged Channel: To analyze the system, the authors compute the expectation value of the quantum channel over the distribution of coin operators. Using the property that for any operator $O$, $E_{U \in \mu_H}[U O U^\dagger] = \frac{\text{tr}(O)}{d} \hat{I}_d$, they derive the "averaged quantum channel" $\bar{E}_{SV}$. This channel acts on the density operator $\rho$ by depolarizing the coin subspace while applying a probabilistic shift to the vertex subspace.
4. Spectral Analysis: The authors analyze the spectrum of the averaged channel's superoperator, specifically looking for fixed points (eigenvalue 1) and period-2 orbits (eigenvalue -1). They examine this for specific cases: the cycle graph, the hypercube, and general Cayley graphs of finite Abelian groups.
5. Variance Estimation: The paper estimates the variance of vertex position measurements for an ensemble of such walks to determine the spreading behavior.

Key Contributions and Results

• Depolarization vs. Information Retention: The averaged channel $\bar{E}_{SV}$ acts as a depolarizing channel on the coin subspace, effectively destroying coherence within the coin space. Consequently, the vertex position distribution for an ensemble of walks resembles a classical random walk with a fair coin (or balanced $d$-sided dice), exhibiting diffusive spreading where variance grows linearly with time ($\sigma^2 \propto t$).
• Non-Ergodicity: A primary finding is that the averaged channel is not ergodic. Unlike typical decoherent channels that converge to a unique fixed point (the maximally mixed state), this channel possesses multiple fixed points in the space of density operators. The number of linearly independent fixed points equals the number of vertices $N$ (or the order of the group for Cayley graphs).
• Persistence of Initial State Information: Despite the coin subspace being depolarized, the paper demonstrates that measurements in the vertex subspace can reveal information about the initial quantum state even after many iterations.
  • Cycle and Hypercube Graphs: For these specific graphs (Cayley graphs of Abelian groups), the authors show that if the initial state is a superposition of specific Fourier basis states (e.g., $|k\rangle_F$ and $|k + N/2\rangle_F$ for the cycle, or $|\tilde{0}\rangle_F$ and $|\tilde{1}\rangle_F$ for the hypercube), off-diagonal terms in the density matrix can persist.
  • Eigenvalue -1: Information persists if the channel has eigenstates with eigenvalue $-1$. This occurs for Cayley graphs of Abelian groups only if all non-identity group elements have even order. In such cases, the off-diagonal terms oscillate (period-2 orbits) rather than decay, allowing the angle of the initial superposition to be recovered via vertex measurements.
  • Correlation Measurements: Even in cases where eigenvalues are strictly less than 1 in magnitude (no period-2 orbits), the paper argues that while the vertex position distribution approaches uniformity, measurements of correlations between pairs of vertices can still reveal the initial superposition angle $\theta$. This is because the channel is dephasing in the Fourier basis, not the vertex basis.
• Variance Behavior: The paper calculates that for an initially localized state, the variance of vertex position measurements for the Haar-random walk increases linearly with the number of iterations ($\sigma^2 \sim t$), confirming the recovery of classical diffusive behavior for the ensemble, distinct from the ballistic spreading of coherent QRWs.

Significance and Claims
The paper claims that this model serves as a specific example of a bipartite strongly interacting system where one subsystem (the coin) is strongly perturbed (depolarized) by a high-temperature reservoir-like environment, yet information about the initial state in the other subsystem (the walker/vertex) remains potentially measurable forever.

The authors explicitly state that due to the decoherence introduced by the Haar-random coin, these walks are not useful for quantum search algorithms, which rely on the ballistic spreading of coherent states. Instead, the significance of this work lies in:

1. Providing a theoretical framework for understanding quantum systems with strongly perturbed subsystems.
2. Illustrating how classical random walk behavior (diffusion) can emerge from a unitary quantum process through averaging over a specific distribution.
3. Demonstrating that "decoherence" in a specific subspace does not necessarily imply the total loss of initial state information if the global channel is non-ergodic and possesses specific spectral properties (eigenvalues of -1 or specific dephasing structures).

The work is presented as a theoretical exploration using analytical tools (averaged channels, Fourier analysis on Abelian groups) and numerical illustrations, without proposing new experimental hardware or immediate practical applications beyond modeling noisy quantum systems.