|
|
|
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.
|
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: chentian@bit.edu.cn
|
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 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
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.
View more on Altmetrics
|
|
|
