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.