Quantum walk mixing is faster than classical on periodic lattices

Abstract

This work focuses on the quantum mixing time, which is crucial for efficient quantum sampling and algorithm performance. We extend Richter's previous analysis of continuous time quantum walks on the periodic lattice ${\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}\times \cdots \times {\mathbb{Z}}_{n_d}$, allowing for non-identical dimensions $n_i$. We present two quantum walks that achieve faster mixing compared to classical random walks. The first is a coordinate-wise quantum walk with a mixing time of $O\left(\left(\sum {i=1}^d{n}_i\right)\log (d/\epsilon )\right)$ and $O(d\log (d/\epsilon ))$ measurements. The second is a continuous-time quantum walk with $O(\log (1/\epsilon ))$ measurements, conjectured to have a mixing time of $O\left({\sum }_{i=1}^d{n}_i(\log (n_1){)}^2\log (1/\epsilon )\right)$. Our results demonstrate a quadratic speedup over classical mixing times on the generalized periodic lattice. We provide analytical evidence and numerical simulations supporting the conjectured faster mixing time. The ultimate goal is to prove the general conjecture for quantum walks on regular graphs.

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• Almost uniform sampling via quantum walks
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
• Large-scale full-programmable quantum walk and its applications
• Universal approach to deterministic spatial search via alternating quantum walks

Cited by in corpus (1)

• Quantum walks as thermalizations, with application to fullerene graphs