Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Quantum walk search algorithm based on phase matching and circuit cmplementation

Chen Han-Wu Li Ke Zhao Sheng-Mei

Citation:

Quantum walk search algorithm based on phase matching and circuit cmplementation

Chen Han-Wu, Li Ke, Zhao Sheng-Mei
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • 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.
      Corresponding author: Chen Han-Wu, hanwu_chen@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61170321, 61271238, 61475075) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant Nos. 20110092110024, 20123223110003).
    [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

  • [1] Yang Jian-Yu, Xi Kun, Zhu Li-Zhe. Transition state searching for complex biomolecules: Algorithms and machine learning. Acta Physica Sinica, 2023, 72(24): 248701. doi: 10.7498/aps.72.20231319
    [2] Zhou Jiang-Ping, Zhou Yuan-Yuan, Zhou Xue-Jun. Asymmetric channel phase matching quantum key distribution. Acta Physica Sinica, 2023, 72(14): 140302. doi: 10.7498/aps.72.20230652
    [3] Jiang Yao-Yao, Zhang Wen-Bin, Chu Peng-Cheng, Ma Hong-Yang. Feedback search algorithm for multi-particle quantum walks over a ring based on permutation groups. Acta Physica Sinica, 2022, 71(3): 030201. doi: 10.7498/aps.71.20211000
    [4] Feedback search algorithm for multi-particle quantum walks over a ring based on permutation groups. Acta Physica Sinica, 2021, (): . doi: 10.7498/aps.70.20211000
    [5] Fan Xin, Liang Hong-Jing, Shan Li-Yu, Yan Bo, Gao Qing-Hua, Ma Ri, Ding Da-Jun. Extreme ultraviolet polarization vortex beam based on high harmonic generation. Acta Physica Sinica, 2020, 69(4): 044203. doi: 10.7498/aps.69.20190834
    [6] Zhang Dong-Xiao, Chen Zhi-Bin, Xiao Cheng, Qin Meng-Ze, Wu Hao. Generation of turbulence phase screen based on gravitational search algorithm. Acta Physica Sinica, 2019, 68(13): 134205. doi: 10.7498/aps.68.20190081
    [7] Teng Huan, Chai Lu, Wang Qing-Yue, Hu Ming-Lie. Optimazation of broadband third-harmonic UV generation in highly nonlinear photonic crystal fiber. Acta Physica Sinica, 2017, 66(4): 044205. doi: 10.7498/aps.66.044205
    [8] Xue Xi-Ling, Chen Han-Wu, Liu Zhi-Hao, Zhang Bin-Bin. Search algorithm of structure anomalies in complete graph based on scattering quantum walk. Acta Physica Sinica, 2016, 65(8): 080302. doi: 10.7498/aps.65.080302
    [9] Li Jian-She, Li Shu-Guang, Zhao Yuan-Yuan, Liu Qiang, Fan Zhen-Kai, Wang Guang-Yao. Experimental studies of two sets of four-wave mixing processes in a single-zero-dispersion microstructured fiber by the same pump. Acta Physica Sinica, 2016, 65(21): 214201. doi: 10.7498/aps.65.214201
    [10] Li Xiao-Ming, Shen Xue-Ju, Liu Xun, Wang Lin. Study on temperature adaptability extension of KTP frequency-doubling device. Acta Physica Sinica, 2015, 64(9): 094205. doi: 10.7498/aps.64.094205
    [11] Liu Yan-Mei, Chen Han-Wu, Liu Zhi-Hao, Xue Xi-Ling, Zhu Wan-Ning. Scattering quantum walk search algorithm on star graph. Acta Physica Sinica, 2015, 64(1): 010301. doi: 10.7498/aps.64.010301
    [12] Wang Zhi-Hao, Wang Ya-Li, Li Tuo, Shi Yi-Shi. Ptychographical imaging algorithm based on illuminating beam matched with rotationalphase encoding. Acta Physica Sinica, 2014, 63(16): 164204. doi: 10.7498/aps.63.164204
    [13] Zhou Qing-Yong, Ji Jian-Feng, Ren Hong-Fei. Quick search algorithm of X-ray pulsar period based on unevenly spaced timing data. Acta Physica Sinica, 2013, 62(1): 019701. doi: 10.7498/aps.62.019701
    [14] Zhao Xing-Tao, Zheng Yi, Han Ying, Zhou Gui-Yao, Hou Zhi-Yun, Shen Jian-Ping, Wang Chun, Hou Lan-Tian. Generation of visible and infrared broadband dispersive waves in photonic crystal fiber cladding. Acta Physica Sinica, 2013, 62(6): 064215. doi: 10.7498/aps.62.064215
    [15] Zeng Wei-You, Xie Kang, Chen Wei, Mao Shu-Zhe. Operation principle of optical waveguide isolator based on TE-TM mode conversion. Acta Physica Sinica, 2012, 61(16): 164201. doi: 10.7498/aps.61.164201
    [16] Ren Ai-Hong, Liu Zheng-Ying, Zhang Rong-Zhu, Liu Jing-Lun, Sun Nian-Chun. Bandwidth in qusai-phase-matched frequency doubling. Acta Physica Sinica, 2010, 59(10): 7050-7054. doi: 10.7498/aps.59.7050
    [17] Zhou Cheng, Gao Yan-Xia, Wang Pei-Ji, Zhang Zhong, Li Ping. Theoretical analysis of second-harmonic conversion efficiency in negative-index materials. Acta Physica Sinica, 2009, 58(2): 914-918. doi: 10.7498/aps.58.914
    [18] Ma Jing, Liu Ying. Group velocity matching in femtosecond optical parametric amplification of the KBe2BO3F2. Acta Physica Sinica, 2009, 58(7): 4697-4701. doi: 10.7498/aps.58.4697
    [19] Chen Liang, Liang Chang-Hong, Dang Xiao-Jie. Second-harmonic generation in nonlinear left-handed metamaterials. Acta Physica Sinica, 2007, 56(11): 6398-6402. doi: 10.7498/aps.56.6398
    [20] Shao Zhong-Hao. . Acta Physica Sinica, 2001, 50(1): 73-78. doi: 10.7498/aps.50.73
Metrics
  • Abstract views:  5572
  • PDF Downloads:  294
  • Cited By: 0
Publishing process
  • Received Date:  22 April 2015
  • Accepted Date:  07 September 2015
  • Published Online:  05 December 2015

/

返回文章
返回