Search algorithm on strongly regular graph by lackadaisical quantum walk

doi:10.1088/1751-8121/ad3055

	Search algorithm on strongly regular graph by lackadaisical quantum walk
	Peng, Fangjie 1,2; Li, Meng 1,2; Sun, Xiaoming 1,2
	2024-03-29
发表期刊	JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
ISSN	1751-8113
卷号	57 期号:13 页码:16
摘要	Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.
关键词	strongly regular graph quantum search discrete-time quantum walk
DOI	10.1088/1751-8121/ad3055
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809[62325210] ; National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809[62301531] ; National Natural Science Foundation of China[XDB28000000] ; Strategic Priority Research Program of Chinese Academy of Sciences[2022M723209] ; China Postdoctoral Science Foundation
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary ; Physics, Mathematical
WOS记录号	WOS:001187440200001
出版者	IOP Publishing Ltd
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38755
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Meng
作者单位	1.Chinese Acad Sci, State Key Lab Processors, Inst Comp Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Wuhan 100049, Peoples R China
推荐引用方式 GB/T 7714	Peng, Fangjie,Li, Meng,Sun, Xiaoming. Search algorithm on strongly regular graph by lackadaisical quantum walk[J]. JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL,2024,57(13):16.
APA	Peng, Fangjie,Li, Meng,&Sun, Xiaoming.(2024).Search algorithm on strongly regular graph by lackadaisical quantum walk.JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL,57(13),16.
MLA	Peng, Fangjie,et al."Search algorithm on strongly regular graph by lackadaisical quantum walk".JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 57.13(2024):16.