搜索

x

留言板

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

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

基于置换群的多粒子环上量子行走的反馈搜索算法

姜瑶瑶 张文彬 初鹏程 马鸿洋

引用本文:
Citation:

基于置换群的多粒子环上量子行走的反馈搜索算法

姜瑶瑶, 张文彬, 初鹏程, 马鸿洋

Feedback search algorithm for multi-particle quantum walks over a ring based on permutation groups

Jiang Yao-Yao, Zhang Wen-Bin, Chu Peng-Cheng, Ma Hong-Yang
PDF
HTML
导出引用
  • 在量子计算科学中, 如何更好地构建量子搜索算法一直以来受到学者们的广泛关注, 并且基于量子行走寻找新的搜索算法也仍吸引着学者们不断深入研究与探索. 本文从减少搜索过程中的时间消耗、增加算法搜索的准确性和可控性等多方面进行考虑, 提出了一种基于置换群的多粒子量子行走搜索算法. 首先分析得到置换群在空间中可看成一个闭环, 定义了置换集合, 并且通过同构映射将数据点所在数据集映射到定义的置换集, 使得置换集合中元素数据点形成一一对应的关系. 其次, 根据给定初始态和硬币算符, 在数据点集与置换集合张成的搜索空间中利用多粒子的量子行走在环上进行目标数据搜索. 最后, 根据函数$\varPhi(w)=1$找到目标数据, 并用量子态存储数值, 用于形成搜索算法的反馈控制; 同时通过控制硬币算符从而控制量子行走在环上的行走方向, 增加搜索的可操作性与准确性. 本文利用多粒子的量子行走进行搜索, 分析得到粒子数量参数j与时间复杂度呈非线性负相关; 提出的量子行走搜索算法符合零点条件与下确界条件, 且不受变量数j的影响; 通过数值分析得到量子行走搜索算法的时间复杂度等价于$O(\sqrt[^3]{N})$, 相比于Grover搜索算法提高了搜索效率.
    In quantum computing science, much attention has been paid to how to construct quantum search algorithms better, moreover, searching for new search algorithms based on quantum walk is still attracting scholars' continuous in-depth research and exploration. In this paper, a multi-particle quantum walk search algorithm based on permutation group is proposed by considering many aspects, such as reducing time consumption and increasing the accuracy and controllability of algorithm search. Firstly, the permutation group can be regarded as a closed loop in space, and the permutation set is defined. The data set of data points is mapped to the defined permutation set by isomorphism mapping, which makes the element data points in the permutation set form a one-to-one correspondence. Secondly, according to the given initial state and coin operator, the target data search is carried out on the ring by using the quantum walk of multiple particles in the search space of the data point set and the permutation set. Finally, the target data is found according to the function $\varPhi(w)=1 $, and the value is stored by the quantum state, which is used to form the feedback control of the search algorithm. At the same time, the direction of quantum walking on the ring is controlled by controlling the coin operator, thus increasing the operability and accuracy of the search. In this paper, the quantum walk of multiple particles is used to search, and the analysis shows that the particle number parameter j is negatively correlated with the time complexity, but not negatively linear. The proposed quantum walk search algorithm conforms to the zero condition and the lower bound condition, and is not affected by the variable parameter j. Through numerical analysis, it is found that the time complexity of the quantum walk search algorithm is equivalent to $O(\sqrt[3]{N})$, which improves the search efficiency compared with the Grover search algorithm.
      通信作者: 马鸿洋, hongyang_ma@aliyun.com
    • 基金项目: 国家自然科学基金(批准号: 11975132, 61772295)、山东省自然科学基金(批准号: ZR2019YQ01)与山东省高等教育科技计划(批准号: J18KZ012)资助课题.
      Corresponding author: Ma Hong-Yang, hongyang_ma@aliyun.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 11975132, 61772295), the Natural Science Foundation of Shandong Province, China (Grant No. ZR2019YQ01), and the Project of Higher Educational Science and Technology Program of Shandong Province, China (Grant No. J18KZ012).
    [1]

    Aharonov Y, Luiz D, Nicim Z 1993 Phys. Rev. A 48 1687Google Scholar

    [2]

    Farhi E, Gutmann S 1998 Phys. Rev. A 58 915Google Scholar

    [3]

    Godsil C, Kirkland S, Severini S, Smith J 2012 Phys. Rev. Lett. 109 050502Google Scholar

    [4]

    Bose S 2003 Phys. Rev. Lett. 91 207901Google Scholar

    [5]

    Childs A M 2009 Phys. Rev. Lett. 102 180501Google Scholar

    [6]

    Berry S D, Wang J B 2011 Phys. Rev. A 83 042317

    [7]

    Zähringer F, Kirchmair G, Gerritsma R, Solano E, Blatt R, Roos C F 2010 Phys. Rev. Lett. 104 100503Google Scholar

    [8]

    Ma H Y, Zhang X, Xu P A, Liu F 2020 Wirel. Pers. Commun. 113 2203Google Scholar

    [9]

    Wocjan P, Abeyesinghe A 2008 Phys. Rev. A 78 042336Google Scholar

    [10]

    Orsucci D, Briegel H J, Dunjko V 2018 Quantum 2 105Google Scholar

    [11]

    Chakraborty S, Novo L, Ambainis A, Omar Y 2016 Phys. Rev. Lett. 116 100501Google Scholar

    [12]

    Chakraborty S, Novo L, Di Giorgio S, Omar Y 2017 Phys. Rev. Lett. 119 220503Google Scholar

    [13]

    Chang C R, Lin Y C, Chiu K L, Huang T W 2020 AAPPS Bull. 30 9Google Scholar

    [14]

    Childs A M 2010 Commun. Math. Phys. 294 581Google Scholar

    [15]

    Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307Google Scholar

    [16]

    Sansoni L, Sciarrino F, Vallone G, Mataloni P, Crespi A, Ramponi R, Osellame R 2012 Phys. Rev. Lett. 108 010502Google Scholar

    [17]

    Caruso F 2014 New J. Phys. 16 055015Google Scholar

    [18]

    Liu F, Zhang X, Xu P A, He Z X, Ma H Y 2020 Int. J. Theor. Phys. 59 3491Google Scholar

    [19]

    Dunjko V, Briegel H J 2015 New J. Phys. 17 073004Google Scholar

    [20]

    Glos A, Krawiec A, Kukulski R, PuchaPuchała Z 2018 Quantum Inf. Process. 17 1Google Scholar

    [21]

    Mülken O, Blumen A 2011 Phys. Rep. 502 37Google Scholar

    [22]

    Long G L, Wang C, Deng F G, Zheng C 2013 Conference on Coherence and Quantum Optics Rochester, New York, USA, June 17–20, 2013 ppM6–42

    [23]

    Kempf A, Portugal R 2009 Phys. Rev. A 79 052317Google Scholar

    [24]

    Zhou L, Sheng Y B, Long G L 2020 Sci. Bull. 65 12Google Scholar

    [25]

    Zhou Z, Sheng Y, Niu P, Yin L, Long G L, Hanzo L 2020 Sci. China: Phys. Mech. Astron. 63 1Google Scholar

    [26]

    Long G L 2001 Phys. Rev. A 64 022307Google Scholar

    [27]

    Zhou N R, Huang L X, Gong L H, Zeng Q W 2020 Quantum Inf. Process. 19 1Google Scholar

    [28]

    Zhou N R, Zhu K N, Zou X F 2019 Ann. Phys. 531 1800520Google Scholar

    [29]

    Zhou N R, Zhu K N, Bi W, Gong L H 2019 Quantum Inf. Process. 18 1Google Scholar

    [30]

    Li H H, Gong L H, Zhou N R 2020 Chin. Phys. B 29 110304Google Scholar

    [31]

    Sheng Y B, Zhou L 2018 Phys. Rev. A 98 052343Google Scholar

    [32]

    Sheng Y B, Zhou L 2017 Sci. Bull. 62 1025Google Scholar

    [33]

    张禾瑞 1997 近世代数基础 (修订本) (北京: 高等教育出版社) 第50页

    Zhang H R 1997 Base of Recent Generations (Vol. 19) (Beijing: Higher Education Press) p50 (in Chinese)

    [34]

    Schreiber A, Cassemiro K N, Potoček V, Gábris A, Mosley P J, Andersson E, Jex I, Silberhorn Ch 2010 Phys. Rev. Lett. 104 050502Google Scholar

    [35]

    Diaconis P, Rockmore D 1990 J. Am. Math. Soc. 3 297Google Scholar

    [36]

    Toyama F M, Van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 p1897Google Scholar

  • 图 1  置换群$ S_{3} $中每个元素的旋转方位图

    Fig. 1.  Diagram of the rotation position of each element in the permutation group $ S_{3} $.

    图 2  在每个子群中各个元素之间的旋转关系图

    Fig. 2.  Diagram of the rotation relationship between the elements in each subgroup.

    图 3  集合W, $ W _{-1} $$ W _{\lambda} $元素之间的对应关系

    Fig. 3.  Corresponding relationship between elements of the sets W, $ W _{-1} $ and $ W _{\lambda} $.

    图 4  量子行走的过程

    Fig. 4.  Process of quantum walk.

    图 5  两种搜索算法时间按复杂度的对比

    Fig. 5.  Comparison of the time complexity of two search algorithms.

    图 6  参数j对搜索算法时间复杂度的影响

    Fig. 6.  Influence of parameter j on the time complexity of search algorithm.

    表 1  置换集合元素分布情况

    Table 1.  Distribution of the elements in permutation set.

    子群 子群族 群内所在元素
    $H_{1}$ $H_{1}^{1}$ $p(1, 1, 1), \; p(1, 1, 2)$
    $\vdots$ $\vdots$
    $H_{1}^{j_{1}}$ $p(1, j_{1}, 1)$, $p(1, j_{1}, 2)$
    $H_{i}$ $H_{i}^{1}$ $p(i, 1, 1), \; p(i, 1, 2)$
    $\vdots$ $\vdots$
    $H_{i}^{j_{i}}$ $p(i, j_{i}, 1)$, $p(i, j_{i}, 2)$
    下载: 导出CSV

    表 2  数据仿真结果

    Table 2.  Numerical simulation results.

    数据点数量N $ j = 1 $ $ j = 2$ $ j = 3 $
    1024 3 2 1
    2048 4 2 2
    4096 4 2 2
    8192 6 3 2
    16384 7 4 3
    32768 8 4 3
    下载: 导出CSV
  • [1]

    Aharonov Y, Luiz D, Nicim Z 1993 Phys. Rev. A 48 1687Google Scholar

    [2]

    Farhi E, Gutmann S 1998 Phys. Rev. A 58 915Google Scholar

    [3]

    Godsil C, Kirkland S, Severini S, Smith J 2012 Phys. Rev. Lett. 109 050502Google Scholar

    [4]

    Bose S 2003 Phys. Rev. Lett. 91 207901Google Scholar

    [5]

    Childs A M 2009 Phys. Rev. Lett. 102 180501Google Scholar

    [6]

    Berry S D, Wang J B 2011 Phys. Rev. A 83 042317

    [7]

    Zähringer F, Kirchmair G, Gerritsma R, Solano E, Blatt R, Roos C F 2010 Phys. Rev. Lett. 104 100503Google Scholar

    [8]

    Ma H Y, Zhang X, Xu P A, Liu F 2020 Wirel. Pers. Commun. 113 2203Google Scholar

    [9]

    Wocjan P, Abeyesinghe A 2008 Phys. Rev. A 78 042336Google Scholar

    [10]

    Orsucci D, Briegel H J, Dunjko V 2018 Quantum 2 105Google Scholar

    [11]

    Chakraborty S, Novo L, Ambainis A, Omar Y 2016 Phys. Rev. Lett. 116 100501Google Scholar

    [12]

    Chakraborty S, Novo L, Di Giorgio S, Omar Y 2017 Phys. Rev. Lett. 119 220503Google Scholar

    [13]

    Chang C R, Lin Y C, Chiu K L, Huang T W 2020 AAPPS Bull. 30 9Google Scholar

    [14]

    Childs A M 2010 Commun. Math. Phys. 294 581Google Scholar

    [15]

    Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307Google Scholar

    [16]

    Sansoni L, Sciarrino F, Vallone G, Mataloni P, Crespi A, Ramponi R, Osellame R 2012 Phys. Rev. Lett. 108 010502Google Scholar

    [17]

    Caruso F 2014 New J. Phys. 16 055015Google Scholar

    [18]

    Liu F, Zhang X, Xu P A, He Z X, Ma H Y 2020 Int. J. Theor. Phys. 59 3491Google Scholar

    [19]

    Dunjko V, Briegel H J 2015 New J. Phys. 17 073004Google Scholar

    [20]

    Glos A, Krawiec A, Kukulski R, PuchaPuchała Z 2018 Quantum Inf. Process. 17 1Google Scholar

    [21]

    Mülken O, Blumen A 2011 Phys. Rep. 502 37Google Scholar

    [22]

    Long G L, Wang C, Deng F G, Zheng C 2013 Conference on Coherence and Quantum Optics Rochester, New York, USA, June 17–20, 2013 ppM6–42

    [23]

    Kempf A, Portugal R 2009 Phys. Rev. A 79 052317Google Scholar

    [24]

    Zhou L, Sheng Y B, Long G L 2020 Sci. Bull. 65 12Google Scholar

    [25]

    Zhou Z, Sheng Y, Niu P, Yin L, Long G L, Hanzo L 2020 Sci. China: Phys. Mech. Astron. 63 1Google Scholar

    [26]

    Long G L 2001 Phys. Rev. A 64 022307Google Scholar

    [27]

    Zhou N R, Huang L X, Gong L H, Zeng Q W 2020 Quantum Inf. Process. 19 1Google Scholar

    [28]

    Zhou N R, Zhu K N, Zou X F 2019 Ann. Phys. 531 1800520Google Scholar

    [29]

    Zhou N R, Zhu K N, Bi W, Gong L H 2019 Quantum Inf. Process. 18 1Google Scholar

    [30]

    Li H H, Gong L H, Zhou N R 2020 Chin. Phys. B 29 110304Google Scholar

    [31]

    Sheng Y B, Zhou L 2018 Phys. Rev. A 98 052343Google Scholar

    [32]

    Sheng Y B, Zhou L 2017 Sci. Bull. 62 1025Google Scholar

    [33]

    张禾瑞 1997 近世代数基础 (修订本) (北京: 高等教育出版社) 第50页

    Zhang H R 1997 Base of Recent Generations (Vol. 19) (Beijing: Higher Education Press) p50 (in Chinese)

    [34]

    Schreiber A, Cassemiro K N, Potoček V, Gábris A, Mosley P J, Andersson E, Jex I, Silberhorn Ch 2010 Phys. Rev. Lett. 104 050502Google Scholar

    [35]

    Diaconis P, Rockmore D 1990 J. Am. Math. Soc. 3 297Google Scholar

    [36]

    Toyama F M, Van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 p1897Google Scholar

  • [1] 张航, 胡月姣, 陈嘉文, 修龙汪. 程能映射下配光平移群的深度神经网络实现. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220178
    [2] 刘瀚扬, 华南, 王一诺, 梁俊卿, 马鸿洋. 基于量子随机行走和多维混沌的三维图像加密算法. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220466
    [3] 王一诺, 宋昭阳, 马玉林, 华南, 马鸿洋. 基于DNA编码与交替量子随机行走的彩色图像加密算法. 物理学报, 2021, 70(23): 230302. doi: 10.7498/aps.70.20211255
    [4] 姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子漫步的反馈搜索算法. 物理学报, 2021, (): . doi: 10.7498/aps.70.20211000
    [5] 张冬晓, 陈志斌, 肖程, 秦梦泽, 吴浩. 基于引力搜索算法的湍流相位屏生成方法. 物理学报, 2019, 68(13): 134205. doi: 10.7498/aps.68.20190081
    [6] 安志云, 李志坚. 逾渗分立时间量子行走的传输及纠缠特性. 物理学报, 2017, 66(13): 130303. doi: 10.7498/aps.66.130303
    [7] 薛希玲, 陈汉武, 刘志昊, 章彬彬. 基于散射量子行走的完全图上结构异常搜索算法. 物理学报, 2016, 65(8): 080302. doi: 10.7498/aps.65.080302
    [8] 王文娟, 童培庆. 广义Fibonacci时间准周期量子行走波包扩散的动力学特性. 物理学报, 2016, 65(16): 160501. doi: 10.7498/aps.65.160501
    [9] 王丹丹, 李志坚. 一维相位缺陷量子行走的共振传输. 物理学报, 2016, 65(6): 060301. doi: 10.7498/aps.65.060301
    [10] 陈汉武, 李科, 赵生妹. 基于相位匹配的量子行走搜索算法及电路实现. 物理学报, 2015, 64(24): 240301. doi: 10.7498/aps.64.240301
    [11] 刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁. 星图上的散射量子行走搜索算法. 物理学报, 2015, 64(1): 010301. doi: 10.7498/aps.64.010301
    [12] 李卓, 邢莉娟. 差错基、量子码与群代数. 物理学报, 2013, 62(13): 130306. doi: 10.7498/aps.62.130306
    [13] 杨芳艳, 胡明, 姚尚平. 连续时间系统同宿轨的搜索算法及其应用. 物理学报, 2013, 62(10): 100501. doi: 10.7498/aps.62.100501
    [14] 周庆勇, 姬剑锋, 任红飞. 非等间隔计时数据的X射线脉冲星周期快速搜索算法. 物理学报, 2013, 62(1): 019701. doi: 10.7498/aps.62.019701
    [15] 任春年, 史鹏, 刘凯, 李文东, 赵洁, 顾永建. 初态对光波导阵列中连续量子行走影响的研究. 物理学报, 2013, 62(9): 090301. doi: 10.7498/aps.62.090301
    [16] 赵亮, 廖晓峰, 向涛, 肖迪. 基于Z矩阵映射和选择加密的彩色图像退化算法研究. 物理学报, 2010, 59(3): 1507-1523. doi: 10.7498/aps.59.1507
    [17] 杨汝, 张波, 赵寿柏, 劳裕锦. 基于符号时间序列方法的开关变换器离散映射算法复杂度分析. 物理学报, 2010, 59(6): 3756-3762. doi: 10.7498/aps.59.3756
    [18] 汪容. 关于规范群中含有Abel子群和有Higgs场的情况下重正化前后规范群的同构. 物理学报, 1981, 30(6): 731-746. doi: 10.7498/aps.30.731
    [19] 陈金全, 王凡, 高美娟. 群表示论的物理方法(Ⅲ)——置换群外积约化系数和SUn群CG系数. 物理学报, 1978, 27(1): 31-40. doi: 10.7498/aps.27.31
    [20] 陈金全, 王凡, 高美娟. 群表示论的物理方法(Ⅱ)——置换群亚标准基和酉群Gelfand基. 物理学报, 1977, 26(5): 427-432. doi: 10.7498/aps.26.427
计量
  • 文章访问数:  927
  • PDF下载量:  135
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-05-27
  • 修回日期:  2021-09-27
  • 上网日期:  2022-01-19
  • 刊出日期:  2022-02-05

基于置换群的多粒子环上量子行走的反馈搜索算法

  • 1. 青岛理工大学理学院, 青岛 266033
  • 2. 青岛理工大学信息与控制工程学院, 青岛 266033
  • 通信作者: 马鸿洋, hongyang_ma@aliyun.com
    基金项目: 国家自然科学基金(批准号: 11975132, 61772295)、山东省自然科学基金(批准号: ZR2019YQ01)与山东省高等教育科技计划(批准号: J18KZ012)资助课题.

摘要: 在量子计算科学中, 如何更好地构建量子搜索算法一直以来受到学者们的广泛关注, 并且基于量子行走寻找新的搜索算法也仍吸引着学者们不断深入研究与探索. 本文从减少搜索过程中的时间消耗、增加算法搜索的准确性和可控性等多方面进行考虑, 提出了一种基于置换群的多粒子量子行走搜索算法. 首先分析得到置换群在空间中可看成一个闭环, 定义了置换集合, 并且通过同构映射将数据点所在数据集映射到定义的置换集, 使得置换集合中元素数据点形成一一对应的关系. 其次, 根据给定初始态和硬币算符, 在数据点集与置换集合张成的搜索空间中利用多粒子的量子行走在环上进行目标数据搜索. 最后, 根据函数$\varPhi(w)=1$找到目标数据, 并用量子态存储数值, 用于形成搜索算法的反馈控制; 同时通过控制硬币算符从而控制量子行走在环上的行走方向, 增加搜索的可操作性与准确性. 本文利用多粒子的量子行走进行搜索, 分析得到粒子数量参数j与时间复杂度呈非线性负相关; 提出的量子行走搜索算法符合零点条件与下确界条件, 且不受变量数j的影响; 通过数值分析得到量子行走搜索算法的时间复杂度等价于$O(\sqrt[^3]{N})$, 相比于Grover搜索算法提高了搜索效率.

English Abstract

    • 量子行走作为经典行走的推广, 是量子计算的基础, 被视为实现量子计算的一种主要工具. 量子行走利用量子态的叠加性, 能够实现同时行走在不同线路上的可能性, 因此与经典行走相比, 量子行走的效率有着指数级的增长. 并且行走者位置的概率分布也与经典行走有着截然不同的形式, 这些性质都有利于量子算法的实现. 量子行走最初是由Aharonov等[1]及Farhi和Gutmann[2]提出的. 其中Aharonov等[1]提出了离散时间状态下的量子行走算法; Farhi和Gutmann[2]提出了连续时间状态下的量子行走算法. 与经典行走相比, 这两种行走方法都提供了加速效果. Godsil等[3]和Bose[4]展示了如何将图论的思想应用到量子行走中来实现更好的状态传输; Childs[5]证明了量子行走可以实现普适的量子计算. 这些成果都体现了量子行走在实际应用中的重要性. 此外, 基于量子行走的许多搜索算法都体现了量子行走在算法领域具有独特的优势[6-12].

      在搜索算法中, Grover算法是第二个量子革命的一个里程碑[13]. 除了数据库搜索, 它还可以用于求解特征值问题, 这是目前最热门的课题之一. 2010年Childs[14]提出基于连续时间量子漫步的算法, 在黑箱问题中量子行走成功实现了指数级的加速. Shenvi等[15]也在超立方体的拓扑知识的基础上提出了基于离散时间量子漫步的搜索算法, 实现了多项式加速效果. 由于搜索算法以及可转化为搜索问题的算法具有广泛适用性的特点, 在这些开创性的工作之后, 学者们又进行了深入的研究[14,16-23]. 在国内, Long等[24-26]不断完善优化Grover搜索算法, 他们研究的算法是所有优化的Grover算法中最优的, 又称龙算法[26]; Zhou等[27-30]和Sheng等[31,32]也分别在量子搜索算法和量子计算领域做出了贡献. 考虑到量子计算的优势, 学者们期待大量新的量子算法的出现, 但事实证明这项任务很难, 值得继续研究和探索.

      基于量子行走寻找新的算法仍然是持续努力的方向, 本文提出了一种基于置换群的空间量子行走搜索算法, 将置换群作为搜素算法和量子行走相结合的桥梁, 目的是减少搜索时间, 提高目标搜索的精度, 提高空间内的搜索效果. 根据置换群中的元素在几何中可以形成环的性质, 将量子行走应用到置换群中, 从而实现在置换群中的量子搜索. 首先通过设置同构映射, 将数据点集合映射到由多个置换群组成的置换集合中的元素, 为了能够实现环上的量子行走, 在同构映射的作用下使数据点集合和置换集合具有一对一的对应关系. 然后, 构造Hilbert空间, 通过控制硬币算子, 给定初始状态, 将搜索空间中的元素作为节点, 进行量子行走. 接着根据函数$ \varPhi(w) = 1 $得到目标点, 并用量子态存储函数值. 最后根据函数的数值形成算法的反馈控制, 以此来判断量子行走的方向以及确定行走的状态. 本文有3个创新点: 1)将数据集同构到置换集, 实现了置换群上的量子行走; 2)多粒子受控的量子行走; 3)增加了反馈控制, 增强算法的可操作性与可控性.

      本文结构如下: 第2节简要介绍置换群$ S_{3} $以及环上的量子行走; 第3节分析并实现量子行走搜索算法, 其中包括10个步骤; 第4节对量子行走搜索算法进行时间复杂度分析; 第5节根据时间复杂度进行数值仿真, 直观明了地体现数值结果; 第6节对算法进行总结.

    • 定义2.1 (置换群): 有限集合到自身的一一映射称为一个置换. 有限集合S 上的一些置换组成的集合, 在置换的乘法下所组成的群, 称为置换群[33]. 任何一个有限群都同构于一个置换群. 因此, 可以把一切有限群都看成置换群. 任一置换可表示成若干不相交循环的乘积, 如$(a_{1},\; a_{2},\;\cdots,\; a_{n}) = $$ \left(\begin{array}{cccc} \alpha_{1} \alpha_{2}\cdots \cdots\alpha_{n-1} \alpha_{n}\\ \alpha_{2} \alpha_{3} \cdots \cdots\alpha_{n} \alpha_{1}\\ \end{array}\right)$称为置换的循环表示. 由于每个循环首尾相连, 因此可以看成是一个闭环.

      本文置换群的选择是根据搜索空间中目标态的维数决定的. 由于本文提出的搜索算法是在三维空间中进行的, 因此只对置换群$ S_{3} $进行研究, 若搜索空间是n维, 可以换成置换群$ S_{n} $, 置换群的选择并不会影响算法的时间复杂度. 其中

      $ S_{3} = \{ (e),(ab),(ac),(bc),(abc),(acb)\}. $

    • 假设群$ \mathit{G} $是有限群, S是该群的生成集合, 环A和群$ \mathit{G} $存在一一对应关系, 若节点g$ g^{\prime} $满足$ g^{\prime} = gh $, 则存在一条边$ (g, g^{\prime}) $, 其中$ g\in G $, $ h\in S $. 将环A中元素量子化:

      $ h\in S\to |{{h}}\rangle \in {\mathscr{H}}_{S},\; g\in G\to |{{g}}\rangle\in {\mathscr{H}}_{G}, $

      其中, $ {\mathscr{H}}_{S} $为硬币算符所在的Hilbert空间, $ {\mathscr{H}}_{G} $为量子行走所处的位置空间. 环上量子行走的演化算符为$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}}) $, $ {\boldsymbol{I}} $为位置空间的单位算符, $ {\boldsymbol{C}} $为硬币算符, $ {\boldsymbol{T}} $为转移算符, 具体定义如下:

      $ {\boldsymbol{C}} = \sum\limits_{h_{1}h_{2}\in H_{S}}|{{h_{{1}}}\rangle\langle {{h}}_{{{2}}}|}, $

      $ {\boldsymbol{T}} = \left[|{{h_{{1}}\rangle\langle h_{{1}}}|}\otimes \sum\limits_{g\in G}|{{gh_{{1}}}\rangle\langle {{g}}|}+|{{h}}_{{2}}\rangle\langle {{h}}_{{2}}|\otimes \sum\limits_{g\in G}|{{ gh_{{{2}}}}\rangle\langle {{g}}|}\right]. $

    • 步骤1 应用置换群的对称运算

      在介绍量子行走搜索算法之前首先利用对称运算证明置换群$ S_{3} $的每个子群在空间中形成一个闭环, 并且根据旋转角度, 规定群内元素的次序. 为了便于下文解释说明, 将群中元素$ a, b, c $替换为$ 1, 2, 3 $.

      对于置换群$ S_{3} $, 有如下保持三角形不变的对称运算: $ (e) $是一个恒等变化; $ (123), (132) $分别为绕中心点逆时针旋转$ \dfrac{2\pi}{3} $$ \dfrac{4\pi}{3} $; $ (12), (13), (23) $分别为围绕x, y, z轴逆时针旋转π. 每个元素旋转情况如图1所示. 同时可以得到置换群$ S_{3} $的4个子群:

      $ \begin{split} &H_{1} = \{e,(12)\}, \quad H_{2} = \{e,(13)\}, \\ &H_{3} = \{e,(123),(132)\}, \quad H_{4} = \{e,(23)\}. \end{split} $

      图  1  置换群$ S_{3} $中每个元素的旋转方位图

      Figure 1.  Diagram of the rotation position of each element in the permutation group $ S_{3} $.

      按照元素的旋转角度, 以单位元为起点, 规定每个子群的元素排列顺序. 例如在子群$ H_{1} $中, 第一个元素是e, 第二个元素是$ (12) $. 同理可得其他子群元素之间的排列顺序. 置换群$ S_{3} $的每个子群内, 各元素在三维空间中的旋转关系如图2所示. 在图2中, 对于子群$ H_{1} $, 元素eX轴逆时针旋转π到达$ (12) $的位置, 同样地, 元素$ (12) $X轴逆时针旋转π到达e的位置; 同理可得其他子群元素之间位置的旋转关系. 从图2还可看出, 置换群$ S_{3} $中每个子群元素之间通过置换群特有的对称运算, 形成了一个闭环.

      图  2  在每个子群中各个元素之间的旋转关系图

      Figure 2.  Diagram of the rotation relationship between the elements in each subgroup.

    • 本节将数据点集与置换群元素通过同构映射实现一一对应, 从而构建量子行走的搜索空间.

      步骤2 构建置换群元素新集合

      定义3.1 (数据集): 由数据点$ d_{1} $, $ d_{2} $, $\cdots$, $ d_{N} $生成的集合称为数据集D, 其中 n 表示量子态数量, $ N = 2^{n} $.

      定义3.2 (置换集): 集合$P \{p (i, j, k)\}, i, j, k\in Z$是由元素$ p (i, j, k) $生成的, 称为置换集. 其中元素$ p(i,\; j,\; k) $通过旋转一定角度变成元素$ p(i,\; j,\; k+1) $, 并且集合P中的元素数量大于等于数据集D中的元素数量.

      构建置换集的具体过程: 由置换群的子群$ H_{i} $衍生出子群族$ H_{i}^{j} $. 对于固定的$ i, \;j $, 子群$ H_{i}^{j} $$ p(i, j, k) $元素生成. 其中$ i = 1, \;2, \;3 $, $ j\in Z $. 对于子群$ H_{i}^{j} $, j表示第j个子群$ H_{i} $, $ k\in Z $表示子群$ H_{i}^{j} $k个元素. 对于同一个i的值, 只要$ j_{1}\neq j_{2} $, 则$ H_{i}^{j_{1}}\neq H_{i}^{j_{2}} $. 同理, 只要$ k_{1}\neq k_{2} $, 则$ p (i, j, k_{1}) \neq p (i, j, k_{2}) $.

      对于集合P和每个子群$ H_{i}^{j} $, 即使包含的元素数与元素的性质相同, 我们也规定, 只要j是不同的, 就被认为是不同的子群. 此外, 对于同一个元素(如e), 只要子群不同, 就被认为是不同的元素. 并且每个子群的元素顺序是逆时针方向. 如对于子群$ H_{1}^{j} $, 指定第一个元素为e, 第二个元素为$ (12) $. 对于$ H_{1}^{j} $的子群, 元素e标记为$ p (1, j, 1) $, $ (12) $标记为$ p (1, j, 2) $. 集合$ P = {p (i, j, k)} $中的每个元素都可以唯一地表示. 元素在置换集中的分布如表1所列.

      子群 子群族 群内所在元素
      $H_{1}$ $H_{1}^{1}$ $p(1, 1, 1), \; p(1, 1, 2)$
      $\vdots$ $\vdots$
      $H_{1}^{j_{1}}$ $p(1, j_{1}, 1)$, $p(1, j_{1}, 2)$
      $H_{i}$ $H_{i}^{1}$ $p(i, 1, 1), \; p(i, 1, 2)$
      $\vdots$ $\vdots$
      $H_{i}^{j_{i}}$ $p(i, j_{i}, 1)$, $p(i, j_{i}, 2)$

      表 1  置换集合元素分布情况

      Table 1.  Distribution of the elements in permutation set.

      又因为

      $ P = \bigcup\limits_{j = 1}^{j_{i}}\bigcup\limits_{i = 1}^{4}H^{j}_{i}, $

      因此得到置换集中的元素数满足$N = \displaystyle\sum\nolimits_{i = 1}^{4} j_{i}k_{i} = $$ 2^{n}$, 其中$ j_{i} $表示$ H_{i} $的子群数, $ k_{i} $表示元素数.

      步骤3 建立置换集与数据集同构

      假设映射$ {\mathscr{F}} $

      $ \begin{split}& {\mathscr{F}}(d_{m}) = p^{m}(i,\;j,\;k),~~~~ {\mathscr{F}}:D\rightarrow P,\end{split}$

      $ p^{m}(i, \;j, \;k) $上标中的m无意义, 只是为了方便区分说明, 其中$ m = 1, \;2,\;\cdots,\;N $. 接下来证明, 映射$ {\mathscr{F}} $是同构的.

      证明 令${\mathscr{F}} (d_{a}) = p^{a} (i, j, c),\;{\mathscr{F}} (d_{b}) = p^{b} (i, j, d).$ 由于$ p^{m} (i, j, d) $的位置只对应于数据点$ d^{m} $, 因此当$ a \neq b $时, $p (i, j, c) \neq p (i, j, d) \Rightarrow d_{a} \neq d_{b}$. 证得$ {\mathscr{F}} $是单射.

      又因为$ d_{a} \neq d_{b} $ ($ a \neq b $), 由元素的唯一性得到$ p (i, j, c) \neq p (i, j, d) $, 所以映射$ {\mathscr{F}} $是同构映射.

      步骤4 建立量子行走搜索空间

      定义3.3 (搜索空间): 空间$ \mathscr{W} $$ W = D \times P $集合生成, 其元素定义为$ w(d_{m},\; p^{m}(i, j, k)) \in \mathscr{W} $, 被称为搜索空间$ \mathscr{W} $. 每个元素$ w(d_{m}, p^{m}(i, j, k)) $包含排列集中的数据点$ d_{m} $和相应的位置$ p^{m}(i, j, k) $.

      重新构造搜索函数$ \varPhi(w) = \varPhi(d) = \{0, 1\} $. 由于 $ p^{m}(i, j, k) $只充当$ w(d_{m}, \;p^{m}(i, j, k)) $中的位置坐标, 该函数对$ p^{m}(i, j, k) $不作用. 这样, 通过函数$ \varPhi(w) = 1 $得到$ w_{{\rm{tar}}}(d_{{\rm{tar}}},\; p^{{\rm{tar}}}(i, j, k)) $, 从而得到目标数据$ d_{{\rm{tar}}} $.

      定义3.4 (集合$ W_{-1} $): 搜索空间$ \mathscr{W} $中定义了一个集合$ W_{-1} = \{w_{-1}(-1, \;p(i, j, k)) \} $. 该集合与W的集合相比, 在相同位置$ p(i, j, k) $上, 集合$ W_{-1} $中的数据$ d = 1 $. 集合W$W _{-1} $的元素对应关系如图3所示.

      图  3  集合W, $ W _{-1} $$ W _{\lambda} $元素之间的对应关系

      Figure 3.  Corresponding relationship between elements of the sets W, $ W _{-1} $ and $ W _{\lambda} $.

      集合W中的元素和集合$ W_{-1} $中的元素满足下列关系:

      $ w_{-1} = \varOmega_{0}(w) = {\boldsymbol{\varphi}}_{{0}} w, $

      其中$ \varOmega_{0} $是转化函数; $ {\boldsymbol{\varphi}}_{{0}} $是矩阵并满足

      $ {\boldsymbol{\varphi}}_{{0}} = \left(\begin{array}{cccccccc} {-1}/{||d_{1}||} & 0 & \cdots & 0 & 0 \\ 0 & {-1}/{||d_{2}||} & \cdots & 0 & 0 \\ \colon &\colon &\colon &\colon &\colon \\ 0 & 0 & \cdots & 0& {-1}/{||d_{N}||} \end{array}\right). $

    • 步骤5 确定量子行走粒子数量

      根据置换集合对应的子集数目, 确定量子行走过程中粒子的数量. 再根据前面的假设, 得到子集数$ j_{1}+j_{2}+j_{3}+j_{4} $. 为了方便计算, 选择 $j_{1}+j_{2}+ $$ j_{3}+j_{4}$的最大值$4 \times {\rm{max}}\{j_{1},\; j_{2}, \;j_{3}, \;j_{4} \}$. 在不失一般性的情况下, 令$j = {\rm{max}}\{j_{1},\; j_{2},\; j_{3},\; j_{4}\}$. 得到$j_{1}+ $$ j_{2}+j_{3}+j_{4}\leqslant 4 \times {\rm{max}}\{j_{1}, j_{2}, j_{3}, j_{4}\} = 4 \times j$.

      因此, 得到子集的数目是 $ 4 \times j $, 即量子行走过程中粒子的数目是$ 4 \times j $, 其中$0\leqslant j \leqslant {N}/{4}$.

    • 前文得出置换群$ S_{3} $的每个子群在空间中形成一个闭环, 并且置换群也与$ Z_{n} $的加法群同构. 根据已经提出的基于Cayley图的量子行走算法[34], 可以得到置换群$ S_{3} $上的量子行走.

      步骤6 置换群上量子行走

      将置换群看成是闭环, 则它的数学描述如下: 假设G是一个有限群, S是该群的生成集合, 置换群$ S_{3} $的元素和群$ {G} $的元素之间存在一一对应关系. 并且如果两个节点g$g'$满足$g' = gh$, 其中$ g\in G $$ h\in S $, 则这两个节点之间存在一条边$ (g, gh) $. 将置换群的元素量子化, 则置换群上的量子行走可以有如下定义: 假设$ \mathscr{H}_{S} $是硬币算子所在的Hilbert空间, 它是由态$ {{ |h}}\rangle $, $ h\in S $生成的; $ \mathscr{H}_{G} $是行走者的位置空间, 它是由态$ |{{g}}\rangle $, $ g\in G $生成, 则演化算符$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}}) $ 的硬币算子$ {\boldsymbol{C}} $和转移算子$ {\boldsymbol{T}} $分别定义为

      $ {\boldsymbol{C}} = \sum\limits_{h_{1}h_{2}\in S}|{{h}}_{{1}}\rangle\langle {{h}}_{{{2}}}|, $

      $ {\boldsymbol{T}} = \sum\limits_{i = 1,2}\bigg(|{{h}}_{{{i}}}\rangle\langle {{h}}_{{{i}}}|\otimes \sum\limits_{g\in G}|{{gh}}_{{{i}}}\rangle\langle {{g}}|)\bigg). $

      其中, 转移算子的作用是

      $ {\boldsymbol{T}}|{{h}}_{{{1}}}\rangle|{{g}}\rangle = |{{h}}_{{1}}\rangle|{{gh}}_{{{1}}}\rangle, $

      从(9)式可以得到, 在置换群上进行量子行走时, 以g为起点位置, 当硬币算符为$ h_{1} $时, 行走者会由节点位置g转移到相邻节点$ gh_{1} $, 其中$gh_{1} = $$ g'$. 根据相邻节点的关系, 可以得到:

      $ g\oplus h_{1} = g', $

      其中$\oplus$是模$ 2 $加运算或模$ 3 $加运算(在$H_{3} $中).

      对群元素进行傅里叶变换[35], 算子的形式如下:

      $ {\boldsymbol{F}} = \frac{1}{\sqrt{G}} \sum\limits_{k, g \in G} \chi_{{{g}}}(k)|{{g}}\rangle\langle {{k}}|, $

      其中, $\chi_{{{g}}}$为群的特征标, $\chi_{g} =\displaystyle \prod\nolimits_{j = 1}^{n} \omega_{N_{j}}^{\varepsilon, k_{j}}$, $\omega_{{N}_{j}} = {\rm{e}}^{\tfrac{2 \pi}{N_{j}}}$.

      将位置空间的基态转换为傅里叶基态: $\left|\widetilde{{{\chi}}}_{{{k}}}\right\rangle= $$ \displaystyle \frac{1}{\sqrt{G}} \sum\nolimits_{k, g \in G} \chi_{g}\left(k^{-1}\right)|{g}\rangle$, 则在$ \mathit{t} $时刻量子行走的状态用傅里叶变换后的基态表示为

      $ |{{\varPsi}}({{t}})\rangle = \sum\limits_{h \in S} \sum\limits_{k, g \in G} \tilde{\psi}_{h, g}(t)|{{\widetilde{\chi}}}_{{{k}}}\rangle, $

      其中, 转移算符对傅里叶基态作用后的形式为

      $ \boldsymbol{T}|{h}\rangle\left|\widetilde{{{\chi}}}_{{{g}}}\right\rangle=\chi_{h}(g)|{h}\rangle\left|\widetilde{{{\chi}} }_{{{g}}}\right\rangle. $

      可以证明傅里叶基态下, 转移算符只改变基态的振幅.

      最后, 得到傅里叶基态下$ \mathit{t} $时刻的振幅为$ \tilde{\psi}_{h, g}(t) $, 通过逆傅里叶变换求解离散时间的振幅:

      $ \psi_{h, g}(t) = \sum\limits_{g \in G} \frac{\chi_{g}\left(g^{-1}\right)}{\sqrt{|G|}} \widetilde{\psi}_{h, g}(t). $

    • 步骤7 构造Hilbert空间并检测合理性

      构造Hilbert空间$ \mathscr{H} = \mathscr{H}_{S}^{4 j}\otimes\mathscr{H}_{G}^{2^{n}}\otimes\mathscr{W} $. 其中$ \mathscr{H}_{S} $是硬币算子所在的Hilbert空间. 两个正交向量$ |{{1}}\rangle $$ |{{-1}}\rangle $可以用来表示硬币算子的状态; ($ |{{1}} \rangle $表示顺时针方向, $ |{{-1}}\rangle $表示逆时针方向). $ \mathscr{H}_{G} $是量子行走的位置空间; $ 4 j $表示量子态的数量; $ N = 2^{n} $; $ \mathscr{W} $是搜索空间, 用来存储函数值$\varPhi(w) = $$ \{0, 1\}$.

      确定硬币算符$ {\boldsymbol{C}} $, 通过硬币算符控制每一步行走. 这一步的目标是保证量子行走的方向一致, 不会往返. 然后通过迭代算子$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $, 进而通过迭代的方法得出迭代算子的数值解. 其中当算子$ {\boldsymbol{\varTheta}} $作用到元素$ w(d_{m}, \;p^{m}(i, j, k)) $时, 可以得到数值$ \delta = \{1, 0 \} $. 根据硬币算子$ {\boldsymbol{C}} $在本文中的作用, 其被定义为

      $ {\boldsymbol{C}} = \sum\limits_{h}|{{-1}}\rangle\langle {{h}}|, h\in S, $

      其中$ S = \{-1, 1\} $. 并且令:

      $ {\boldsymbol{\varTheta}} = \left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right). $

      根据构建的Hilbert空间, 检验转移算子$ {\boldsymbol{T}} $、转换算子$ {\boldsymbol{\varTheta}} $和迭代算子$ {\boldsymbol{U_{i}} } $是酉算子, 其中$i = $$ 1, \;2,\; 3$. 推导结果如下:

      $ \begin{split} &\boldsymbol{T^{\dagger}}=\sum\limits_{i=1,2}\bigg({|h'_{i}\rangle\langle h'_{i}|} \otimes\sum\limits_{g'\in G}{|g^{\prime}\rangle\langle g'h'_{i}|} \bigg), \\ &\boldsymbol{T^{\dagger}T}= \bigg[ \sum\limits_{i=1,2}\bigg( {|h'_{i}\rangle\langle h'_{i}|} \otimes\sum\limits_{g'\in G}{|g'\rangle\langle g'h'_{i}|} \bigg)\bigg] \\ &\qquad\quad\times\bigg[\sum\limits_{i=1,2}\bigg({|h_{i}\rangle\langle h_{i}|}\otimes \sum\limits_{g\in G}{|gh_{i}\rangle\langle g|}\bigg)\bigg]\\ &\qquad=\boldsymbol{I}.\\[-10pt] \end{split}$

      因为转换算子

      $ {\boldsymbol{\varTheta}} = \left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right) \Rightarrow {\boldsymbol{\varTheta^{\dagger}}} = \left(\begin{array}{ccc} 1 & 0& 0 \\ -(2)^{\varPhi(w_{m3})}&1 & 0 \\ 0 &0 & 1 \end{array}\right), $

      得到

      $ {\boldsymbol{\varTheta^{\dagger}\varTheta}} = \left(\begin{array}{ccc} 1 & 0& 0 \\ -(2)^{\varPhi(w_{m3})}&1 & 0 \\ 0 &0 & 1 \end{array}\right) \cdot \left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right) = {\boldsymbol{I}}. $

      又因为

      $ \begin{split} &\left[ ({\boldsymbol{C}} \otimes {\boldsymbol{I}}) \otimes {\boldsymbol{\varTheta}}\right]^{\dagger}\cdot\left[ ({\boldsymbol{C}} \otimes {\boldsymbol{I}}) \otimes {\boldsymbol{\varTheta}}\right] \\ = \;&\left[ \sum\limits_{h \in S}|{{-1}}\rangle\langle {{h}|}\otimes {\boldsymbol{I}}\otimes\left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right)\right]^{\dagger} \cdot\left[ \sum\limits_{h \in S}|{{-1}}\rangle\langle {{h}}|\otimes {\boldsymbol{I}} \otimes\left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right)\right]\\ =\; &\left[ \sum\limits_{h \in S}|{{h}}\rangle\langle {{-1}}|\otimes {\boldsymbol{I}} \otimes\left(\begin{array}{ccc} 1 & 0& 0 \\ -(2)^{\varPhi(w_{m3})} &1 & 0 \\ 0 &0 & 1\end{array}\right)\right] \cdot \left[ \sum\limits_{h \in S}|{{-1}}\rangle\langle {{h}}|\otimes {\boldsymbol{I}} \otimes\left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right)\right] = {\boldsymbol{I}}, \end{split} $

      根据$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $, 得到:

      $ \begin{split} \;& {\boldsymbol{U^{\dagger}}U} = \left[ {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} \right] ^{\dagger}\left[ {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} \right]\\ =\; & \left[ ({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} \right] ^{\dagger}\cdot \boldsymbol {T^{\dagger}T} \cdot \left[ ({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} \right] = {\boldsymbol{I}}, \end{split} $

      ${\boldsymbol{U}}_{{{i}}}^{\dagger }{{\boldsymbol{U}}_{{i}}}=\boldsymbol{I}$.

      因此通过上述验证过程得出转移算子$ {\boldsymbol{T}} $、转换算子$ {\boldsymbol{\varTheta}} $和迭代算子${\boldsymbol U}_{i}$是酉算子.

    • 步骤8 分析量子行走路径

      给定初始态$|{{\psi}}_{{{0}}}\rangle = \dfrac{1}{\sqrt{ {N}/({4j})}}\displaystyle\sum\limits_{1}^{[{N}/({4j})]}|{{-1}} \rangle \otimes |{{0}} \rangle $$ \otimes |{{\delta}}\rangle$, 其中$ \delta = 1, 0 $, 符号$\left[\; \right]$表示取整函数. 通过迭代算子$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $可以得到:

      $ \begin{equation*} {\boldsymbol{U}_{i}} = {\boldsymbol{\psi}}_{{{t}} = {{1}}} = |{{-1}} \rangle \otimes |{{-i }} \rangle \otimes |{{\delta}}\rangle \end{equation*}, $

      从而控制了在置换群中的量子行走方向. 整个量子行走过程如图4所示.

      图  4  量子行走的过程

      Figure 4.  Process of quantum walk.

      图4中黄色的圆点表示数据点, 绿色的球体表示空间, 标有数字$ 1, 2, 3 $的蓝色圆圈表示数据点$ p^{m}(i, j, 1) $, $ p^{m+1}(i, j, 2) $, $ p^{m+2}(i, j, 3) $, 位置在某个子群$ H_{i}^{j} $中. 红色的虚线表示运动轨迹, 从$1\to 2\to 3$都是利用反馈控制继续前进的. 当$3\to 1$时, 运动轨迹就是黑色箭头所表示的方向, 通过反馈控制, 发现此方向是被禁止的, 于是设定硬币算符为$ {\boldsymbol{C}^{*}} = \dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) $, 随机选择行走方向(橙色箭头), 进行下一个子群中进行的量子行走.

    • 步骤9 存储函数结果形成反馈控制

      $ \varPhi $作用于元素$ w(d_{m}, \;p^{m}(i, j, k)) $时, 得到函数的值$ \delta = 1 $$ 0 $, 并将数值存储在量子态中. 其中对于量子态$ |{{1}}\rangle $, 表示所对应的数据d正是目标数据$ d_{{\rm{tar}}} $. 为了形成含有数值结果的量子态集合, 让δ替换$ W_{-1} $集合中的$ -1 $.

      更换过程如下:

      $ \begin{split} &\delta_{m1}^{H_{1}} = \varOmega_{1}(w_{-1}) = {{\boldsymbol{{\phi}}}}_{{{1}}}w_{-1} = {\boldsymbol{\varTheta}}_{1}\big(w_{m1}^{H_{1}}\big) = {{{\boldsymbol{\varphi}}}}_{{{1}}} w_{m1}^{H_{1}},\\ &\delta_{m2}^{H_{2}} = \varOmega_{2}(w_{-1}) = {{\boldsymbol{{\phi}}}}_{{{2}}}w_{-1} = {\boldsymbol{\varTheta}}_{2}\big(w_{m2}^{H_{2}}\big) = {{{\boldsymbol{\varphi}}}}_{{{2}}} w_{m2}^{H_{2}}, \\ &\delta_{m3}^{H_{3}} = \varOmega_{3}(w_{-1}) = {\boldsymbol{\phi}}_{3}{}w_{-1} = {\boldsymbol{\varTheta}}_{3}\big(w_{m3}^{H_{3}}\big) = {{{\boldsymbol{\varphi}}}}_{{{3}}} w_{m3}^{H_{3}}, \\ &\delta_{m4}^{H_{4}} = \varOmega_{4}(w_{-1}) = {{{\boldsymbol{\phi}}}}_{{{4}}}w_{-1} = {\boldsymbol{\varTheta}}_{4}\big(w_{m2}^{H_{4}}\big) = {{{\boldsymbol{\varphi}}}}_{{{4}}} w_{m4}^{H_{4}}, \end{split} $

      其中, $\varOmega_{i} ({\boldsymbol{\varTheta}}_{i})$表示转换函数, 使得数据$ d = -1(d) $成为δ, $ w_{mi}^{H_{i}} $表示$ H_{i} $中的一个元素, $ \delta_{mi}^{H_{i}} $表示$ w_{mi} $在函数Φ的作用下的函数值, $ i = 1, 2, 3, 4 $. ${\boldsymbol \phi}_{i}$是矩阵并满足

      $ \begin{split} & {\boldsymbol{\phi}}_{{{1}}} = \left(\begin{array}{cc} 1 & -(2)^{\varPhi(w_{m1})} \\ 0 &1 \end{array}\right),\;~~ {\boldsymbol{\phi}}_{{{2}}} = \left(\begin{array}{cc} 1 & -(2)^{\varPhi(w_{m2})} \\ 0 &1 \end{array}\right), \\ & {\boldsymbol{\phi}}_{{{3}}} = \left(\begin{array}{ccc} 1 & -(2)^{\varPhi(w_{m3})}& 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{array}\right), ~~ \;{\boldsymbol{\phi}}_{{{4}}} = \left(\begin{array}{cc} 1 & -(2)^{\varPhi(w_{m4})} \\ 0 &1 \end{array}\right). \end{split} $

      $ {\boldsymbol{\varphi}_{i}} $是矩阵并满足

      $ {{{\boldsymbol \varphi}_{{{1}}}}} = \left(\begin{array}{cc} \dfrac{-1}{||d_{m1}||} & \dfrac{(2)^{\varPhi(w_{m1})}}{||d_{m1+1}||} \\ 0 &\dfrac{-1}{||d_{m1+1}||} \end{array}\right),\;~~ {{{\boldsymbol \varphi}_{{{2}}}}} = \left(\begin{array}{cc} \dfrac{-1}{||d_{m2}||} & \dfrac{(2)^{\varPhi(w_{m2})}}{||d_{m2+1}||} \\ 0 &\dfrac{-1}{||d_{m2+1}||} \end{array}\right), $

      $ {{{\boldsymbol \varphi}_{{{3}}}}} = \left(\begin{array}{ccc} \dfrac{-1}{||d_{m3}||} & \dfrac{(2)^{\varPhi(w_{m3})}}{||d_{m3+1}||} & 0 \\ 0 &\dfrac{-1}{||d_{m3+1}||} & 0 \\ 0 & 0 &\dfrac{-1}{||d_{m3+2}||} \end{array}\right),\;~~ {{{\boldsymbol \varphi}_{{{4}}}}} = \left(\begin{array}{cc} \dfrac{-1}{||d_{m4}||} & \dfrac{(24)^{\varPhi(w_{m24})}}{||d_{m4+1}||} \\ 0 &\dfrac{-1}{||d_{m4+1}||} \end{array}\right). $

      当函数$ \varOmega_{i} $(图3中简称为Ω)在进行数据更新时, 存储函数值的量子态会出现3个数值, 分别是$ |{{1}}\rangle $, $ |{{0}}\rangle $$ |{{-1}}\rangle $. 为了方便说明, 用量子态$ |{{\lambda}}\rangle $表示, 并且建立集合$ W_{\lambda} = \{ (\lambda, \;p(i, j, k))\} $ ($ W_{-1} \rightarrow W_{\lambda} $), 其中$ \lambda = 0, \;1, \;-1 $. 集合W, $ W _{-1} $$ W _{\lambda} $三者之间的关系变化如图3所示.

    • 步骤10 根据反馈结果判定后续方向

      当量子行走进行到某步时, 设此时的迭代次数是t. 当迭代次数是$ t+1 $时, 判断量子行走过程是否继续或者停止. 判断过程如下:

      当行走到位置$ p^{m}(i, j, k) $时, 判断相应集合$ W_{\lambda} $对应的数据λ, 如果$ \lambda < 0 $, 量子行走在此环(置换群)中继续进行; 如果$\lambda\geqslant 0$, 量子行走将在此置换群中停止, 设定硬币算符为 $ {\boldsymbol{C}^{*}} = \dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) $, 随机行走到其他置换群的位置.

    • 本文采取多粒子的量子行走, 这样时间复杂度取决于数据点的数量N和量子行走的数量j, 即时间复杂度$ t = t_{{\rm{in}}}+t_{{\rm{out}}} $最终取决于参数jN.

      对于量子态$|{{\chi}}\rangle = \dfrac{1}{\sqrt{N}}\displaystyle \sum\nolimits_{x = 1}^{N}|{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle$, 其中$ y = 1, 2, 3 $, $ \delta = 0, 1 $, 正交归一化后得到:

      $ \begin{split} &|{{\chi}}\rangle = \sqrt{\frac{M}{N}} \left( \dfrac{1}{\sqrt{M}} \sum\limits_{x\in\varPhi^{-1}(1)} |{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle \right) \\ & +\sqrt{\frac{N-M}{N}}\left( \dfrac{1}{\sqrt{N-M}}\sum\limits_{x\in \varPhi^{-1}(0)}|{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle \right) , \end{split}$

      其中, M表示目标点的数量.

      分析时间复杂度$t_{{\rm{in}}}$, 根据${\boldsymbol{C}} = \displaystyle\sum\nolimits_{h}|{{-1}}\rangle\langle {{h}}|, $$ h\in S$可以得到每一步的硬币算符是

      $ {\boldsymbol{C}}_{{{1}}} = |{{-1\rangle\langle 1|}}, \quad {\boldsymbol{C}}_{{{2}}} = |{{-1\rangle\langle -1|}}, \quad {\boldsymbol{C}}_{{{3}}} = |{{-1\rangle\langle -1|}}, $

      其中, 两个正交向量$ |{{1}}\rangle $$ |{{-1}}\rangle $可以用来表示硬币的状态. $ |{{1 }} \rangle $表示顺时针方向, $ |{{-1}}\rangle $表示逆时针方向.

      通过迭代方法, 可以得到:

      $\left\{\begin{aligned} &{\boldsymbol{U}}_{{{1}}}={\boldsymbol{\psi}}_{{{t}}={{1}}}=|-{{1}}\rangle|-{{1}}\rangle|\otimes| {{\delta}}\rangle, \\ &{\boldsymbol{U}}_{{{2}}}={\boldsymbol{\psi}}_{{{t}}={{2}}}=|-{{1}}\rangle|-{{2}}\rangle|\otimes| {{\delta}}\rangle, \\ &{\boldsymbol{U}}_{{{3}}}={\boldsymbol{\psi}}_{{{t}}={{3}}}=|-{{1}}\rangle|-{{3}}\rangle|\otimes| {{\delta}}\rangle. \end{aligned}\right.$

      由于本文选择的是置换群$ S_{3} $, 因此完成一次置换群上行走次数为$t\leqslant 3$. 又因为在在置换群中完成一次量子行走时, 才进行一次硬币算符为$ {\boldsymbol{C}^{*}} $的量子行走. 即完成一次更换需要的时间$t = t_{{\rm{in}}}+ $$ t_{{\rm{out}}} \leqslant 3+1 = 4$, 因此完成所有行走过程时间复杂度为$ t = t_{{\rm{in}}}+t_{{\rm{out}}} \leqslant 4 t_{{\rm{out}}} $, 得到$ t = 4 t_{{\rm{out}}} $. 所以只需要计算时间复杂度$ t_{{\rm{out}}} $即可.

      $\begin{split} &|{{\alpha}}\rangle = \dfrac{1}{\sqrt{N-M}}\sum_{x\in \varPhi^{-1}(0)}|{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle , \\ &|{{\beta}}\rangle = \dfrac{1}{\sqrt{M}} \sum_{x\in\varPhi^{-1}(1)}|{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle ,\\ & \sin\theta = \sqrt{ {M}/{N}} = \sqrt{\kappa}, \end{split}$

      于是得到

      $ |{{\chi}}\rangle = \sqrt{ {M}/{N}}|{{\alpha}}\rangle+\sqrt{({N-M})/{N}}|{{\beta}}\rangle. $

      令迭代算符$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}^{*}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $作用到量子态$ |{{\chi}}\rangle $, 通过计算离散量子行走时刻连续叠加态的振幅得到时间复杂度$ t_{{\rm{out}}} $和参数N的关系.

      $ \begin{split}\;& {\boldsymbol{U}_{t}|\chi\rangle } = \left[ {\boldsymbol{T}} ({\boldsymbol{C}^{*}}\otimes {\boldsymbol{I}}) \otimes {\boldsymbol{\varTheta}}\right]^{t}|{{\chi}}\rangle\\ =\; &\left[ {\boldsymbol{T}}({\boldsymbol{C}^{*}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} \right]^{t}\left(\cos\theta |{{\alpha}}\rangle+\sin\theta |{{\beta}}\rangle\right) \\ =\; &\frac{1}{\sqrt{N}}\sum\limits_{k}X(t)|{{\alpha}}\rangle+\frac{1}{\sqrt{N}}\sum\limits_{k} Y(t)|{{\beta}}\rangle ,\end{split} $

      其中, 当$ t_{{\rm{out}}} $为偶数时:

      $ \begin{split} &X(t) = \cos (\theta_{k} t)-\dfrac{{\rm{i}} \cos \dfrac{2 \pi k}{N} \sin (\theta_{k} t)}{\sqrt{1+\cos ^{2} ({2 \pi k}/{N})}}, \\ &Y(t) = -\dfrac{{\rm{i}} {\rm{e}}^{{\rm{i}} \tfrac{2 \pi}{N}} \sin (\theta_{k} t)}{\sqrt{1+\cos ^{2} ({2 \pi k}/{N})}}; \end{split}$

      $ t_{{\rm{out}}} $为奇数时:

      $ \begin{split} &X(t) = -{\rm{i}} \sin (\theta_{k} t)-\dfrac{{\rm{i}} \cos ({2 \pi k}/{N}) \sin (\theta_{k} t)}{\sqrt{1+\cos ^{2} ({2 \pi k}/{N})}},\\ &Y(t) = -\dfrac{{\rm{i}}{\rm{e}}^{{\rm{i}} \tfrac{2 \pi k}{N}} \sin (\theta_{k} t)}{\sqrt{1+\cos ^{2} ({2 \pi k}/{N})}}. \end{split}$

      $ \theta_{k} $满足$\sin \theta_{k} = \dfrac{1}{\sqrt{2}} \sin \dfrac{2 \pi k}{N}$.

      搜索目的是为了找遍空间中所有子群, 即搜索到目标数据点的概率等于${M}/{N}$.

      得到:

      $ \begin{split} &\frac{1}{N^{2}}\left|\sum\limits_{j = 1}^{\frac{N}{4}}\sum\limits_{k = 0}^{4j-1} Y_{k}(t){\rm{e}}^{{\rm{i}}k}\right|^{2} \\ =\;& \frac{M}{N} \Rightarrow \left|\sum\limits_{j = 1}^{\frac{N}{4}}\sum\limits_{k = 0}^{4j-1} Y_{k}(t){\rm{e}}^{{\rm{i}}k}\right|^{2} = MN. \end{split}$

      由于参数jN有关, 若取 $ j = \sqrt[3]N $. 求解方程(28)可得

      $ \begin{split} & \left|\sum_{j = 1}^{{N}/{4}}\sum_{k = 0}^{4j-1} Y_{k}(t){\rm{e}}^{{\rm{i}}k}\right|^{2} = MN \\ \Rightarrow\;& \sum_{j = 1}^{\frac{N}{4}}\sum_{k = 0}^{4j-1}\left| Y_{k}(t){\rm{e}}^{{\rm{i}}k}\right|^{2} \leqslant MN \\ \Rightarrow\;& \sum_{j = 1}^{{N}/{4}}\sum_{k = 0}^{4j-1}\left|-\frac{{\rm{i}} {\rm{e}}^{{\rm{i}} \tfrac{2 \pi k}{N}} \sin (\theta_{k} t)}{\sqrt{1+\cos ^{2} \dfrac{2 \pi k}{N}}}{\rm{e}}^{{\rm{i}}k}\right|^{2} \leqslant MN \\ \Rightarrow\;& t^{2}\sum_{j}\bigg\{ \dfrac{1}{2}\left[j^{2}(j+1)\right] + \left(\dfrac{\pi^{2}}{6N^{2}}-\dfrac{\pi^{4}}{27N^{4}}\right)\\ & \times (j+1)^{2}j^{3} + \dfrac{2\pi^{4}}{27N^{4}}(j+1)^{3}j^{4}\bigg\} \leqslant MN \\ \Rightarrow \; &t^{2}\left( \dfrac{14\pi^{4}}{27N^{2}}N^{{7}/{3}}\right) \leqslant MN \Rightarrow t \leqslant \dfrac{27M}{14\pi^{4}}\sqrt[3]N, \end{split}$

      得出关于变量N的数值表达式$t_{{\rm{out}}}(N) = O(\sqrt[^3]N)$, 即得到关于变量N的数值表达式$t(N) = O(\sqrt[^3]N)$.

    • 将本文提出的量子行走搜索算法与Grover搜索算法关于时间复杂度进行对比, 设定参数M = 10, $ N = 200 $, 得到图5所示的对比曲线. 从图5(a)得到量子行走搜索算法所用时间要比Grover搜索算法所用时间短, 即量子行走搜索算法的速率更高; 从图5(b)得到量子行走搜索算法是满足原点条件和下确界条件的, 即满足当$ N = 0 $时, $ t = 0 $; $ N = 1 $时, $ t = 1 $.

      图  5  两种搜索算法时间按复杂度的对比

      Figure 5.  Comparison of the time complexity of two search algorithms.

      为了直观地体现算法的高效性, 下面用两种不同算法进行举例比较: 一个采用标准的Grover-Long算法[36], 一个采用本文提出的量子行走搜索算法. $ N = 64 $时, Grover-Long算法需要$O(\sqrt[^2]N) = $$ 8$次搜索, 采用本文的方法, 最多需要$O(\sqrt[^3]N) = 4$次搜索.

      进而又对参数j对搜索的时间复杂度的影响进行了分析. 选取了参数$ M = 10 $, $ N = 200 $分别对参数$ j = 1 $, $ j = 2 $, $ j = 3 $三条曲线进行分析, 得到图6所示曲线. 从图6(a)得到参数j与时间复杂度呈负相关, 即参数j的取值越大, 所用时间越短, 搜索速率越快; 从图6(b)得到参数j不影响量子行走搜索算法, 且满足原点条件和下确界条件.

      图  6  参数j对搜索算法时间复杂度的影响

      Figure 6.  Influence of parameter j on the time complexity of search algorithm.

      最后分析了变量参数j, N与时间复杂度t的关系, 得到数值仿真结果如表2所列. 从表中数据进一步得出, 参数与时间复杂度不是呈负线性关系.

      数据点数量N $ j = 1 $ $ j = 2$ $ j = 3 $
      1024 3 2 1
      2048 4 2 2
      4096 4 2 2
      8192 6 3 2
      16384 7 4 3
      32768 8 4 3

      表 2  数据仿真结果

      Table 2.  Numerical simulation results.

    • 本文基于量子行走提出的搜索算法, 将时间复杂度减少到$O(\sqrt[^3]{N})$. 相对于Grover算法中时间复杂度等价于$O(\sqrt{N})$, 降低了时间消耗; 通过对硬币算符进行控制, 从而控制了整个行走过程, 增加了算法的可控性; 通过增加反馈控制, 使得算法更具有灵活性与可操作性. 最后通过模型仿真, 分析变量参数j与时间复杂度的关系得到, 参数j与时间复杂度呈非线性负相关; 提出的量子行走搜索算法符合零点条件与下确界条件, 即满足当$ N = 0 $时, $ t = 0 $; $ N = 1 $时, $ t = 1 $; 且不受参数j的影响.

参考文献 (36)

目录

    /

    返回文章
    返回