Robustness of the adiabatic quantum search

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.

Figure 1

Local search with $W\left(r\right)=H\left(r\right)$ and success probability 0.5. The curves show ${\log }_{2}T$ vs ${\log }_{2}N$, where $T$ is the run time needed to obtain the success probability 0.5, and where $N$ is the list length. Each curve shows the result for a given degree of decoherence $\omega$. Counted from below, the curves correspond to $\omega =0$, 0.1,…, 0.9, 0.95, 1, interpolating between the closed $(\omega =0)$ and wide-open $(\omega =1)$ case. As seen, all curves tend to the slope $\frac{1}{2}$, except the uppermost wide-open case, which tends to the slope 1.