What arguments point towards D-Wave devices being potentially useful?

Question

I'm looking for any evidence pointing towards D-Wave's approach to quantum computation being promising to achieve any sort of computational advantage with respect to classical devices.

Note that I'm not asking about quantum annealing in general. As also mentioned e.g. in this answer and (Aharonov et al. 2014), one can show the equivalence between adiabatic quantum computation and the gate model, which, although I'm not sure how much this proof applies to D-Wave-like devices, I suppose is a decent argument towards the advantages of quantum annealing in general. But D-Wave devices are generally, as far as I can tell, tailored to specific tasks, and far from universal, so these general arguments about equivalence with gate-based computing do not seem to apply.

I am also not asking about evidence that D-Wave devices are capable of providing right now any sort of computational advantages. There's already some posts on this topic on the site, e.g.

• Is there quantum advantage to be had with a D-Wave computer in 2020?
• Is there proof that the D-wave (one) is a quantum computer and is effective?
• Do real commercial quantum computers exist?

Obviously showing that right now D-Wave provides computational advantages would also answer this question, but here I'm setting the bar lower than that, as it is my understanding that there is no such clear (as in, undisputed within the community) evidence as of now. Rather, I'm asking for any reason to believe D-Wave's approach is going to be useful at any point in the future. In other words, that the general approach is viable, even though there might be a number of technical hurdles to overcome before reaching that point.

I am also not necessarily asking about theoretical proofs of quantum advantage for specific problems, nor necessarily for evidence of exponential advantages, or even for any sort of scaling advantage. As discussed e.g. in this post, there doesn't seem to be any such proof at the moment. Rather, I'm looking for any argument of the form "there is a chance that D-Wave devices are going to be useful at some point in the future because XXX". I leave "be useful" intentionally vague, but I'd only qualify it in that I'm looking for "usefulness" in the applicational sense. Any such device is arguably "useful" in that these are complex machines and even the sole act of building them and testing them furthers our scientific understanding of the topic, but that's not what I'm talking about here.

Finally, I would point out that arguments of the form "D-Wave's device X has been used to solve optimisation task Y and was found to be more efficient than classical algorithm Z" can be possible answers, but they are also a rather weak form of evidence, unless there is also good reason to believe there are no better classical algorithms to solve the same problem.

---

This is also related to Is there any real world problem where I can see quantum computing being better than classical computing?.

Answer 1

Great question. Let me first start with non-quantum stuff that turns out to be pretty important when talking about D-Wave's quantum annealers or any other solvers like VQE, QAOA etc.

QA is designed to solve Quadratic unconstrained binary optimization (QUBO) problems. Many interesting and important combinatorial problems are non-QUBO. In fact, Integer Programming is a huge research field with an extraordinary number of industrial applications. Integer programs can be linear, with integer variables and many linear constraints. And here we have it, the largest class of useful problems can't be directly solved on QA. However, if we desperately want to use QA for integer programming, then we must reformulate a problem as QUBO. However, in most cases, when we convert a problem into QUBO, the new problem becomes really hard. This hardness comes due to additional slack variables that must be present in a QUBO model to account for inequality constraints. It turns out, that in the new QUBO problem, every neighbouring solution (which is one-bit flip away) is infeasible. So, each feasible solution is separated by an ocean of infeasible solutions. Such an issue is called a rugged optimization landscape. Basically, we have to navigate through a rocky energy landscape with exponentially high peaks of energy. This is really hard for both QA and classical heuristics such as simulated annealing, tabu search etc.

The above discussion points out that even if we get a perfect QA, a problem it tries to solve may be really hard because it was converted to QUBO. At this point, it is best to keep the original formulation and use the usual simplex-like algorithm with a branch-and-bound heuristic. It will do much much better.

Ok, let's say we are not interested in the largest class of problems and want to solve native problems like MaxCut, Quadratic Assignment Problem, spin-glass systems etc. These problems are naturally QUBO, so the above discussion about a messed-up energy landscape and additional slack variables does not apply. But, we have a little issue again. We still need to embed a problem on a QPU. The embedding problem is NP-hard. So, before you start solving an optimization problem, you need to solve the embedding problem! If you are an experienced D-Wave user, then this is not an issue. Pros usually have a handly library of mappings which allows them to bypass the embedding stage to some extent.

So to conclude, given perfectly-working QA it is only reasonable to solve a very limited class of problems. If you want to extend the application of QA to a wider class of problems then prepare to incur an unreasonable tax on the performance and quantum resource requirements.

Now, why does QA has potential? QA is a heuristic. Hence, it is fair to compare it with other classical heuristics such as simulated annealing, tabu search, parallel-tempering, evolution algorithms etc. All these classical algorithms can be called local-search and hill-climbing heuristics. Hill-climbing is a mechanism to avoid getting trapped in local minima. All these classical algorithms deploy various schemes to hill-climb the energy landscape to find the minimum. Climbing hills is really hard because if the energy peak is very high and you want to traverse it, the chances you succeed with classical heuristics are pretty low. This is because an algorithm will have to accept too many uphill moves. And if it accepts too many uphill moves it may never converge. This is when QA can make a difference! QA can hill-climb and most importantly it can quantum tunnel through the high peaks of energy towards the global minimum. So, in theory, QA has a much more robust landscape exploration mechanism and can tunnel towards the global optimum due to the adiabatic theorem! This feature sets apart QA from all other classical heuristics.

You can simulate some sort of tunnelling classically by flipping multiple bits of a current solution, but there is no guarantee that the newly obtained solution is closer to the global minimum.

So, to conclude, the tunnelling and the adiabatic process are two main things that set QA apart from classical heuristics that blindly climb the landscape. There is no way to simulate the QA tunnelling classically because we don't know the direction in which the global minimum is. So, if D-Wave irons out their tech issues (whatever they are) the future looks promising for optimization of native QUBO problems.

And now here are my two cents: I think D-Wave felt a victim of its own marketing. There is a lot of underserved bad talk on the internet about their tech. They created high expectations, and various folks ran to benchmark QA and publish their findings with claims that it didn't work as expected. But this is the same as trying to benchmark IBM's or Google's QPUs. They work... but kinda don't work for anything useful. Does it mean they have no potential? No! Just as anything quantum, QA is a very early tech so the smartest thing to do is just to have the same expectations you have from other quantum companies, that is: "Yes, they got a quantum something-something. Yes, they claimed some quantum advantage over something-something... but let's check-in in a couple of years".