In this talk I will discuss connections between the physics of complex
systems such as spin glasses and attempts to solve optimization
problems by ”Adiabatic Quantum Computing” (AQC), a version of ”Quantum Annealing” (QA). An optimization problem is one in which one has to minimize (or maximize) an energy function in which
there is competition between different terms so no single configuration
of the variables minimizes each term in the energy. In statistical
physics this competition is called ”frustration”. It leads to a complex
energy ”landscape” with many valleys separated by barriers, so
simple algorithms easily get trapped in local minima which have a
higher energy than the global minimum. Many problems in science,
and engineering are formulated as optimization problems. In quantum
annealing one tries to avoid being trapped in a local minimum by
adding quantum fluctuations so the system can tunnel to regions of
lower energy. The strength of the quantum fluctuations is gradually
reduced to zero during the annealing schedule. This method applies
to problems with binary variables, known as qubits in the quantum
case. There is considerable interest in AQC at present, in large part
because a company, D-Wave, has produced an actual device, the latest
version of which has about one thousand qubits. In addition,
there has been considerable theoretical work mainly using computer
simulations to see if there is a ”quantum speedup” compared with
analogous classical algorithms in which thermal, rather than quantum,
fluctuations are used to escape from local minima. In the talk
I will discuss difficulties in obtaining a quantum speedup due to (i)
(quantum) phase transitions that the system can undergo during the
annealing schedule, and (ii) the sensitivity of the state of the system
to the precise values of the interactions, i.e. chaos. A related chaotic
effect is that the state of the system can change dramatically with
small changes in the temperature (temperature-chaos), for thermal
annealing, and the strength of the quantum fluctuations, for quantum
annealing.