Adiabatic Quantum Search in Open Systems

We explore the dynamics of an adiabatic quantum search algorithm in an open system in order to identify potential speed-up or slow-down due to the coupling to the environment. We show that even for a very general environment, Grover's scaling of the computation time with the size of the search space remains optimal. In the presence of a bosonic environment, we observe a dynamic phase transition from underdamped to overdamped evolution of the system as a function of the noise spectral density. The phase transition is further reflected by a change of the thermalization rate. For underdamped evolution, the thermalization rate obeys the optimal, quantum-enhanced scaling with the size of the search space, whereas the scaling is classical in the overdamped regime. We provide a physical interpretation of the phase transition in terms of a renormalized tunneling rate and hence show that quantum speed-up is only attainable in the underdamped phase.