4.8 Article

A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem

Journal

SCIENCE
Volume 292, Issue 5516, Pages 472-476

Publisher

AMER ASSOC ADVANCEMENT SCIENCE
DOI: 10.1126/science.1057726

Keywords

-

Ask authors/readers for more resources

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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.8
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available