Quantum Walks Advantage on the Dihedral Group for Uniform Sampling Problem
Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh, Xiu–Hao Deng · 2024
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.