dorsal/arxiv
View SchemaSimulation of Quantum Adiabatic Search in the Presence of Noise
| Authors | Frank Gaitan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0601116 |
| URL | https://arxiv.org/abs/quant-ph/0601116 |
| Journal | Int. J. Q. Info. vol. 4, 843-870 (2006) |
Abstract
Results are presented of a large-scale simulation of the quantum adiabatic search (QuAdS) algorithm in the presence of noise. The algorithm is applied to the NP-Complete problem Exact Cover 3 (EC3). The noise is assumed to Zeeman-couple to the qubits and its effects on the algorithm's performance is studied for various levels of noise power, and for 4 different types of noise polarization. We examine the scaling relation between the number of bits N (EC3 problem size) and the algorithm's noise-averaged median run-time <T(N)>. Clear evidence is found of the algorithm's sensitivity to noise. Two fits to the simulation results were done: (1) power-law scaling <T(N)> = aN**b; and (2) exponential scaling <T(N)> = a[exp(bN) - 1]. Both types of scaling relations provided excellent fits. We demonstrate how noise leads to decoherence in QuAdS, estimate the amount of decoherence in our simulations, and derive an upper bound for the noise-averaged QuAdS success probability in the weak noise limit appropriate for our simulations.
{
"annotation_id": "c734dfaf-356e-413f-bbc1-cd3526fccc5f",
"date_created": "2026-03-02T18:02:24.206000Z",
"date_modified": "2026-03-02T18:02:24.206000Z",
"file_hash": "a157f9703b86d3747262638343d01a4a6fb2f93b241f8d023a6d710f854544e0",
"private": false,
"record": {
"abstract": "Results are presented of a large-scale simulation of the quantum adiabatic\nsearch (QuAdS) algorithm in the presence of noise. The algorithm is applied to\nthe NP-Complete problem Exact Cover 3 (EC3). The noise is assumed to\nZeeman-couple to the qubits and its effects on the algorithm\u0027s performance is\nstudied for various levels of noise power, and for 4 different types of noise\npolarization. We examine the scaling relation between the number of bits N (EC3\nproblem size) and the algorithm\u0027s noise-averaged median run-time \u003cT(N)\u003e. Clear\nevidence is found of the algorithm\u0027s sensitivity to noise. Two fits to the\nsimulation results were done: (1) power-law scaling \u003cT(N)\u003e = aN**b; and (2)\nexponential scaling \u003cT(N)\u003e = a[exp(bN) - 1]. Both types of scaling relations\nprovided excellent fits. We demonstrate how noise leads to decoherence in\nQuAdS, estimate the amount of decoherence in our simulations, and derive an\nupper bound for the noise-averaged QuAdS success probability in the weak noise\nlimit appropriate for our simulations.",
"arxiv_id": "quant-ph/0601116",
"authors": [
"Frank Gaitan"
],
"categories": [
"quant-ph"
],
"journal_ref": "Int. J. Q. Info. vol. 4, 843-870 (2006)",
"title": "Simulation of Quantum Adiabatic Search in the Presence of Noise",
"url": "https://arxiv.org/abs/quant-ph/0601116"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "18f34128-3dde-44fe-9554-3c22effd00c5",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}