Quantum adiabatic search with decoherence in the instantaneous energy eigenbasis

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

Figure 1

(Color online) Global search with $W\left(s\right)=H\left(s\right)$. Each curve shows ${\log }_{2}T$ vs ${\log }_{2}N$, where $T$ is the run time needed to obtain a given success probability $p$ at $s=1$, and where $N$ is the list length. The dimensionless run time $T$ is the quotient between the physical run time and $T_0$ defined in Eq. (148). The dotted curves correspond to the wide-open case, defined by the degree of openness $\omega =1$. The dashed curves correspond to the semiopen case $\omega =0.9$, and the solid correspond to $\omega =0.5$. Within each group, each curve corresponds to a success probability, which counted from below is $p=0.4,0.5,0.6,0.7,0.8$. As seen, the asymptotic slope appears to be independent of the choice of success probability $p$. For the wide-open case the asymptotic slope seems to tend to $\nu =3∕2$, independent of $p$. For the semiopen cases the asymptotic slope appears to tend to $\nu =1$, independent of $p$.

Figure 2

(Color online) Local search with $W\left(s\right)=H\left(s\right)$. Each curve shows ${\log }_{2}T$ vs ${\log }_{2}N$, where $T$ is the run time needed to obtain a given success probability $p$ at $s=1$, and where $N$ is the list length. The dimensionless run time $T$ is the quotient between the physical run time and $T_0$ defined in Eq. (148). Similar to Fig. 1 the dotted curves correspond to the wide-open case, defined by the degree of openness $\omega =1$. The dashed curves correspond to the semiopen case $\omega =0.9$, and the solid curves correspond to $\omega =0.5$. Within each group each curve corresponds to a success probability $p=0.4,0.5,0.6,0.7,0.8$, counted from below. Similarly to the global search, the asymptotic slope appears to be independent of the choice of success probability $p$. For the wide-open case the asymptotic slope seems to tend to $\nu =1$, independent of $p$. For the semiopen cases the asymptotic slope appears to tend to the $\nu =1∕2$, independent of $p$.

Figure 3

(Color online) Global search with $W\left(s\right)=H\left(s\right)$ and success probability $p=1∕2$. The curves show ${\log }_{2}T$ vs ${\log }_{2}N$, where $T$ is the run time needed to obtain the success probability $p=1∕2$ at $s=1$, and where $N$ is the list length. The dimensionless run time $T$ is the quotient between the physical run time and $T_0$ defined in Eq. (148). Each line shows the result for a given value of the degree of openness $\omega$. Counted from below, the lines correspond to $\omega =0,0.1,\dots ,0.9,1$. Hence, the uppermost line corresponds to the wide-open case $\omega =1$ and the lowermost line corresponds to the closed case $\omega =0$. All the lines seem to tend to the slope $\nu =1$, except the uppermost which seems to tend to $\nu =3∕2$.

Figure 4

(Color online) Local search with $W\left(r\right)=H\left(r\right)$ and success probability $p=1∕2$. The curves show ${\log }_{2}T$ vs ${\log }_{2}N$ plots, where $T$ is the run time needed to obtain the success probability $p=1∕2$ at $s=1$, and where $N$ is the list length. The dimensionless run time $T$ is the quotient between the physical run time and $T_0$ defined in Eq. (148). Each line shows the result for a given value of the degree of openness $\omega$. Counted from below, the lines correspond to $\omega =0,0.1,\dots ,0.9,1$. All the lines seem to tend to the slope $\nu =1∕2$, except the uppermost which appears to tend to $\nu =1$.