[1]陈汉武,李文骞,刘志昊,等.完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨[J].东南大学学报(自然科学版),2017,47(5):866-872.[doi:10.3969/j.issn.1001-0505.2017.05.005]
 Chen Hanwu,Li Wenqian,Liu Zhihao,et al.Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking[J].Journal of Southeast University (Natural Science Edition),2017,47(5):866-872.[doi:10.3969/j.issn.1001-0505.2017.05.005]
点击复制

完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
47
期数:
2017年第5期
页码:
866-872
栏目:
计算机科学与工程
出版日期:
2017-09-20

文章信息/Info

Title:
Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking
作者:
陈汉武12李文骞13刘志昊12赵生妹4
1东南大学计算机科学与工程学院, 南京 211189; 2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189; 3南京森林公安学院信息技术系, 南京 210023; 4南京邮电大学通信与信息工程学院, 南京 210003
Author(s):
Chen Hanwu12 Li Wenqian13 Liu Zhihao12 Zhao Shengmei4
1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
3 Department of Information Technology, Nanjing Forest Police College, Nanjing 210023, China
4College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
关键词:
散射量子行走 完全图 结构异常 不变子空间 微扰理论
Keywords:
scattering quantum walk complete graph structural anomalies invariant subspace perturbation theory
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2017.05.005
摘要:
采用量子计算思维探索新的图结构搜索方法,提出了一种基于散射量子行走的完全图上结构异常的搜索算法.在N个顶点的完全图上外接一个悬挂点,既破坏了完全图的对称性,也预示着图的拓扑结构将发生变化.首先给出完全图上散射量子行走酉算子U的解析刻画,将行走的Hilbert空间投影到低维不变子空间S,并给出酉算子U在空间S中的作用US的形式;然后将完全图中所有状态的均匀叠加态选择为行走的初态,借用微扰理论求出酉算子US的本征值和特征向量,通过数学解析计算出行走的终态(悬挂点);最后分析算法的时间复杂度和成功概率.算法分析及Matlab仿真结果表明,利用散射量子行走可以在O((N)1/2)步内以接近于1的概率找到异常位置,而经典算法中使用邻接矩阵查找该异常点的时间复杂度为O(N),因此相对特定问题和特定的经典算法,使用散射量子行走搜索算法可以实现二次加速.
Abstract:
Quantum computing thinking is used to explore new search methods for graph structures. A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph, in which the number of vertices is N, breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First, the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a lower-dimensional invariant subspace S, and the action of the evolutionary operator in the subspace US is given. Then, the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of US is calculated by using the perturbation theory, and the final state(pendants)of the algorithm is solved. Finally, the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2)12 steps with the probability near to 1. However, the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O(N). Therefore, the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.

参考文献/References:

[1] Toyama F M, van Dijk W, Nogami Y. Quantum search with certainty based on modified Grover algorithms: Optimum choice of parameters[J]. Quantum Information Processing, 2012, 12(5): 1897-1914. DOI:10.1007/s11128-012-0498-0.
[2] Liu Y, Zhang F. First experimental demonstration of an exact quantum search algorithm in nuclear magnetic resonance system[J]. Science China Physics, Mechanics & Astronomy, 2015, 58(7): 1-6. DOI:10.1007/s11433-015-5661-z.
[3] Long G L. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64(2). DOI:10.1103/physreva.64.022307.
[4] Long G, Liu Y. Search an unsorted database with quantum mechanics[J]. Frontiers of Computer Science in China, 2007, 1(3): 247-271. DOI:10.1007/s11704-007-0026-z.
[5] Kempe J. Quantum random walks: An introductory overview[J]. Contemporary Physics, 2009, 50(1): 339-359. DOI:10.1080/00107510902734722.
[6] Aharonov Y, Davidovich L, Zagury N. Quantum random walks[J]. Physical Review A, 1993, 48(2): 1687-1690. DOI:10.1103/physreva.48.1687.
[7] Shenvi N, Kempe J, Whaley K B. Quantum random-walk search algorithm[J]. Physical Review A, 2003, 67(5). DOI:10.1103/physreva.67.052307.
[8] Childs A M. Universal computation by quantum walk[J]. Phys Rev Lett, 2009, 102(18): 180501. DOI:10.1103/PhysRevLett.102.180501.
[9] Lovett N B, Cooper S, Everitt M, et al. Universal quantum computation using the discrete-time quantum walk[J]. Physical Review A, 2010, 81(4): 042330. DOI:10.1103/physreva.81.042330.
[10] Ambainis A, Bach E, Nayak A, et al. One-dimensional quantum walks [C]//Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Heraklion, Greece, 2001: 37-49. DOI:10.1145/380752.380757.
[11] Aharonov D, Ambainis A, Kempe J, et al. Quantum walks on graphs [C]//Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Heraklion, Greece, 2001: 50-59.DOI:10.1145/380752.380758.
[12] Childs A M, Farhi E, Gutmann S. An example of the difference between quantum and classical random walks [J]. Quantum Information Processing, 2002, 1(1/2): 35-43.DOI: https://doi.org/10.1023/A:1019609420309.
[13] Ambainis A, Kempe J, Rivosh A. Coins make quantum walks faster [C]//Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Philadelphia, USA, 2005: 1099-1108.
[14] Hillery M, Bergou J, Feldman E. Quantum walks based on an interferometric analogy [J]. Physical Review A, 2003, 68(3):032314. DOI:10.1103/physreva.68.032314.
[15] Andrade F M,da Luz M G E. Equivalence between discrete quantum walk models in arbitrary topologies [J]. Physical Review A, 2009, 80(5): 052301. DOI:10.1103/physreva.80.052301.
[16] 刘艳梅, 陈汉武, 刘志昊, 等. 星图上的散射量子行走搜索算法[J]. 物理学报, 2015, 64(1): 010301. DOI:10.7498/aps.64.010301.
Liu Yanmei, Chen Hanwu, Liu Zhihao, et al. Scattering quantum walk search algorithm on star graph[J]. Acta Physica Sinica, 2015, 64(1): 010301. DOI:10.7498/aps.64.010301. (in Chinese)
[17] Childs A M. On the relationship between continuous-and discrete-time quantum walk [J]. Communications in Mathematical Physics, 2010, 294(2): 581-603. DOI:10.1007/s00220-009-0930-1.
[18] Kempe J. Discrete quantum walks hit exponentially faster[J]. Probability Theory and Related Fields, 2005, 133(2): 215-235. DOI:10.1007/s00440-004-0423-2.
[19] Travaglione B C, Milburn G J. Implementing the quantum random walk[J]. Physical Review A, 2002, 65(3). DOI:10.1103/physreva.65.032310.
[20] Wang C, Li Y, Hao L. Optical implementation of quantum random walks using weak cross-Kerr media[J]. Chinese Science Bulletin, 2011, 56(20): 2088-2091. DOI:10.1007/s11434-011-4545-5.
[21] Xue P, Zhang R, Qin H, et al. Experimental quantum-walk revival with a time-dependent coin [J]. Physical Review Letters, 2015, 114(14): 140502. DOI:10.1103/PhysRevLett.114.140502.
[22] Ambainis A. Quantum walk algorithm for element distinctness [J]. SIAM Journal on Computing, 2007, 37(1): 210-239. DOI:10.1137/s0097539705447311.
[23] Childs A M, Eisenberg J M. Quantum algorithms for subset finding [J]. Quantum Information & Computation, 2003, 5(7):593-604.
[24] Wang H, Ma Z, Ma C. An efficient quantum meet-in-the-middle attack against NTRU-2005[J]. Chinese Science Bulletin, 2013, 58(28): 3514-3518. DOI:10.1007/s11434-013-6020-y.
[25] Lee J, Lee H W, Hillery M. Searches on star graphs and equivalent oracle problems [J]. Physical Review A, 2011, 83(2): 022318. DOI:https://doi.org/10.1103/PhysRevA.83.022318.
[26] Potoˇ/cek V, Gábris A, Kiss T, et al. Optimized quantum random-walk search algorithms on the hypercube [J]. Physical Review A, 2009, 79(1): 012325. DOI:10.1103/physreva.79.012325.
[27] Reitzner D, Hillery M, Feldman E, et al. Quantum searches on highly symmetric graphs [J]. Physical Review A, 2009, 79(1): 012323. DOI:10.1103/physreva.79.012323.
[28] Feldman E, Hillery M, Lee H W, et al. Finding structural anomalies in graphs by means of quantum walks [J]. Physical Review A, 2010, 82(4): 83-79. DOI:https://doi.org/10.1103/PhysRevA.82.040301.
[29] Hillery M, Zheng H, Feldman E, et al. Quantum walks as a probe of structural anomalies in graphs [J]. Physical Review A, 2012, 85(6): 062325. DOI:10.1103/physreva.85.062325.
[30] Cottrell S, Hillery M. Finding structural anomalies in star graphs using quantum walks[J]. Phys Rev Lett, 2014, 112(3): 030501. DOI:10.1103/PhysRevLett.112.030501.
[31] 薛希玲, 李文骞, 陈汉武, 等. 基于 Grover 硬币算子的量子行走在商图上的演化算子[J]. 电子学报, 2016, 44(3): 555-559. DOI:10.3969/j.issn.0372-2112.2016.03.009.
Xue Xiling, Li Wenqian, Chen Hanwu, et al. The evolutionary operator of quantum walks with Grover coin on quotient graph[J]. 2016, 44(3): 555-559. DOI:10.3969/j.issn.0372-2112.2016.03.009. (in Chinese)

备注/Memo

备注/Memo:
收稿日期: 2017-02-20.
作者简介: 陈汉武(1955—),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
引用本文: 陈汉武,李文骞,刘志昊,等.完全图上结构异常的搜索算法:融入量子计算思维的经典算法探讨[J].东南大学学报(自然科学版),2017,47(5):866-872. DOI:10.3969/j.issn.1001-0505.2017.05.005.
更新日期/Last Update: 2017-09-20