dorsal/arxiv
View SchemaDynamics of quantum adiabatic evolution algorithm for Number Partitioning
| Authors | Vadim N. Smelyanskiy, Udo v. Toussaint, Dogan A. Timucin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0202155 |
| URL | https://arxiv.org/abs/quant-ph/0202155 |
Abstract
We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size $n$. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, $g_{\rm min}={\cal O}(n 2^{-n/2})$, corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
{
"annotation_id": "52d49b2c-2f0d-4b3c-a9fa-fa45760290fc",
"date_created": "2026-03-02T18:01:48.474000Z",
"date_modified": "2026-03-02T18:01:48.474000Z",
"file_hash": "da8a87024caecd5aad259b3e9ecb8bca95cb36a348e973ee199f5c172f459949",
"private": false,
"record": {
"abstract": "We have developed a general technique to study the dynamics of the quantum\nadiabatic evolution algorithm applied to random combinatorial optimization\nproblems in the asymptotic limit of large problem size $n$. We use as an\nexample the NP-complete Number Partitioning problem and map the algorithm\ndynamics to that of an auxilary quantum spin glass system with the slowly\nvarying Hamiltonian. We use a Green function method to obtain the adiabatic\neigenstates and the minimum excitation gap, $g_{\\rm min}={\\cal O}(n 2^{-n/2})$,\ncorresponding to the exponential complexity of the algorithm for Number\nPartitioning. The key element of the analysis is the conditional energy\ndistribution computed for the set of all spin configurations generated from a\ngiven (ancestor) configuration by simulteneous fipping of a fixed number of\nspins. For the problem in question this distribution is shown to depend on the\nancestor spin configuration only via a certain parameter related to the energy\nof the configuration. As the result, the algorithm dynamics can be described in\nterms of one-dimenssional quantum diffusion in the energy space. This effect\nprovides a general limitation on the power of a quantum adiabatic computation\nin random optimization problems. Analytical results are in agreement with the\nnumerical simulation of the algorithm.",
"arxiv_id": "quant-ph/0202155",
"authors": [
"Vadim N. Smelyanskiy",
"Udo v. Toussaint",
"Dogan A. Timucin"
],
"categories": [
"quant-ph"
],
"title": "Dynamics of quantum adiabatic evolution algorithm for Number Partitioning",
"url": "https://arxiv.org/abs/quant-ph/0202155"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c153e8d4-9afe-430d-bc34-b1294430bb4c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}