Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.15693 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929608665858048 |
|---|---|
| author | Dhamapurkar, Shyam Dang, Yuhang Wagh, Saniya Deng, Xiu-Hao |
| author_facet | Dhamapurkar, Shyam Dang, Yuhang Wagh, Saniya Deng, Xiu-Hao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15693 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum walks advantage on the dihedral group for uniform sampling problem Dhamapurkar, Shyam Dang, Yuhang Wagh, Saniya Deng, Xiu-Hao Quantum Physics 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. |
| title | Quantum walks advantage on the dihedral group for uniform sampling problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2312.15693 |