Quantum walk algorithm on periodic lattices and Cayley graphs
- Dr. Shyam Dhamapurkar, SUS Tech
- Time: 2024-12-23 15:00
- Host: Dr. Tongyang Li
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
Quantum walk-based algorithms have garnered significant attention in quantum computation due to their potential applications in search problems, quantum transport properties, and speedups in query-based models. In this talk, we delve into quantifying the mixing time of quantum walks on generalized periodic lattices and Cayley graphs of the Dihedral group ($D_{2n}$).
We explore two versions of quantum walks on periodic lattices, establishing a mixing time complexity of approximately $O\Big(\Big(\sum\limits_{i=1}^{d} n_i \Big) \log{(d/\epsilon)}\Big)$ with $O(d \log(d/\epsilon))$ measurements. Additionally, we propose an improved mixing time of $O(\sum\limits_{i=1}^d n_i(\log(n_1))^2 \log(1/\epsilon))$ with a complexity of $O(\log{(1/\epsilon)})$.
For Cayley graphs associated with $D_{2n}$, we analyze continuous-time quantum walks with repeated measurements, revealing a mixing time of approximately $O(n (\log{(n)})^5)$ with $O(\log{(1/\epsilon)})$ iterations. This demonstrates a quadratic advantage over the classical mixing time lower bound of $\Omega(n^2 \log{(1/2\epsilon)})$, supported by insights into eigenvalue gaps of the Cayley graph.
Our findings underscore the promising avenues for investigating the mixing time of quantum walks on regular and Cayley graphs of non-abelian groups, highlighting their relevance in quantum algorithm design and analysis.
Biography
Shyam Dhamapurkar completed his PhD in physics from Institute for quantum science and engineering, SUSTech, Shenzhen, under the supervision Xiu-hao Deng and Oscar Dahlsten. He did master’s study at Savitribai Phule Pune University specializing in industrial mathematics with computer applications. He majored in Mathematics and obtained a Bachelor of Science degree. During the PhD program, he was a visiting scholar at the Centre for Quantum Technologies, NUS, Singapore, and the University of Strathclyde, Scotland. His primary research interests lie in quantum algorithms, particularly focused on quantum walks, as well as exploring the set membership problem using quantum probes.