Quantum random walks on d-regular graphs with Haar-random coin operators
Abstract
With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.
Related
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- The distribution of eccentricities in random regular graphs
- Error correction and quantum information spreading on sparse random graphs
- Random Cellular Automata and deBruijn Graphs
- Beyond the lemon: Spectra of random Lindblad operators with a Hamiltonian component
BibTeX
@misc{quillen2026quantum,
title = {{Quantum random walks on d-regular graphs with Haar-random coin operators}},
author = {Alice C. Quillen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.04584},
eprint = {2607.04584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.04584},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum random walks on d-regular graphs with Haar-random coin operators
AU - Alice C. Quillen
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.04584
UR - https://arxiv.org/abs/2607.04584
AB - With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.
ER -