Average Mixing in Quantum Walks of Reversible Markov Chains

• URL: http://arxiv.org/abs/2211.02037v2
• Date: Fri, 07 Feb 2025 18:40:17 GMT
• Title: Average Mixing in Quantum Walks of Reversible Markov Chains
• Abstract summary: The Szegedy quantum walk is a discrete time quantum walk model which defines a quantum analogue of any Markov chain.<n>We prove a formula for our mixing matrix in terms of the spectral decomposition of the Markov chain.<n>In particular, we prove that average uniform mixing in the continuous walk implies average uniform mixing in the Szegedy walk.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Szegedy quantum walk is a discrete time quantum walk model which defines a quantum analogue of any Markov chain. The long-term behavior of the quantum walk can be encoded in a matrix called the average mixing matrix, whose columns give the limiting probability distribution of the walk given an initial state. We define a version of the average mixing matrix of the Szegedy quantum walk which allows us to more readily compare the limiting behavior to that of the chain it quantizes. We prove a formula for our mixing matrix in terms of the spectral decomposition of the Markov chain and show a relationship with the mixing matrix of a continuous quantum walk on the chain. In particular, we prove that average uniform mixing in the continuous walk implies average uniform mixing in the Szegedy walk. We conclude by giving examples of Markov chains of arbitrarily large size which admit average uniform mixing in both the continuous and Szegedy quantum walk.

Related papers

• Quantum Stochastic Walks on the Permutation Group [1.1327508153380308]
  We prove that quantum coherence can only decrease the distance from the uniform distribution in a computational basis.<n>An analysis of the slowest mode yields a criterion for the coupling strength required to produce an appreciable speedup.<n>Our results illustrate how coherence and dissipation can cooperate in the emergence of randomness in walks on permutation groups.
  arXiv  Detail & Related papers  (2026-09-11T18:00:09Z)
• On aggregation-quantization permutability problem for discrete-time Markov chains [0.056179939237156]
  Given random walk on a graph, the corresponding discrete-time quantum walk can be constructed using the method proposed by Szegedy.<n>We extend the aggregation technique to the level of quantum Markov chains.
  arXiv  Detail & Related papers  (2026-03-15T08:01:47Z)
• 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 walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
  A quantum walk is the quantum analogue of a random walk. We show that quantum walks can speed up the spreading or mixing rate of random walks on graphs.
  arXiv  Detail & Related papers  (2024-02-12T17:15:19Z)
• Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
  Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.
  arXiv  Detail & Related papers  (2023-12-25T11:21:55Z)
• Non-uniform Mixing of Quantum Walks on the Symmetric Group [0.0]
  We analyze the spectra of the Szegedy walk operators using the representation theory of the symmetric group. Our techniques are general, and we believe they can be applied to derive similar analytical results for other non-commutative groups.
  arXiv  Detail & Related papers  (2023-11-06T03:17:36Z)
• Unexpected Averages of Mixing Matrices [0.0]
  We consider alternative probability distributions, either discrete or continuous. We show that several algebraic properties that hold for the average mixing matrix still stand for this more general setting. We employ concepts of classical probability theory not usually seen in texts about quantum walks.
  arXiv  Detail & Related papers  (2023-08-31T00:44:58Z)
• 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)
• Quantifying measurement-induced quantum-to-classical crossover using an open-system entanglement measure [49.1574468325115]
  We study the entanglement of a single particle under continuous measurements. We find that the entanglement at intermediate time scales shows the same qualitative behavior as a function of the measurement strength.
  arXiv  Detail & Related papers  (2023-04-06T09:45:11Z)
• Preserving quantum correlations and coherence with non-Markovianity [50.591267188664666]
  We demonstrate the usefulness of non-Markovianity for preserving correlations and coherence in quantum systems. For covariant qubit evolutions, we show that non-Markovianity can be used to preserve quantum coherence at all times.
  arXiv  Detail & Related papers  (2021-06-25T11:52:51Z)
• Generalized quantum measurements with matrix product states: Entanglement phase transition and clusterization [58.720142291102135]
  We propose a method for studying the time evolution of many-body quantum lattice systems under continuous and site-resolved measurement. We observe a peculiar phenomenon of measurement-induced particle clusterization that takes place only for frequent moderately strong measurements, but not for strong infrequent measurements.
  arXiv  Detail & Related papers  (2021-04-21T10:36:57Z)
• 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)
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
  We simulate a noisy quantum Fourier transform processor with up to 21 qubits. We take into account microscopic dissipative processes rather than relying on digital error models. We show that depending on the dissipative mechanisms at play, the choice of input state has a strong impact on the performance of the quantum algorithm.
  arXiv  Detail & Related papers  (2021-02-08T14:55:44Z)
• From stochastic spin chains to quantum Kardar-Parisi-Zhang dynamics [68.8204255655161]
  We introduce the asymmetric extension of the Quantum Symmetric Simple Exclusion Process. We show that the time-integrated current of fermions defines a height field which exhibits a quantum non-linear dynamics.
  arXiv  Detail & Related papers  (2020-01-13T14:30:36Z)
• The $χ^2$-divergence and Mixing times of quantum Markov processes [0.0]
  We introduce quantum versions of the $chi2$-divergence, provide a detailed analysis of their properties, and apply them in the investigation of mixing times of quantum Markov processes. A strict spectral bound to the convergence rate can be given for time-discrete as well as for time-continuous quantum Markov processes.
  arXiv  Detail & Related papers  (2010-05-13T15:56: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.