Strengths and Weaknesses of Simulated Quantum Annealing

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

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.