基于相位匹配的量子行走搜索算法及电路实现

陈汉武; 李科; 赵生妹

doi:10.7498/aps.64.240301

摘要

量子行走是经典随机行走在量子力学框架下的对应, 理论上可以用来解决一类无序数据库的搜索问题. 因为携带信息的量子态的扩散速度与经典相比有二次方式的增长, 所以量子行走优于经典随机行走, 量子行走的特性值得加以利用. 量子行走作为一种新发现的物理现象的数学描述, 引发了一种新的思维方式, 孕育了一种新的理论计算模型. 最新研究表明, 量子行走本身也是一种通用计算模型, 可被视为设计量子算法的高级工具, 因此受到部分计算机理论科学领域学者的关注和研究. 对于多数问题求解方案的量子算法的设计, 理论上可以只在量子行走模型下进行考虑. 基于Grover算法的相位匹配条件, 本文提出了一个新的基于量子行走的搜索算法. 理论演算表明: 一般情况下本算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时, 本算法搜索成功的概率要大于Grover算法. 本文不但利用Grover算法中相位匹配条件构造了一个新的量子行走搜索算法, 而且在本研究室原有的量子电路设计研究成果的基础上给出了该算法的量子电路表述.

关键词:

Abstract

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Keywords:

作者及机构信息

1.
东南大学计算机科学与工程学院, 南京 210096;

2.
南京邮电大学通信与信息工程学院, 南京 210003

通信作者: 陈汉武, hanwu_chen@163.com

基金项目: 国家自然科学基金(批准号: 61170321, 61271238, 61475075)和高等学校博士学科点专项科研基金(批准号: 20110092110024, 20123223110003)资助的课题.

Authors and contacts

1.
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China;

2.
School of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Corresponding author: Chen Han-Wu, hanwu_chen@163.com

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61170321, 61271238, 61475075) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant Nos. 20110092110024, 20123223110003).

参考文献

[1]	Shor P W 1997 SIAM J. Comput. 26 1484
[2]	Grover L K 1996 Proceedings of 28th ACM Symposium on Theory of Computation Philadelphia, USA, May 22-24, 1996 p212
[3]	Long G L 2001 Phys. Rev. A 64 022307
[4]	Toyama F M, van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 5
[5]	Liu Y, Zhang F H 2015 Sci. China: Phys. Mech. Astron. 58 7
[6]	Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p37
[7]	Aharonov D, Ambainis A, Kempe J, Vazirani U 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p50
[8]	Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[9]	Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314
[10]	Ambainis A, Kempe J, Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms Philadelphia, USA, January 23-25, 2005 p1099
[11]	Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307
[12]	Potoček V, Gábris A, Kiss T, Jex I 2009 Phys. Rev. A 79 012325
[13]	Reitzner D, Hillery M, Feldman E, Buzek V 2009 Phys. Rev. A 79 012323
[14]	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]
[15]	Kempe J 2005 Probability Theory and Related Fields 133 215
[16]	Wang H, Ma Z, Ma C G 2013 Chin. Sci. Bull. 58 28
[17]	Travaglione B C, Milburn G J 2002 Phys. Rev. A 65 3
[18]	WANG C, LI Y S, HAO L 2011 Chin. Sci. Bull. 56 20
[19]	Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502
[20]	Ambainis A 2007 SIAM J. Comput. 37 210
[21]	Childs A M, Eisenberg J M 2005 Quantum Inf. Comput. 5 593
[22]	Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[23]	Long G L, Liu Y 2007 Front. Comput. Sci. 1 3
[24]	Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[25]	Fredkin E, Toffoli T 1982 Int. J. Theor. Phys. 21 219
[26]	Toffoli T 1981 Math. Syst. Theory 14 13
[27]	Grover L K 1998 Phys. Rev. Lett. 80 4329
[28]	Long G L, Li Y S, Zhang W L, Niu L 1999 Phys. Lett. A 262 27
[29]	Younes A 2007 Appl. Math. Informat. 7 93
[30]	Li P C, Li S Y 2007 Phys. Lett. A 366 42
[31]	Long G L, Li X, Sun Y 2002 Phys. Lett. A 294 3

施引文献

[1]	Shor P W 1997 SIAM J. Comput. 26 1484
[2]	Grover L K 1996 Proceedings of 28th ACM Symposium on Theory of Computation Philadelphia, USA, May 22-24, 1996 p212
[3]	Long G L 2001 Phys. Rev. A 64 022307
[4]	Toyama F M, van Dijk W, Nogami Y 2013 Quantum Inf. Process. 12 5
[5]	Liu Y, Zhang F H 2015 Sci. China: Phys. Mech. Astron. 58 7
[6]	Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p37
[7]	Aharonov D, Ambainis A, Kempe J, Vazirani U 2001 Proceedings of the 33th ACM Symposium on Theory of Computing Heraklion, Greece, July 6-8, 2001 p50
[8]	Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[9]	Hillery M, Bergou J, Feldman E 2003 Phys. Rev. A 68 032314
[10]	Ambainis A, Kempe J, Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms Philadelphia, USA, January 23-25, 2005 p1099
[11]	Shenvi N, Kempe J, Whaley K B 2003 Phys. Rev. A 67 052307
[12]	Potoček V, Gábris A, Kiss T, Jex I 2009 Phys. Rev. A 79 012325
[13]	Reitzner D, Hillery M, Feldman E, Buzek V 2009 Phys. Rev. A 79 012323
[14]	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]
[15]	Kempe J 2005 Probability Theory and Related Fields 133 215
[16]	Wang H, Ma Z, Ma C G 2013 Chin. Sci. Bull. 58 28
[17]	Travaglione B C, Milburn G J 2002 Phys. Rev. A 65 3
[18]	WANG C, LI Y S, HAO L 2011 Chin. Sci. Bull. 56 20
[19]	Xue P, Zhang R, Qin H, Zhan X, Bian Z H, Li J, Sanders B C 2015 Phys. Rev. Lett. 114 140502
[20]	Ambainis A 2007 SIAM J. Comput. 37 210
[21]	Childs A M, Eisenberg J M 2005 Quantum Inf. Comput. 5 593
[22]	Childs A M, Farhi E, Gutmann S 2002 Quantum Inf. Process. 1 35
[23]	Long G L, Liu Y 2007 Front. Comput. Sci. 1 3
[24]	Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[25]	Fredkin E, Toffoli T 1982 Int. J. Theor. Phys. 21 219
[26]	Toffoli T 1981 Math. Syst. Theory 14 13
[27]	Grover L K 1998 Phys. Rev. Lett. 80 4329
[28]	Long G L, Li Y S, Zhang W L, Niu L 1999 Phys. Lett. A 262 27
[29]	Younes A 2007 Appl. Math. Informat. 7 93
[30]	Li P C, Li S Y 2007 Phys. Lett. A 366 42
[31]	Long G L, Li X, Sun Y 2002 Phys. Lett. A 294 3

[1]	袁金健, 顾民, 黄润生. 运动界面的电磁波相位匹配. , 2024, 73(13): 134201. doi: 10.7498/aps.73.20240269
[2]	杨建宇, 席昆, 竺立哲. 生物大分子过渡态搜索算法及其中的机器学习. , 2023, 72(24): 248701. doi: 10.7498/aps.72.20231319
[3]	周江平, 周媛媛, 周学军. 非对称信道相位匹配量子密钥分发. , 2023, 72(14): 140302. doi: 10.7498/aps.72.20230652
[4]	姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子行走的反馈搜索算法. , 2022, 71(3): 030201. doi: 10.7498/aps.71.20211000
[5]	姜瑶瑶, 张文彬, 初鹏程, 马鸿洋. 基于置换群的多粒子环上量子漫步的反馈搜索算法. , 2021, (): . doi: 10.7498/aps.70.20211000
[6]	范鑫, 梁红静, 单立宇, 闫博, 高庆华, 马日, 丁大军. 基于高次谐波产生的极紫外偏振涡旋光. , 2020, 69(4): 044203. doi: 10.7498/aps.69.20190834
[7]	张冬晓, 陈志斌, 肖程, 秦梦泽, 吴浩. 基于引力搜索算法的湍流相位屏生成方法. , 2019, 68(13): 134205. doi: 10.7498/aps.68.20190081
[8]	滕欢, 柴路, 王清月, 胡明列. 高非线性光子晶体光纤中优化产生宽带紫外三次谐波. , 2017, 66(4): 044205. doi: 10.7498/aps.66.044205
[9]	薛希玲, 陈汉武, 刘志昊, 章彬彬. 基于散射量子行走的完全图上结构异常搜索算法. , 2016, 65(8): 080302. doi: 10.7498/aps.65.080302
[10]	李建设, 李曙光, 赵原源, 刘强, 范振凯, 王光耀. 在单零色散微结构光纤中一次抽运同时发生两组四波混频的实验观察. , 2016, 65(21): 214201. doi: 10.7498/aps.65.214201
[11]	李晓明, 沈学举, 刘恂, 王琳. KTP倍频器件温度适应性扩展研究. , 2015, 64(9): 094205. doi: 10.7498/aps.64.094205
[12]	刘艳梅, 陈汉武, 刘志昊, 薛希玲, 朱皖宁. 星图上的散射量子行走搜索算法. , 2015, 64(1): 010301. doi: 10.7498/aps.64.010301
[13]	王治昊, 王雅丽, 李拓, 史祎诗. 基于旋转相位编码与照明光束匹配的叠层衍射成像算法研究. , 2014, 63(16): 164204. doi: 10.7498/aps.63.164204
[14]	赵兴涛, 郑义, 韩颖, 周桂耀, 侯峙云, 沈建平, 王春, 侯蓝田. 光子晶体光纤包层可见光及红外宽带色散波产生. , 2013, 62(6): 064215. doi: 10.7498/aps.62.064215
[15]	曾维友, 谢康, 陈伟, 毛书哲. TE-TM模变换型光波导隔离器的理论研究. , 2012, 61(16): 164201. doi: 10.7498/aps.61.164201
[16]	任爱红, 刘正颖, 张蓉竹, 刘静伦, 孙年春. 准相位匹配倍频系统的带宽性质研究. , 2010, 59(10): 7050-7054. doi: 10.7498/aps.59.7050
[17]	周城, 高艳侠, 王培吉, 张仲, 李萍. 负折射率材料中二次谐波转换效率的理论分析. , 2009, 58(2): 914-918. doi: 10.7498/aps.58.914
[18]	马晶, 刘迎. KBe2BO3F2飞秒光参量放大中的群速匹配. , 2009, 58(7): 4697-4701. doi: 10.7498/aps.58.4697
[19]	陈亮, 梁昌洪, 党晓杰. 非线性左手材料中的二次谐波. , 2007, 56(11): 6398-6402. doi: 10.7498/aps.56.6398
[20]	邵钟浩. 具有非均匀零色散波长光纤中的四波混频. , 2001, 50(1): 73-78. doi: 10.7498/aps.50.73

计量

文章访问数: 7133
PDF下载量: 304
被引次数: 0

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

搜索

留言板