dorsal/arxiv
View SchemaA Random Matrix Model of Adiabatic Quantum Computing
| Authors | David R. Mitchell, Christoph Adami, Waynn Lue, Colin P. Williams |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0409088 |
| URL | https://arxiv.org/abs/quant-ph/0409088 |
| DOI | 10.1103/PhysRevA.71.052324 |
| Journal | Phys. Rev. A 71 052324 (2005) |
Abstract
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of Random Matrix Theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances, i.e., those having a critical ratio of clauses to variables, the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to non-adiabatic Landau-Zener type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.
{
"annotation_id": "a1a46e38-7617-46b2-9d4a-bb6397641101",
"date_created": "2026-03-02T18:02:10.443000Z",
"date_modified": "2026-03-02T18:02:10.443000Z",
"file_hash": "a2016760143d2e46120e7edec4ed2efbea133d235b620eb1ddd630178afc5ff7",
"private": false,
"record": {
"abstract": "We present an analysis of the quantum adiabatic algorithm for solving hard\ninstances of 3-SAT (an NP-complete problem) in terms of Random Matrix Theory\n(RMT). We determine the global regularity of the spectral fluctuations of the\ninstantaneous Hamiltonians encountered during the interpolation between the\nstarting Hamiltonians and the ones whose ground states encode the solutions to\nthe computational problems of interest. At each interpolation point, we\nquantify the degree of regularity of the average spectral distribution via its\nBrody parameter, a measure that distinguishes regular (i.e., Poissonian) from\nchaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor\nspacings. We find that for hard problem instances, i.e., those having a\ncritical ratio of clauses to variables, the spectral fluctuations typically\nbecome irregular across a contiguous region of the interpolation parameter,\nwhile the spectrum is regular for easy instances. Within the hard region, RMT\nmay be applied to obtain a mathematical model of the probability of avoided\nlevel crossings and concomitant failure rate of the adiabatic algorithm due to\nnon-adiabatic Landau-Zener type transitions. Our model predicts that if the\ninterpolation is performed at a uniform rate, the average failure rate of the\nquantum adiabatic algorithm, when averaged over hard problem instances, scales\nexponentially with increasing problem size.",
"arxiv_id": "quant-ph/0409088",
"authors": [
"David R. Mitchell",
"Christoph Adami",
"Waynn Lue",
"Colin P. Williams"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.71.052324",
"journal_ref": "Phys. Rev. A 71 052324 (2005)",
"title": "A Random Matrix Model of Adiabatic Quantum Computing",
"url": "https://arxiv.org/abs/quant-ph/0409088"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0f9f4355-9bf5-4de5-90e9-a0909d1b916e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}