Quantum walk mixing is faster than classical on periodic lattices

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}_n1times mathbb{Z}_n2times dots times mathbb{Z}_nd, 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 Oleft\(left(sum{i=1}^d n_i right\) log{(d/ε)}right) and O\(d log(d/ε\)) measurements. The second is a continuous-time quantum walk with O\(log(1/ε\)) measurements, conjectured to have a mixing time of Oleft\(sum_i=1^d n_i(log(n₁\))² log(1/ε)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.