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 [. 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 , where is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.
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).
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. A64 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 Nature393 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. USA98 9490 [9] Dodd J L, Ralph T C and Milburn G J 2003 Phys. Rev. A68 042328 [10] Home J P, Hanneke D, Jost J D, Amini J M, Leibfried D and Wineland D J 2009 Science325 1227 [11] Childs A and Goldstone J 2004 Phys. Rev. A70 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. Plus129 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. A67 052307 [21] Keating J P, Linden N, Matthews J C F and Winter A 2007 Phys. Rev. A76 012315 [22] Zhang Y, Bao W, Wang X and Fu X 2015 Chin. Phys. B24 080307 [23] Chen T and Zhang X D 2016 Sci. Rep.6 25767 [24] Chen T and Zhang X D 2016 Phys. Rev. A94 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. B28 020501 [28] Li T, Zhang S, Fu X Q, Wang X, Wang Y, Lin J and Bao W S 2019 Chin. Phys. B28 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. A102 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 Research2021 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. A93 062313 [38] Wong T G and Philipp P 2016 Phys. Rev. A94 022304 [39] Tulsi A 2016 Quantum Inf. Process.15 2675 [40] Wong T G 2016 Quantum Inf. Process.15 1411
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
