dorsal/arxiv
View SchemaQuantum simulated annealing
| Authors | Steve Huntsman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0012112 |
| URL | https://arxiv.org/abs/quant-ph/0012112 |
Abstract
The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.
{
"annotation_id": "bbf3dbe1-1fb8-4497-a858-94e9e3716270",
"date_created": "2026-03-02T18:01:42.256000Z",
"date_modified": "2026-03-02T18:01:42.256000Z",
"file_hash": "d3a9dbe60e7c97486f261037770e3037362e6fade89d66ddfde166949275f8a7",
"private": false,
"record": {
"abstract": "The question of whether or not quantum computers can efficiently solve\nNP-complete problems is open, although indications are that BQP does not\ncontain NP. Still, many of these problems are natural candidates for solution\non quantum computers. We outline a thermodynamical formalism for the traveling\nsalesman problem which allows for its expected polytime solution on a quantum\ncomputer with probability arbitrarily close to unity, given sufficient energy\nresources and subject to a weak nondegeneracy constraint on the distances.\nApplications to other problems are also discussed.",
"arxiv_id": "quant-ph/0012112",
"authors": [
"Steve Huntsman"
],
"categories": [
"quant-ph"
],
"title": "Quantum simulated annealing",
"url": "https://arxiv.org/abs/quant-ph/0012112"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6d78b79b-8d9a-4b89-9a20-2f9554e9c98e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}