dorsal/arxiv
View SchemaComments on Adiabatic Quantum Algorithms
| Authors | Mary Beth Ruskai |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0203127 |
| URL | https://arxiv.org/abs/quant-ph/0203127 |
| Journal | Contemporary Mathematics 307, 265--274 (AMS Press, 2002) |
Abstract
Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.
{
"annotation_id": "8c6e0ca1-5a15-4b51-9684-91f533177293",
"date_created": "2026-03-02T18:01:49.498000Z",
"date_modified": "2026-03-02T18:01:49.498000Z",
"file_hash": "86aed03bad9ba2cade87a43c2c6b492bbecd9abbac9d6138817f6774f0d6846e",
"private": false,
"record": {
"abstract": "Recently a method for adiabatic quantum computation has been proposed and\nthere has been considerable speculation about its efficiency for NP-complete\nproblems. Heuristic arguments in its favor are based on the unproven assumption\nof an eigenvalue gap.\n We show that, even without the assumption of an eigenvalue gap, other\nstandard arguments can be used to show that a large class of Hamiltonians\nproposed for adiabatic quantum computation have unique ground states.\n We also discuss some of the issues which arise in trying to analyze the\nbehavior of the eigenvalue gap. In particular, we propose several mechanisms\nfor modifying to final Hamiltonian to perform an adiabatic search with\nefficiency comparable to that for 3-SAT. We also propose the use of randomly\ndefined final Hamiltonians as a mechanism for analyzing the generic spectral\nbehavior of the interpolating Hamiltonians associated with problems which lack\nsufficent structure to be amenable to efficient classical algorithms.",
"arxiv_id": "quant-ph/0203127",
"authors": [
"Mary Beth Ruskai"
],
"categories": [
"quant-ph",
"math-ph",
"math.MP"
],
"journal_ref": "Contemporary Mathematics 307, 265--274 (AMS Press, 2002)",
"title": "Comments on Adiabatic Quantum Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0203127"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e655e25b-f7dd-4a68-ada1-b4f007c51fca",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}