dorsal/arxiv
View SchemaTotal suppression of a large spin tunneling barrier in quantum adiabatic computation
| Authors | Alex Bulatov, Vadim Smelyanskiy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0208189 |
| URL | https://arxiv.org/abs/quant-ph/0208189 |
Abstract
We apply a quantum adiabatic evolution algorithm to a combinatorial optimization problem where the cost function depends entirely on the of the number of unit bits in a n-bit string (Hamming weight). The solution of the optimization problem is encoded as a ground state of the problem Hamiltonian H_p for the z-projection of a total spin-n/2. We show that tunneling barriers for the total spin can be completely suppressed during the algorithm if the initial Hamiltonian has its ground state extended in the space of the z-projections of the spin. This suppression takes place even if the cost function has deep and well separated local minima. We provide an intuitive picture for this effect and show that it guarantees the polynomial complexity of the algorithm in a very broad class of cost functions. We suggest a simple example of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hat S_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1. We use WKB analysis for the large spin to estimate the minimum energy gap between the two lowest adiabatic eigenvalues of H(tau).
{
"annotation_id": "72e5418e-0948-4acc-97cd-510af517aed7",
"date_created": "2026-03-02T18:01:53.045000Z",
"date_modified": "2026-03-02T18:01:53.045000Z",
"file_hash": "7943cfcd307a33da80d4ea787261e4632c94c20e1d7378071522d8c898caa6c3",
"private": false,
"record": {
"abstract": "We apply a quantum adiabatic evolution algorithm to a combinatorial\noptimization problem where the cost function depends entirely on the of the\nnumber of unit bits in a n-bit string (Hamming weight). The solution of the\noptimization problem is encoded as a ground state of the problem Hamiltonian\nH_p for the z-projection of a total spin-n/2. We show that tunneling barriers\nfor the total spin can be completely suppressed during the algorithm if the\ninitial Hamiltonian has its ground state extended in the space of the\nz-projections of the spin. This suppression takes place even if the cost\nfunction has deep and well separated local minima. We provide an intuitive\npicture for this effect and show that it guarantees the polynomial complexity\nof the algorithm in a very broad class of cost functions. We suggest a simple\nexample of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hat\nS_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1.\nWe use WKB analysis for the large spin to estimate the minimum energy gap\nbetween the two lowest adiabatic eigenvalues of H(tau).",
"arxiv_id": "quant-ph/0208189",
"authors": [
"Alex Bulatov",
"Vadim Smelyanskiy"
],
"categories": [
"quant-ph"
],
"title": "Total suppression of a large spin tunneling barrier in quantum adiabatic computation",
"url": "https://arxiv.org/abs/quant-ph/0208189"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "97a3ef91-edbf-4c1c-a53d-7aa41ae9ff3f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}