Please wait a minute...
Chin. Phys. B, 2022, Vol. 31(7): 070504    DOI: 10.1088/1674-1056/ac5241
GENERAL Prev   Next  

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
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.
Keywords:  quantum search      the joined complete graph      quantum walk      many vertices  
Received:  24 October 2021      Revised:  29 December 2021      Accepted manuscript online:  07 February 2022
PACS:  05.40.Fb (Random walks and Levy flights)  
  03.67.-a (Quantum information)  
  02.10.Ox (Combinatorics; graph theory)  
Fund: 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).
Corresponding Authors:  Tian Chen     E-mail:

Cite this article: 

Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东) Quantum search of many vertices on the joined complete graph 2022 Chin. Phys. B 31 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
[1] Efficient quantum private comparison protocol based on one direction discrete quantum walks on the circle
Jv-Jie Wang(王莒杰), Zhao Dou(窦钊), Xiu-Bo Chen(陈秀波), Yu-Ping Lai(赖裕平), and Jian Li(李剑). Chin. Phys. B, 2022, 31(5): 050308.
[2] Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube
Yao-Yao Jiang(姜瑶瑶), Peng-Cheng Chu(初鹏程), Wen-Bin Zhang(张文彬), and Hong-Yang Ma(马鸿洋). Chin. Phys. B, 2022, 31(4): 040307.
[3] Disorder in parity-time symmetric quantum walks
Peng Xue(薛鹏). Chin. Phys. B, 2022, 31(1): 010311.
[4] Quantum walk under coherence non-generating channels
Zishi Chen(陈子石) and Xueyuan Hu(胡雪元). Chin. Phys. B, 2021, 30(3): 030305.
[5] State transfer on two-fold Cayley trees via quantum walks
Xi-Ling Xue(薛希玲) and Yue Ruan(阮越). Chin. Phys. B, 2021, 30(2): 020304.
[6] Quantum dynamics on a lossy non-Hermitian lattice
Li Wang(王利), Qing Liu(刘青), and Yunbo Zhang(张云波). Chin. Phys. B, 2021, 30(2): 020506.
[7] High winding number of topological phase in non-unitary periodic quantum walk
Yali Jia(贾雅利) and Zhi-Jian Li(李志坚). Chin. Phys. B, 2021, 30(10): 100301.
[8] Probe of topological invariants using quantum walks of a trapped ion in coherent state space
Ya Meng(蒙雅), Feng Mei(梅锋), Gang Chen(陈刚), Suo-Tang Jia(贾锁堂). Chin. Phys. B, 2020, 29(7): 070501.
[9] A two-dimensional quantum walk driven by a single two-side coin
Quan Lin(林泉), Hao Qin(秦豪) Kun-Kun Wang(王坤坤), Lei Xiao(肖磊), and Peng Xue(薛鹏). Chin. Phys. B, 2020, 29(11): 110303.
[10] Quantum intelligence on protein folding pathways
Wen-Wen Mao(毛雯雯), Li-Hua Lv(吕丽花), Yong-Yun Ji(季永运), You-Quan Li(李有泉). Chin. Phys. B, 2020, 29(1): 018702.
[11] Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method
Tan Li(李坦), Shuo Zhang(张硕), Xiang-Qun Fu(付向群), Xiang Wang(汪翔), Yang Wang(汪洋), Jie Lin(林杰), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2019, 28(12): 120301.
[12] The entanglement of deterministic aperiodic quantum walks
Ting-Ting Liu(刘婷婷), Ya-Yun Hu(胡亚运), Jing Zhao(赵静), Ming Zhong(钟鸣), Pei-Qing Tong(童培庆). Chin. Phys. B, 2018, 27(12): 120305.
[13] Transitionless driving on local adiabatic quantum search algorithm
Feng-guang Li(李风光), Wan-su Bao(鲍皖苏), Shuo Zhang(张硕), Xiang Wang(汪翔), He-liang Huang(黄合良), Tan Li(李坦), Bo-wen Ma(马博文). Chin. Phys. B, 2018, 27(1): 010308.
[14] Search algorithm on strongly regular graphsbased on scattering quantum walks
Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武). Chin. Phys. B, 2017, 26(1): 010301.
[15] A quantum walk in phase space with resonator-assisted double quantum dots
Zhi-Hao Bian(边志浩), Hao Qin(秦豪), Xiang Zhan(詹翔), Jian Li(李剑), Peng Xue(薛鹏). Chin. Phys. B, 2016, 25(2): 020307.
No Suggested Reading articles found!