Please wait a minute...
Chin. Phys. B, 2017, Vol. 26(1): 010301    DOI: 10.1088/1674-1056/26/1/010301
GENERAL   Next  

Search algorithm on strongly regular graphsbased on scattering quantum walks

Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武)
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Abstract  

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs (SRGs) with parameters (N,k,λ,μ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs. The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as √N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

Keywords:  scattering quantum walk      quantum search      strongly regular graph  
Received:  13 August 2016      Revised:  24 October 2016      Accepted manuscript online: 
PACS:  03.67.Ac (Quantum algorithms, protocols, and simulations)  
  03.67.Lx (Quantum computation architectures and implementations)  
  03.65.Aa (Quantum systems with finite Hilbert space)  
Fund: 

Project supported by the National Natural Science Foundation of China (Grant Nos. 61502101 and 61170321), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), and the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110092110024).

Corresponding Authors:  Han-Wu Chen     E-mail:  hanwu_chen@163.com

Cite this article: 

Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武) Search algorithm on strongly regular graphsbased on scattering quantum walks 2017 Chin. Phys. B 26 010301

[1] Childs A M 2009 Phys. Rev. Lett. 102 180501
[2] Childs A M, Gosset D and Webb Z 2013 Science 339 6121
[3] Lovett N B, CooperS, Everitt M, Trevers M and Kendon V 2010 Phys. Rev. A 81 042330
[4] Andrade F M and da Luz M G E 2009 Phys. Rev. A 80 052301
[5] Fu Z, Ren K, Shu J, Sun X and Huang F 2016 IEEE T. Parall. Distr. 27 2546
[6] Xia Z, Wang X, Sun X and Wang Q 2015 IEEE T. Parall. Distr. 27 340
[7] Fu Z, Sun X, Liu Q, Zhou L and Shu J 2015 IEICE T. Commun. E98-B 190
[8] Liu W J, Wang H B, Yuan G L, Xu Y, Chen Z Y, An X X, Ji F G and Gnitou G T 2016 Quantum Inf. Process. 15 869
[9] Liu W J, Wang F, Ji S, Qu Z G and Wang X J 2014 Commun. Theor. Phys. 61 686
[10] ShenviN, KempeJ and K Birgitta W 2003 Phys. Rev. A 67 052307
[11] Ambainis A, Kempe J and Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, January 23-25, 2005, Vancouver, Canada, p. 1099
[12] Ambainis A 2007 SIAM Journal on Computing 37 210
[13] Reitzner D, Hillery M and Feldman E 2009 Phys. Rev. A 79 012323
[14] Hillery M, Reitzner D and Bužek V 2010 Phys. Rev. A 81 062324
[15] Janmark J, Meyer D A and Wong T G 2014 Phys. Rev. Lett. 112 210502
[16] Liu Y M, Chen H W, Liu Z H, Xue X L and Zhu W N 2015 Acta Phys. Sin. 64 010301 (in Chinese)
[17] Zhang Y C, Bao W S, Wang X and Fu X Q 2015 Chin. Phys. B 24 110309
[18] Feldman E, Hillery M, Lee H W, Reitzner D, Zheng H and Bužek V 2010 Phys. Rev. A 82 040301R
[19] Hillery M, Zheng H, Feldman E, Reitzner D and Bužek V 2012 Phys. Rev. A 85 062325
[20] Xue X L, Chen H W, Liu Z H and Zhang B B 2016 Acta Phys. Sin. 65 080302 (in Chinese)
[21] Cottrell S S and Hillery M 2014 Phys. Rev. Lett. 112 030501
[22] Cottrell S S 2015 J. Phys. A:Math. Theor. 48 035304
[23] Xie S and Wang Y 2014 Wireless. Pers. Commun. 78 231
[24] Ma T, Zhou J, Tang M, Tian Y, Al-Dhelaan A, Al-Rodhaan M and Lee S 2015 IEICE. T. Inf. Syst. E98D 902
[25] Krovi H and Brun T A 2007 Phys. Rev. A 75 062332
[26] Grover L K 1997 Phys. Rev. Lett. 79 325
[27] Mahasinghe A, Wang J B and Wijerathna J K 2014 J. Phys. A 47 505301
[28] Wang H Q, Wu J J, Yang X J and Xun Y 2015 J. Phys. A:Math. Theor. 48 115302
[1] Quantum search of many vertices on the joined complete graph
Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Chin. Phys. B, 2022, 31(7): 070504.
[2] Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method
Tan Li(李坦), Shuo Zhang(张硕), Xiang-Qun Fu(付向群), Xiang Wang(汪翔), Yang Wang(汪洋), Jie Lin(林杰), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2019, 28(12): 120301.
[3] 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.
[4] Decoherence in optimized quantum random-walk search algorithm
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(8): 080307.
[5] Effects of systematic phase errors on optimized quantum random-walk search algorithm
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(6): 060304.
[6] Optimized quantum random-walk search algorithm for multi-solution search
Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(11): 110309.
[7] Partial evolution based local adiabatic quantum search
Sun Jie(孙杰), Lu Song-Feng(路松峰), Liu Fang(刘芳), and Yang Li-Ping(杨莉萍) . Chin. Phys. B, 2012, 21(1): 010306.
[8] A quantum search algorithm based on partial adiabatic evolution
Zhang Ying-Yu(张映玉), Hu He-Ping(胡和平), and Lu Song-Feng(路松峰) . Chin. Phys. B, 2011, 20(4): 040309.
[9] Implementation of quantum search scheme by adiabatic passage in a cavity--laser--atom system
Liu Wen-Wu(刘文武), Li Hong-Cai(李洪才), and Yang Rong-Can(杨榕灿). Chin. Phys. B, 2009, 18(1): 23-29.
No Suggested Reading articles found!