Complexity of Simulating Quantum Adiabatic Optimization by Quantum Monte Carlo Methods

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

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.