Complexity of Simulating Quantum Adiabatic Optimization by Quantum Monte Carlo Methods

用量子蒙特卡罗方法模拟量子绝热优化的复杂性

• 批准号: 1314969
• 负责人: Willem van Dam
• 金额: $ 25万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1314969&HistoricalAwards=false
• 关键词: Complexity; Simulating; Quantum; Adiabatic; Optimization

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.

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