Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Markov Chain Mixing and Dissipative Engineering

M. R. James

Published Jan 1, 2015• 5 citations
OpenAlex

Abstract

This thesis is the fruit of investigations on the extension of ideas of Markov chain mixing to the quantum setting, and its application to problems of dissipative engineering. A Markov chain describes a statistical process where the probability of future events depends only on the state of the system at the present point in time, but not on the history of events. Very many important processes in nature are of this type, therefore a good understanding of their behavior has turned out to be very fruitful for science. Markov chains always have a non-empty set of limiting distributions (stationary states). The aim of Markov chain mixing is to obtain (upper and/or lower) bounds on the number of steps it takes for the Markov chain to reach a stationary state. The natural quantum extensions of these notions are density matrices and quantum channels. We set out to develop a general mathematical framework for studying quantum Markov chain mixing. We introduce two new distance measures into the quantum setting; the quantum χ2divergence and Hilbert’s projective metric. The quantum χ2 divergence allows us to extend the class of functional techniques called Poincare inequalities to the quantum setting. In the process, we identify the appropriate framework for discussing notions such as detailed balance and χ2-mixing: monotone Riemannian metrics on matrix spaces. This insight allows us to characterize the connection between spectral properties of a (primitive) quantum channel and its mixing time. Within the same framework we also derive a restricted quantum version of the celebrated conductance bound (Cheeger’s inequality). We then consider Hilbert’s projective metric a well known tool in Perron-Frobenius theory in the context of quantum information theory. As a classic tool for analyzing convergence of positive maps on cones, Hilbert’s projective metric is especially good at providing existence proofs of maps between two spaces (or cones). We relate this measure to distinguishability measures on restricted cones of operators, and analyze the observable loss of information after the application of a quantum channel under a restrict set of measurements. Various notions of contractivity of quantum channels are revealed through Hilbert’s metric. Still on the topic of quantum Markov chains, we introduce the notion of cutoff phenomenon to the quantum setting. The cutoff phenomenon describes the situation when a Markov chain does not converge for a potentially long time, and then at a specific point in time abruptly converges to equilibrium. In the thermodynamic limit, the convergence profile will then look like a step function. We show that this type of convergence behavior occurs, as measured in trace-norm, when a system is subject to a product channel, and the noise on each product is modeled by a one-parameter semigroup of quantum channels. Finally, we consider three independent tasks of dissipative engineering. The first task, which is aimed at experimental realization in the near future, consists in dissipatively

Related papers

Analog quantum algorithms for the mixing of Markov chains

Shantanav Chakraborty, Kyle Luh, Jérémie Roland

The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.

arXiv:1904.11895•Physical Review A•Aug 25, 2020•19 citations

A cutoff phenomenon for quantum Markov chains

Michael J Kastoryano, David Reeb, Michael M Wolf

We derive upper and lower bounds on the convergence behavior of certain classes of one-parameter quantum dynamical semigroups. The classes we consider, consist of tensor product channels and of channels with commuting Liouvillians. We introduce the notion of cutoff phenomenon in the setting of quantum information theory, and show how it exemplifies the fact that the convergence of (quantum) stochastic processes is not solely governed by the spectral gap of the transition map. We apply the new methods to show that graph states can be prepared efficiently, albeit not in constant time, by dissipation, and give the exact scaling behavior of the time to stationarity.

arXiv:1111.2123•Journal of Physics A Mathematical and Theoretical•Feb 1, 2012•41 citations

Spectral Methods for quantum Markov chains

Oleg Szehr

The aim of this project is to contribute to our understanding of quantum time evolutions, whereby we focus on quantum Markov chains. The latter constitute a natural generalization of the ubiquitous concept of a classical Markov chain to describe evolutions of quantum mechanical systems. We contribute to the theory of such processes by introducing novel methods that allow us to relate the eigenvalue spectrum of the transition map to convergence as well as stability properties of the Markov chain.

•Jan 1, 2015•0 citations

Quantum and stochastic processes

Tom Bannink

In this dissertation we present results for various quantum and stochastic processes. First, we bound separations between the entangled and classical values for several classes of nonlocal t-player games. We show that for many general classes of such games, the entangled winning probability can not be much higher than the classical one. The proofs use semidefinite-programming techniques and hypergraph norms. Next, we study so-called quasirandom properties of graphs, and extend this to the quantum realm. For a certain class of quantum channels we generalize several results on equivalence between different quasirandom properties, using the non-commutative Grothendieck inequality. We also look at methods for sampling random graphs with power-law degree distributions, using Markov Chain switching methods. Using these samples we present a conjecture on the asymptotic number of triangles in the uniform random graph model. Next we study a class of stochastic processes on graphs that include the discrete Bak-Sneppen process and the contact process. These processes exhibit a phenomenon which we call the Power Light Cone, that has been used in the physics community for a long time but had not yet been proven. We provide this proof, which allows for numerical computations that estimate critical exponents. Finally, we consider a quantum version of Pascal's triangle. When Pascal's triangle is plotted modulo 2, the Sierpinski triangle appears. We prove that when the quantum version of this triangle is plotted modulo 3, a fractal known as the Sierpinski carpet emerges.

•Jan 30, 2020•0 citations

Discrete Quantum Markov Chains

Ulrich Faigle, Alexander Schönhuth

A framework for finite-dimensional quantum Markov chains on Hilbert spaces is introduced. Quantum Markov chains generalize both classical Markov chains with possibly hidden states and existing models of quantum walks on finite graphs. Quantum Markov chains are based on Markov operations that may be applied to quantum systems and include quantum measurements, for example. It is proved that quantum Markov chains are asymptotically stationary and hence possess ergodic and entropic properties. With a quantum Markov chain one may associate a quantum Markov process, which is a stochastic process in the classical sense. Generalized Markov chains allow a representation with respect to a generalized Markov source model with definite (but possibly hidden) states relative to which observables give rise to classical stochastic processes. It is demonstrated that this model allows for observables to violate Bell’s inequality.

•Nov 4, 2010•3 citations

Tight Contraction Rates for Primitive Channels under Quantum $f$-Divergences

Matthew Simon Tan, Marco Tomamichel, Ian George

Data-processing inequalities capture the phenomenon that two probability distributions can only become less distinguishable under any common post-processing. For more fine-grained inequalities, one turns to strong data-processing inequality (SDPI) constants, which give the strongest inequalities for a given channel and reference state for a fixed measure of distinguishability. These quantities have been used to quantify the rate at which time-homogeneous Markov chains contract towards a fixed point both in the classical and quantum setting. In this work, we establish that quantum $f$-divergences satisfy a local reverse Pinsker inequality, which implies the asymptotic contraction rate of a primitive channel to its stationary state is upper bounded by the SDPI constant of any non-commutative $χ^2$-divergence. Using quantum-detailed balance, we establish a sufficient condition for these bounds to be tight. Finally, we apply these results to Petz, Matsumoto, and Hirche-Tomamichel $f$-divergences, establishing new and strengthening previously known results.

quant-pharXiv:2605.06452•May 8, 2026•0 citations
This thesis is the fruit of investigations on the extension of ideas of Markov chain mixing to the quantum setting, and its application to problems of dissipative engineering. A Markov chain describes a statistical process where the probability of future events depends only on the state of the system at the present point in time, but not on the history of events. Very many important processes in nature are of this type, therefore a good understanding of their behavior has turned out to be very fruitful for science. Markov chains always have a non-empty set of limiting distributions (stationary states). The aim of Markov chain mixing is to obtain (upper and/or lower) bounds on the number of steps it takes for the Markov chain to reach a stationary state. The natural quantum extensions of these notions are density matrices and quantum channels. We set out to develop a general mathematical framework for studying quantum Markov chain mixing. We introduce two new distance measures into the quantum setting; the quantum χ2divergence and Hilbert’s projective metric. The quantum χ2 divergence allows us to extend the class of functional techniques called Poincare inequalities to the quantum setting. In the process, we identify the appropriate framework for discussing notions such as detailed balance and χ2-mixing: monotone Riemannian metrics on matrix spaces. This insight allows us to characterize the connection between spectral properties of a (primitive) quantum channel and its mixing time. Within the same framework we also derive a restricted quantum version of the celebrated conductance bound (Cheeger’s inequality). We then consider Hilbert’s projective metric a well known tool in Perron-Frobenius theory in the context of quantum information theory. As a classic tool for analyzing convergence of positive maps on cones, Hilbert’s projective metric is especially good at providing existence proofs of maps between two spaces (or cones). We relate this measure to distinguishability measures on restricted cones of operators, and analyze the observable loss of information after the application of a quantum channel under a restrict set of measurements. Various notions of contractivity of quantum channels are revealed through Hilbert’s metric. Still on the topic of quantum Markov chains, we introduce the notion of cutoff phenomenon to the quantum setting. The cutoff phenomenon describes the situation when a Markov chain does not converge for a potentially long time, and then at a specific point in time abruptly converges to equilibrium. In the thermodynamic limit, the convergence profile will then look like a step function. We show that this type of convergence behavior occurs, as measured in trace-norm, when a system is subject to a product channel, and the noise on each product is modeled by a one-parameter semigroup of quantum channels. Finally, we consider three independent tasks of dissipative engineering. The first task, which is aimed at experimental realization in the near future, consists in dissipatively
The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.
We derive upper and lower bounds on the convergence behavior of certain classes of one-parameter quantum dynamical semigroups. The classes we consider, consist of tensor product channels and of channels with commuting Liouvillians. We introduce the notion of cutoff phenomenon in the setting of quantum information theory, and show how it exemplifies the fact that the convergence of (quantum) stochastic processes is not solely governed by the spectral gap of the transition map. We apply the new methods to show that graph states can be prepared efficiently, albeit not in constant time, by dissipation, and give the exact scaling behavior of the time to stationarity.
In this dissertation we present results for various quantum and stochastic processes. First, we bound separations between the entangled and classical values for several classes of nonlocal t-player games. We show that for many general classes of such games, the entangled winning probability can not be much higher than the classical one. The proofs use semidefinite-programming techniques and hypergraph norms. Next, we study so-called quasirandom properties of graphs, and extend this to the quantum realm. For a certain class of quantum channels we generalize several results on equivalence between different quasirandom properties, using the non-commutative Grothendieck inequality. We also look at methods for sampling random graphs with power-law degree distributions, using Markov Chain switching methods. Using these samples we present a conjecture on the asymptotic number of triangles in the uniform random graph model. Next we study a class of stochastic processes on graphs that include the discrete Bak-Sneppen process and the contact process. These processes exhibit a phenomenon which we call the Power Light Cone, that has been used in the physics community for a long time but had not yet been proven. We provide this proof, which allows for numerical computations that estimate critical exponents. Finally, we consider a quantum version of Pascal's triangle. When Pascal's triangle is plotted modulo 2, the Sierpinski triangle appears. We prove that when the quantum version of this triangle is plotted modulo 3, a fractal known as the Sierpinski carpet emerges.
A framework for finite-dimensional quantum Markov chains on Hilbert spaces is introduced. Quantum Markov chains generalize both classical Markov chains with possibly hidden states and existing models of quantum walks on finite graphs. Quantum Markov chains are based on Markov operations that may be applied to quantum systems and include quantum measurements, for example. It is proved that quantum Markov chains are asymptotically stationary and hence possess ergodic and entropic properties. With a quantum Markov chain one may associate a quantum Markov process, which is a stochastic process in the classical sense. Generalized Markov chains allow a representation with respect to a generalized Markov source model with definite (but possibly hidden) states relative to which observables give rise to classical stochastic processes. It is demonstrated that this model allows for observables to violate Bell’s inequality.
Tight Contraction Rates for Primitive Channels under Quantum fff-Divergences
Data-processing inequalities capture the phenomenon that two probability distributions can only become less distinguishable under any common post-processing. For more fine-grained inequalities, one turns to strong data-processing inequality (SDPI) constants, which give the strongest inequalities for a given channel and reference state for a fixed measure of distinguishability. These quantities have been used to quantify the rate at which time-homogeneous Markov chains contract towards a fixed point both in the classical and quantum setting. In this work, we establish that quantum fff-divergences satisfy a local reverse Pinsker inequality, which implies the asymptotic contraction rate of a primitive channel to its stationary state is upper bounded by the SDPI constant of any non-commutative χ2χ^2χ2-divergence. Using quantum-detailed balance, we establish a sufficient condition for these bounds to be tight. Finally, we apply these results to Petz, Matsumoto, and Hirche-Tomamichel fff-divergences, establishing new and strengthening previously known results.