Title  Quantum walk mixing is faster than classical on periodic lattices 
Author  
Corresponding Author  Dhamapurkar, Shyam 
Publication Years  20231115

DOI  
Source Title  
ISSN  03784371

EISSN  18732119

Volume  630 
Abstract  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 ddimensional periodic lattice Z(n)xZ(n)x...xZ(n). We extend this analysis to the periodic lattice L = Zn1 x Zn2 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 coordinatewise 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 continuoustime 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 continuoustime 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. 
Keywords  
URL  [Source Record] 
Indexed By  
Language  English

SUSTech Authorship  First
; Corresponding

Funding Project  KeyArea Research and Development Program of GuangDong Province[2018B030326001]
; Shenzhen Science and Technology Program[KQTD20200820113010023]

WOS Research Area  Physics

WOS Subject  Physics, Multidisciplinary

WOS Accession No  WOS:001088706300001

Publisher  
ESI Research Field  PHYSICS

Data Source  Web of Science

Citation statistics  
Document Type  Journal Article 
Identifier  http://kc.sustech.edu.cn/handle/2SGJ60CL/582776 
Department  Institute for Quantum Science and Engineering 
Affiliation  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 
First Author Affilication  Institute for Quantum Science and Engineering 
Corresponding Author Affilication  Institute for Quantum Science and Engineering 
First Author's First Affilication  Institute for Quantum Science and Engineering 
Recommended Citation GB/T 7714 
Dhamapurkar, Shyam,Deng, XiuHao. Quantum walk mixing is faster than classical on periodic lattices[J]. PHYSICA ASTATISTICAL MECHANICS AND ITS APPLICATIONS,2023,630.

APA 
Dhamapurkar, Shyam,&Deng, XiuHao.(2023).Quantum walk mixing is faster than classical on periodic lattices.PHYSICA ASTATISTICAL MECHANICS AND ITS APPLICATIONS,630.

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

Files in This Item:  
There are no files associated with this item. 
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment