|
|
Optimized quantum random-walk search algorithm for multi-solution search |
Zhang Yu-Chao (张宇超)a b, Bao Wan-Su (鲍皖苏)a b, Wang Xiang (汪翔)a b, Fu Xiang-Qun (付向群)a b |
a Zhengzhou Information Science and Technology Institute, Zhengzhou 450004, China; b Synergetic Innovation Center of Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China |
|
|
Abstract This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q. For a given q, we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.
|
Received: 11 July 2015
Revised: 10 October 2015
Accepted manuscript online:
|
PACS:
|
03.67.Lx
|
(Quantum computation architectures and implementations)
|
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
|
Fund: Project supported by the National Basic Research Program of China (Grant No. 2013CB338002). |
Corresponding Authors:
Bao Wan-Su
E-mail: 2010thzz@sina.com
|
Cite this article:
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群) Optimized quantum random-walk search algorithm for multi-solution search 2015 Chin. Phys. B 24 110309
|
[1] |
Feynman R;1982 Int. J. Theor. Phys. 21 467
|
[2] |
Deutsch D;1985 Proeeeding of the Royal Soeiety of London A: Mathematical, Physical and Engineering Sciences 400 97
|
[3] |
Shor P W;1997 SIAM J. Comput. 26 1484
|
[4] |
Grover L K 1996 Proceeding of the 28th ACM Symposium on Theory of Computation (New York: ACM Press) pp. 212-219
|
[5] |
Kane B E;1998 Nature 393 133
|
[6] |
Zhang Y Y, Hu H P and Lu S F;2011 Chin. Phys. B 20 040309
|
[7] |
Fu X Q, Bao W S, Li F D and Zhang Y C;2014 Chin. Phys. B 23 020306
|
[8] |
Long G L;2001 Phys. Rev. A 64 022307
|
[9] |
Toyama F M, van Dijk W and Nogami Y;2013 Quantum Inf. Process. 12 1897
|
[10] |
Wang X, Bao W S and Fu X Q;2011 Chin. Sci. Bull. 56 484
|
[11] |
Long G L, Li Y S, Zhang W L and Niu L;1999 Phys. Lett. A 262 27
|
[12] |
Long G L, Xiao L and Sun Y;2002 Phys. Lett. A 294 143
|
[13] |
Li T, Bao W S, Lin W Q and Fu X Q;2014 Chin. Phys. Lett. 31 050301
|
[14] |
Long G L and Liu Y;2007 Front. Comput. Sci. China 1 247
|
[15] |
Liu Y;2013 Chin. Sci. Bull. 58 2927
|
[16] |
Liu Y and Ou-Yang X P;2013 Chin. Sci. Bull. 58 2329
|
[17] |
Ampadu C;2014 Chin. Phys. B 23 030302
|
[18] |
Xue P, Qin H, Tang B, Zhan X, Bian Z H and Li J;2014 Chin. Phys. B 23 110307
|
[19] |
Wu J J, Zhang B D, Tang Y H, Qiang X G and Wang H Q;2013 Chin. Phys. B 22 050304
|
[20] |
Ambainis A;2007 SIAM J. Comput. 37 210
|
[21] |
Tulsi A;2008 Phys. Rev. A 78 012310
|
[22] |
Magniez F, Nayak A, Roland J and Santha M;2011 SIAM J. Comput. 40 142
|
[23] |
Shenvi N, Kempe J and Whaley K B;2003 Phys. Rev. A 67 052307
|
[24] |
Travaglione B C and Milburn G J;2002 Phys. Rev. A 65 032310
|
[25] |
Dür W, Raussendorf R, Kendon V M and Briegel H J;2002 Phys. Rev. A 66 052319
|
[26] |
Li Y 2006 Investigations on Quantum Random-Walk Search Algorithm (Dissertation) (Shanghai: East China Normal University) (in Chinese)
|
[27] |
Potocek V, Gábris A, Kiss T and Jex I 2009 Phys. Rev. A 79 012325
|
[28] |
Zhang Y C, Bao W S, Wang X and Fu X Q;2015 Chin. Phys. B 24 060304
|
[29] |
Ambainis A, Kempe J and Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 1099-1108
|
[30] |
Szegedy M 2004 arXiv: quant-ph/0401053
|
[31] |
Moore C and Russell A 2002 Randomization and Approximation Techniques in Computer Science (Berlin, Heidelberg: Springer) pp. 164-178
|
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
|
|
|