|
|
|
Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube |
| Yao-Yao Jiang(姜瑶瑶)1, Peng-Cheng Chu(初鹏程)1, Wen-Bin Zhang(张文彬)2, and Hong-Yang Ma(马鸿洋)1,† |
1 School of Science, Qingdao University of Technology, Qingdao 266033, China;
2 School of Information and Control Engineering, Qingdao University of Technology, Qingdao 266033, China |
|
|
|
|
Abstract Shenvi et al. have proposed a quantum algorithm based on quantum walking called Shenvi-Kempe-Whaley (SKW) algorithm, but this search algorithm can only search one target state and use a specific search target state vector. Therefore, when there are more than two target nodes in the search space, the algorithm has certain limitations. Even though a multi-objective SKW search algorithm was proposed later, when the number of target nodes is more than two, the SKW search algorithm cannot be mapped to the same quotient graph. In addition, the calculation of the optimal target state depends on the number of target states m. In previous studies, quantum computing and testing algorithms were used to solve this problem. But these solutions require more Oracle calls and cannot get a high accuracy rate. Therefore, to solve the above problems, we improve the multi-target quantum walk search algorithm, and construct a controllable quantum walk search algorithm under the condition of unknown number of target states. By dividing the Hilbert space into multiple subspaces, the accuracy of the search algorithm is improved from pc=(1/2)-O(1/n) to pc=1-O(1/n). And by adding detection gate phase, the algorithm can stop when the amplitude of the target state becomes the maximum for the first time, and the algorithm can always maintain the optimal number of iterations, so as to reduce the number of unnecessary iterations in the algorithm process and make the number of iterations reach $ t_{\rm f}=(\pi /2)\sqrt{2^{n-2}} $.
|
Received: 22 August 2021
Revised: 04 September 2021
Accepted manuscript online: 18 September 2021
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
02.70.-c
|
(Computational techniques; simulations)
|
| |
02.20.-a
|
(Group theory)
|
|
| Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 11975132 and 61772295), the Natural Science Foundation of Shandong Province, China (Grant No. ZR2019YQ01), and the Project of Shandong Provincial Higher Educational Science and Technology Program, China (Grant No. J18KZ012). Thanks to Chen Zhenyu, Yan Dandan, and Ma Yulin for their help in the numerical simulation experiment. Special thanks to the scholars who have made important contributions in quantum computing and quantum search algorithm. |
Corresponding Authors:
Hong-Yang Ma
E-mail: hongyang_ma@aliyun.com
|
Cite this article:
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 2022 Chin. Phys. B 31 040307
|
[1] Steane A 1998 Rep. Prog. Phys. 61 117
[2] Orsucci D, Briegel H J and Dunjko V 2018 Quantum 2 105
[3] Grover L K 1996 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, July 1, 1996, New York, USA, pp. 212- 219
[4] Chakraborty S, Novo L, Ambainis A and Omar Y 2016 Phys. Rev. Lett. 116 100501
[5] Chakraborty S, Novo L, Di Giorgio S and Omar Y 2017 Phys. Rev. Lett. 119 220503
[6] Glos A, Krawiec A, Kukulski R and Puchala Z 2018 Quantum. Inf. Process. 17 1
[7] Berry S D and Wang J B 2011 Phys. Rev. A 83 042317
[8] Zähringer F, Kirchmair G, Gerritsma R, Solano E, Blatt R and Roos C F 2010 Phys. Rev. Lett. 104 100503
[9] Kempf A and Portugal R 2009 Phys. Rev. A 79 052317
[10] Sansoni L, Sciarrino F, Vallone G, Mataloni P, Crespi A, Ramponi R and Osellame R 2012 Phys. Rev. Lett. 108 010502
[11] Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307
[12] Potoček V, Gábris A, Kiss T and Jex I 2009 Phys. Rev. A 79 012325
[13] Zhu W N, Chen H W, Liu Z H and Xue X L 2014 International Conference in Swarm Intelligence, October 17-20, 2014, Hefei, China, pp. 357-364
[14] Long G L 2001 Phys. Rev. A 64 022307
[15] Hu X M, Huang C X, Sheng Y B, Zhou L, Liu B H, Guo Y and Guo G C 2021 Phys. Rev. Lett. 126 010503
[16] Zhou L, Sheng Y B and Long G L 2020 Sci. Bull. 65 12
[17] Zhou Z R, Sheng Y B, Niu P H, Yin L G, Long G L and Hanzo L 2020 Sci. China Phys. Mech. Astron. 63 230362
[18] Zhou N R, Huang L X, Gong L H and Zeng Q W 2020 Quantum. Inf. Process. 19 1
[19] Zhou N R, Zhu K N and Zou X F 2019 Ann. Phys-Berlin. 531 1800520
[20] Zhou N R, Zhu K N, Bi W and Gong L H 2019 Quantum. Inf. Process. 18 1
[21] Li H H, Gong L H and Zhou N R 2020 Chin. Phys. B 29 110304 |
| 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
|
|
|
