Decoherence in optimized quantum random-walk search algorithm

doi:10.1088/1674-1056/24/8/080307

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

Decoherence in optimized quantum random-walk search algorithm

张宇超^{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-01-06 修回日期:2015-03-11 出版日期:2015-08-05 发布日期:2015-08-05
基金资助:
Project supported by the National Basic Research Program of China (Grant No. 2013CB338002).

Decoherence in optimized quantum random-walk search algorithm

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-01-06 Revised:2015-03-11 Online:2015-08-05 Published:2015-08-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 paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the optimized quantum random-walk search algorithm with decoherence is depicted through defining the shift operator which includes the possibility of broken links. For a given database size, we obtain the maximum success rate of the algorithm and the required number of iterations through numerical simulations and analysis when the algorithm is in the presence of decoherence. Then the computational complexity of the algorithm with decoherence is obtained. The results show that the ultimate effect of broken-link-type decoherence on the optimized quantum random-walk search algorithm is negative.

关键词: quantum search algorithm, quantum random walk, decoherence

Abstract: This paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the optimized quantum random-walk search algorithm with decoherence is depicted through defining the shift operator which includes the possibility of broken links. For a given database size, we obtain the maximum success rate of the algorithm and the required number of iterations through numerical simulations and analysis when the algorithm is in the presence of decoherence. Then the computational complexity of the algorithm with decoherence is obtained. The results show that the ultimate effect of broken-link-type decoherence on the optimized quantum random-walk search algorithm is negative.

Key words: quantum search algorithm, quantum random walk, decoherence

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

03.67.Lx

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

张宇超, 鲍皖苏, 汪翔, 付向群. Decoherence in optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(8): 80307-080307.

Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Decoherence in optimized quantum random-walk search algorithm[J]. Chin. Phys. B, 2015, 24(8): 80307-080307.

参考文献 28

[1]	Grover L 1996 Proceedings of the 28th Annual ACM Symposium on Theory of Computing (New York: ACM Press) p. 212
[2]	Shor P W 1997 SIAM J. Comput. 26 1484
[3]	Schoning T 1999 Foundations of Computer Science, the 40th Annual Symposium on IEEE, pp. 410–414
[4]	Motwani R and Raghavan P 1996 Randomized Algorithms (Cambridge: Cambridge University Press)
[5]	Kempe J 2005 Probability Theory and Related Fields 133 215
[6]	Krovi H and Brun T A 2006 Phys. Rev. A 73 032341
[7]	Nayak A and Vishwanath A 2000 arXiv: 0010117v1 [quant-ph]
[8]	Xue P and Zhang Y S 2013 Chin. Phys. B 22 070302
[9]	Qin H and Xue P 2014 Chin. Phys. B 23 010301
[10]	Zhang R, Xu Y Q and Xue P 2015 Chin. Phys. B 24 010303
[11]	Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307
[12]	Potocek V, Gábris A, Kiss T and Jex I 2009 Phys. Rev. A 79 012325
[13]	Li Y 2006 "Investigations on Quantum Random-Walk Search Algorithm", MS Thesis (Shanghai: East China Normal University) p. 34 (in Chinese)
[14]	Zhang Y C, Bao W S, Wang X and Fu X Q 2015 Chin. Phys. B 24 060304
[15]	Childs A M, Cleve R, Deotto E, Farhi E, Gutmann S and Spielman D A 2003 Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 59–68
[16]	Ambainis A 2007 SIAM J. Comput. 37 210
[17]	Krovi H, Magniez F, Ozols M and Roland J 2010 Automata Languages and Programming (Berlin/Heidelberg: Springer) pp. 540–551
[18]	Childs A and Goldstone J 2004 Phys. Rev. A 70 022314
[19]	Tulsi A 2008 Phys. Rev. A 78 012310
[20]	Long G L, Li Y S, Zhang W L and Tu C C 2000 Phys. Rev. A 61 042305
[21]	Shenvi N, Brown K R and Whaley K B 2003 Phys. Rev. A 68 052313
[22]	Li Y, Ma L and Zhou J 2006 J. Phys. A: Math. Gen. 39 9309
[23]	Abal G, Donangelo R, Marquezino F L, Oliveira A C and Portugal R 2009 arXiv: 0912.1523v1 [quant-ph]
[24]	Kendon V and Tregenna B 2003 Phys. Rev. A 67 042315
[25]	Romanelli A, Siri R, Abal G, Auyuanet A and Donangelo R 2005 Physica A: Statistical Mechanics and Its Applications 347 137
[26]	Oliveira A C, Portugal R and Donangelo R 2006 Phys. Rev. A 74 012312
[27]	Alagic G and Russell A 2005 Phys. Rev. A 72 062304
[28]	Marquezino F L, Portugal R, Abal G and Donangelo R 2008 Phys. Rev. A 77 042312

Decoherence in optimized quantum random-walk search algorithm

Decoherence in optimized quantum random-walk search algorithm

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 28

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Huan Yang(杨欢), Ling-Ling Xing(邢玲玲), Zhi-Yong Ding(丁智勇), Gang Zhang(张刚), and Liu Ye(叶柳). Steering quantum nonlocalities of quantum dot system suffering from decoherence[J]. 中国物理B, 2022, 31(9): 90302-090302.
[2]	Bao-Min Li(李保民), Ming-Liang Hu(胡明亮), and Heng Fan(范桁). Nonlocal advantage of quantum coherence and entanglement of two spins under intrinsic decoherence[J]. 中国物理B, 2021, 30(7): 70307-070307.
[3]	赵文垒, 揭泉林. Quantum to classical transition induced by a classically small influence[J]. 中国物理B, 2020, 29(8): 80302-080302.
[4]	杜倩, 蓝康, 张延惠, 姜露静. Geometric phase of an open double-quantum-dot system detected by a quantum point contact[J]. 中国物理B, 2020, 29(3): 30302-030302.
[5]	张子静, 王峰, 宋杰, 赵远. The effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk[J]. 中国物理B, 2020, 29(2): 20503-020503.
[6]	Munsif Jan, 许小冶, 王琴琴, 陈哲, 韩永建, 李传锋, 郭光灿. Dipole-dipole interactions enhance non-Markovianity and protect information against dissipation[J]. 中国物理B, 2019, 28(9): 90303-090303.
[7]	向左鲜, 唐传祥, 颜立新. A primary model of decoherence in neuronal microtubules based on the interaction Hamiltonian between microtubules and plasmon in neurons[J]. 中国物理B, 2019, 28(4): 48701-048701.
[8]	麦麦提依明·吐孙, 吐孙, 荣星, 杜江峰. Physics of quantum coherence in spin systems[J]. 中国物理B, 2019, 28(2): 24204-024204.
[9]	刘郴荣, 喻佩, 陈宪章, 徐洪亚, 黄亮, 来颖诚. Enhancing von Neumann entropy by chaos in spin-orbit entanglement[J]. 中国物理B, 2019, 28(10): 100501-100501.
[10]	李红梅, 郭苗迪, 张锐, 苏雪梅. Boundary states for entanglement robustness under dephasing and bit flip channels[J]. 中国物理B, 2019, 28(10): 100302-100302.
[11]	杨阳, 王安民, 曹连振, 赵加强, 逯怀新. Decoherence for a two-qubit system in a spin-chain environment[J]. 中国物理B, 2018, 27(9): 90302-090302.
[12]	高德营, 高强, 夏云杰. Classical-driving-assisted coherence dynamics and its conservation[J]. 中国物理B, 2018, 27(6): 60304-060304.
[13]	向少华, 朱喜香, 宋克慧. Non-Gaussianity dynamics of two-mode squeezed number states subject to different types of noise based on cumulant theory[J]. 中国物理B, 2018, 27(10): 100305-100305.
[14]	董国慧, 马宇翰, 陈劲夫, 王欣, 孙昌璞. Decoherence of macroscopic objects from relativistic effect[J]. 中国物理B, 2018, 27(10): 100301-100301.
[15]	李风光, 鲍皖苏, 张硕, 汪翔, 黄合良, 李坦, 马博文. Transitionless driving on local adiabatic quantum search algorithm[J]. 中国物理B, 2018, 27(1): 10308-010308.