Classical Optimization Using Quantum Annealing Machines
Classical optimization methods are a vital resource in virtually every large-scale, complex human endeavor, from timely delivery of our mail to the planning of deep-space exploration missions. Because of this ubiquity, any technology which can provide substantial improvements in optimization efficiency or effectiveness has the potential for enormous practical impact. For this reason, the recent demonstration (by the Canadian company D-Wave systems) of an entirely new type of classical optimization machine, based on so-called “quantum annealing” technology, has generated strong interest from the academic community, private industry, government, and even in the popular press. This is true in spite of the fact that unlike quantum computation, where a provable exponential speedup exists over any known or even anticipated classical methods for a few problems (most notably Shor’s algorithm for integer factoring), the computational power of quantum annealing is virtually unknown theoretically. Although some reasonable physical arguments for its potential can be made, a realistic assessment of its performance for problems of any practical interest would likely require understanding complex many-body open-system quantum mechanics at size scales far beyond that accessible to any presently known theoretical methods or classical simulation technology.
Extensive investigations of the behavior and performance of the D-Wave quantum annealing machines have been carried out since their introduction in 2010, across a wide variety of problems (though only at the relatively small problem sizes up to ~1000 binary variables that the present day hardware can accommodate). Although there is still no clear indication from this research whether quantum annealing is likely to ever have an important practical impact, much has been learned about the limitations of the existing machines and their underlying technology. Since 2014, MIT-LL has been centrally involved in a large-scale research effort focused on the development of more advanced hardware, architectures, and algorithms for quantum annealing, with the goal of exploring a much wider parameter space than is possible with existing machines. In this presentation, after an introduction to both classical and quantum optimization methods, I will give an overview of the quantum annealing technology being developed at MIT-LL, and its potential to go far beyond current capabilities