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.
AI Summary
The paper asks whether many-particle KMP redistribution processes mix on essentially the single-particle timescale, independently of particle number, and whether this can characterize Haar-like behavior of parallel Kac walks.
For discrete KMP on any connected $d$-vertex graph, it proves the total-variation mixing bound $O(\gamma^{-1}(\log d+\log(1/\varepsilon)))$, uniformly in the number $t$ of particles, where $\gamma$ is the single-particle spectral gap. At constant accuracy, this is at most an $O(\log d)$ overhead relative to single-particle mixing. The bound transfers to continuous KMP. Identifying coordinate hit-and-run on the standard simplex with continuous KMP on a star gives $O(n(\log n+\log(1/\varepsilon)))$ steps from any initial distribution, improving the cited $\widetilde O(n^3)$ bound.
The analysis conditions on shared random redistribution parameters, making labeled particles evolve independently. Two-particle dynamics control covariance contraction, initially yielding a $\log t$ dependence; a two-stage exact coupling removes it for the unlabeled process. The same framework gives parallel KMP mixing in $O(\log d+\log(1/\varepsilon))$ steps. An exact reduction of parallel Kac twirling to a partition-resampling chain then establishes the same convergence bound to Haar twirling on the symmetric subspace, uniformly in moment order $t$, including ancillary systems.
Assuming quantum-secure one-way functions, this yields scalable pseudorandom unitaries only against non-adaptive queries supported on the symmetric subspace. Full-space or adaptive security is not established; extensions to other representation sectors and control of inter-sector coherences remain open.
Little sign of AI-generated textAI use disclosed
In preparation of this version, OpenAI's GPT-6 Astra was used to further scrutinize the proofs and polish the exposition of this manuscript.
Error found: The proof of Lemma lem:isomorphism incorrectly counts degree-at-most-t monomials in d variables and calls their restrictions a basis on the simplex; using d−1 independent coordinates repairs the dimension argument.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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(logd) 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 O(n3) [KV26] to 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(logd+log(1/ε)) repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of (Cd)⊗t to error ε, 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.
The paper asks whether many-particle KMP redistribution processes mix on essentially the single-particle timescale, independently of particle number, and whether this can characterize Haar-like behavior of parallel Kac walks.
For discrete KMP on any connected d-vertex graph, it proves the total-variation mixing bound O(γ−1(logd+log(1/ε))), uniformly in the number t of particles, where γ is the single-particle spectral gap. At constant accuracy, this is at most an O(logd) overhead relative to single-particle mixing. The bound transfers to continuous KMP. Identifying coordinate hit-and-run on the standard simplex with continuous KMP on a star gives O(n(logn+log(1/ε))) steps from any initial distribution, improving the cited O(n3) bound.
The analysis conditions on shared random redistribution parameters, making labeled particles evolve independently. Two-particle dynamics control covariance contraction, initially yielding a logt dependence; a two-stage exact coupling removes it for the unlabeled process. The same framework gives parallel KMP mixing in O(logd+log(1/ε)) steps. An exact reduction of parallel Kac twirling to a partition-resampling chain then establishes the same convergence bound to Haar twirling on the symmetric subspace, uniformly in moment order t, including ancillary systems.
Assuming quantum-secure one-way functions, this yields scalable pseudorandom unitaries only against non-adaptive queries supported on the symmetric subspace. Full-space or adaptive security is not established; extensions to other representation sectors and control of inter-sector coherences remain open.
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 Θ(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(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 k orthonormal quantum states. We prove that, for any 1≤k<d, after O((k+logd)log(d/ε)) steps, the joint distribution of the k output states is ε-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 Vd,k={X∈Cd×k:X†X=Ik}, we show that the parallel Kac's walk mixes rapidly on Vd,k, with both Wasserstein and total variation mixing times bounded by 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}.
Most approximation algorithms for #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. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain P on 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 Znd is O(ndlogd), 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 (the obvious lower bound) up to at most a logarithmic factor.
Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the n-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs Kn, the continuous-time quantum walk is neither instantaneous (except for n=2,3,4) nor average uniform mixing (except for n=2). We explore two natural {\em group-theoretic} generalizations of the n-cube as a G-circulant and as a bunkbed $G \rtimes \Int_{2}$, where G is a finite group. Analyses of these classes suggest that the n-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.
Quantum walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems.These links and acceleration claims have been made with various levels of detail.Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph.Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain.We here show that the same speedup can be attained with a classical process, if a similar classical coin is added.We establish a precise correspondence between the mixing performance of quantum walks and such "lifted walks" for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time.We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design.However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster.
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.
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.