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}.

Related papers

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•1 citation

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 inspired by the analysis of Kac's walk, 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

From Ehrenfest to Heisenberg scales: a hierarchy of mixing times for a phase-randomized quantum baker walk

Amir Sepehri

The quantum baker map is a standard model of quantum chaos, but rigorous analysis of how it spreads random perturbations remains difficult. Following the repeated ``baker plus refreshed diagonal perturbation'' architecture of Schack and Caves, we study a tractable strong-noise model based on the Balazs--Voros quantization: at each time step, its unitary propagator is followed by a diagonal unitary whose entries are independent and uniform on the unit circle. The resulting random propagator is a structured random walk on $\U(N)$, $N=2^k$. We quantify how quickly the baker dynamics spreads this basis-local randomness at three levels: ensemble means, two-copy statistics, and the full law of the accumulated propagator. The walk becomes an exact unitary $1$-design at time $k+1$, while its fixed-accuracy $2$-design mixing time is $Θ(\log N)$. Thus the induced state ensembles reproduce Haar means and two-copy statistics on the Ehrenfest scale. The full law mixes much more slowly. A phase-adapted path coupling gives normalized Wasserstein mixing in $O_\varepsilon(N)$ steps, whereas metric-entropy and Haar small-ball estimates give an $Ω_\varepsilon(N/\log N)$ lower bound and asymptotically maximal distance at every $t=o(N/\log N)$. The law remains singular with respect to Haar measure for every $t

arXiv:2609.32067•Sep 25, 2026•0 citations

Efficient unitary designs and pseudorandom unitaries from permutations

Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão +3 more

In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{Ω(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.

arXiv:2404.16751•Apr 25, 2024•4 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 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•9 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}.
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.
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 inspired by the analysis of Kac's walk, 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.
The quantum baker map is a standard model of quantum chaos, but rigorous analysis of how it spreads random perturbations remains difficult. Following the repeated ``baker plus refreshed diagonal perturbation'' architecture of Schack and Caves, we study a tractable strong-noise model based on the Balazs--Voros quantization: at each time step, its unitary propagator is followed by a diagonal unitary whose entries are independent and uniform on the unit circle. The resulting random propagator is a structured random walk on $\U(N)$, N=2kN=2^kN=2k. We quantify how quickly the baker dynamics spreads this basis-local randomness at three levels: ensemble means, two-copy statistics, and the full law of the accumulated propagator. The walk becomes an exact unitary 111-design at time k+1k+1k+1, while its fixed-accuracy 222-design mixing time is Θ(log⁡N)Θ(\log N)Θ(logN). Thus the induced state ensembles reproduce Haar means and two-copy statistics on the Ehrenfest scale. The full law mixes much more slowly. A phase-adapted path coupling gives normalized Wasserstein mixing in Oε(N)O_\varepsilon(N)Oε​(N) steps, whereas metric-entropy and Haar small-ball estimates give an Ωε(N/log⁡N)Ω_\varepsilon(N/\log N)Ωε​(N/logN) lower bound and asymptotically maximal distance at every t=o(N/log⁡N)t=o(N/\log N)t=o(N/logN). The law remains singular with respect to Haar measure for every $t
In this work we give an efficient construction of unitary kkk-designs using O~(k⋅poly(n))\tilde{O}(k\cdot poly(n))O~(k⋅poly(n)) quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over S(N)S(N)S(N) to random unitaries over U(N)U(N)U(N) for N=2nN=2^nN=2n. In particular, we show that products of exponentiated sums of S(N)S(N)S(N) permutations with random phases approximately match the first 2Ω(n)2^{Ω(n)}2Ω(n) moments of the Haar measure. By substituting either O~(k)\tilde{O}(k)O~(k)-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-NNN) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-NNN by interpolating from the much simpler large-NNN limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-NNN expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension NNN.
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.
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.