Princeton University Department of Physics Colloquium

There is a lot of interest in knowing what problems could be solved more efficiently by a quantum computer than a classical computer, if and when a quantum computer can be built. There are a small number of specialized algorithms, of which Shor's algorithm for factoring large integers is the most famous, for which a quantum computer would be more efficient than any existing classical algorithm. In addition, the Quantum Adiabatic Algorithm (QAA) has been proposed as a way of solving a wide class of hard optimization problems on a quantum computer. In this approach one uses the quantum computer as an analogue computer, encodes the interactions of the problem in the connections between the qubits, and evolves the system slowly (one hopes adiabatically) in real time. However, there is no proof that this approach, even if one could implement it, would be more efficient than classical optimization algorithms such as simulated annealing. Early studies on very small sizes (up to about N=20 bits) indicated that the time to solve the problem only increased with a low power of N. If this trend continued to large N, the QAA would be very powerful since existing classical algorithms take an exponential amount of time (for the "worst" instances and usually for "typical" instances too). We have recently applied the technique of Quantum Monte Carlo simulations from statistical physics to study much larger sizes. During the time evolution the system undergoes a quantum phase transition, and we find that, as the size increases, an increasing fraction of instances have a first order (discontinuous) phase transition, which would be very difficult for the QAA. Prospects for the future will be discussed. Work in collaboration with Vadim Smelyanskiy and Sergey Knysh, NASA Ames Lab. A preliminary account of this work appeared in Phys. Rev. Lett. 101, 170503 (2008).