Quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
2005 (English)In: Physical Review A. Atomic, Molecular, and Optical Physics, ISSN 1050-2947, E-ISSN 1094-1622, Vol. 72, no 4, 042317- p.Article in journal (Refereed) Published
In Phys. Rev. A 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 N3∕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→1 limit. We supplement the analytical results by numerical simulations of the global and local search.
Place, publisher, year, edition, pages
2005. Vol. 72, no 4, 042317- p.
Quantum computation, adiabatic approximation, search algorithm, open quantum systems
Research subject Physics
IdentifiersURN: urn:nbn:se:uu:diva-93321DOI: 10.1103/PhysRevA.72.042317ISI: 000232931800051OAI: oai:DiVA.org:uu-93321DiVA: diva2:166765
Also in Virtual Journal of Nanoscale Science and Technology, October 31 issue 2005 and Virtual Journal of Quantum Information, November issue 2005. 2005-09-012005-09-012011-10-06