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

• URL: http://arxiv.org/abs/2607.04584v2
• Date: Wed, 08 Jul 2026 11:18:35 GMT
• Title: Quantum random walks on d-regular graphs with Haar-random coin operators
• Abstract summary: We construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph.<n>The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace.<n>We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Orientation-dependent Pauli noise in one-dimensional discrete-time quantum walks [41.99844472131922]
  We study the long-time dynamics of a one-dimensional discrete-time quantum walk under Pauli noise acting on the coin.<n>All channels induce a crossover from ballistic to diffusive spreading, with a second moment growing linearly at long times.<n>The quantum-to-classical transition is governed by the relative alignment of the noise, the coherent walk dynamics, and the initial state.
  arXiv  Detail & Related papers  (2026-09-11T18:02:03Z)
• Freeness Reined in by a Single Qubit [36.94429692322632]
  We find that, even in this setting, the correlation functions predicted by free probability theory receive corrections of order $O(1)$.<n>We trace their origin to non-uniformly distributed stationary quantum states, which we characterize analytically and confirm numerically.
  arXiv  Detail & Related papers  (2025-12-15T19:00:09Z)
• Quantum-driven sampling of the quasi-uniform distribution via quantum walks [0.5097809301149341]
  We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution.<n>We show that when the quantum walk parameters, such as the coin operator and initial state, satisfy the conditions of the ergodic theorem for random walks on finite groups, the resulting sequence convergesally to the uniform distribution.
  arXiv  Detail & Related papers  (2025-11-11T14:26:18Z)
• Chaos in Systems with Quantum Group Symmetry [45.88028371034407]
  We show an explicit example of a system with quantum group global symmetry which is chaotic.<n>The spin chain is non-unitary but PT-symmetric and, in addition to chaos, exhibits an interesting transition after which the eigenvalues become complex.
  arXiv  Detail & Related papers  (2025-10-27T12:07:16Z)
• Symmetric quantum walks on Hamming graphs and their limit distributions [0.0]
  We study a class of symmetric quantum walks on Hamming graphs.<n> Eigenvalues of the unitary operator of the walks are zeros of certain self-reciprocals.
  arXiv  Detail & Related papers  (2025-09-30T13:36:34Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
  This paper advances the general understanding of quantum walk mixing on Cayley graphs.<n>It highlights the improved mixing time achieved by continuous-time quantum walks on $D_2n$.<n>This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
  arXiv  Detail & Related papers  (2023-12-25T11:21:55Z)
• Normal quantum channels and Markovian correlated two-qubit quantum errors [77.34726150561087]
  We study general normally'' distributed random unitary transformations. On the one hand, a normal distribution induces a unital quantum channel. On the other hand, the diffusive random walk defines a unital quantum process.
  arXiv  Detail & Related papers  (2023-07-25T15:33:28Z)
• Cutoff phenomenon and entropic uncertainty for random quantum circuits [0.0]
  How fast a state of a system converges to a stationary state is one of the fundamental questions in science. Some Markov chains and random walks on finite groups are known to exhibit the non-asymptotic convergence to a stationary distribution. We show how quickly a random quantum circuit could transform a quantum state to a Haar-measure random quantum state.
  arXiv  Detail & Related papers  (2023-05-20T03:33:48Z)
• Geometric phases along quantum trajectories [58.720142291102135]
  We study the distribution function of geometric phases in monitored quantum systems. For the single trajectory exhibiting no quantum jumps, a topological transition in the phase acquired after a cycle. For the same parameters, the density matrix does not show any interference.
  arXiv  Detail & Related papers  (2023-01-10T22:05:18Z)
• Observation of entanglement negativity transition of pseudo-random mixed states [23.43987389179338]
  Multipartite entanglement is a key resource for quantum computation. Here, we report the observation of entanglement transition quantified by negativity using a fully connected 20-qubit superconducting processor. Our simulator provides a powerful tool to generate random states and understand the entanglement structure for multipartite quantum systems.
  arXiv  Detail & Related papers  (2022-08-29T02:56:05Z)
• Discrete Quantum Walks on the Symmetric Group [0.0]
  In quantum walks, the propagation is governed by quantum mechanical rules; generalizing random walks to the quantum setting. In this paper we investigate the discrete time coined quantum walk (DTCQW) model using tools from non-commutative Fourier analysis. Specifically, we are interested in characterizing the DTCQW on Cayley graphs generated by the symmetric group ($sym$) with appropriate generating sets.
  arXiv  Detail & Related papers  (2022-03-28T23:48:08Z)
• Bernstein-Greene-Kruskal approach for the quantum Vlasov equation [91.3755431537592]
  The one-dimensional stationary quantum Vlasov equation is analyzed using the energy as one of the dynamical variables. In the semiclassical case where quantum tunneling effects are small, an infinite series solution is developed.
  arXiv  Detail & Related papers  (2021-02-18T20:55:04Z)
• Mapping a finite and an infinite Hadamard quantum walk onto a unique case of a random walk process [0.0]
  A new model that maps a quantum random walk described by a Hadamard operator is presented. The model is represented by a Markov chain with a matrix. The probability distributions in space of the two quantum states |1>, |0> are revealed.
  arXiv  Detail & Related papers  (2020-11-17T16:49:00Z)

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.