A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Edward Farhi,1*
Jeffrey Goldstone,1
Sam Gutmann,2
Joshua Lapan,3
Andrew Lundgren,3
Daniel Preda3
A quantum system will stay near its instantaneous ground
state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of
algorithms for quantum computing. We tested one such algorithm by
applying it to randomly generated hard instances of an NP-complete
problem. For the small examples that we could simulate, the quantum
adiabatic algorithm worked well, providing evidence that quantum
computers (if large ones can be built) may be able to outperform
ordinary computers on hard sets of instances of NP-complete problems.
1 Center for Theoretical Physics, Massachusetts
Institute of Technology, Cambridge, MA 02139, USA.
2 Department of Mathematics, Northeastern
University, Boston, MA 02115, USA.
3 Massachusetts
Institute of Technology, Cambridge, MA 02139, USA.
*
To whom correspondence should be addressed. E-mail:
farhi{at}mit.edu
