Quantum Walk Mixing Is Faster Than Classical On Periodic Lattices | Awesome Quantum Computing Papers

Quantum Walk Mixing Is Faster Than Classical On Periodic Lattices

Shyam Dhamapurkar, Xiu-Hao Deng · Physica A Statistical Mechanics and its Applications Volume 630 15 November 2023 129252 · 2023

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 \dots \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.

Explore more on:
Quantum Algorithms
Similar Work
Loading…