dorsal/arxiv
View SchemaQuantum Adiabatic Computation and the Travelling Salesman Problem
| Authors | Tien D. Kieu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0601151 |
| URL | https://arxiv.org/abs/quant-ph/0601151 |
Abstract
The NP-complete problem of the travelling salesman (TSP) is considered in the framework of quantum adiabatic computation (QAC). We first derive a remarkable lower bound for the computation time for adiabatic algorithms in general as a function of the energy involved in the computation. Energy, and not just time and space, must thus be considered in the evaluation of algorithm complexity, in perfect accordance with the understanding that all computation is physical. We then propose, with oracular Hamiltonians, new quantum adiabatic algorithms of which not only the lower bound in time but also the energy requirement do not increase exponentially in the size of the input. Such an improvement in both time and energy complexity, as compared to all other existing algorithms for TSP, is apparently due to quantum entanglement. We also appeal to the general theory of Diophantine equations in a speculation on physical implementation of those oracular Hamiltonians.
{
"annotation_id": "996f6945-4a61-45c1-b3a0-38d1b91cdcdb",
"date_created": "2026-03-02T18:02:24.278000Z",
"date_modified": "2026-03-02T18:02:24.278000Z",
"file_hash": "d02662b3044591b745decb797d97669190eba7c081e60e1a94a958090ef4b160",
"private": false,
"record": {
"abstract": "The NP-complete problem of the travelling salesman (TSP) is considered in the\nframework of quantum adiabatic computation (QAC). We first derive a remarkable\nlower bound for the computation time for adiabatic algorithms in general as a\nfunction of the energy involved in the computation. Energy, and not just time\nand space, must thus be considered in the evaluation of algorithm complexity,\nin perfect accordance with the understanding that all computation is physical.\nWe then propose, with oracular Hamiltonians, new quantum adiabatic algorithms\nof which not only the lower bound in time but also the energy requirement do\nnot increase exponentially in the size of the input. Such an improvement in\nboth time and energy complexity, as compared to all other existing algorithms\nfor TSP, is apparently due to quantum entanglement. We also appeal to the\ngeneral theory of Diophantine equations in a speculation on physical\nimplementation of those oracular Hamiltonians.",
"arxiv_id": "quant-ph/0601151",
"authors": [
"Tien D. Kieu"
],
"categories": [
"quant-ph"
],
"title": "Quantum Adiabatic Computation and the Travelling Salesman Problem",
"url": "https://arxiv.org/abs/quant-ph/0601151"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e682b911-3a5a-4d00-91f2-62672f7ce63b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}