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.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, 20241 citation

Continuous-Time Quantum Walks on the Symmetric Group

Heath Gerhardt, John Watrous

Lecture notes in computer scienceJan 1, 200374 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.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.15693Communications in Theoretical PhysicsSep 26, 20240 citations

Quantum Stochastic Walks on the Permutation Group

Feng He, Arthur Hutsalyuk, Giuseppe Mussardo +1 more

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

cond-mat.stat-mechCross-listedarXiv:2609.13387Sep 15, 20260 citations

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.