  We analyze the performance of adiabatic quantum computation (AQC) under the
effect of decoherence. To this end, we introduce an inherently open-systems
approach, based on a recent generalization of the adiabatic approximation. In
contrast to closed systems, we show that a system may initially be in an
adiabatic regime, but then undergo a transition to a regime where adiabaticity
breaks down. As a consequence, the success of AQC depends sensitively on the
competition between various pertinent rates, giving rise to optimality
criteria.
