Related papers: Quantum Stochastic Walks on the Permutation Group

Quantum Stochastic Walks on the Permutation Group

URL: http://arxiv.org/abs/2609.13387v1
Date: Fri, 11 Sep 2026 18:00:09 GMT
Title: Quantum Stochastic Walks on the Permutation Group
Abstract summary: We prove that quantum coherence can only decrease the distance from the uniform distribution in a computational basis.<n>An analysis of the slowest mode yields a criterion for the coupling strength required to produce an appreciable speedup.<n>Our results illustrate how coherence and dissipation can cooperate in the emergence of randomness in walks on permutation groups.
Score: 1.1327508153380308
License: http://creativecommons.org/licenses/by/4.0/
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 $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.

Related papers

Identifying quantum coherence in quantum annealers [37.067444579637076]
We use many-body coherent oscillations (MBCO) as a diagnostic for the identification of system-wide coherence in analog quantum simulators.<n>This work gives a general roadmap for the search for quantum coherence in noisy, large-scale quantum platforms.
arXiv Detail & Related papers (2026-02-24T20:39:41Z)
Quantum-driven sampling of the quasi-uniform distribution via quantum walks [0.5097809301149341]
We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution.<n>We show that when the quantum walk parameters, such as the coin operator and initial state, satisfy the conditions of the ergodic theorem for random walks on finite groups, the resulting sequence convergesally to the uniform distribution.
arXiv Detail & Related papers (2025-11-11T14:26:18Z)
Average-case quantum complexity from glassiness [45.57609001239456]
Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
arXiv Detail & Related papers (2025-10-09T17:37:33Z)
Speeding up quantum Markov processes through lifting [15.031583573428481]
We generalize the concept of non-reversible lifts for diffusion reversible processes initiated by Eberle and Lorler (2024) to quantum Markov dynamics.<n>We prove that the $L2$ convergence rate of the lifted process is bounded above by the square root of the spectral gap of its overdamped dynamics.
arXiv Detail & Related papers (2025-05-18T01:19:08Z)
Quantum Dissipative Search via Lindbladians [0.0]
We analyze a purely dissipative quantum random walk on an unstructured classical search space.<n>We show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks.<n>We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search.
arXiv Detail & Related papers (2024-07-16T14:39:18Z)
Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits [15.89518426969296]
We investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed.
arXiv Detail & Related papers (2024-05-21T14:42:39Z)
Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
This paper advances the general understanding of quantum walk mixing on Cayley graphs.<n>It highlights the improved mixing time achieved by continuous-time quantum walks on $D_2n$.<n>This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
arXiv Detail & Related papers (2023-12-25T11:21:55Z)
Non-uniform Mixing of Quantum Walks on the Symmetric Group [0.0]
We analyze the spectra of the Szegedy walk operators using the representation theory of the symmetric group. Our techniques are general, and we believe they can be applied to derive similar analytical results for other non-commutative groups.
arXiv Detail & Related papers (2023-11-06T03:17:36Z)
Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
arXiv Detail & Related papers (2023-10-17T17:55:32Z)
Quantum dynamics corresponding to chaotic BKL scenario [62.997667081978825]
Quantization smears the gravitational singularity avoiding its localization in the configuration space. Results suggest that the generic singularity of general relativity can be avoided at quantum level.
arXiv Detail & Related papers (2022-04-24T13:32:45Z)
Unification of Random Dynamical Decoupling and the Quantum Zeno Effect [68.8204255655161]
We show that the system dynamics under random dynamical decoupling converges to a unitary with a decoupling error that characteristically depends on the convergence speed of the Zeno limit. This reveals a unification of the random dynamical decoupling and the quantum Zeno effect.
arXiv Detail & Related papers (2021-12-08T11:41:38Z)
From Classical to quantum stochastic process [0.0]
We construct quantum analogs starting from classical processes, by replacing random which path decisions with superpositions of all paths. In spite of their transient nature, these coherences can change the scaling behavior of classical observables.
arXiv Detail & Related papers (2021-10-07T17:52:08Z)
Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers [0.0]
We show how to tackle the problem using a suitably quantum computer. We propose a hybrid quantum-classical sampling scheme to escape local minima.
arXiv Detail & Related papers (2021-08-25T18:04:52Z)
From stochastic spin chains to quantum Kardar-Parisi-Zhang dynamics [68.8204255655161]
We introduce the asymmetric extension of the Quantum Symmetric Simple Exclusion Process. We show that the time-integrated current of fermions defines a height field which exhibits a quantum non-linear dynamics.
arXiv Detail & Related papers (2020-01-13T14:30:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.