On aggregation-quantization permutability problem for discrete-time Markov chains

• URL: http://arxiv.org/abs/2603.14269v1
• Date: Sun, 15 Mar 2026 08:01:47 GMT
• Title: On aggregation-quantization permutability problem for discrete-time Markov chains
• Abstract summary: 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.
• Score: 0.056179939237156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given random walk on a graph, the corresponding discrete-time quantum walk can be constructed using the method proposed by Szegedy. On the other hand, given a partition of the set of states of a Markov chain, one can study the corresponding aggregated process. We extend the aggregation technique to the level of quantum Markov chains. We provide conditions under which application of these two operations - Szegedy's quantization and aggregation - give the same result. In particular, we show that the conditions are satisfied in the case of the random walk on graphs equipped with equitable partitions. We present several examples, which include the classical/quantum walks on Platonic solids. We discuss also relation of discrete-time classical/quantum walks on $N$-dimensional hypercube and the Ehrenfests urn model with $N$ particles. We apply our technique for of discrete-time walks on Cayley graphs of free groups. We also compare our results with those obtained using Cantero-Moral-Velazquez uniformization of unitary matrices.

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)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• 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)
• 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)
• Average Mixing in Quantum Walks of Reversible Markov Chains [0.0]
  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.
  arXiv  Detail & Related papers  (2022-11-03T17:55:18Z)
• Markov Chain Monte Carlo for Continuous-Time Switching Dynamical Systems [26.744964200606784]
  We propose a novel inference algorithm utilizing a Markov Chain Monte Carlo approach. The presented Gibbs sampler allows to efficiently obtain samples from the exact continuous-time posterior processes.
  arXiv  Detail & Related papers  (2022-05-18T09:03:00Z)
• Protocols for Trainable and Differentiable Quantum Generative Modelling [21.24186888129542]
  We propose an approach for learning probability distributions as differentiable quantum circuits (DQC) We perform training of a DQC-based model, where data is encoded in a latent space with a phase feature map, followed by a variational quantum circuit. This allows fast sampling from parametrized distributions using a single-shot readout.
  arXiv  Detail & Related papers  (2022-02-16T18:55:48Z)
• Quantum Quantile Mechanics: Solving Stochastic Differential Equations for Generating Time-Series [19.830330492689978]
  We propose a quantum algorithm for sampling from a solution of differential equations (SDEs) We represent the quantile function for an underlying probability distribution and extract samples as expectation values. We test the method by simulating the Ornstein-Uhlenbeck process and sampling at times different from the initial point.
  arXiv  Detail & Related papers  (2021-08-06T16:14:24Z)
• 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)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• 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.