Quantum Stochastic Walks on the Permutation Group
Abstract
How rapidly does order give way to randomness, and can quantum coherence accelerate this process? We address these questions through the paradigmatic problem of card shuffling, formulated as a random walk on the symmetric group Sn. We first recast the random-transposition walk studied by Diaconis and Shahshahani, as well as more general walks generated by conjugacy classes of Sn, in continuous time. We then identify the transition matrix of each classical walk with a permutation Hamiltonian generating a corresponding unitary quantum walk. Purely unitary evolution, however, does not generically converge to the uniform distribution in the classical sense of mixing: coherence preserves information rather than erasing it. We therefore embed the problem into a quantum stochastic walk, where coherent dynamics competes with the dissipative process responsible for classical mixing. In this setting, quantum coherence assists randomization. We prove that it can only decrease the distance from the uniform distribution in the computational basis and can therefore accelerate mixing. An analysis of the slowest mode yields a criterion for the coupling strength required to produce an appreciable speedup. Finally, numerical results reveal a scaling collapse of the ratio between quantum and classical mixing times onto a simple one-parameter form. Our results illustrate how coherence and dissipation can cooperate in the emergence of randomness in walks on permutation groups.
Related
- Extremal and global-time statistics of sluggish random walks with stochastic resetting
- Real-Space renormalization for the drawups and drawdowns of stochastic trajectories: universality classes for diffusion processes and random walks via the scale function
- Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
- Spectral Criterion for Disorder-Free Localization of Quantum Walks on Hypercube: QBN Approach
- The equivalence of quantum deletion and insertion errors on permutation-invariant codes
BibTeX
@misc{he2026quantum,
title = {{Quantum Stochastic Walks on the Permutation Group}},
author = {Feng He and Arthur Hutsalyuk and Giuseppe Mussardo and Andrea Stampiggi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13387},
eprint = {2609.13387},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13387},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Stochastic Walks on the Permutation Group
AU - Feng He
AU - Arthur Hutsalyuk
AU - Giuseppe Mussardo
AU - Andrea Stampiggi
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.13387
UR - https://arxiv.org/abs/2609.13387
AB - How rapidly does order give way to randomness, and can quantum coherence accelerate this process? We address these questions through the paradigmatic problem of card shuffling, formulated as a random walk on the symmetric group S_n. We first recast the random-transposition walk studied by Diaconis and Shahshahani, as well as more general walks generated by conjugacy classes of S_n, in continuous time. We then identify the transition matrix of each classical walk with a permutation Hamiltonian generating a corresponding unitary quantum walk. Purely unitary evolution, however, does not generically converge to the uniform distribution in the classical sense of mixing: coherence preserves information rather than erasing it. We therefore embed the problem into a quantum stochastic walk, where coherent dynamics competes with the dissipative process responsible for classical mixing. In this setting, quantum coherence assists randomization. We prove that it can only decrease the distance from the uniform distribution in the computational basis and can therefore accelerate mixing. An analysis of the slowest mode yields a criterion for the coupling strength required to produce an appreciable speedup. Finally, numerical results reveal a scaling collapse of the ratio between quantum and classical mixing times onto a simple one-parameter form. Our results illustrate how coherence and dissipation can cooperate in the emergence of randomness in walks on permutation groups.
ER -