Optimized quantum random-walk search algorithm for multi-solution search

doi:10.1088/1674-1056/24/11/110309

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!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Optimized quantum random-walk search algorithm for multi-solution search

Cite this article:

Online attention