A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
15 pages, 8 figures, LaTeX with BoxedEPS macros; email to farhi@mit.edu
15 pages, 8 figures, LaTeX with BoxedEPS macros; email to farhi@mit.edu