搜索

x

留言板

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

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

基于散射量子行走的完全图上结构异常搜索算法

薛希玲 陈汉武 刘志昊 章彬彬

引用本文:
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
导出引用
  • 完全图KN 上某个顶点连接到图G将破坏其对称性. 为加速定位这类结构异常, 基于散射量子行走模型设计搜索算法, 首先给出了算法酉算子的定义, 在此基础上利用完全图的对称性, 将算法的搜索空间限定为一个低维的坍缩图空间. 以G为一个顶点的情况为例, 利用硬币量子行走模型上的研究结论简化了坍缩图空间中酉算子的计算, 并借助矩阵扰动理论分析算法演化过程. 针对星图SN 上结构异常的研究表明, 以星图中心节点为界将整个图分为左右两个部分, 当且仅当两部分在N时具有相同的特征值, 搜索算法可以获得量子加速. 本文说明星图上的分析方法和结论可以推广至完全图的坍缩图上. 基于此, 本文证明无论完全图连接的图G结构如何, 搜索算法均可在O(N) 时间内定位到目标顶点, 成功概率为1-O(1N), 即量子行走搜索该类异常与经典搜索相比有二次加速.
    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.
      通信作者: 陈汉武, hanwu_chen@163.com
    • 基金项目: 国家自然科学基金(批准号: 61502101, 61170321)、江苏省自然科学基金(批准号: BK20140651) 和高等学校博士学科点专项科研基金(批准号: 20110092110024)资助的课题.
      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] 李艳. 粒子间长程相互作用以及晶格中孤立缺陷点对两硬核玻色子在一维晶格势阱中量子行走的影响. 物理学报, 2023, 72(17): 170501. doi: 10.7498/aps.72.20230642
    [2] 刘瀚扬, 华南, 王一诺, 梁俊卿, 马鸿洋. 基于量子随机行走和多维混沌的三维图像加密算法. 物理学报, 2022, 71(17): 170303. doi: 10.7498/aps.71.20220466
    [3] 姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子行走的反馈搜索算法. 物理学报, 2022, 71(3): 030201. doi: 10.7498/aps.71.20211000
    [4] 王一诺, 宋昭阳, 马玉林, 华南, 马鸿洋. 基于DNA编码与交替量子随机行走的彩色图像加密算法. 物理学报, 2021, 70(23): 230302. doi: 10.7498/aps.70.20211255
    [5] 姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子漫步的反馈搜索算法. 物理学报, 2021, (): . doi: 10.7498/aps.70.20211000
    [6] 李保民, 胡明亮, 范桁. 量子相干. 物理学报, 2019, 68(3): 030304. doi: 10.7498/aps.68.20181779
    [7] 田宇玲, 冯田峰, 周晓祺. 基于冗余图态的多人协作量子计算. 物理学报, 2019, 68(11): 110302. doi: 10.7498/aps.68.20190142
    [8] 安志云, 李志坚. 逾渗分立时间量子行走的传输及纠缠特性. 物理学报, 2017, 66(13): 130303. doi: 10.7498/aps.66.130303
    [9] 王文娟, 童培庆. 广义Fibonacci时间准周期量子行走波包扩散的动力学特性. 物理学报, 2016, 65(16): 160501. doi: 10.7498/aps.65.160501
    [10] 王丹丹, 李志坚. 一维相位缺陷量子行走的共振传输. 物理学报, 2016, 65(6): 060301. doi: 10.7498/aps.65.060301
    [11] 梁建武, 程资, 石金晶, 郭迎. 基于量子图态的量子秘密共享. 物理学报, 2016, 65(16): 160301. doi: 10.7498/aps.65.160301
    [12] 陈汉武, 李科, 赵生妹. 基于相位匹配的量子行走搜索算法及电路实现. 物理学报, 2015, 64(24): 240301. doi: 10.7498/aps.64.240301
    [13] 刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁. 星图上的散射量子行走搜索算法. 物理学报, 2015, 64(1): 010301. doi: 10.7498/aps.64.010301
    [14] 肖延东, 老松杨, 侯绿林, 白亮. 一种基于网络最大可控子图的导航搜索模型. 物理学报, 2013, 62(24): 248901. doi: 10.7498/aps.62.248901
    [15] 任春年, 史鹏, 刘凯, 李文东, 赵洁, 顾永建. 初态对光波导阵列中连续量子行走影响的研究. 物理学报, 2013, 62(9): 090301. doi: 10.7498/aps.62.090301
    [16] 徐健, 陈小余, 李海涛. 多进制量子图态纠缠的确定. 物理学报, 2012, 61(22): 220304. doi: 10.7498/aps.61.220304
    [17] 王云江, 白宝明, 彭进业, 王新梅. 针对X-Z型Pauli信道的量子稀疏图码的反馈式和积译码算法. 物理学报, 2011, 60(3): 030306. doi: 10.7498/aps.60.030306
    [18] 王云江, 白宝明, 王新梅. 量子稀疏图码的反馈式迭代译码. 物理学报, 2010, 59(11): 7591-7595. doi: 10.7498/aps.59.7591
    [19] 许宗荣, 高艳玲. 量子散射跃迁矩阵元的双线性变分法. 物理学报, 1995, 44(1): 24-28. doi: 10.7498/aps.44.24
    [20] 潘晓川, 梁晓玲, 李家明. 量子数亏损理论——多重散射计算方法. 物理学报, 1987, 36(4): 426-435. doi: 10.7498/aps.36.426
计量
  • 文章访问数:  4809
  • PDF下载量:  186
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-11-02
  • 修回日期:  2016-01-11
  • 刊出日期:  2016-04-05

/

返回文章
返回