Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds
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 Θ(dlog 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≤ k < d, after O ((k+log d)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∈ℂd× 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+log d)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}.
Related
- Rapid mixing of quantum spin chains at any finite temperature
- Rapid mixing for Gibbs samplers for quantum spin systems with all-to-all interactions
- Is rapid mixing stable?
- Spectral Analysis Beyond the Spectral Gap: Rapid Mixing of Quantum Gibbs Samplers in One Dimension
- Rapid mixing of Gibbs samplers via quantum Dobrushin--Shlosman conditions
BibTeX
@misc{chen2026rapid,
title = {{Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds}},
author = {Qian Chen and Minglong Qin and Fang Song and Penghui Yao and Mingnan Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37999},
eprint = {2609.37999},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37999},
}
RIS
TY - UNPB
TI - Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds
AU - Qian Chen
AU - Minglong Qin
AU - Fang Song
AU - Penghui Yao
AU - Mingnan Zhao
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37999
UR - https://arxiv.org/abs/2609.37999
AB - 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 Θ(dlog 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≤ k < d, after O ((k+log d)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 V_d,k={X∈ℂ^d× k:X^† 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 ((k+log d)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}.
ER -