dorsal/arxiv
View SchemaQuantum Adiabatic Algorithm and Large Spin Tunnelling
| Authors | A. Boulatov, V. N. Smelyanskiy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0309150 |
| URL | https://arxiv.org/abs/quant-ph/0309150 |
| DOI | 10.1103/PhysRevA.68.062321 |
Abstract
We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in [E. Farhi, et al., arXiv:quant-ph/0208135]. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H(\tau) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H(\tau) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin-n/2 and provide a complete characterization of such paths.
{
"annotation_id": "eaf7cf01-3a27-48d0-8e0c-ad1109dbffcd",
"date_created": "2026-03-02T18:02:03.141000Z",
"date_modified": "2026-03-02T18:02:03.141000Z",
"file_hash": "a215c4f73a227e99fc6af045ea8049084c2f75dbc69d945ba4767bb723f7ef64",
"private": false,
"record": {
"abstract": "We provide a theoretical study of the quantum adiabatic evolution algorithm\nwith different evolution paths proposed in [E. Farhi, et al.,\narXiv:quant-ph/0208135]. The algorithm is applied to a random binary\noptimization problem (a version of the 3-Satisfiability problem) where the\nn-bit cost function is symmetric with respect to the permutation of individual\nbits. The evolution paths are produced, using the generic control Hamiltonians\nH(\\tau) that preserve the bit symmetry of the underlying optimization problem.\nIn the case where the ground state of H(0) coincides with the totally-symmetric\nstate of an n-qubit system the algorithm dynamics is completely described in\nterms of the motion of a spin-n/2.\n We show that different control Hamiltonians can be parameterized by a set of\nindependent parameters that are expansion coefficients of H(\\tau) in a certain\nuniversal set of operators. Only one of these operators can be responsible for\navoiding the tunnelling in the spin-n/2 system during the quantum adiabatic\nalgorithm. We show that it is possible to select a coefficient for this\noperator that guarantees a polynomial complexity of the algorithm for all\nproblem instances. We show that a successful evolution path of the algorithm\nalways corresponds to the trajectory of a classical spin-n/2 and provide a\ncomplete characterization of such paths.",
"arxiv_id": "quant-ph/0309150",
"authors": [
"A. Boulatov",
"V. N. Smelyanskiy"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.68.062321",
"title": "Quantum Adiabatic Algorithm and Large Spin Tunnelling",
"url": "https://arxiv.org/abs/quant-ph/0309150"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "15a1224f-ea4f-4622-99b6-45d6072afdd2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}