dorsal/arxiv
View SchemaAdiabatic Quantum Computing for Random Satisfiability Problems
| Authors | Tad Hogg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0206059 |
| URL | https://arxiv.org/abs/quant-ph/0206059 |
| DOI | 10.1103/PhysRevA.67.022314 |
| Journal | Phys Rev A 67 022314 (2003) |
Abstract
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
{
"annotation_id": "85368690-ff2d-4c4b-9bd4-0fc4aab7fd78",
"date_created": "2026-03-02T18:01:51.828000Z",
"date_modified": "2026-03-02T18:01:51.828000Z",
"file_hash": "63c6367db86ba613f9b09356eb0a52011dd37ba5fc1cf94b52b31abcf69ddf6a",
"private": false,
"record": {
"abstract": "The discrete formulation of adiabatic quantum computing is compared with\nother search methods, classical and quantum, for random satisfiability (SAT)\nproblems. With the number of steps growing only as the cube of the number of\nvariables, the adiabatic method gives solution probabilities close to 1 for\nproblem sizes feasible to evaluate via simulation on current computers.\nHowever, for these sizes the minimum energy gaps of most instances are fairly\nlarge, so the good performance scaling seen for small problems may not reflect\nasymptotic behavior where costs are dominated by tiny gaps. Moreover, the\nresulting search costs are much higher than for other methods. Variants of the\nquantum algorithm that do not match the adiabatic limit give lower costs, on\naverage, and slower growth than the conventional GSAT heuristic method.",
"arxiv_id": "quant-ph/0206059",
"authors": [
"Tad Hogg"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.67.022314",
"journal_ref": "Phys Rev A 67 022314 (2003)",
"title": "Adiabatic Quantum Computing for Random Satisfiability Problems",
"url": "https://arxiv.org/abs/quant-ph/0206059"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "bdf82f3e-db58-4478-8037-7f44f3f6dde8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}