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

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

中国物理B ›› 2015, Vol. 24 ›› Issue (11): 110309-110309.doi: 10.1088/1674-1056/24/11/110309

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

张宇超^{a b}, 鲍皖苏^{a b}, 汪翔^{a b}, 付向群^{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

收稿日期:2015-07-11 修回日期:2015-10-10 出版日期:2015-11-05 发布日期:2015-11-05
通讯作者: Bao Wan-Su E-mail:2010thzz@sina.com
基金资助:
Project supported by the National Basic Research Program of China (Grant No. 2013CB338002).

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

Received:2015-07-11 Revised:2015-10-10 Online:2015-11-05 Published:2015-11-05
Contact: Bao Wan-Su E-mail:2010thzz@sina.com
Supported by:
Project supported by the National Basic Research Program of China (Grant No. 2013CB338002).

摘要/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.

关键词: quantum search algorithm, quantum random walk, multi-solution, abstract search algorithm

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.

Key words: quantum search algorithm, quantum random walk, multi-solution, abstract search algorithm

中图分类号: (Quantum computation architectures and implementations)

03.67.Lx

03.67.Ac (Quantum algorithms, protocols, and simulations)

张宇超, 鲍皖苏, 汪翔, 付向群. Optimized quantum random-walk search algorithm for multi-solution search[J]. 中国物理B, 2015, 24(11): 110309-110309.

Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Optimized quantum random-walk search algorithm for multi-solution search[J]. Chin. Phys. B, 2015, 24(11): 110309-110309.

参考文献 31

[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

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

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

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 31

相关文章 6

Metrics

本文评价

推荐阅读 0

[1]	张子静, 王峰, 宋杰, 赵远. The effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk[J]. 中国物理B, 2020, 29(2): 20503-020503.
[2]	李风光, 鲍皖苏, 张硕, 汪翔, 黄合良, 李坦, 马博文. Transitionless driving on local adiabatic quantum search algorithm[J]. 中国物理B, 2018, 27(1): 10308-010308.
[3]	张宇超, 鲍皖苏, 汪翔, 付向群. Decoherence in optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(8): 80307-080307.
[4]	张宇超, 鲍皖苏, 汪翔, 付向群. Effects of systematic phase errors on optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(6): 60304-060304.
[5]	Clement Ampadu. Averaging in SU(2) open quantum random walk[J]. 中国物理B, 2014, 23(3): 30302-030302.
[6]	李敏, 张永生, 郭光灿. Average position in quantum walks with a U(2) coin[J]. 中国物理B, 2013, 22(3): 30310-030310.