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年以上，但仍不知道扩展这种量子启发式的效果比经典启发式方法更好。一方面，使用量子蒙特卡洛方法的经典算法可能能够有效地模拟量子绝热优化，这证明对量子绝热方法的“量子益处”的强烈限制来求解优化问题。另一方面，也有可能证明量子蒙特卡洛方法无法成功地模仿绝热算法，从而提供了有力的证据，表明量子绝热优化确实具有超出经典计算的计算能力。项目旨在确定这两种可能性中的哪一种。量子计算中的研究是高学科的，在许多物理和计算机科学领域都有影响。此外，该项目将支持这项跨学科研究中研究生的教育和培训。