Decoherence in optimized quantum random-walk search algorithm

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

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.

Keywords: quantum search algorithm quantum random walk decoherence

Received: 06 January 2015
Revised: 11 March 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 (付向群) Decoherence in optimized quantum random-walk search algorithm 2015 Chin. Phys. B 24 080307

[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

[1]	Steering quantum nonlocalities of quantum dot system suffering from decoherence Huan Yang(杨欢), Ling-Ling Xing(邢玲玲), Zhi-Yong Ding(丁智勇), Gang Zhang(张刚), and Liu Ye(叶柳). Chin. Phys. B, 2022, 31(9): 090302.
[2]	Nonlocal advantage of quantum coherence and entanglement of two spins under intrinsic decoherence Bao-Min Li(李保民), Ming-Liang Hu(胡明亮), and Heng Fan(范桁). Chin. Phys. B, 2021, 30(7): 070307.
[3]	Quantum to classical transition induced by a classically small influence Wen-Lei Zhao(赵文垒), Quanlin Jie(揭泉林). Chin. Phys. B, 2020, 29(8): 080302.
[4]	Geometric phase of an open double-quantum-dot system detected by a quantum point contact Qian Du(杜倩), Kang Lan(蓝康), Yan-Hui Zhang(张延惠), Lu-Jing Jiang(姜露静). Chin. Phys. B, 2020, 29(3): 030302.
[5]	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.
[6]	Dipole-dipole interactions enhance non-Markovianity and protect information against dissipation Munsif Jan, Xiao-Ye Xu(许小冶), Qin-Qin Wang(王琴琴), Zhe Chen(陈哲), Yong-Jian Han(韩永建), Chuan-Feng Li(李传锋), Guang-Can Guo(郭光灿). Chin. Phys. B, 2019, 28(9): 090303.
[7]	A primary model of decoherence in neuronal microtubules based on the interaction Hamiltonian between microtubules and plasmon in neurons Zuoxian Xiang(向左鲜), Chuanxiang Tang(唐传祥), Lixin Yan(颜立新). Chin. Phys. B, 2019, 28(4): 048701.
[8]	Physics of quantum coherence in spin systems Maimaitiyiming Tusun(麦麦提依明·吐孙), Xing Rong(荣星), Jiangfeng Du(杜江峰). Chin. Phys. B, 2019, 28(2): 024204.
[9]	Boundary states for entanglement robustness under dephasing and bit flip channels Hong-Mei Li(李红梅), Miao-Di Guo(郭苗迪), Rui Zhang(张锐), Xue-Mei Su(苏雪梅). Chin. Phys. B, 2019, 28(10): 100302.
[10]	Enhancing von Neumann entropy by chaos in spin-orbit entanglement Chen-Rong Liu(刘郴荣), Pei Yu(喻佩), Xian-Zhang Chen(陈宪章), Hong-Ya Xu(徐洪亚), Liang Huang(黄亮), Ying-Cheng Lai(来颖诚). Chin. Phys. B, 2019, 28(10): 100501.
[11]	Decoherence for a two-qubit system in a spin-chain environment Yang Yang(杨阳), An-Min Wang(王安民), Lian-Zhen Cao(曹连振), Jia-Qiang Zhao(赵加强), Huai-Xin Lu(逯怀新). Chin. Phys. B, 2018, 27(9): 090302.
[12]	Classical-driving-assisted coherence dynamics and its conservation De-Ying Gao(高德营), Qiang Gao(高强), Yun-Jie Xia(夏云杰). Chin. Phys. B, 2018, 27(6): 060304.
[13]	Decoherence of macroscopic objects from relativistic effect Guo-Hui Dong(董国慧), Yu-Han Ma(马宇翰), Jing-Fu Chen(陈劲夫), Xin Wang(王欣), Chang-Pu Sun(孙昌璞). Chin. Phys. B, 2018, 27(10): 100301.
[14]	Non-Gaussianity dynamics of two-mode squeezed number states subject to different types of noise based on cumulant theory Shaohua Xiang(向少华), Xixiang Zhu(朱喜香), Kehui Song(宋克慧). Chin. Phys. B, 2018, 27(10): 100305.
[15]	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.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Decoherence in optimized quantum random-walk search algorithm

Cite this article:

Online attention