First order phase transition in the Quantum Adiabatic Algorithm
ORAL
Abstract
We investigate the complexity of the Quantum Adiabatic Algorithm using quantum Monte Carlo simulations incorporating parallel tempering for sizes up to $N = 256$. For a particular model, known as Exact Cover, we find that an increasing fraction of instances have a first order (discontinuous) quantum phase transition during the evolution of the algorithm. This implies a very small gap (probably exponential) and hence a very long running time for the algorithm to succeed. Preliminary results on other models will also be reported.
*Work supported by the Army Research Office, the National Science Foundation, the National Security Agency's Laboratory of Physics Sciences and the NASA Ames NAS Supercomputing Center.
–