Quantum walk mixing is faster than classical on periodic lattices

Dhamapurkar, Shyam1; Deng, Xiu-Hao1,2,3

2023-11-15

10.1016/j.physa.2023.129252

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS   Impact Factor & Quartile

0378-4371

1873-2119

The quantum mixing time is a critical factor affecting the efficiency of quantum sampling and algorithm performance. It refers to the minimum time required for a quantum walk to approach its limiting distribution closely and has implications across the areas of quantum computation. This work focuses on the continuous time quantum walk mixing on a regular graph, evolving according to the unitary map U = e(t (A) over bart), where the Hamiltonian (A) over bar is the normalized adjacency matrix of the graph. In [Physical Review A 76, 042306 (2007).], Richter previously showed that this walk mixes in time O(nd log (d) log (1/epsilon)) with O(log (d) log (1/epsilon.)) intermediate measurements when the graph is the d-dimensional periodic lattice Z(n)xZ(n)x...xZ(n). We extend this analysis to the periodic lattice L = Zn-1 x Zn-2 x ... x Z(nd), relaxing the assumption that n(t) are identical. We provide two quantum walks on periodic lattices that achieve faster mixing compared to classical random walks: 1. A coordinate-wise quantum walk that mixes in o((Sigma(d)(t=1) n(t)) log (d/epsilon)) time with O(d. log(d/epsilon)) measurements. 2. A continuous-time quantum walk with O(log(1/epsilon)) measurements that conjecturally mixes in O(Sigma(d)(t=1) n(t) (log(n(1)))(2) log(1/epsilon)) time. Our results demonstrate a quadratic speedup over the classical mixing time O(dn(1)(2) log(d/epsilon)) on the generalized periodic lattice L. We have provided analytical evidence and numerical simulations to support the conjectured faster mixing time of the continuous-time quantum walk algorithm. Making progress towards proving the general conjecture that quantum walks on regular graphs mix in O(delta(-1/2) log(N) log(N) log(1/epsilon)) time, where delta. is the spectral gap and.. is the number of vertices.

Continuous time quantum walks Periodic lattices Mixing time

SCI

English

First ; Corresponding

Key-Area Research and Development Program of Guang-Dong Province[2018B030326001] ; Shenzhen Science and Technology Program[KQTD20200820113010023]

Physics

Physics, Multidisciplinary

WOS:001088706300001

ELSEVIER

PHYSICS

Web of Science

1.Southern Univ Sci & Technol, Shenzhen Inst Quantum Sci & Engn SIQSE, Shenzhen, Peoples R China
2.Int Quantum Acad SIQA, Shenzhen, Peoples R China
3.Hefei Natl Lab, Shenzhen Branch, Shenzhen, Peoples R China

Dhamapurkar, Shyam,Deng, Xiu-Hao. Quantum walk mixing is faster than classical on periodic lattices[J]. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,2023,630.

Dhamapurkar, Shyam,&Deng, Xiu-Hao.(2023).Quantum walk mixing is faster than classical on periodic lattices.PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,630.

Dhamapurkar, Shyam,et al."Quantum walk mixing is faster than classical on periodic lattices".PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 630(2023).