搜索

x

留言板

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

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

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

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

陈云云, 郑改革, 顾芳, 李振华. 尘埃粒子电势对等离子体电导率的影响. 物理学报, 2012, 61(15): 154202. doi: 10.7498/aps.61.154202
引用本文: 陈云云, 郑改革, 顾芳, 李振华. 尘埃粒子电势对等离子体电导率的影响. 物理学报, 2012, 61(15): 154202. doi: 10.7498/aps.61.154202
Chen Yun-Yun, Zheng Gai-Ge, Gu Fang, Li Zhen-Hua. Effect of dust particle potential on plasma conductivity. Acta Phys. Sin., 2012, 61(15): 154202. doi: 10.7498/aps.61.154202
Citation: Chen Yun-Yun, Zheng Gai-Ge, Gu Fang, Li Zhen-Hua. Effect of dust particle potential on plasma conductivity. Acta Phys. Sin., 2012, 61(15): 154202. doi: 10.7498/aps.61.154202

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

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

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
Article Text (iFLYTEK Translation)
PDF
HTML
导出引用
  • 在量子计算科学中, 如何更好地构建量子搜索算法一直以来受到学者们的广泛关注, 并且基于量子行走寻找新的搜索算法也仍吸引着学者们不断深入研究与探索. 本文从减少搜索过程中的时间消耗、增加算法搜索的准确性和可控性等多方面进行考虑, 提出了一种基于置换群的多粒子量子行走搜索算法. 首先分析得到置换群在空间中可看成一个闭环, 定义了置换集合, 并且通过同构映射将数据点所在数据集映射到定义的置换集, 使得置换集合中元素数据点形成一一对应的关系. 其次, 根据给定初始态和硬币算符, 在数据点集与置换集合张成的搜索空间中利用多粒子的量子行走在环上进行目标数据搜索. 最后, 根据函数Φ(w)=1找到目标数据, 并用量子态存储数值, 用于形成搜索算法的反馈控制; 同时通过控制硬币算符从而控制量子行走在环上的行走方向, 增加搜索的可操作性与准确性. 本文利用多粒子的量子行走进行搜索, 分析得到粒子数量参数j与时间复杂度呈非线性负相关; 提出的量子行走搜索算法符合零点条件与下确界条件, 且不受变量数j的影响; 通过数值分析得到量子行走搜索算法的时间复杂度等价于O(3N), 相比于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 Φ(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(3N), which improves the search efficiency compared with the Grover search algorithm.
      PACS:
      42.25.Bs(Wave propagation, transmission and absorption)
      52.25.Mq(Dielectric properties)
      52.35.Hr(Electromagnetic waves (e.g., electron-cyclotron, Whistler, Bernstein, upper hybrid, lower hybrid))
      通信作者: 马鸿洋, 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  置换群S3中每个元素的旋转方位图

    Fig. 1.  Diagram of the rotation position of each element in the permutation group S3.

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

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

    图 3  集合W, W1Wλ元素之间的对应关系

    Fig. 3.  Corresponding relationship between elements of the sets W, W1 and Wλ.

    图 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.

    子群 子群族 群内所在元素
    H1 H11 p(1,1,1),p(1,1,2)
    Hj11 p(1,j1,1), p(1,j1,2)
    Hi H1i p(i,1,1),p(i,1,2)
    Hjii p(i,ji,1), p(i,ji,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] 张伊祎, 韦雪玲, 农洁, 马汉斯, 叶子阳, 徐文杰, 张振荣, 杨俊波. 基于直接二进制搜索算法设计的超紧凑In2Se3可调控功率分束器. 物理学报, 2023, 72(15): 154207. doi: 10.7498/aps.72.20230459
    [2] 杨建宇, 席昆, 竺立哲. 生物大分子过渡态搜索算法及其中的机器学习. 物理学报, 2023, 72(24): 248701. doi: 10.7498/aps.72.20231319
    [3] 李艳. 粒子间长程相互作用以及晶格中孤立缺陷点对两硬核玻色子在一维晶格势阱中量子行走的影响. 物理学报, 2023, 72(17): 170501. doi: 10.7498/aps.72.20230642
    [4] 张航, 胡月姣, 陈嘉文, 修龙汪. 程能映射下配光平移群的深度神经网络实现. 物理学报, 2022, 71(13): 134201. doi: 10.7498/aps.71.20220178
    [5] 刘瀚扬, 华南, 王一诺, 梁俊卿, 马鸿洋. 基于量子随机行走和多维混沌的三维图像加密算法. 物理学报, 2022, 71(17): 170303. doi: 10.7498/aps.71.20220466
    [6] 周文豪, 王耀, 翁文康, 金贤敏. 集成光量子计算的研究进展. 物理学报, 2022, 71(24): 240302. doi: 10.7498/aps.71.20221782
    [7] 王一诺, 宋昭阳, 马玉林, 华南, 马鸿洋. 基于DNA编码与交替量子随机行走的彩色图像加密算法. 物理学报, 2021, 70(23): 230302. doi: 10.7498/aps.70.20211255
    [8] 姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子漫步的反馈搜索算法. 物理学报, 2021, (): . doi: 10.7498/aps.70.20211000
    [9] 张冬晓, 陈志斌, 肖程, 秦梦泽, 吴浩. 基于引力搜索算法的湍流相位屏生成方法. 物理学报, 2019, 68(13): 134205. doi: 10.7498/aps.68.20190081
    [10] 薛希玲, 陈汉武, 刘志昊, 章彬彬. 基于散射量子行走的完全图上结构异常搜索算法. 物理学报, 2016, 65(8): 080302. doi: 10.7498/aps.65.080302
    [11] 王文娟, 童培庆. 广义Fibonacci时间准周期量子行走波包扩散的动力学特性. 物理学报, 2016, 65(16): 160501. doi: 10.7498/aps.65.160501
    [12] 王丹丹, 李志坚. 一维相位缺陷量子行走的共振传输. 物理学报, 2016, 65(6): 060301. doi: 10.7498/aps.65.060301
    [13] 陈汉武, 李科, 赵生妹. 基于相位匹配的量子行走搜索算法及电路实现. 物理学报, 2015, 64(24): 240301. doi: 10.7498/aps.64.240301
    [14] 刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁. 星图上的散射量子行走搜索算法. 物理学报, 2015, 64(1): 010301. doi: 10.7498/aps.64.010301
    [15] 杨芳艳, 胡明, 姚尚平. 连续时间系统同宿轨的搜索算法及其应用. 物理学报, 2013, 62(10): 100501. doi: 10.7498/aps.62.100501
    [16] 周庆勇, 姬剑锋, 任红飞. 非等间隔计时数据的X射线脉冲星周期快速搜索算法. 物理学报, 2013, 62(1): 019701. doi: 10.7498/aps.62.019701
    [17] 任春年, 史鹏, 刘凯, 李文东, 赵洁, 顾永建. 初态对光波导阵列中连续量子行走影响的研究. 物理学报, 2013, 62(9): 090301. doi: 10.7498/aps.62.090301
    [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
计量
  • 文章访问数:  5453
  • PDF下载量:  197
出版历程
  • 收稿日期:  2021-05-27
  • 修回日期:  2021-09-27
  • 上网日期:  2022-01-19
  • 刊出日期:  2022-02-05

/

返回文章
返回