A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Simple item page
dc.creatorFarhi, Edward
dc.creatorGoldstone, Jeffrey
dc.creatorGutmann, Sam
dc.date2000-07-19
dc.date.accessioned2026-07-07T06:00:26Z
dc.date.available2026-07-07T06:00:26Z
dc.descriptionQuantum 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.
dc.description15 pages, 8 figures, LaTeX with BoxedEPS macros; email to farhi@mit.edu
dc.identifierhttps://arxiv.org/abs/quant-ph/0007071
dc.identifierhttp://arxiv.org/abs/quant-ph/0007071
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/88975
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleA Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
dc.typetext

Files

Collections

arXiv