Harnessing Quantum Dynamics for Optimization

D-Wave
3 min readApr 19, 2023

--

By Andrew King, Director of Performance Research, D-Wave

3D spin glasses have long been a canonical example of hard optimization problems. In fact, experiments on disordered alloys in the 1990s told us that if we could build a programmable annealing quantum computer, then quantum dynamics could offer a speedup over classical approaches for optimization problems. So, D-Wave built one, and today, our experimental demonstration of the predicted speedup was published in Nature. The collaboration between D-Wave and Boston University researchers, “Quantum critical dynamics in a 5,000-qubit programmable spin glass”, marks the largest programmable quantum simulation achieved to date. The experiments were carried out on the same D-Wave AdvantageTM processor available to our LeapTM cloud customers, and clearly shows the power of quantum annealing in solving hard optimization problems.

The 5760-qubit Advantage processor (left) was programmed to realize 3D spin glass optimization problems (right, artist’s interpretation)

Quantum annealing on easy problems and hard problems

Last year, we published research showing that D-Wave annealing quantum computers closely matched theoretical predictions on a simple toy model: a 2,000-qubit 1D chain. The 1D model is exactly solvable with classical computers, and as it turns out, the primary characteristic power of quantum and classical optimization in this model are exactly the same. Now we’ve taken the same approach with 3D spin glasses, which are intractable (NP-hard) to solve, and where quantum dynamics are expected to be more powerful than classical dynamics. The one tricky part is that as far as anybody knows, classical computers cannot simulate quantum dynamics on this problem. If it was going to be at all possible, it would need to be on Advantage.

To tackle this issue, we made things easy for a classical computer. For 16-variable problems, classical computers can handle things easily, and we could confirm that the Advantage processor produced the right solutions according to the time-dependent Schrödinger equation. So far so good. For larger problems — — up to 5376 variables — — we had at least some information to go on. By using predictive scaling laws of the quantum Kibble-Zurek mechanism, we could confirm that average statistics produced by Advantage followed the correct scaling.

More importantly, this same Kibble-Zurek approach predicts that quantum annealing should reduce energy faster than simulated annealing. In other words, after quantum annealing and simulated annealing spend some time with an optimization problem, which one has a better answer? And if you double the time spent, which answer improves more? In both cases, the answer is quantum annealing.

Quantum annealing (QA) shows better scaling in both theory and experiment, versus simulated annealing (SA) and simulated quantum annealing (SQA). This means that QA’s advantage increases to roughly 80,000 times faster than simulated annealing on a CPU. As coherence improves, so will this advantage.

Eyeing a coherent future

D-Wave is now developing both gate-based and annealing-based quantum computers. While each platform has its strengths, we see quantum annealing as the way forward for optimization. Our new research gives us a better look than ever at the value of coherence in quantum annealing, and this is great news, because hand-in-hand development of the gate and annealing programs will bring us to longer coherence times and better qubit parameters, allowing our advantage over classical optimization to grow. This research marks the first of many explorations into coherent quantum dynamics. We’re also exploring coherent annealing in exotic quantum condensed matter systems and working to determine how long classical computers can keep up with us. As we continue development on the Advantage2™ processor, we expect it to mark a quantum leap in exploring coherent dynamics of both exotic phases of matter and industry-relevant optimization problems.

--

--