Can a quantum computer solve optimization problems more Efficiently than a classical computer? - a podcast by Michael Haack

In this talk I will discuss connections between the physics of complex
systems such as spin glasses and attempts to solve optimizationproblems 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 configurationof the variables minimizes each term in the energy. In statistical
physics this competition is called ”frustration”. It leads to a complexenergy ”landscape” with many valleys separated by barriers, so
simple algorithms easily get trapped in local minima which have ahigher energy than the global minimum. Many problems in science,
and engineering are formulated as optimization problems. In quantumannealing one tries to avoid being trapped in a local minimum by
adding quantum fluctuations so the system can tunnel to regions oflower energy. The strength of the quantum fluctuations is gradually
reduced to zero during the annealing schedule. This method appliesto problems with binary variables, known as qubits in the quantum
case. There is considerable interest in AQC at present, in large partbecause 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 withanalogous classical algorithms in which thermal, rather than quantum,
fluctuations are used to escape from local minima. In the talkI will discuss difficulties in obtaining a quantum speedup due to (i)
(quantum) phase transitions that the system can undergo during theannealing schedule, and (ii) the sensitivity of the state of the system
to the precise values of the interactions, i.e. chaos. A related chaoticeffect is that the state of the system can change dramatically with
small changes in the temperature (temperature-chaos), for thermalannealing, and the strength of the quantum fluctuations, for quantum
annealing.

Further episodes of Sommerfeld Theory Colloquium (ASC)

Further podcasts by Michael Haack

Website of Michael Haack