Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with $n^2 D(G)$ vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph $G$ with $n$ vertices, where $D(G)$ is the diameter of $G$ . Moreover, the mixing time of this chain is $D(G)$ timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in $n$ . As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with $n^2 D(G)$ vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph $G$ with $n$ vertices, where $D(G)$ is the diameter of $G$. Moreover, the mixing time of this chain is $D(G)$ timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in $n$. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).

arXiv:1712.02318Dec 6, 20171 citation

Average mixing of continuous quantum walks

Chris D. Godsil

Journal of Combinatorial Theory Series AJun 18, 201335 citations

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.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.11895Physical Review AAug 25, 202019 citations

Quantum speedup of classical mixing processes

Peter C. Richter

Most approximation algorithms for # $\mathit{P}$ -complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\pi}$ over a large set $\mathcal{S}$ . This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain $P$ on $\mathcal{S}$ with stationary distribution $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of $P$ , is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of $P$ and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice ${\mathbb{Z}}_{n}^{d}$ is $O(nd\text{ }\text{log}\text{ }d)$ , which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of ${\mathbb{Z}}_{n}^{d}$ (the obvious lower bound) up to at most a logarithmic factor.Most approximation algorithms for #$\mathit{P}$-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\pi}$ over a large set $\mathcal{S}$. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain $P$ on $\mathcal{S}$ with stationary distribution $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of $P$, is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of $P$ and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice ${\mathbb{Z}}_{n}^{d}$ is $O(nd\text{ }\text{log}\text{ }d)$, which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of ${\mathbb{Z}}_{n}^{d}$ (the obvious lower bound) up to at most a logarithmic factor.

arXiv:quant-ph/0609204Physical Review AOct 4, 200782 citations

n^2 D(G)

vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph

G

with

n

vertices, where

D(G)

is the diameter of

G

. Moreover, the mixing time of this chain is

D(G)

timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in

n

. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).

Most approximation algorithms for #

\mathit{P}

-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\pi}$ over a large set

\mathcal{S}

. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain

P

\mathcal{S}

with stationary distribution $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of

P

, is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of

P

and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice

{\mathbb{Z}}_{n}^{d}

O(nd\text{ }\text{log}\text{ }d)

, which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of

{\mathbb{Z}}_{n}^{d}

(the obvious lower bound) up to at most a logarithmic factor.