dorsal/arxiv
View SchemaExponential complexity of an adiabatic algorithm for an NP-complete problem
| Authors | Marko Znidaric, Martin Horvat |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0509162 |
| URL | https://arxiv.org/abs/quant-ph/0509162 |
| DOI | 10.1103/PhysRevA.73.022329 |
| Journal | Phys.Rev.A. 73, 022329 (2006) |
Abstract
We prove an analytical expression for the size of the gap between the ground and the first excited state of quantum adiabatic algorithm for the 3-satisfiability, where the initial Hamiltonian is a projector on the subspace complementary to the ground state. For large problem sizes the gap decreases exponentially and as a consequence the required running time is also exponential.
{
"annotation_id": "7d8dbcd0-4d93-4e8d-9690-b7c6b7508017",
"date_created": "2026-03-02T18:02:20.596000Z",
"date_modified": "2026-03-02T18:02:20.596000Z",
"file_hash": "0fc4f77be4f913916d41f12a067f3eb0d60d0399ed3f5a5e797144a4d6b3888d",
"private": false,
"record": {
"abstract": "We prove an analytical expression for the size of the gap between the ground\nand the first excited state of quantum adiabatic algorithm for the\n3-satisfiability, where the initial Hamiltonian is a projector on the subspace\ncomplementary to the ground state. For large problem sizes the gap decreases\nexponentially and as a consequence the required running time is also\nexponential.",
"arxiv_id": "quant-ph/0509162",
"authors": [
"Marko Znidaric",
"Martin Horvat"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.73.022329",
"journal_ref": "Phys.Rev.A. 73, 022329 (2006)",
"title": "Exponential complexity of an adiabatic algorithm for an NP-complete problem",
"url": "https://arxiv.org/abs/quant-ph/0509162"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "63553e85-cf79-4d24-b777-90f4b0a786d2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}