Quantum adiabatic search with decoherence in the instantaneous energy eigenbasis (16 pages)

Nicolas J. Cerf, Jérémie Roland

M. Andrecut, Mazhar Ali

Johan Åberg, David Kult, Erik Sjöqvist

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 ${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\ensuremath{\rightarrow}1$ limit. We supplement the analytical results by numerical simulations of the global and local search.

Johan Åberg, David Kult, Erik Sjöqvist

The robustness of the local adiabatic quantum search to decoherence in the instantaneous eigenbasis of the search Hamiltonian is examined. We demonstrate that the asymptotic time complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the special case of pure decoherence where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search.

Edward Farhi

Tameem Albash, Daniel A. Lidar

Recent experiments with increasingly larger numbers of qubits have sparked renewed interest in adiabatic quantum computation, and in particular quantum annealing. A central question that is repeatedly asked is whether quantum features of the evolution can survive over the long time scales used for quantum annealing relative to standard measures of the decoherence time. We reconsider the role of decoherence in adiabatic quantum computation and quantum annealing using the adiabatic quantum master-equation formalism. We restrict ourselves to the weak-coupling and singular-coupling limits, which correspond to decoherence in the energy eigenbasis and in the computational basis, respectively. We demonstrate that decoherence in the instantaneous energy eigenbasis does not necessarily detrimentally affect adiabatic quantum computation, and in particular that a short single-qubit ${T}_{2}$ time need not imply adverse consequences for the success of the quantum adiabatic algorithm. We further demonstrate that boundary cancellation methods, designed to improve the fidelity of adiabatic quantum computing in the closed-system setting, remain beneficial in the open-system setting. To address the high computational cost of master-equation simulations, we also demonstrate that a quantum Monte Carlo algorithm that explicitly accounts for a thermal bosonic bath can be used to interpolate between classical and quantum annealing. Our study highlights and clarifies the significantly different role played by decoherence in the adiabatic and circuit models of quantum computing.