Adiabatic Quantum Search in Open Systems

Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.

Figure 1

Qualitative dynamics of the adiabatic quantum search algorithm in an open system. The evolution of the system is coherent below the critical temperature $T^{*}$ (indicated by the solid curves) and a quantum speedup is available in this regime. The three curves correspond to different sizes $N$ of the search space. The parameter $\eta$ characterizes the noise spectral density at low frequency $\propto {\omega }^{\eta }$, with $\eta =1$ corresponding to an Ohmic bath. The dependence of $T^{*}$ on $\eta$ changes qualitatively at ${\eta }_c$ due to scattering processes contributing significantly when $\eta >{\eta }_c$. The inset shows the spectrum of the AQS Hamiltonian for $N=256$.

Figure 2

Dependence of the critical temperature $T^{*}$ on the search space size $N$. The critical temperature follows a power law $T^{*}=O(N^{\delta })$. Above $T^{*}$, the system evolves incoherently, while below, quantum coherence is retained. The qualitative change at ${\eta }_c$ is due to competition between single- and two-boson processes. For $\eta <1$, the dynamics are incoherent even at zero temperature in the limit of large $N$.