When can Quantum Annealing win?

During the last two years, the Google Quantum AI team has made progress in understanding the physics governing quantum annealers. We recently applied these new insights to construct proof-of-principle optimization problems and programmed these into the D-Wave 2X quantum annealer that Google operates jointly with NASA. The problems were designed to demonstrate that quantum annealing can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes.

We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 10⁸ times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 10⁸.

Time to find the optimal solution with 99% probability for different problem sizes. We compare Simulated Annealing (SA), Quantum Monte Carlo (QMC) and D-Wave 2X. Shown are the 50, 75 and 85 percentiles over a set of 100 instances. We observed a speedup of many orders of magnitude for the D-Wave 2X quantum annealer for this optimization problem characterized by rugged energy landscapes. For such problems quantum tunneling is a useful computational resource to traverse tall and narrow energy barriers.

While these results are intriguing and very encouraging, there is more work ahead to turn quantum enhanced optimization into a practical technology. The design of next generation annealers must facilitate the embedding of problems of practical relevance. For instance, we would like to increase the density and control precision of the connections between the qubits as well as their coherence. Another enhancement we wish to engineer is to support the representation not only of quadratic optimization, but of higher order optimization as well. This necessitates that not only pairs of qubits can interact directly but also larger sets of qubits. Our quantum hardware group is working on these improvements which will make it easier for users to input hard optimization problems. For higher-order optimization problems, rugged energy landscapes will become typical. Problems with such landscapes stand to benefit from quantum optimization because quantum tunneling makes it easier to traverse tall and narrow energy barriers.

We should note that there are algorithms, such as techniques based on cluster finding, that can exploit the sparse qubit connectivity in the current generation of D-Wave processors and still solve our proof-of-principle problems faster than the current quantum hardware. But due to the denser connectivity of next generation annealers, we expect those methods will become ineffective. Also, in our experience we find that lean stochastic local search techniques such as simulated annealing are often the most competitive for hard problems with little structure to exploit. Therefore, we regard simulated annealing as a generic classical competition that quantum annealing needs to beat. We are optimistic that the significant runtime gains we have found will carry over to commercially relevant problems as they occur in tasks relevant to machine intelligence.

For details please refer to http://arxiv.org/abs/1512.02206.