量子非局域性与量子通信复杂度研究

doi:10.19678/j.issn.1000-3428.0052199

计算机工程 ›› 2018, Vol. 44 ›› Issue (12): 28-32. doi: 10.19678/j.issn.1000-3428.0052199

所属专题：量子信息技术专题；

量子非局域性与量子通信复杂度研究

张弘弛^1a,2,刘百祥^1a,1b,2,文捷^1a,1b,2

1.复旦大学a.计算机科学技术学院上海市智能信息处理重点实验室; b.校园信息化办公室,上海 200433; 2.复旦-众安区块链与信息安全联合实验室,上海 200433

收稿日期:2018-07-24 出版日期:2018-12-15 发布日期:2018-12-15
作者简介:张弘弛(1992—),男,硕士研究生,主研方向为量子计算、计算复杂性;刘百祥、文捷,工程师。
基金资助:
国家自然科学基金(61672166);上海市科技创新行动计划(16JC1402700);上海市优秀学术带头人计划(16XD1400200);上海市领军人才计划(JLH2301003)。

Research on Quantum Non-locality and Quantum Communication Complexity

ZHANG Hongchi^1a,2,LIU Baixiang ^1a,1b,2,WEN Jie ^1a,1b,2

1a.Shanghai Key Laboratory of Intelligent Information Processing,School of Computer Science; 1b.Informatization Office,Fudan University,Shanghai 200433,China; 2.Fudan and Zhong’an Blockchain and Information Security Joint Lab,Shanghai 200433,China

Received:2018-07-24 Online:2018-12-15 Published:2018-12-15

摘要/Abstract

摘要：

论述国内外量子通信研究现状,研究量子非局域性问题和量子通信复杂度问题,通过纠缠态粒子解决GHZ问题,利用分布式算法讨论传递比特的最小数目。分析非局域性与通信复杂度之间的关联关系,进而研究同时消息传递模型。分析结果表明,与经典通信相比,量子通信效率较高,且量子非局域性问题和量子通信复杂度问题可以相互转换。

关键词: 量子通信, 量子计算, 纠缠态粒子, 通信复杂度, 量子非局域性

Abstract:

The research status of quantum communication at home and abroad is discussed.The problem of quantum non-locality and quantum communication complexity is studied.The GHZ problem is solved by entangled particles,and the minimum number of transmitted bits is discussed by using distributed algorithm.The relationship between non-locality and communication complexity is analyzed,and then the simultaneous message passing model is studied.The results show that compared with the classical communication,the quantum communication efficiency is high,and the quantum non-locality problem and the quantum communication complexity problem can be mutually converted.

Key words: quantum communication, quantum computation, entangled particle, communication complexity, quantum non-locality

中图分类号:

O413

张弘弛,刘百祥,文捷. 量子非局域性与量子通信复杂度研究[J]. 计算机工程, 2018, 44(12): 28-32.

ZHANG Hongchi,LIU Baixiang,WEN Jie. Research on Quantum Non-locality and Quantum Communication Complexity[J]. Computer Engineering, 2018, 44(12): 28-32.

http://www.ecice06.com/CN/Y2018/V44/I12/28

参考文献

［1］SHOR P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer［J］.SIAM Review,1999,41(2):303-332.
［2］DEUTSCH D,JOZSA R.Rapid solution of problems by quantum computation［J］.Mathematical and Physical Sciences,1992,439:553-558.
［3］麻敏,李志慧,徐廷廷.可验证的(n,n)门限量子密码共享方案［J］.计算机工程,2017,43(8):169-172.
［4］冯晓华,孙永奇.基于量子进化的给定围长构造算法［J］.计算机工程,2017,43(10):141-146.
［5］YAO C C.Quantum circuit complexity［C］//Proceedings of the 34th IEEE Annual Foundations of Computer Science.Washington D.C.,USA:IEEE Press,1993:352-361.
［6］MERMIN N D.Extreme quantum entanglement in a superposition of macroscopically distinct states［J］.Physical Review Letters,1990,65(15):1838.
［7］BUHRMAN H,CLEVE R,WIGDERSON A.Quantum vs.classical communication and computation［C］//Proceedings of the 30th ACM Symposium on Theory of Computing.New York,USA:ACM Press,1998:63-68.
［8］BENENTI G,CASATI G,STRINI G.量子计算与量子信息原理［M］.王文阁,李宝文,译.北京:科学出版社,2011.
［9］ARORA S,BARAK B.Computational complexity:a modern approach［M］.Cambridge,UK:Cambridge University Press.2009.
［10］CLEVE R,BUHRMAN H.Substituting quantum entangle-ment for communication［J］.Physical Review A,1997,56(2):1201-1204.
［11］AMBAINIS A,SCHULMAN L J,TA-SHMA A,et al.The quantum communication complexity of sampling［C］// Proceedings of Symposium on Foundations of Computer Science.Washington D.C.,USA:IEEE Press,1998:342-351.
［12］季赛,陈思怡,瞿治国.一种安全的大容量量子图像水印协议［J］.计算机工程,2018,44(5):234-239.
［13］FRANKL P,RDL V.Forbidden intersections［J］.Transactions of the American Mathematical Society,1987,300(1):259-286.
［14］BUHRMAN H,CLEVE R,MASSAR S,et al.Nonlocality and communication complexity［J］.Review of Modern Physics,2010,82(1):665-698.
［15］JAIN R,WEI Z,YAO P,et al.Multipartite quantum correlation and communication complexities［J］.Computational Complexity,2014,26(1):1-30.
［16］BUHRMAN H,CZEKAJ L,GRUDKA A,et al.Quantum communication complexity advantage implies violation of a bell inequality［J］.National Academy of Sciences,2015,113(12):3191-3196.
［17］YAO C C.Some complexity questions related to distributive computing［C］//Proceedings of the 7th ACM Symposium on Theory of Computing.New York,USA:ACM Press,1979:209-213.
［18］AMBAINIS A.Communication complexity in a 3-computer model［J］.Algorithmica,1996,16(3):298-301.
［19］BEALS R,BUHRMAN H,CLEVE R,et al.Quantum lower bounds by polynomials［C］//Proceedings of the 39th Annual Symposium on Foundations of Computer Science.New York,USA:ACM Press,1998:352.

[1]	张然, 高莹雪, 赵钰, 丁元明. 基于Q学习量子蚁群的微纳卫星路由算法[J]. 计算机工程, 2022, 48(3): 162-169,188.
[2]	喻志超, 李扬中, 刘磊, 冯圣中. 量子计算模拟及优化方法综述[J]. 计算机工程, 2022, 48(1): 1-11.
[3]	王富民, 倪明, 周明, 吴永政. 量子绝热近似求解最大割问题的最优解[J]. 计算机工程, 2020, 46(1): 25-30.
[4]	陈思宇,熊丽,黄铭. 生成轨道角动量的圆极化螺母型贴片天线[J]. 计算机工程, 2019, 45(6): 254-258.
[5]	江岸,李向阳. 基于信息位分组的标签防碰撞算法[J]. 计算机工程, 2018, 44(3): 294-300.
[6]	陈振宇,杨阳,季赛,刘文杰. 基于量子委托计算模式的半量子密钥协商[J]. 计算机工程, 2018, 44(3): 178-181,188.
[7]	栾添,张雪松,陈徐宗. 量子气体在光晶格中的一维玻色-哈伯德模型模拟[J]. 计算机工程, 2018, 44(12): 1-5.
[8]	卫佳,倪明,周明,江文兵. 基于IBM Q平台的量子算法研究[J]. 计算机工程, 2018, 44(12): 6-12.
[9]	郭鹏，张海燕，赵宝柱，刘振永. 基于RFID的低功耗邮件识别系统设计[J]. 计算机工程, 2013, 39(9): 289-292.
[10]	沙林秀，贺昱曜. 一种新的自适应量子遗传算法[J]. 计算机工程, 2013, 39(9): 218-221.
[11]	戴勇谦, 张明武, 祝胜林, 戴勇新. 基于变异概率分析的改进QGA及其应用[J]. 计算机工程, 2013, 39(7): 247-251,256.
[12]	赵程程, 杨亚涛, 李子臣, 阎晓姮. 基于McEliece公钥密码体制的盲签名算法[J]. 计算机工程, 2013, 39(6): 146-149.
[13]	黄俊华, 唐平, 陈松龄, 江小平, 梁英蓬. 量子遗传算法在口腔种植定位中的研究与应用[J]. 计算机工程, 2013, 39(1): 208-212.
[14]	曹斯彤, 陈贤富. 一种新型量子演化算法及其应用研究[J]. 计算机工程, 2012, 38(24): 188-190.
[15]	鲁晓彬, 李发达, 田礼, 鲍皖苏. 一种改进的多变量数字签名方案安全性分析[J]. 计算机工程, 2012, 38(22): 95-98.

选择文件类型/文献管理软件名称

选择包含的内容

量子非局域性与量子通信复杂度研究

Research on Quantum Non-locality and Quantum Communication Complexity

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

量子非局域性与量子通信复杂度研究

Research on Quantum Non-locality and Quantum Communication Complexity

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价