19
$\begingroup$

I would like to know your thoughts on whether or not D-Wave has shown a a smoking-gun example of quantum advantage this year. I am genuinely not quite sure what to think, but I believe the answer to this question is important in understanding the current state-of-the-art of quantum annealing technologies and their promise for solving real-world problems more efficiently than classical computers. For some context, here is a summary of the situation from my understanding:

In April 2023, the D-Wave team put out a nature paper (arXiv version here) discussing how they used a D-Wave system to compute the ground state of a 3-D spin-glass Hamiltonian.

In particular (from my understanding) they use quantum annealing to solve many instances of small 3D spin glass models (16 particles) and a large one (128 particles). They benchmark their computation by by 1) using already established but very slow methods to solve the problem exactly and then 2) using several approximation methods (including quantum annealing) to see how much time it takes them to get a good enough approximate solution. The results are a bit difficult to interpret but it seems like quantum annealing gets them to the same “good enough” solution 10-20x faster than classical methods.

They also have more theoretical arguments for speedups. They plot the time it takes to perform (simulated and quantum) annealing for different levels of approximations. They then use fits and other theories to compute metrics like the Binder cumulant and KZ exponent and show that the time to solution scales as t^(-k) where k is bigger (0.7-1) for quantum annealing than for the other techniques (0.25-0.5). But to be honest, the details and methodologies of these arguments are outside my field of expertise.

enter image description here

This seems to imply a quantum advantage, at least for one of the few reasonable definitions of quantum advantage. In the online version of the talk given by the first author Andrew King, they acknowledge a comment by an audience member that it is a first example of quantum advantage in some precise specifics of the context (minute 20:21).

I would love to know people's thoughts on this, especially if there is additional information, context or subtleties to this study that I am missing out on. Thank you!

$\endgroup$

2 Answers 2

23
$\begingroup$

A clear case of quantum advantage

Google's quantum group demonstrated quantum advantage with a much earlier version of D-Wave hardware in the following figure from a 2016 paper, in which the D-Wave hardware found the ground state of Ising (spin glass) Hamiltonians involving up to 945 spins/qubits, about 7 orders of magnitude faster than the best they were capable of doing with classical computers (SA = simulated annealing, QMC = quantum Monte Carlo):

enter image description here

Hartmut Neven, the leader of Google's quantum group and the last author on the paper, said at the APS March Meeting in 2016 in front of a room that was so packed that people had to stand at the back due to a lack of enough seats, that Google spent about 1 million dollars on producing the green curve on classical supercomputers (notice that they gave up on completing the dotted line and dashed line for QMC).

If with quantum annealing you can solve a problem 10,000,000 times faster than you can with $1 million worth of classical supercomputer time, then the quantum annealer does have some type of advantage.

The April 2023 paper

What have they done differently here compared to the aforementioned paper from 7 years ago? In both cases, they found the ground state of an Ising problem, although in the April 2023 case they didn't compare the speed to a classical computer, so they didn't demonstrate any quantum advantage. The precise number of qubits used was shockingly difficult for me to find, but based on pg 33 out of 45 it seems that they used 5374 qubits, so I do believe that their hardware found the ground states faster than a classical computer could have (just see the above figure and imagine what happens if it goes up to 5000 qubits and when the D-Wave hardware has likely improved significantly over the last 7 years for this specific task compared to classical hardware).

However, a 3D spin glass is just a spin glass (for which the same advantages were shown in the above 2016 paper). Perhaps for the 3D spin glass you are choosing to couples specific qubits together, in order to mimic a 3D lattice, but this is still just a special case of what could be done many years ago with the same hardware.

The problem with this type of quantum advantage

The problem with this the recent series of papers by D-Wave in which they over and over again simulate spin glasses and publish the results in Nature and Science journals (see here and here and here and here, in addition to the April 2023 one that you mentioned, and others that a seemingly endless number of papers that were not published in Nature journals, such as this and this for example),is that: they are not solving any real-world problem that our population wants solved.

Even the last sentence of the April 2023 paper is saying that solving "relevant" problems is hopefully the "next step" (but this has been the case since at least the aforementioned 2016 paper):

"Extending this characterization of quantum dynamics to industry-relevant optimization problems, which generally do not allow for analysis via universal critical exponents or finite-size scaling, would mark an important next step in practical quantum computing."

Real-world problems

There are in fact real-world problems that can be solved by finding the ground state of an Ising model (or spin glass Hamiltonian). I'm not going to say that factoring numbers is a "real-world problem" unless you desperately need to decrypt someone's messages that were encoded using RSA, and although it was indeed useful to be able to decrypt the Enigma cryptosystem during World War II, when countries are at war now, they probably don't use RSA to encrypt their messages (even GitHub and GitLab asked us to change our SSH keys to use things like EdDSA a long time ago).

However, I truly believe that the integer factorization problem is one of the best ways to understand how the solution to a "real" computation of something that is not physics-related can be encoded into the ground state of a spin glass Hamiltonian (just see Table 1 and Eq. 12 of this). For an overview of how this works to solve other problems in operations research, see this.

The evils of quantum annealing

Unfortunately, when the solution to a real-world is encoded into the ground state of an Ising Hamiltonian, the bits (0s and 1s) of the real-world problem are encoded by spins, and naturally, certain spins will have to interact with certain other spins in order to solve the real-world problem. The D-Wave machine only allows 2-spin interactions (quadratic Hamiltonians, in which each term may contain at most 2 spin operators instead of 3, 4 or more), so quadratization is needed, which seems to be a deal-breaker due to the huge number of extra qubits needed (for example, factoring an "interesting" number like RSA-230 can be done by finding the ground state of a 5893-spin Ising problem if each term can involve up to 4 spin operators, but if we only allow quadratic terms then we would need 148,776 qubits). The need for quadratization is one evil force that prevents us from solving real-world problems on quantum annealers.

When we are lucky enough that after the solution of our real-world problem is encoded in the ground state of an Ising Hamiltonian, we magically end up with a quadratic Ising Hamiltonian that doesn't need auxiliary qubits for quadratization, we are limited by the connectivity of the spins in our Ising problem. D-Wave hardware is limited in the connectivity between its quits. The Chimera architecture allowed each spin/qubit to interact with only 6 other spins/qubits, and the much newer Pegaus architecture allows each spin/qubit to interact with only 15 other spins/qubits. Since 2021 D-Wave has been saying that they have a new architecture called "Zephyr" in which each qubit can interact with up to 20 qubits, but details remain nowhere to be seen, and disappointingly, the April 2023 paper that you mentioned still used the Pegasus architecture from much earlier. Just to put this into context, in the integer factorization problem, even after quadratization, the Ising problem in the above paper was such that one of the qubits needed to be coupled to 5000 qubits. This can't happen on hardware in which each qubit can only couple to 20 other qubits (and in my experience minor-embedding techniques don't really help in real-world problems). The need for embedding the real-world problem to match precisely the connectivity between the qubits in an annealing hardware, is another evil force preventing us from solving real-world problems on them.

The third evil force that I'll mention (we can list more if we want, for example not allowing a universal set of interactions between the spins, which has been partially addressed here but not for more than maybe two qubits), is the strength of the couplings between the spins. D-Wave hardware allows the coefficients of each term in the Ising Hamiltonian to be maybe between -2^5 and +2^5, which would mean that you can't find the ground state of a Hamiltonian like:

$$H = 33Z_1Z_2 - Z_2Z_3 - 33Z_1Z_3,\tag{1}$$

without introducing more auxiliary qubits or making approximations. The limitation on the strengths of the couplings between spins is the third evil force that I'll mention here, that is preventing us from solving real-world problems on quantum annealers.

Conclusion

A quantum annealer can beat a classical computer in speed at finding the ground state of an Ising problem (whether 3D or whatever), and this was known well before April 2023 (see the above 2016 paper). However, for the annealer to work the Ising problem can only involve certain spin-spin interactions (in the Chimera annealers, spin-1 can couple with spin-2, spin-3, spin-4, spin-5, spin-6 and spin-7, but not with spin-8, spin-9, spin-10, etc.) and the range of spin-spin coupling coefficients is very limited. Real-world problems can be solved by solving Ising problems, but it is extremely unlikely for any real-world problem to satisfy these constraints within the number of qubits available in today's devices. Studying 3D spin glasses, is not a "real-world" problem that any funding agency or tax-payer wants us to solve, so quantum annealers remain as a specialized resource in a very small number of HPC centers, where they can be used by academics to play.

$\endgroup$
4
  • 7
    $\begingroup$ What a thorough answer. $\endgroup$ Sep 1, 2023 at 23:26
  • $\begingroup$ Thank you @user1271772 for the thorough and understandable answer. A follow up question that came to mind is, does the D-Wave show any advantage for use-cases that academics, e.g. condensed matter physicists, would care about? Or do the issues you mentioned (e.g. quadritization) still indicate that there's more work to be done before the D-Wave can be more useful than classical machines for studying complex and interesting enough Hamiltonians currently looked at in academic fields as well? $\endgroup$ Sep 3, 2023 at 14:24
  • 1
    $\begingroup$ I generally encourage users to write each question in a separate post. $\endgroup$ Sep 3, 2023 at 16:08
  • $\begingroup$ Thanks! quantumcomputing.stackexchange.com/questions/34025/… $\endgroup$ Sep 5, 2023 at 6:49
4
$\begingroup$

The answer that @user1271772 gave is quite comprehensive - however I think that there are at least a few additional important papers which give arguments on the topic of the current capabilities of D-Wave quantum annealing devices.

  1. Scaling advantage in quantum simulation of geometrically frustrated magnets
  2. On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization
  3. Demonstration of a scaling advantage for a quantum annealer over simulated annealing
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.