Physical Review Letters · 2008 · 109 citations · 26 references
Natural SciencesPhysicsCondensed Matter PhysicsQuantum MechanicsStochastic ProcessesPhase TransitionsQuantum AnnealingQuantum DynamicsQuantum StatesStatistical MechanicsAnnealingFirst-order Phase TransitionsInstanton SolutionsInstanton TheoryQuantum Phase TransitionsSatisfiabilitySpin GlassesSpin Systems
We study first-order quantum phase transitions in mean-field spin glasses. We solve the quantum random energy model using elementary methods and show that at the transition the eigenstate suddenly projects onto the unperturbed ground state and that the gap between the lowest states is exponentially small in the system size. We argue that this is a generic feature of all "random first-order" models, which includes benchmarks such as random satisfiability. We introduce a two-time instanton to calculate this gap in general, and discuss the consequences for quantum annealing.
26
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
<i>Spin Glass Theory and Beyond</i>
Marc Mézard, Giorgio Parisi, M. A. Virasoro et al. · Physics Today · 1988 · 2.8K citations
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et al. · Science · 2001 · 2.1K citations · Full text
Computing, Computer Science, Physics +15