Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D
Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
Science. 2001 Apr 20;292(5516):472-5. doi: 10.1126/science.1057726.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
如果支配量子系统演化的哈密顿量变化足够缓慢，该量子系统将保持在其瞬时基态附近。这种量子绝热行为是一类新型量子计算算法的基础。我们通过将一种这样的算法应用于随机生成的NP完全问题的困难实例来对其进行测试。对于我们能够模拟的小例子，量子绝热算法运行良好，这表明量子计算机（如果能够制造出大型量子计算机）在NP完全问题的困难实例集上可能能够超越普通计算机。
