A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

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 i...

Full description

Saved in:
Bibliographic Details
Published in:Science (American Association for the Advancement of Science) 2001-04, Vol.292 (5516), p.472-476
Main Authors: Farhi, Edward, Goldstone, Jeffrey, Gutmann, Sam, Lapan, Joshua, Lundgren, Andrew, Preda, Daniel
Format: Article
Language:English
Subjects:
Algorithms
Atoms
Classical and quantum physics: mechanics and fields
Computers
Data lines
Evidence
Exact sciences and technology
Ground state
Integers
Laser beams
Mathematics
Numbers
Physics
Polynomials
Quantum computation
Quantum computers
Quantum information
Quantum Mechanics
Quantum theory
Rotation
Software
Statistical median
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0036-8075
1095-9203
DOI:10.1126/science.1057726