Lackadaisical discrete-time quantum walk on Johnson graph

doi:10.1016/j.physa.2024.129495

	Lackadaisical discrete-time quantum walk on Johnson graph
	Peng, Fangjie 1,2; Li, Meng 1,2; Sun, Xiaoming 1,2,3
	2024-02-01
发表期刊	PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS
ISSN	0378-4371
卷号	635 页码:16
摘要	Quantum walk is widely used in search problems, and it has an ideal acceleration effect compared with classical algorithm. Suppose there is a marked vertex omega on Johnson graph J(n, k), we hope to find omega using quantum walk. We adopt the coined quantum walk model, and we have proved that, for fixed order k, lackadaisical discrete-time quantum walk (DTQW) can find omega with success probability 1-o(1), keeping a quadratic speedup. Before this paper, the best result of DTQW is that discrete-time quantum walk finds.. with success probability 1/2 -o(1). We improve the success probability to 1 -o(1) by adding self-loops with proper weights and choose the appropriate oracle operator. Our result also matches the result of continuous-time quantum walk.
关键词	Discrete-time quantum walk Johnson graph Quadratic speedup
DOI	10.1016/j.physa.2024.129495
收录类别	SCI
语种	英语
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary
WOS记录号	WOS:001158500800001
出版者	ELSEVIER
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38356
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Meng
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China 3.Shanghai Innovat Ctr Processor Technol, Shanghai 200234, Peoples R China
推荐引用方式 GB/T 7714	Peng, Fangjie,Li, Meng,Sun, Xiaoming. Lackadaisical discrete-time quantum walk on Johnson graph[J]. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,2024,635:16.
APA	Peng, Fangjie,Li, Meng,&Sun, Xiaoming.(2024).Lackadaisical discrete-time quantum walk on Johnson graph.PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,635,16.
MLA	Peng, Fangjie,et al."Lackadaisical discrete-time quantum walk on Johnson graph".PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 635(2024):16.