Complexity of Simulating Quantum Adiabatic Optimization by Quantum Monte Carlo Methods

“量子蒙特卡罗方法模拟量子绝热优化的复杂性”项目研究了一种广泛使用的模拟量子物理方法的计算能力和弱点。量子蒙特卡罗方法是分析和模拟大型相干量子系统的常用算法。虽然我们知道这种方法不能有效地模拟所有的量子力学系统，但它也为此类系统的一个大子类提供了可靠的答案。该项目关注的具体问题是，运行量子绝热优化算法的量子计算机是否可以通过量子蒙特卡罗方法有效地模拟。量子计算理论研究的是在量子计算机上可以有效地解决经典计算无法有效解决的问题。该理论的一个重要案例涉及量子绝热优化，这是一种通用的量子算法，试图在指数级大的函数值景观中找到最优值。尽管经过了12年多的研究，量子启发式在哪些方面比经典启发式表现得更好仍然是未知的。一方面，使用量子蒙特卡罗方法的经典算法可能能够有效地模拟量子绝热优化，这将证明量子绝热方法解决优化问题的“量子效益”有很强的局限性。另一方面，也有可能证明量子蒙特卡罗方法不能成功地有效地模拟量子绝热算法，从而有力地证明量子绝热优化确实具有超越经典计算的计算能力。这个项目旨在确定这两种可能性中的哪一种是正确的。量子计算的研究是高度跨学科的，影响着物理学和计算机科学的许多领域。此外，该项目将支持该跨学科研究的研究生教育和培训。

The project "Complexity of Simulating Quantum Adiabatic Optimization by Quantum Monte Carlo Methods" investigates the computational power and weaknesses of a widely used method for simulating quantum physics. The Quantum Monte Carlo method is a commonly used algorithm for analyzing and simulating large, coherent quantum systems. Although it is known that this method can not efficiently simulate all quantum mechanical systems, it is also known to provide reliable answers for a large subclass of such systems. The project focuses on the specific question whether or not a quantum computer running the Quantum Adiabatic Optimization algorithm is efficiently simulatable by the Quantum Monte Carlo method.  The theory of quantum computation looks at the question which problems can be solved efficiently on a quantum computer that do not have an efficient solution using classical computation. An important case of this theory concerns Quantum Adiabatic Optimization, which is a general purpose quantum algorithm that attempts to find the optimal value in an exponentially large landscape of function values. Despite more than 12 years of study, it is still not known to which extend this quantum heuristic performs better than classical heuristics. On the one hand, it is possible that a classical algorithm that uses the Quantum Monte Carlo method will be able to efficiently simulate quantum adiabatic optimization, which would prove a strong limitation on the 'quantum benefit' of the quantum adiabatic approach to solving optimization problems. On the other hand, it is also possible that one can prove that the Quantum Monte Carlo method does not succeed in efficiently mimicking the quantum adiabatic algorithm, thus providing strong evidence that quantum adiabatic optimization does indeed have computational powers that go beyond classical computation. This project aims to determine which one of these two possibilities is the case. Research in quantum computation is high interdisciplinary with impacts in a number of areas of physics and computer science. In addition, this project will support the education and training of a graduate student in this cross-disciplinary research.