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

By Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua M. Lapan, A. Lundgren, Daniel Preda. Science, 2001

1,921 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d2d5e71b19740bf91b1704570958bf235967857c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

High-fidelity quantum driving (2011, background): “Quantum control may aim at reaching a given target state, as in the cooling of atomic ensembles [14] and nano-mechanical oscillators [15], or at tracking the instantaneous ground state of a system during its evolution as in adiabatic quantum computation [16].”
Colloquium: Nonequilibrium dynamics of closed interacting quantum systems (2010, methodology): “On one hand, the design and realization of interacting many-body systems could in principle be used to perform practical tasks, such as quantum information processing (Farhi et al., 2001).”
Quantum algorithms: an overview (2015, neutral): “Although numerical experiments can be carried out to evaluate its performance on small instances [38], this rapidly becomes infeasible for larger problems.”
Landau-Zener-Stückelberg interferometry (2009, background): “The basic idea of AQC is as follows: one subjects a physical system to a simple initial Hamiltonian, such that it is guaranteed that the system will relax to its ground state.”
Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices (2018, methodology): “[40] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda, “A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,” Science 292, 472– 475 (2001).”