ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2008, Vol. 45 ›› Issue (9): 1501-1508.

• • 上一篇    下一篇

量子退火算法研究进展

杜卫林 李 斌 田 宇   

  1. (中国科学技术大学电子科学与技术系 合肥 230027) (wldu@mail.ustc.edu.cn)
  • 出版日期: 2008-09-15

Quantum Annealing Algorithms: State of the Art

Du Weilin, Li Bin, and Tian Yu   

  1. (Department of Electronic Science and Technology, University of Science and Technology of China, Hefei 230027)
  • Online: 2008-09-15

摘要: 在数学和应用领域,量子退火算法是一类新的量子优化算法.不同于经典模拟退火算法利用热波动来搜寻问题的最优解,量子退火算法利用量子波动产生的量子隧穿效应来使算法摆脱局部最优,而实现全局优化.在已有的研究中,量子退火算法在某些问题上展现出良好的优化效果.系统地综述了量子退火算法的基本原理和近年来的主要研究进展,较为详细地介绍了几个主要的量子退火算法,对量子退火算法的优点和可能的不足进行了分析评述,并对今后的研究方向进行了展望.

关键词: 量子退火, 蒙特卡罗方法, 优化算法, 量子优化, 量子计算

Abstract: In mathematics and applications, quantum annealing is a new method for finding solutions to combinatorial optimization problems and ground states of glassy systems using quantum fluctuations. Quantum fluctuations can be simulated in computers using various quantum Monte Carlo techniques, such as the path integral Monte Carlo method, and thus they can be used to obtain a new kind of heuristic algorithm for global optimization. It can be said that the idea of quantum annealing comes from the celebrated classical simulated thermal annealing invented by Kirkpatrick. However, unlike a simulated annealing algorithm, which utilizes thermal fluctuations to help the algorithm jump from local optimum to global optimum, quantum annealing algorithms utilize quantum fluctuations to help the algorithm tunnel through the barriers directly from local optimum to global optimum. According to the previous studies, although the quantum annealing algorithm is not capable, in general, of finding solutions to NP-complete problems in polynomial time, quantum annealing is still a promising optimization technique, which exhibits good performances on some typical optimization problems, such as the transverse Ising model and the traveling salesman problem. Provided in this paper is an overview of the principles and research progresses of quantum annealing algorithms in recent years; several different kinds of quantum annealing algorithms are presented in detail; both the advantages and disadvantages of each algorithm are analyzed; and prospects for the research orientation of the quantum annealing algorithm in future are given.

Key words: quantum annealing, Monte Carlo method, optimization algorithms, quantum optimization, quantum computation