dorsal/arxiv
View SchemaSingle-Step Quantum Search Using Problem Structure
| Authors | Tad Hogg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812049 |
| URL | https://arxiv.org/abs/quant-ph/9812049 |
| DOI | 10.1142/S0129183100000663 |
| Journal | Int.J.Mod.Phys. C11 (2000) 739-773 |
Abstract
The structure of satisfiability problems is used to improve search algorithms for quantum computers and reduce their required coherence times by using only a single coherent evaluation of problem properties. The structure of random k-SAT allows determining the asymptotic average behavior of these algorithms, showing they improve on quantum algorithms, such as amplitude amplification, that ignore detailed problem structure but remain exponential for hard problem instances. Compared to good classical methods, the algorithm performs better, on average, for weakly and highly constrained problems but worse for hard cases. The analytic techniques introduced here also apply to other quantum algorithms, supplementing the limited evaluation possible with classical simulations and showing how quantum computing can use ensemble properties of NP search problems.
{
"annotation_id": "1035f888-12eb-41fc-b9c7-6f080f83aed8",
"date_created": "2026-03-02T18:02:44.189000Z",
"date_modified": "2026-03-02T18:02:44.189000Z",
"file_hash": "62b68734d52ce7f1a07fc1c7f9723124f1d7f5bb772ff347cfae146b6da0f00b",
"private": false,
"record": {
"abstract": "The structure of satisfiability problems is used to improve search algorithms\nfor quantum computers and reduce their required coherence times by using only a\nsingle coherent evaluation of problem properties. The structure of random k-SAT\nallows determining the asymptotic average behavior of these algorithms, showing\nthey improve on quantum algorithms, such as amplitude amplification, that\nignore detailed problem structure but remain exponential for hard problem\ninstances. Compared to good classical methods, the algorithm performs better,\non average, for weakly and highly constrained problems but worse for hard\ncases. The analytic techniques introduced here also apply to other quantum\nalgorithms, supplementing the limited evaluation possible with classical\nsimulations and showing how quantum computing can use ensemble properties of NP\nsearch problems.",
"arxiv_id": "quant-ph/9812049",
"authors": [
"Tad Hogg"
],
"categories": [
"quant-ph"
],
"doi": "10.1142/S0129183100000663",
"journal_ref": "Int.J.Mod.Phys. C11 (2000) 739-773",
"title": "Single-Step Quantum Search Using Problem Structure",
"url": "https://arxiv.org/abs/quant-ph/9812049"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a850872e-ca50-4bc2-b647-32b454e11523",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}