  Quantum annealing is a general strategy for solving difficult optimization
problems with the aid of quantum adiabatic evolution. Both analytical and
numerical evidence suggests that under idealized, closed system conditions,
quantum annealing can outperform classical thermalization-based algorithms such
as simulated annealing. Do engineered quantum annealing devices effectively
perform classical thermalization when coupled to a decohering thermal
environment? To address this we establish, using superconducting flux qubits
with programmable spin-spin couplings, an experimental signature which is
consistent with quantum annealing, and at the same time inconsistent with
classical thermalization, in spite of a decoherence timescale which is orders
of magnitude shorter than the adiabatic evolution time. This suggests that
programmable quantum devices, scalable with current superconducting technology,
implement quantum annealing with a surprising robustness against noise and
imperfections.
