dorsal/arxiv
View SchemaQuantum Computing and Phase Transitions in Combinatorial Search
| Authors | Tad Hogg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9508012 |
| URL | https://arxiv.org/abs/quant-ph/9508012 |
| Journal | J. of Artificial Intelligence Research 4,91-128 (1996) |
Abstract
We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average. This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices. This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism. Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods. Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.
{
"annotation_id": "9f0214b8-f756-4be4-b056-4fe96039d457",
"date_created": "2026-03-02T18:02:37.881000Z",
"date_modified": "2026-03-02T18:02:37.881000Z",
"file_hash": "eacef5a00acb9f59d9c322b774bc1e104837787a2020f48152ba5b1afb13f4c8",
"private": false,
"record": {
"abstract": "We introduce an algorithm for combinatorial search on quantum computers that\nis capable of significantly concentrating amplitude into solutions for some NP\nsearch problems, on average. This is done by exploiting the same aspects of\nproblem structure as used by classical backtrack methods to avoid unproductive\nsearch choices. This quantum algorithm is much more likely to find solutions\nthan the simple direct use of quantum parallelism. Furthermore, empirical\nevaluation on small problems shows this quantum algorithm displays the same\nphase transition behavior, and at the same location, as seen in many previously\nstudied classical search methods. Specifically, difficult problem instances are\nconcentrated near the abrupt change from underconstrained to overconstrained\nproblems.",
"arxiv_id": "quant-ph/9508012",
"authors": [
"Tad Hogg"
],
"categories": [
"quant-ph"
],
"journal_ref": "J. of Artificial Intelligence Research 4,91-128 (1996)",
"title": "Quantum Computing and Phase Transitions in Combinatorial Search",
"url": "https://arxiv.org/abs/quant-ph/9508012"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d428cc2f-cafb-49e5-aec8-2dd32e5918f6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}