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

arXiv:2609.37999

Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds

Qian Chen, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

Abstract

Kac's walk is a classical local random walk whose action on a single real unit vector in dimension $d$ mixes in total variation in $Θ(d\log d)$ sequential steps~\cite{PS17}. Lu, Qin, Song, Yao, and Zhao introduced a parallel version of Kac's walk that mixes a single quantum state in $O(\log d)$ rounds~\cite{LQSY+26}. After discretizing the randomness and replacing it by suitable pseudorandom primitives, this parallel walk gives rise to pseudorandom state scramblers, and was subsequently shown to yield pseudorandom unitaries~\cite{LQSY+25}. We study what happens when the parallel Kac's walk acts simultaneously on $k$ orthonormal quantum states. We prove that, for any $1\leq k < d$, after $O\!\left((k+\log d)\log(d/\varepsilon)\right)$ steps, the joint distribution of the $k$ output states is $\varepsilon$-close, in both Wasserstein and total variation distance, to that obtained by applying a common Haar-random unitary to the same inputs. This generalizes the dispersing property of the parallel Kac's walk from a single quantum state to multiple orthonormal quantum states. Equivalently, viewing an ordered collection of $k$ orthonormal states as a point on the complex Stiefel manifold $V_{d,k}=\{X\in\mathbb C^{d\times k}:X^\dagger X=I_k\}$, we show that the parallel Kac's walk mixes rapidly on $V_{d,k}$, with both Wasserstein and total variation mixing times bounded by $O\!\left((k+\log d)\log(d/\varepsilon)\right)$. This extends the Wasserstein mixing result of Pillai, Smith, and Vaikuntanathan for the standard Kac's walk on real Stiefel manifolds~\cite{PSV26}.

AI Summary

Parallel Kac’s walk samples a random perfect matching of $d$ coordinates in each round and applies independent Haar-random $\mathrm{SU}(2)$ rotations to the matched pairs. Previous mixing guarantees concerned a single input state. This paper studies its simultaneous action on $k$ orthonormal states, represented by the complex Stiefel manifold $V_{d,k}$, asking when their joint distribution approaches that produced by one common Haar-random unitary. For even $d$ and $1\leq k<d$, it proves mixing in both Wasserstein and total variation distance within $O((k+\log d)\log(d/\varepsilon))$ rounds. The explicit total variation bound is $2^{20}(k+\log d)\log(d/\varepsilon)$. For $d=2^n$, this becomes $O((k+n)(n+\log(1/\varepsilon)))$, giving polynomially many rounds for polynomially many inputs and inverse-exponential error. A corollary gives $O(d\log(d/\varepsilon))$ total variation mixing on $\mathrm{SU}(d)$. The proof first couples nearby frames using optimal pairwise $\mathrm{SU}(2)$ alignments. Maximum-row-norm estimates and local-to-global contraction establish Wasserstein mixing. To obtain total variation convergence, it bounds the surjectivity of the Jacobian mapping rotation sequences to final frames, then constructs a controlled flow adjusting the rotations so nearby walks coalesce while only slightly perturbing the product-Haar distribution. The theorem concerns the ideal continuous-randomness walk, rather than a new discretized or pseudorandom implementation. The stated Stiefel result excludes $k=d$, where determinant conservation prevents mixing to Haar measure on $\mathrm{U}(d)$. Extension to sequential real Kac’s walk, potentially resolving a stated open total variation mixing question, is suggested but not proved.

Likely largely AI-generatedAI use disclosed
OpenAI GPT-6 Astra was used extensively throughout the preparation of this manuscript, including for mathematical exploration, checking proof arguments, drafting, and language polishing.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

A Tale of Two Walks: From Kac to KMP and Back

Qian Chen, Jingcheng Liu, Minglong Qin +4 more

We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the $t$-particle process on any connected $d$-vertex graph is at most $O(\log d)$ times the corresponding single-particle mixing time, uniformly in $t$. As an application, we improve the mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde{O}(n^3)$ [KV26] to $O(n\log n)$, while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb{C}^d)^{\otimes t}$ to error $\varepsilon$, uniformly in all $t$. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the $\log(π_{\min}^{-1})$ dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.

quant-pharXiv:2609.38044•Sep 30, 2026•0 citations

Quantum Walks on the Hypercube

Cristopher Moore, Alexander C. Russell

Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.

arXiv:quant-ph/0104137•Apr 29, 2001•69 citations

Almost uniform sampling via quantum walks

Peter C. Richter

Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.

arXiv:quant-ph/0606202•New Journal of Physics•Mar 22, 2007•54 citations

Quantum Pseudorandom Scramblers

Chuhan Lu, Minglong Qin, Fang Song +2 more

Abstract. Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.

arXiv:2309.08941•SIAM Journal on Computing•Aug 21, 2026•19 citations

Quantum Pseudorandom Primitives Beyond Pseudorandom States

Chuhan Lu

Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.

•Aug 26, 2025•0 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.

arXiv:quant-ph/0609204•Physical Review A•Oct 4, 2007•87 citations
Kac's walk is a classical local random walk whose action on a single real unit vector in dimension ddd mixes in total variation in Θ(dlog⁡d)Θ(d\log d)Θ(dlogd) sequential steps~\cite{PS17}. Lu, Qin, Song, Yao, and Zhao introduced a parallel version of Kac's walk that mixes a single quantum state in O(log⁡d)O(\log d)O(logd) rounds~\cite{LQSY+26}. After discretizing the randomness and replacing it by suitable pseudorandom primitives, this parallel walk gives rise to pseudorandom state scramblers, and was subsequently shown to yield pseudorandom unitaries~\cite{LQSY+25}.
We study what happens when the parallel Kac's walk acts simultaneously on kkk orthonormal quantum states. We prove that, for any 1≤k<d1\leq k < d1≤k<d, after O ⁣((k+log⁡d)log⁡(d/ε))O\!\left((k+\log d)\log(d/\varepsilon)\right)O((k+logd)log(d/ε)) steps, the joint distribution of the kkk output states is ε\varepsilonε-close, in both Wasserstein and total variation distance, to that obtained by applying a common Haar-random unitary to the same inputs. This generalizes the dispersing property of the parallel Kac's walk from a single quantum state to multiple orthonormal quantum states. Equivalently, viewing an ordered collection of kkk orthonormal states as a point on the complex Stiefel manifold Vd,k={X∈Cd×k:X†X=Ik}V_{d,k}=\{X\in\mathbb C^{d\times k}:X^\dagger X=I_k\}Vd,k​={X∈Cd×k:X†X=Ik​}, we show that the parallel Kac's walk mixes rapidly on Vd,kV_{d,k}Vd,k​, with both Wasserstein and total variation mixing times bounded by O ⁣((k+log⁡d)log⁡(d/ε))O\!\left((k+\log d)\log(d/\varepsilon)\right)O((k+logd)log(d/ε)). This extends the Wasserstein mixing result of Pillai, Smith, and Vaikuntanathan for the standard Kac's walk on real Stiefel manifolds~\cite{PSV26}.
Parallel Kac’s walk samples a random perfect matching of ddd coordinates in each round and applies independent Haar-random SU(2)\mathrm{SU}(2)SU(2) rotations to the matched pairs. Previous mixing guarantees concerned a single input state. This paper studies its simultaneous action on kkk orthonormal states, represented by the complex Stiefel manifold Vd,kV_{d,k}Vd,k​, asking when their joint distribution approaches that produced by one common Haar-random unitary.
For even ddd and 1≤k<d1\leq k<d1≤k<d, it proves mixing in both Wasserstein and total variation distance within O((k+log⁡d)log⁡(d/ε))O((k+\log d)\log(d/\varepsilon))O((k+logd)log(d/ε)) rounds. The explicit total variation bound is 220(k+log⁡d)log⁡(d/ε)2^{20}(k+\log d)\log(d/\varepsilon)220(k+logd)log(d/ε). For d=2nd=2^nd=2n, this becomes O((k+n)(n+log⁡(1/ε)))O((k+n)(n+\log(1/\varepsilon)))O((k+n)(n+log(1/ε))), giving polynomially many rounds for polynomially many inputs and inverse-exponential error. A corollary gives O(dlog⁡(d/ε))O(d\log(d/\varepsilon))O(dlog(d/ε)) total variation mixing on SU(d)\mathrm{SU}(d)SU(d).
The proof first couples nearby frames using optimal pairwise SU(2)\mathrm{SU}(2)SU(2) alignments. Maximum-row-norm estimates and local-to-global contraction establish Wasserstein mixing. To obtain total variation convergence, it bounds the surjectivity of the Jacobian mapping rotation sequences to final frames, then constructs a controlled flow adjusting the rotations so nearby walks coalesce while only slightly perturbing the product-Haar distribution.
The theorem concerns the ideal continuous-randomness walk, rather than a new discretized or pseudorandom implementation. The stated Stiefel result excludes k=dk=dk=d, where determinant conservation prevents mixing to Haar measure on U(d)\mathrm{U}(d)U(d). Extension to sequential real Kac’s walk, potentially resolving a stated open total variation mixing question, is suggested but not proved.
We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the ttt-particle process on any connected ddd-vertex graph is at most O(log⁡d)O(\log d)O(logd) times the corresponding single-particle mixing time, uniformly in ttt. As an application, we improve the mixing-time bound for coordinate hit-and-run on the nnn-dimensional standard simplex from O~(n3)\widetilde{O}(n^3)O(n3) [KV26] to O(nlog⁡n)O(n\log n)O(nlogn), while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that O(log⁡d+log⁡(1/ε))O(\log d+\log(1/\varepsilon))O(logd+log(1/ε)) repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of (Cd)⊗t(\mathbb{C}^d)^{\otimes t}(Cd)⊗t to error ε\varepsilonε, uniformly in all ttt. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the log⁡(πmin⁡−1)\log(π_{\min}^{-1})log(πmin−1​) dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.
Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
Abstract. Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.
Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
Most approximation algorithms for #P\mathit{P}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 S\mathcal{S}S. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain PPP on S\mathcal{S}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 PPP, 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 PPP 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 Znd{\mathbb{Z}}_{n}^{d}Znd​ is O(nd log d)O(nd\text{ }\text{log}\text{ }d)O(nd log 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 Znd{\mathbb{Z}}_{n}^{d}Znd​ (the obvious lower bound) up to at most a logarithmic factor.