dorsal/arxiv
View SchemaQuantum adiabatic optimization and combinatorial landscapes
| Authors | V. N. Smelyanskiy, S. Knysh, R. D. Morris |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0402199 |
| URL | https://arxiv.org/abs/quant-ph/0402199 |
| DOI | 10.1103/PhysRevE.70.036702 |
Abstract
In this paper we analyze the performance of the Quantum Adiabatic Evolution algorithm on a variant of Satisfiability problem for an ensemble of random graphs parametrized by the ratio of clauses to variables, $\gamma=M/N$. We introduce a set of macroscopic parameters (landscapes) and put forward an ansatz of universality for random bit flips. We then formulate the problem of finding the smallest eigenvalue and the excitation gap as a statistical mechanics problem. We use the so-called annealing approximation with a refinement that a finite set of macroscopic variables (versus only energy) is used, and are able to show the existence of a dynamic threshold $\gamma=\gamma_d$ starting with some value of K -- the number of variables in each clause. Beyond dynamic threshold, the algorithm should take exponentially long time to find a solution. We compare the results for extended and simplified sets of landscapes and provide numerical evidence in support of our universality ansatz. We have been able to map the ensemble of random graphs onto another ensemble with fluctuations significantly reduced. This enabled us to obtain tight upper bounds on satisfiability transition and to recompute the dynamical transition using the extended set of landscapes.
{
"annotation_id": "9135fce8-ec99-48ec-ab2d-4c48c6372a9f",
"date_created": "2026-03-02T18:02:06.937000Z",
"date_modified": "2026-03-02T18:02:06.937000Z",
"file_hash": "d3e361e03c4ae984b453431c20ee7da96c9ed13e1c0131ca526ffbebe0095f7a",
"private": false,
"record": {
"abstract": "In this paper we analyze the performance of the Quantum Adiabatic Evolution\nalgorithm on a variant of Satisfiability problem for an ensemble of random\ngraphs parametrized by the ratio of clauses to variables, $\\gamma=M/N$. We\nintroduce a set of macroscopic parameters (landscapes) and put forward an\nansatz of universality for random bit flips. We then formulate the problem of\nfinding the smallest eigenvalue and the excitation gap as a statistical\nmechanics problem. We use the so-called annealing approximation with a\nrefinement that a finite set of macroscopic variables (versus only energy) is\nused, and are able to show the existence of a dynamic threshold\n$\\gamma=\\gamma_d$ starting with some value of K -- the number of variables in\neach clause. Beyond dynamic threshold, the algorithm should take exponentially\nlong time to find a solution. We compare the results for extended and\nsimplified sets of landscapes and provide numerical evidence in support of our\nuniversality ansatz. We have been able to map the ensemble of random graphs\nonto another ensemble with fluctuations significantly reduced. This enabled us\nto obtain tight upper bounds on satisfiability transition and to recompute the\ndynamical transition using the extended set of landscapes.",
"arxiv_id": "quant-ph/0402199",
"authors": [
"V. N. Smelyanskiy",
"S. Knysh",
"R. D. Morris"
],
"categories": [
"quant-ph",
"cond-mat.stat-mech"
],
"doi": "10.1103/PhysRevE.70.036702",
"title": "Quantum adiabatic optimization and combinatorial landscapes",
"url": "https://arxiv.org/abs/quant-ph/0402199"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f0c09586-b6b4-486e-aa78-9e2a4a391aa4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}