dorsal/arxiv
View SchemaA Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
| Authors | Edward Farhi, Jeffrey Goldstone, Sam Gutmann |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0007071 |
| URL | https://arxiv.org/abs/quant-ph/0007071 |
Abstract
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.
{
"annotation_id": "97b493d0-4d88-4a5c-a74c-3da5d32b24c8",
"date_created": "2026-03-02T18:01:38.925000Z",
"date_modified": "2026-03-02T18:01:38.925000Z",
"file_hash": "f6a8183ff84e48dc9d2ca850b4ccf2d40bb808ef9de0f5871505cfd7cf87099f",
"private": false,
"record": {
"abstract": "Quantum computation by adiabatic evolution, as described in quant-ph/0001106,\nwill solve satisfiability problems if the running time is long enough. In\ncertain special cases (that are classically easy) we know that the quantum\nalgorithm requires a running time that grows as a polynomial in the number of\nbits. In this paper we present numerical results on randomly generated\ninstances of an NP-complete problem and of a problem that can be solved\nclassically in polynomial time. We simulate a quantum computer (of up to 16\nqubits) by integrating the Schrodinger equation on a conventional computer. For\nboth problems considered, for the set of instances studied, the required\nrunning time appears to grow slowly as a function of the number of bits.",
"arxiv_id": "quant-ph/0007071",
"authors": [
"Edward Farhi",
"Jeffrey Goldstone",
"Sam Gutmann"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability",
"url": "https://arxiv.org/abs/quant-ph/0007071"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fff57a9d-717a-4d17-a716-4abb540f4ccf",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}