Please wait a minute...
Chin. Phys. B, 2015, Vol. 24(11): 110309    DOI: 10.1088/1674-1056/24/11/110309
GENERAL Prev   Next  

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.
Keywords:  quantum search algorithm      quantum random walk      multi-solution      abstract search algorithm  
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
[1] The effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk
Zijing Zhang(张子静), Feng Wang(王峰), Jie Song(宋杰), Yuan Zhao(赵远). Chin. Phys. B, 2020, 29(2): 020503.
[2] 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.
[3] Decoherence in optimized quantum random-walk search algorithm
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(8): 080307.
[4] Effects of systematic phase errors on optimized quantum random-walk search algorithm
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(6): 060304.
[5] Averaging in SU(2) open quantum random walk
Clement Ampadu. Chin. Phys. B, 2014, 23(3): 030302.
[6] Average position in quantum walks with a U(2) coin
Li Min (李敏), Zhang Yong-Sheng (张永生), Guo Guang-Can (郭光灿). Chin. Phys. B, 2013, 22(3): 030310.
[7] Implementation of quantum search scheme by adiabatic passage in a cavity--laser--atom system
Liu Wen-Wu(刘文武), Li Hong-Cai(李洪才), and Yang Rong-Can(杨榕灿). Chin. Phys. B, 2009, 18(1): 23-29.
No Suggested Reading articles found!