dorsal/arxiv
View SchemaThe quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
| Authors | Johan Åberg, David Kult, Erik Sjöqvist |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0507010 |
| URL | https://arxiv.org/abs/quant-ph/0507010 |
| DOI | 10.1103/PhysRevA.72.042317 |
| Journal | Phys. Rev. A 72, 042317 (2005) |
Abstract
In Phys. Rev. A {\bf 71}, 060312(R) (2005) the robustness of the local adiabatic quantum search to decoherence in the instantaneous eigenbasis of the search Hamiltonian was examined. We expand this analysis to include the case of the global adiabatic quantum search. As in the case of the local search the asymptotic time complexity for the global search is the same as for the ideal closed case, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, we find that the time complexity of the global quantum adiabatic search scales like $N^{3/2}$, where $N$ is the list length. We moreover extend the analysis to include success probabilities $p<1$ and prove bounds on the run time with the same scaling as in the conditions for the $p\to 1$ limit. We supplement the analytical results by numerical simulations of the global and local search.
{
"annotation_id": "01b09d6d-83d7-4ae1-8af4-e9481ef9eced",
"date_created": "2026-03-02T18:02:16.536000Z",
"date_modified": "2026-03-02T18:02:16.536000Z",
"file_hash": "d52bcde48d71159d91c42ca6744aca81544bebb2d4dad06f116f270f5a945023",
"private": false,
"record": {
"abstract": "In Phys. Rev. A {\\bf 71}, 060312(R) (2005) the robustness of the local\nadiabatic quantum search to decoherence in the instantaneous eigenbasis of the\nsearch Hamiltonian was examined. We expand this analysis to include the case of\nthe global adiabatic quantum search. As in the case of the local search the\nasymptotic time complexity for the global search is the same as for the ideal\nclosed case, as long as the Hamiltonian dynamics is present. In the case of\npure decoherence, where the environment monitors the search Hamiltonian, we\nfind that the time complexity of the global quantum adiabatic search scales\nlike $N^{3/2}$, where $N$ is the list length. We moreover extend the analysis\nto include success probabilities $p\u003c1$ and prove bounds on the run time with\nthe same scaling as in the conditions for the $p\\to 1$ limit. We supplement the\nanalytical results by numerical simulations of the global and local search.",
"arxiv_id": "quant-ph/0507010",
"authors": [
"Johan \u00c5berg",
"David Kult",
"Erik Sj\u00f6qvist"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.72.042317",
"journal_ref": "Phys. Rev. A 72, 042317 (2005)",
"title": "The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis",
"url": "https://arxiv.org/abs/quant-ph/0507010"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6297e643-afc2-4b56-9360-c445a85495df",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}