Sommerfeld Theory Colloquium, 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.