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算法来克服这些障碍。另一个研究主题是设计一个黑盒问题的可能性，这个问题可以使用标准绝热优化有效地解决，但可以证明没有有效的经典模拟。