-
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
-
Keywords:
- Grover algorithm /
- phase matching /
- quantum walk search algorithm
[1] Shor P W 1997 SIAM J. Comput. 26 1484
[2] Grover L K 1996 Proceedings of 28th ACM Symposium on Theory of Computation Philadelphia, USA, May 22-24, 1996 p212
[3] Long G L 2001 Phys. Rev. A 64 022307
[4] Toyama F M, van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 5
[5] Liu Y, Zhang F H 2015 Sci. China: Phys. Mech. Astron. 58 7
[6] Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p37
[7] Aharonov D, Ambainis A, Kempe J, Vazirani U 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p50
[8] Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[9] Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314
[10] Ambainis A, Kempe J, Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms Philadelphia, USA, January 23-25, 2005 p1099
[11] Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307
[12] Potoček V, Gábris A, Kiss T, Jex I 2009 Phys. Rev. A 79 012325
[13] Reitzner D, Hillery M, Feldman E, Buzek V 2009 Phys. Rev. A 79 012323
[14] Liu Y M, Chen H W, Liu Z H, Xue X L, Zhu W N 2015 Acta Phys. Sin. 64 010301 (in Chinese) [刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁 2015 64 010301]
[15] Kempe J 2005 Probability Theory and Related Fields 133 215
[16] Wang H, Ma Z, Ma C G 2013 Chin. Sci. Bull. 58 28
[17] Travaglione B C, Milburn G J 2002 Phys. Rev. A 65 3
[18] WANG C, LI Y S, HAO L 2011 Chin. Sci. Bull. 56 20
[19] Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502
[20] Ambainis A 2007 SIAM J. Comput. 37 210
[21] Childs A M, Eisenberg J M 2005 Quantum Inf. Comput. 5 593
[22] Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[23] Long G L, Liu Y 2007 Front. Comput. Sci. 1 3
[24] Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[25] Fredkin E, Toffoli T 1982 Int. J. Theor. Phys. 21 219
[26] Toffoli T 1981 Math. Syst. Theory 14 13
[27] Grover L K 1998 Phys. Rev. Lett. 80 4329
[28] Long G L, Li Y S, Zhang W L, Niu L 1999 Phys. Lett. A 262 27
[29] Younes A 2007 Appl. Math. Informat. 7 93
[30] Li P C, Li S Y 2007 Phys. Lett. A 366 42
[31] Long G L, Li X, Sun Y 2002 Phys. Lett. A 294 3
-
[1] Shor P W 1997 SIAM J. Comput. 26 1484
[2] Grover L K 1996 Proceedings of 28th ACM Symposium on Theory of Computation Philadelphia, USA, May 22-24, 1996 p212
[3] Long G L 2001 Phys. Rev. A 64 022307
[4] Toyama F M, van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 5
[5] Liu Y, Zhang F H 2015 Sci. China: Phys. Mech. Astron. 58 7
[6] Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p37
[7] Aharonov D, Ambainis A, Kempe J, Vazirani U 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p50
[8] Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[9] Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314
[10] Ambainis A, Kempe J, Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms Philadelphia, USA, January 23-25, 2005 p1099
[11] Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307
[12] Potoček V, Gábris A, Kiss T, Jex I 2009 Phys. Rev. A 79 012325
[13] Reitzner D, Hillery M, Feldman E, Buzek V 2009 Phys. Rev. A 79 012323
[14] Liu Y M, Chen H W, Liu Z H, Xue X L, Zhu W N 2015 Acta Phys. Sin. 64 010301 (in Chinese) [刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁 2015 64 010301]
[15] Kempe J 2005 Probability Theory and Related Fields 133 215
[16] Wang H, Ma Z, Ma C G 2013 Chin. Sci. Bull. 58 28
[17] Travaglione B C, Milburn G J 2002 Phys. Rev. A 65 3
[18] WANG C, LI Y S, HAO L 2011 Chin. Sci. Bull. 56 20
[19] Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502
[20] Ambainis A 2007 SIAM J. Comput. 37 210
[21] Childs A M, Eisenberg J M 2005 Quantum Inf. Comput. 5 593
[22] Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[23] Long G L, Liu Y 2007 Front. Comput. Sci. 1 3
[24] Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[25] Fredkin E, Toffoli T 1982 Int. J. Theor. Phys. 21 219
[26] Toffoli T 1981 Math. Syst. Theory 14 13
[27] Grover L K 1998 Phys. Rev. Lett. 80 4329
[28] Long G L, Li Y S, Zhang W L, Niu L 1999 Phys. Lett. A 262 27
[29] Younes A 2007 Appl. Math. Informat. 7 93
[30] Li P C, Li S Y 2007 Phys. Lett. A 366 42
[31] Long G L, Li X, Sun Y 2002 Phys. Lett. A 294 3
Catalog
Metrics
- Abstract views: 7135
- PDF Downloads: 304
- Cited By: 0
下载:
