dorsal/arxiv
View SchemaSolving Random Satisfiability Problems with Quantum Computers
| Authors | Tad Hogg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0104048 |
| URL | https://arxiv.org/abs/quant-ph/0104048 |
Abstract
Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.
{
"annotation_id": "13c3baed-4a2c-4c1e-aa3f-2b2ff2cf6bb6",
"date_created": "2026-03-02T18:01:42.582000Z",
"date_modified": "2026-03-02T18:01:42.582000Z",
"file_hash": "339a5f47e4675314ac89c31cc81a3d108c30a08aa3f8fcf93c207728ed97e89d",
"private": false,
"record": {
"abstract": "Quantum computer algorithms can exploit the structure of random\nsatisfiability problems. This paper extends a previous empirical evaluation of\nsuch an algorithm and gives an approximate asymptotic analysis accounting for\nboth the average and variation of amplitudes among search states with the same\ncosts. The analysis predicts good performance, on average, for a variety of\nproblems including those near a phase transition associated with a high\nconcentration of hard cases. Based on empirical evaluation for small problems,\nmodifying the algorithm in light of this analysis improves its performance. The\nalgorithm improves on both GSAT, a commonly used conventional heuristic, and\nquantum algorithms ignoring problem structure.",
"arxiv_id": "quant-ph/0104048",
"authors": [
"Tad Hogg"
],
"categories": [
"quant-ph"
],
"title": "Solving Random Satisfiability Problems with Quantum Computers",
"url": "https://arxiv.org/abs/quant-ph/0104048"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a30e5ddf-0ab4-4b02-b29d-477c11b1f586",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}