|
Seminar Announcement Date: Wednesday, 23 April 2025 Time: 2.15 PM Venue: Seminar Hall Quantum walk algorithm on periodic lattices and Cayley graphs Shyam Dhamapurkar Chennai Mathematical Institute. 23-03-25 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 and potential open problems.
|
