Strengths and Weaknesses of Simulated Quantum Annealing

模拟量子退火的优点和缺点

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

This project will investigate the benefits of quantum annealing for solving computational problems. It is known that quantum computers that use quantum mechanical phenomena (such as tunneling, interference, superpositions, and entanglement) to process information would be able to solve certain problems that are infeasible to tackle with current day classical computers. However, there are other computational tasks for which a quantum computer would not provide any significant benefit. This project on quantum computation investigates the extent to which quantum computers will outperform classical ones by comparing the capabilities of quantum algorithms to the power of the best possible classical algorithms. Quantum annealing is a heuristic quantum approach for solving general optimization problems. In comparison, simulated quantum annealing refers to a class of classical algorithms that simulate quantum annealing dynamics. This project will investigate the extent to which these classical algorithms are capable of efficiently simulating quantum computing protocols. The outcomes of this research should clarify whether quantum computers are needed to achieve the performance of quantum annealing algorithms, or if this performance can be reproduced using classical simulations. This project will quantify the computational power of algorithms that simulate the quantum mechanical process of annealing. One focus of this project is on the ability of algorithms that use Quantum Monte Carlo (QMC) techniques to find the ground state in settings where quantum adiabatically these states are found efficiently. It is sometimes claimed that Quantum Adiabatic Optimization (QAO) will be superior to classical optimization as it is able to quantum tunnel through barriers to find the global minimum of cost functions. There is however also recent evidence that path integral Quantum Monte Carlo algorithms are able to efficiently simulate this behavior. Part of this project will analyze if the power of QMC tunneling is indeed identical to that of QAO tunneling. A situation where QMC appears to fail in simulating quantum adiabatic systems is in the presence of so-called "topological obstructions". This project will investigate ways to adjust QMC algorithms to overcome such obstructions. Another topic of research concerns the possibility of designing a black-box problem that can be solved efficiently using standard adiabatic optimization but that provably does not have an efficient classical simulation.

该项目将研究量子退火对解决计算问题的好处。众所周知，使用量子机械现象（例如隧道，干扰，叠加和纠缠）来处理信息的量子计算机将能够解决某些与当前的古典计算机解决的问题。但是，还有其他计算任务，量子计算机无法提供任何重大好处。量子计算上的该项目通过将量子算法的能力与最好的经典算法的功能进行比较，研究了量子计算机将超过经典计算机的程度。量子退火是解决一般优化问题的一种启发式量子方法。相比之下，模拟的量子退火是指模拟量子退火动力学的一类经典算法。该项目将研究这些经典算法能够有效模拟量子计算协议的程度。这项研究的结果应阐明是否需要量子计算机来实现量子退火算法的性能，还是使用经典模拟可以再现此性能。该项目将量化模拟退火的量子机械过程的算法的计算能力。该项目的一个重点是使用量子蒙特卡洛（QMC）技术的算法的能力，以在绝热的量子上有效地发现了这些状态。有时据称量子绝热优化（QAO）将优于经典优化，因为它能够通过障碍量子隧道以找到全球成本功能的最低限度。但是，最近还有证据表明，路径积分量子蒙特卡洛算法能够有效地模拟这种行为。该项目的一部分将分析QMC隧道的力量是否确实与QAO隧道相同。 QMC在模拟量子绝热系统中似乎失败的情况是在存在所谓的“拓扑障碍”的情况下。该项目将研究调整QMC算法以克服此类障碍的方法。研究的另一个主题涉及设计黑框问题的可能性，可以使用标准绝热优化有效地解决该问题，但事实证明，这不是有效的经典模拟。