Theory of Quantum Annealing of an Ising Spin Glass

By G. Santoro, R. Martoňák, E. Tosatti, Roberto Car. Science, 2002

602 citations recorded by the source corpus.

Probing the lowest energy configuration of a complex system by quantum annealing was recently found to be more effective than its classical, thermal counterpart. By comparing classical and quantum Monte Carlo annealing protocols on the two-dimensional random Ising model (a prototype spin glass), we confirm the superiority of quantum annealing relative to classical annealing. We also propose a theory of quantum annealing based on a cascade of Landau-Zener tunneling events. For both classical and quantum annealing, the residual energy after annealing is inversely proportional to a power of the logarithm of the annealing time, but the quantum case has a larger power that makes it faster.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Condensed Matter Physics

View Paper: https://www.semanticscholar.org/paper/f19cee6e5ad555d4cc414aac3a09fa34bb8fabde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Condensed Matter Physics

Citations in the corpus

Adiabatic quantum computation is equivalent to standard quantum computation (2004, background): “Moreover, [11,29,32] showed that adiabatic computation can ‘tunnel’ through wide energy barriers and thus outperform simulated annealing, a classical counterpart of the adiabatic model.”
Ising formulations of many NP problems (2013, background): “2If one is only interested in approximate solutions (for example, finding a state whose energy per site is optimal, in the thermodynamic (N → ∞) limit, as opposed to finding the exact ground state), one expects T = O(N) [5, 10].”
Entanglement in a Quantum Annealing Processor (2014, background): “A wide variety of optimization problems naturally map onto this physical system [19–22].”
Phase space representation of quantum dynamics (2009, methodology): “This method is also closely related to quantum annealing algorithms (Das and Chakrabarti, 2005; Farhi et al., 2001; Kadowaki and Nishimori, 1998; Santoro et al., 2002).”
Decoherence in adiabatic quantum computation (2015, methodology): “In simulated quantum annealing [24, 74, 75] (SQA), Monte Carlo dynamics are used to sample from the instantaneous Gibbs state along the annealing evolution.”
Evidence for quantum annealing with more than one hundred qubits (2013, methodology): “[11], we also observe that the simulated quantum annealer here scales slightly worse than the simulated classical annealer.”
Quantum Optimization of Fully-Connected Spin Glasses (2014, background): “While the founding principles of the technique have been investigated numerically [3], analytically [4,5], and experimentally [6] in the past decade, the disordered, interacting, time-dependent, and open nature of the many-body problem makes it very hard to draw universal conclusions about the power”