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:2311.02843 · Linear Algebra and its Applications

Non-uniform mixing of quantum walks on the symmetric group

Avah Banerjee

Published Apr 13, 2026• 0 citations
arXivHTMLPDF
DOI
10.1016/j.laa.2026.04.006

Related papers

Discrete quantum walks on the symmetric group

Avah Banerjee

arXiv:2203.15148•Quantum Studies Mathematics and Foundations•May 2, 2024•6 citations

ϵ\epsilon ϵ-Uniform mixing in discrete quantum walks

Hanmeng Zhan

arXiv:2311.18797•Journal of Algebraic Combinatorics•Jun 1, 2025•3 citations

Continuous-Time Quantum Walks on the Symmetric Group

Heath Gerhardt, John Watrous

Lecture notes in computer science•Jan 1, 2003•71 citations

Discrete-time quantum walks on the symmetric group (quantum card shuffling)

Zlatko Dimcovic, Yevgeniy Kovchegov

Bulletin of the American Physical Society•Feb 29, 2012•0 citations

Quantum Walks Advantage on the Dihedral Group for Uniform Sampling Problem

Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh +1 more

Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Jul 1, 2024•0 citations

Quantum walks advantage on the dihedral group for uniform sampling problem

Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh +1 more

Abstract Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D 2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω ( n 2 log ( 1 / 2 ϵ ) ) , the continuous-time quantum walk mixing time on D 2n is of order O ( n ( log n ) 5 log ( 1 / ϵ ) ) , achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D 2n . This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.

arXiv:2312.15693•Communications in Theoretical Physics•Sep 26, 2024•0 citations
Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
Abstract Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D 2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω ( n 2 log ( 1 / 2 ϵ ) ) , the continuous-time quantum walk mixing time on D 2n is of order O ( n ( log n ) 5 log ( 1 / ϵ ) ) , achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D 2n . This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.