Quantum walk mixing is faster than classical on periodic lattices

Shyam Dhamapurkar and Xiu-Hao Deng

Physica A: Statistical Mechanics and its Applications, 2023, vol. 630, issue C

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=eiĀt, where the Hamiltonian Ā 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(ndlog(d)log(1/ϵ)) with O(log(d)log(1/ϵ)) intermediate measurements when the graph is the d−dimensional periodic lattice Zn×Zn×⋯×Zn. We extend this analysis to the periodic lattice L=Zn1×Zn2×⋯×Znd, relaxing the assumption that ni 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((∑i=1dni)log(d/ϵ)) time with O(dlog(d/ϵ)) measurements. 2. A continuous-time quantum walk with O(log(1/ϵ)) measurements that conjecturally mixes in O(∑i=1dni(log(n1))2log(1/ϵ)) time. Our results demonstrate a quadratic speedup over the classical mixing time O(dn12log(d/ϵ)) 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(δ−1/2log(N)log(1/ϵ)) time, where δ is the spectral gap and N is the number of vertices.

Keywords: Continuous time quantum walks; Periodic lattices; Mixing time (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437123008075
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:630:y:2023:i:c:s0378437123008075

DOI: 10.1016/j.physa.2023.129252

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().