Strengths and Weaknesses of Simulated Quantum Annealing

这个项目将研究量子退火在解决计算问题方面的好处。众所周知，利用量子力学现象（如隧道、干涉、叠加和纠缠）来处理信息的量子计算机将能够解决当前经典计算机无法解决的某些问题。然而，还有其他计算任务，量子计算机不会提供任何显着的好处。这个关于量子计算的项目通过比较量子算法的能力和最好的经典算法的能力来研究量子计算机在多大程度上优于经典计算机。量子退火是求解一般优化问题的一种启发式量子方法。相比之下，模拟量子退火是一类模拟量子退火动力学的经典算法。该项目将研究这些经典算法在多大程度上能够有效地模拟量子计算协议。这项研究的结果应该澄清是否需要量子计算机来实现量子退火算法的性能，或者是否可以使用经典模拟来再现这种性能。这个项目将量化模拟退火量子力学过程的算法的计算能力。这个项目的一个重点是使用量子蒙特卡罗（QMC）技术的算法的能力，以在量子绝热的情况下有效地找到这些状态。量子绝热优化（QAO）有时被认为优于经典优化，因为它能够通过量子隧道找到成本函数的全局最小值。然而，最近也有证据表明，路径积分量子蒙特卡罗算法能够有效地模拟这种行为。本项目的一部分将分析QMC隧道的功率是否确实与QAO隧道相同。在所谓的“拓扑障碍”存在的情况下，QMC似乎无法模拟量子绝热系统。这个项目将研究如何调整QMC算法来克服这些障碍。另一个研究课题是设计一个黑盒问题的可能性，该问题可以使用标准绝热优化有效地解决，但可以证明没有有效的经典模拟。

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.