-
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.
-
Keywords:
- scattering quantum walk /
- quantum search /
- complete graph
[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
Catalog
Metrics
- Abstract views: 6193
- PDF Downloads: 196
- Cited By: 0
下载:
