量子退火理论及其应用综述  

Theories and applications of quantum annealing:A literature survey

作　　者：王宝楠 水恒华 王苏敏 胡风[3,4] 王潮 WANG BaoNan;SHUI HengHua;WANG SuMin;HU Feng;WANG Chao(College Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200090,China;School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China;China Key Laboratory of Specialty Fiber Optics and Optical Access Networks,Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication,Shanghai University,Shanghai 200444,China;State Key Laboratory of Cryptology,Beijing 100878,China;Center for Quantum Computing,Peng Cheng Laboratory,Shenzhen 518000,China)

机构地区：[1]上海电力大学计算机科学与技术学院,上海200090 [2]南京工程学院计算机工程学院,南京211167 [3]上海大学,特种光纤与光接入网重点实验室,特种光纤与先进通信国际合作联合实验室,上海200444 [4]密码科学技术国家重点实验室,北京100878 [5]鹏城实验室量子计算中心,深圳518000

出　　处：《中国科学：物理学、力学、天文学》2021年第8期1-13,共13页Scientia Sinica Physica,Mechanica & Astronomica

基　　金：上海市“科技创新行动计划”扬帆计划(编号:21YF1415100);国家自然科学基金(编号:61572304,61272096,61332019);密码科学技术国家重点实验室开放课题基金项目资助。

摘　　要：量子退火算法是在经典模拟退火算法基础上演进出来的一种新的量子优化算法.与经典模拟退火算法利用热波动来搜索问题的最优解不同,量子退火算法利用量子隧穿效应使得量子具有穿透比其自身能量高的势垒的能力,从而使算法摆脱局部极值,以更高概率逼近全局最优.目前,量子退火算法在组合优化类问题中已展现出良好的优化性能.本文系统地综述了D-Wave量子计算机核心原理——量子退火算法的基本概念及其应用领域,较为详细地分析了量子退火算法在密码学、旅行商问题、图着色问题、交通路径等领域的应用,并对未来量子退火算法的更多待深化与探索的方向进行展望.Quantum annealing(QA) algorithm is a new quantum optimization algorithm based on the classical simulated annealing(SA) algorithm. Unlike classical SA algorithm, which uses the thermal waves to search for the optimal solution, the QA algorithm uses the quantum tunneling effect to allow a quantum to penetrate a potential barrier with a higher energy than itself. Therefore, the algorithm can get rid of the local extreme values and is more likely to approach the global optimal with higher probability. In the literature, the QA algorithm has shown perfect optimization effects on combinatorial optimization problems. In this paper, the basic concepts and application fields of QA algorithm, which is the core principle of D-Wave quantum computer, are systematically reviewed. The applications of QA algorithm in cryptography,traveling salesman problem, graph coloring problem, and traffic path are discussed in detail. In addition, the direction of future research for QA algorithm is explored.

关 键 词：量子退火 D-Wave量子计算机 量子计算 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]