Quantum search of many vertices on the joined complete graph

doi:10.1088/1674-1056/ac5241

中国物理B ›› 2022, Vol. 31 ›› Issue (7): 70504-070504.doi: 10.1088/1674-1056/ac5241

Quantum search of many vertices on the joined complete graph

Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天)^†, and Xiangdong Zhang(张向东)

Key Laboratory of Advanced Optoelectronic Quantum Architecture and Measurements of Ministry of Education, Beijing Key Laboratory of Nanophotonics&Ultrafine Optoelectronic Systems, School of Physics, Beijing Institute of Technology, Beijing 100081, China

收稿日期:2021-10-24 修回日期:2021-12-29 接受日期:2022-02-07 出版日期:2022-06-09 发布日期:2022-06-09
通讯作者: Tian Chen E-mail:chentian@bit.edu.cn
基金资助:
Project supported by the National Key R&D Program of China (Grant No. 2017YFA0303800) and the National Natural Science Foundation of China (Grant Nos. 91850205 and 11974046).

Quantum search of many vertices on the joined complete graph

Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天)^†, and Xiangdong Zhang(张向东)

Key Laboratory of Advanced Optoelectronic Quantum Architecture and Measurements of Ministry of Education, Beijing Key Laboratory of Nanophotonics&Ultrafine Optoelectronic Systems, School of Physics, Beijing Institute of Technology, Beijing 100081, China

Received:2021-10-24 Revised:2021-12-29 Accepted:2022-02-07 Online:2022-06-09 Published:2022-06-09
Contact: Tian Chen E-mail:chentian@bit.edu.cn
Supported by:
Project supported by the National Key R&D Program of China (Grant No. 2017YFA0303800) and the National Natural Science Foundation of China (Grant Nos. 91850205 and 11974046).

摘要/Abstract

摘要： The quantum search on the graph is a very important topic. In this work, we develop a theoretic method on searching of single vertex on the graph [$Phys. Rev. Lett$. 114 110503 (2015)], and systematically study the search of many vertices on one low-connectivity graph, the joined complete graph. Our results reveal that, with the optimal jumping rate obtained from the theoretical method, we can find such target vertices at the time $O\left({\sqrt N } \right)$, where $N$ is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.

关键词: quantum search, the joined complete graph, quantum walk, many vertices

Abstract: The quantum search on the graph is a very important topic. In this work, we develop a theoretic method on searching of single vertex on the graph [$Phys. Rev. Lett$. 114 110503 (2015)], and systematically study the search of many vertices on one low-connectivity graph, the joined complete graph. Our results reveal that, with the optimal jumping rate obtained from the theoretical method, we can find such target vertices at the time $O\left({\sqrt N } \right)$, where $N$ is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.

Key words: quantum search, the joined complete graph, quantum walk, many vertices

中图分类号: (Random walks and Levy flights)

05.40.Fb

03.67.-a (Quantum information) 02.10.Ox (Combinatorics; graph theory)

Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Quantum search of many vertices on the joined complete graph[J]. 中国物理B, 2022, 31(7): 70504-070504.

Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Quantum search of many vertices on the joined complete graph[J]. Chin. Phys. B, 2022, 31(7): 70504-070504.

参考文献

[1] Grover L K 1998 Phys. Rev. Lett. 80 4329
[2] Long G L 2001 Phys. Rev. A 64 022307
[3] Long G L and Xiao L 2003 J. Chem. Phys. 119 8473
[4] Aharonov D, Ambainis A, Kempe J and Vazirani U 2001 STOC'01:Proceedings of the 33th Annual ACM Symposium on Theory of Computing, July 6, 2001, Hersonissos, Greece, pp. 50-59
[5] Nielsen M A and Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge:Cambridge University Press) pp. 248-271
[6] Jones J A, Mosca M and Hansen R H 1998 Nature 393 344
[7] Kwiat P G, Mitchell J R, Schwindt P D D and White A G 2000 J. Mod. Opt. 47 257
[8] Scully M O and Zubairy M S 2001 Proc. Natl. Acad. Sci. USA 98 9490
[9] Dodd J L, Ralph T C and Milburn G J 2003 Phys. Rev. A 68 042328
[10] Home J P, Hanneke D, Jost J D, Amini J M, Leibfried D and Wineland D J 2009 Science 325 1227
[11] Childs A and Goldstone J 2004 Phys. Rev. A 70 022314
[12] Manouchehri K and Wang J B 2014 Physical Implementation of Quantum Walks (Perth:The University of Western Australia) pp. 39-59
[13] Portugal R 2013 Quantum Walks and Search Algorithms (New York:Springer New York) pp. 17-37
[14] Abal G, Donangelo R, Marquezino F L and Portugal R 2010 Math. Struct. Comput. Sci. 20 999
[15] Childs A, Farhi E and Gutmann S 2002 Quantum Inf. Process. 1 35
[16] Childs A M, Cleve R, Deotto E, Farhi E, Gutmann S and Spielman D A 2003 STOC'03:Proceedings of the 35th Annual ACM Symposiumon on Theory of Computing, June 9-11, 2003, San Diego, California, pp. 59-68
[17] Paparo G D and Martin-Delgado M A 2012 Sci. Rep. 2 444
[18] Paparo G D, Muller M, Comellas F and Martin-Delgado M A 2014 Eur. Phys. J. Plus 129 150
[19] Zhang H X, Chen T, Pan N Q and Zhang X D 2022 Adv. Quantum Technol. 5 2270043
[20] Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307
[21] Keating J P, Linden N, Matthews J C F and Winter A 2007 Phys. Rev. A 76 012315
[22] Zhang Y, Bao W, Wang X and Fu X 2015 Chin. Phys. B 24 080307
[23] Chen T and Zhang X D 2016 Sci. Rep. 6 25767
[24] Chen T and Zhang X D 2016 Phys. Rev. A 94 012316
[25] Niu R W and Pan G J 2016 Chin. Phys. Lett. 33 68901
[26] Figgatt C, Maslov D, Landsman K A, Linke N M, Debnath S and Monroe C 2017 Nat. Commun. 8 1918
[27] Lv L S, Zhang K, Zhang T and Ma M Y 2019 Chin. Phys. B 28 020501
[28] Li T, Zhang S, Fu X Q, Wang X, Wang Y, Lin J and Bao W S 2019 Chin. Phys. B 28 120301
[29] Zhang J, Hegde S S and Suter D 2020 Phys. Rev. Lett. 125 030501
[30] Zhang R, Liu Y and Chen T 2020 Phys. Rev. A 102 022218
[31] Qiang X G, Wang Y Z, Xue S C, Ge R Y, Chen L F, Liu Y W, Huang A Q, Fu X, Xu P, Yi T, Xu F F, Deng M T, Wang J B, Meinecke J D A, Matthews J C F, Cai X L, Yang X J and Wu J J 2021 Sci. Adv. 7 eabb8375
[32] Pan N Q, Chen T, Sun H J and Zhang X D 2021 Research 2021 9793071
[33] Zhang R and Chen T 2022 Commun. Theor. Phys. 74 045101
[34] Janmark J, Meyer D A and Wong T G 2014 Phys. Rev. Lett. 112 210502
[35] Meyer D A and Wong T G 2015 Phys. Rev. Lett. 114 110503
[36] Chakraborty S, Novo L, Ambainis A and Omar Y 2016 Phys. Rev. Lett. 116 100501
[37] Wong T G and Meyer D A 2016 Phys. Rev. A 93 062313
[38] Wong T G and Philipp P 2016 Phys. Rev. A 94 022304
[39] Tulsi A 2016 Quantum Inf. Process. 15 2675
[40] Wong T G 2016 Quantum Inf. Process. 15 1411

Quantum search of many vertices on the joined complete graph

Quantum search of many vertices on the joined complete graph

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Jv-Jie Wang(王莒杰), Zhao Dou(窦钊), Xiu-Bo Chen(陈秀波), Yu-Ping Lai(赖裕平), and Jian Li(李剑). Efficient quantum private comparison protocol based on one direction discrete quantum walks on the circle[J]. 中国物理B, 2022, 31(5): 50308-050308.
[2]	Yao-Yao Jiang(姜瑶瑶), Peng-Cheng Chu(初鹏程), Wen-Bin Zhang(张文彬), and Hong-Yang Ma(马鸿洋). Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube[J]. 中国物理B, 2022, 31(4): 40307-040307.
[3]	Peng Xue(薛鹏). Disorder in parity-time symmetric quantum walks[J]. 中国物理B, 2022, 31(1): 10311-010311.
[4]	Yali Jia(贾雅利) and Zhi-Jian Li(李志坚). High winding number of topological phase in non-unitary periodic quantum walk[J]. 中国物理B, 2021, 30(10): 100301-100301.
[5]	蒙雅, 梅锋, 陈刚, 贾锁堂. Probe of topological invariants using quantum walks of a trapped ion in coherent state space[J]. 中国物理B, 2020, 29(7): 70501-070501.
[6]	毛雯雯, 吕丽花, 季永运, 李有泉. Quantum intelligence on protein folding pathways[J]. 中国物理B, 2020, 29(1): 18702-018702.
[7]	李坦, 张硕, 付向群, 汪翔, 汪洋, 林杰, 鲍皖苏. Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method[J]. 中国物理B, 2019, 28(12): 120301-120301.
[8]	刘婷婷, 胡亚运, 赵静, 钟鸣, 童培庆. The entanglement of deterministic aperiodic quantum walks[J]. 中国物理B, 2018, 27(12): 120305-120305.
[9]	李风光, 鲍皖苏, 张硕, 汪翔, 黄合良, 李坦, 马博文. Transitionless driving on local adiabatic quantum search algorithm[J]. 中国物理B, 2018, 27(1): 10308-010308.
[10]	薛希玲, 刘志昊, 陈汉武. Search algorithm on strongly regular graphsbased on scattering quantum walks[J]. 中国物理B, 2017, 26(1): 10301-010301.
[11]	边志浩, 秦豪, 詹翔, 李剑, 薛鹏. A quantum walk in phase space with resonator-assisted double quantum dots[J]. 中国物理B, 2016, 25(2): 20307-020307.
[12]	胡杨熠, 陈平形. Localization of quantum walks on finite graphs[J]. 中国物理B, 2016, 25(12): 120303-120303.
[13]	骆浩, 詹翔, 张芃, 薛鹏. Stopping time of a one-dimensional bounded quantum walk[J]. 中国物理B, 2016, 25(11): 110304-110304.
[14]	秦豪, 薛鹏. Quantum walks with coins undergoing different quantum noisy channels[J]. 中国物理B, 2016, 25(1): 10501-010501.
[15]	张宇超, 鲍皖苏, 汪翔, 付向群. Decoherence in optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(8): 80307-080307.