Search

Article

x

留言板

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

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

Search algorithm of structure anomalies in complete graph based on scattering quantum walk

Xue Xi-Ling Chen Han-Wu Liu Zhi-Hao Zhang Bin-Bin

Citation:

Search algorithm of structure anomalies in complete graph based on scattering quantum walk

Xue Xi-Ling, Chen Han-Wu, Liu Zhi-Hao, Zhang Bin-Bin
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • Quantum walks have been proven to be a useful framework in designing new quantum algorithms, of which the search algorithm is the most notable. Besides a general search for a special vertex, recent researches have shown that quantum walks can also be used to find structural anomalies. Suppose a vertex of complete graph KN is attached to a second graph G, then the kind of structure anomaly will break the symmetry of the complete graph. The search algorithm based on scattering quantum walk model is presented to speed up locating this kind of structure anomaly. The concepts of scattering quantum walk model and collapsed graphs are presented. The definition of the evolutionary operator, which is different from that of a general search, is given. Based on the specific definition of evolutionary operator and the obvious symmetry of complete graph, it is shown that the search space is confined to a low-dimensional collapsed space, and the initial state is chosen to lie in this subspace. To illustrate the evolutionary process of the search algorithm, an example is given in the case that G is a single vertex. Taking advantage of our earlier study on the evolutionary operator of coined quantum walks with Grover coin, calculations of the unitary operator in the collapsed space are greatly simplified. To quantify the evolutionary process of the algorithm, we use the matrix perturbation theory involving a perturbative approach to find the eigenvalues and eigenstates. It is the degenerate zeroth-order eigenvalue 0 = 1 that leads to the interesting parts of the Hilbert space. Most of the recent researches of searching the structure anomalies focus on star graph SN with an unspecified graph G attached to one of its external vertices, where the overall graph is divided into two parts by the central vertex. It is shown that quantum speedup will occur if and only if the eigenvalues associated with these two parts in the N limit are the same. In this paper, we find that the collapsed graph of complete graphs can also be divided into two parts by a single collapsed vertex. As these two parts roughly correspond to the initial state and the desired state respectively, the techniques and results in star graphs can be generalized to the collapse graph on complete graph. What is more, under our definition of unitary evolution operator these two parts in the N limit will always share the same eigenvalue, i.e. 0 = 1, no matter what the structure of graph G is. Based on this, we prove that the search algorithm can find the target vertex in O(N) time steps with a success probability of 1-O(1N). That is to say, the quantum search algorithm gains a quadratic speedup over classical counterpart.
      Corresponding author: Chen Han-Wu, hanwu_chen@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61502101, 61170321), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), and the Research Fund for the Doctoral Program of Higher Education, China (Grant No. 20110092110024).
    [1]

    Childs A M 2009 Phys. Rev. Lett. 102 180501

    [2]

    Childs A M, Gosset D, Webb Z 2013 Science 339 6121

    [3]

    Lovett N B, Cooper S, Everitt M, Trevers M, Kendon V 2010 Phys. Rev. A 81 042330

    [4]

    Kempe J 2003 Contemp. Phys. 44 307

    [5]

    Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314

    [6]

    Andrade F M, da Luz M G E 2009 Phys. Rev. A 80 052301

    [7]

    Karski M, Frster L, Choi J M, Steffen A, Alt W, Meschede D, Widera A 2009 Science 325 174

    [8]

    Schreiber A, Gbris A, Rohde P P, Laiho K, tefaňk M, Potocek V, Hamilton C, Jex I, Silberhorn C 2012 Science 336 55

    [9]

    Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502

    [10]

    Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307

    [11]

    Zhang Y C, Bao W S, Wang X, Fu X Q 2015 Chin. Phys. B 24 110309

    [12]

    Ambainis A 2007 SIAM J. Comput. 37 210

    [13]

    Tulsi A 2015 Phys. Rev. A 91 052307

    [14]

    Janmark J, Meyer D A, Wong T G 2014 Phys. Rev. Lett. 112 210502

    [15]

    Meyer D A, Wong T G 2015 Phys. Rev. Lett. 114 110503

    [16]

    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]

    [17]

    Hillery M, Reitzner D, Bužek V 2010 Phys. Rev. A 81 062324

    [18]

    Feldman E, Hillery M, Lee H W, Reitzner D, Zheng H, Bužek V 2010 Phys. Rev. A 82 040301R

    [19]

    Hillery M, Zheng H, Feldman E, Reitzner D, Bužek V 2012 Phys. Rev. A 85 062325

    [20]

    Cottrell S S, Hillery M 2014 Phys. Rev. Lett. 112 030501

    [21]

    Cottrell S S 2015 J. Phys. A: Math. Theor. 48 035304

    [22]

    Krovi H, Brun T A Phys. Rev. A 75 062332

    [23]

    Grover L K 1997 Phys. Rev. Lett. 79 325

    [24]

    Long G L 2001 Phys. Rev. A 64 22307

    [25]

    Bennett C H, Bernstein E, Brassard G, Vazirani U 1997 SIAM J. Comput. 26 1510

  • [1]

    Childs A M 2009 Phys. Rev. Lett. 102 180501

    [2]

    Childs A M, Gosset D, Webb Z 2013 Science 339 6121

    [3]

    Lovett N B, Cooper S, Everitt M, Trevers M, Kendon V 2010 Phys. Rev. A 81 042330

    [4]

    Kempe J 2003 Contemp. Phys. 44 307

    [5]

    Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314

    [6]

    Andrade F M, da Luz M G E 2009 Phys. Rev. A 80 052301

    [7]

    Karski M, Frster L, Choi J M, Steffen A, Alt W, Meschede D, Widera A 2009 Science 325 174

    [8]

    Schreiber A, Gbris A, Rohde P P, Laiho K, tefaňk M, Potocek V, Hamilton C, Jex I, Silberhorn C 2012 Science 336 55

    [9]

    Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502

    [10]

    Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307

    [11]

    Zhang Y C, Bao W S, Wang X, Fu X Q 2015 Chin. Phys. B 24 110309

    [12]

    Ambainis A 2007 SIAM J. Comput. 37 210

    [13]

    Tulsi A 2015 Phys. Rev. A 91 052307

    [14]

    Janmark J, Meyer D A, Wong T G 2014 Phys. Rev. Lett. 112 210502

    [15]

    Meyer D A, Wong T G 2015 Phys. Rev. Lett. 114 110503

    [16]

    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]

    [17]

    Hillery M, Reitzner D, Bužek V 2010 Phys. Rev. A 81 062324

    [18]

    Feldman E, Hillery M, Lee H W, Reitzner D, Zheng H, Bužek V 2010 Phys. Rev. A 82 040301R

    [19]

    Hillery M, Zheng H, Feldman E, Reitzner D, Bužek V 2012 Phys. Rev. A 85 062325

    [20]

    Cottrell S S, Hillery M 2014 Phys. Rev. Lett. 112 030501

    [21]

    Cottrell S S 2015 J. Phys. A: Math. Theor. 48 035304

    [22]

    Krovi H, Brun T A Phys. Rev. A 75 062332

    [23]

    Grover L K 1997 Phys. Rev. Lett. 79 325

    [24]

    Long G L 2001 Phys. Rev. A 64 22307

    [25]

    Bennett C H, Bernstein E, Brassard G, Vazirani U 1997 SIAM J. Comput. 26 1510

  • [1] Li Yan. Effects of long-range inter-particle interactions and isolated defect on quantum walks of two hard-core bosons in one-dimensional lattices. Acta Physica Sinica, 2023, 72(17): 170501. doi: 10.7498/aps.72.20230642
    [2] Liu Han-Yang, Hua Nan, Wang Yi-Nuo, Liang Jun-Qing, Ma Hong-Yang. Three dimensional image encryption algorithm based on quantum random walk and multidimensional chaos. Acta Physica Sinica, 2022, 71(17): 170303. doi: 10.7498/aps.71.20220466
    [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] Wang Yi-Nuo, Song Zhao-Yang, Ma Yu-Lin, Hua Nan, Ma Hong-Yang. Color image encryption algorithm based on DNA code and alternating quantum random walk. Acta Physica Sinica, 2021, 70(23): 230302. doi: 10.7498/aps.70.20211255
    [5] 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
    [6] Li Bao-Min, Hu Ming-Liang, Fan Heng. Quantum coherence. Acta Physica Sinica, 2019, 68(3): 030304. doi: 10.7498/aps.68.20181779
    [7] Tian Yu-Ling, Feng Tian-Feng, Zhou Xiao-Qi. Collaborative quantum computation with redundant graph state. Acta Physica Sinica, 2019, 68(11): 110302. doi: 10.7498/aps.68.20190142
    [8] An Zhi-Yun, Li Zhi-Jian. Properties of distribution and entanglement in discrete-time quantum walk with percolation. Acta Physica Sinica, 2017, 66(13): 130303. doi: 10.7498/aps.66.130303
    [9] Wang Wen-Juan, Tong Pei-Qing. Dynamic behaviors of spreading in generalized Fibonacci time quasiperiodic quantum walks. Acta Physica Sinica, 2016, 65(16): 160501. doi: 10.7498/aps.65.160501
    [10] Wang Dan-Dan, Li Zhi-Jian. Resonance transmission of one-dimensional quantum walk with phase defects. Acta Physica Sinica, 2016, 65(6): 060301. doi: 10.7498/aps.65.060301
    [11] Liang Jian-Wu, Cheng Zi, Shi Jin-Jing, Guo Ying. Quantum secret sharing with quantum graph states. Acta Physica Sinica, 2016, 65(16): 160301. doi: 10.7498/aps.65.160301
    [12] Chen Han-Wu, Li Ke, Zhao Sheng-Mei. Quantum walk search algorithm based on phase matching and circuit cmplementation. Acta Physica Sinica, 2015, 64(24): 240301. doi: 10.7498/aps.64.240301
    [13] 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
    [14] Xiao Yan-Dong, Lao Song-Yang, Hou Lü-Lin, Bai Liang. A navigation search model based on subnet of maximum controllability. Acta Physica Sinica, 2013, 62(24): 248901. doi: 10.7498/aps.62.248901
    [15] Ren Chun-Nian, Shi Peng, Liu Kai, Li Wen-Dong, Zhao Jie, Gu Yong-Jian. Effects of initial states on continuous-time quantum walk in the optical waveguide array. Acta Physica Sinica, 2013, 62(9): 090301. doi: 10.7498/aps.62.090301
    [16] Xu Jian, Chen Xiao-Yu, Li Hai-Tao. Determing the entanglement of quantum nonbinary graph states. Acta Physica Sinica, 2012, 61(22): 220304. doi: 10.7498/aps.61.220304
    [17] Peng Jin-Ye, Wang Yun-Jiang, Wang Xin-Mei, Bai Bao-Ming. Feedback sum-product decoding of sparse quantum codes for X-Z Pauli channels. Acta Physica Sinica, 2011, 60(3): 030306. doi: 10.7498/aps.60.030306
    [18] Wang Yun-Jiang, Bai Bao-Ming, Wang Xin-Mei. Feedback iterative decoding of sparse quantum codes. Acta Physica Sinica, 2010, 59(11): 7591-7595. doi: 10.7498/aps.59.7591
    [19] XU ZONG-RONG, GAO YAN-LIN. . Acta Physica Sinica, 1995, 44(1): 24-28. doi: 10.7498/aps.44.24
    [20] PAN XIAO-CHUAN, LIANG XIAO-LING, LI JIA-MING. QUANTUM DEFECT THEORY——THEORETICAL MULTIPLE-SCATTERING CALCULATIONS. Acta Physica Sinica, 1987, 36(4): 426-435. doi: 10.7498/aps.36.426
Metrics
  • Abstract views:  4837
  • PDF Downloads:  187
  • Cited By: 0
Publishing process
  • Received Date:  02 November 2015
  • Accepted Date:  11 January 2016
  • Published Online:  05 April 2016

/

返回文章
返回