|
|
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.
|
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
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|