Is there proof that the D-wave (one) is a quantum computer and is effective?

Question

I'm admittedly a novice in this field, but I have read that, while the D-wave (one) is an interesting device, there is some skepticism regarding it being 1) useful and 2) actually a 'quantum computer'.

For example, Scott Aaronson has expressed multiple times that he is skeptical about whether the 'quantum' parts in the D-wave are actually useful:

It remains true, as I’ve reiterated here for years, that we have no direct evidence that quantum coherence is playing a role in the observed speedup, or indeed that entanglement between qubits is ever present in the system.

Exerpt from this blog.

Additionally, the relevant Wikipedia section on skepticism against the D-wave is a mess.

So, I ask:

1. I know that D-wave claims to use some sort of quantum annealing. Is there (dis)proof of the D-wave actually using quantum annealing (with effect) in its computations?

2. Has it been conclusively shown that the D-wave is (in)effective? If not, is there a clear overview of the work to attempt this?

Answer 1

There is still a search for problems where the D-Wave shows improvement over classical algorithms. One might recall media splashes where the D-Wave solved some instances $10^8$ times faster than a classical algorithms but forgot to mention that the problem can be solved in polynomial time using minimum weight perfect matching.

Denchev showing $10^8$ speedup https://arxiv.org/abs/1512.02206

Mandra using MWPM https://arxiv.org/abs/1703.00622

There is some evidence that there are indeed some quantum effects used by the D-Wave. Notably a study by Katzgraber et al. that compares the D-Wave with simulated annealing and the effects of reducing barrier thickness in the energy landscape (to make tunneling more probable). In Fig. 5 of the following paper the barrier thickness is reduced and the D-Wave shows improvement on the class of problems while Simulated Annealing shows no improvement.

https://arxiv.org/abs/1505.01545

Full disclosure: Katzgraber was my PhD advisor so I am most familiar with his work.

On the other hand, there have been a few papers on the topic of the D-Wave being a simple thermal annealer with no quantum effects, notably the papers by Smolin although they are a bit dated now.

https://arxiv.org/abs/1305.4904

https://arxiv.org/abs/1401.7087

More recently Albash et al. discussed the finite temperature as a reason for quantum annealers not functioning competitively.

https://arxiv.org/abs/1703.03871

Answer 2

• Is there proof that the D-wave (one) is a quantum computer and is effective?

D-Wave Video - Offers an explanation of: "How do we know ...": https://youtu.be/kq9VqR0ZGNc

One analogy you might make with the D-Wave One, an adiabatic ('analog') computer, is to the "south-pointing chariot" or the "Antikythera mechanism".

A lengthy explanation is offered in this Ars Technica (Wired) article: "Going digital may make analog quantum computer scaleable":

• "... They pretty much all fall into two categories. In most labs, researchers work on what could be called a digital quantum computer, which has the quantum equivalent of logic gates, and qubits are based on well-defined and well-understood quantum states. The other camp works on analog devices called adiabatic quantum computers. In these devices, qubits do not perform discrete operations, but continuously evolve from some easily understood initial state to a final state that provides the answer to some problem" (end quote), or quantum annealing.

• "Adiabatic quantum computers are inherently analog devices: each qubit is driven by how strongly it is coupled to every other qubit. Computation is performed by continuously adjusting these couplings between some starting and final value. Tiny errors in the coupling—due to environmental effects, for instance—tend to build up and throw off the final value.".

• "Digital quantum computing, which uses logic operations and quantum gates, offers the possibility of error correction. By encoding information in multiple qubits, you can detect and correct errors. Unfortunately, digital qubits are delicate things compared to those used in adiabatic quantum computers, and the ability to ...". (Go read the article if you don't want a condensed version).

• "What about a hybrid approach? That's the question asked by a international group of researchers in a recently-published paper in Nature. They’ve tested a system where the computation is performed by qubits that were operating as an adiabatic quantum computer, but with connections between the adiabatic qubits is controlled via a digital network of qubits. This allows the benefits of scale and flexibility that you get from adiabatic quantum computing, while also making the connections less susceptible to noise.".

So, yes. It is a computer and uses quantum methods.

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to do calculations1 and is closely related to, and may be regarded as a subclass of, quantum annealing.

Another analogy, probably as unfair as the last, is that AQC is a one-trick-ponyism. It's limited in what it can do, but it does it quickly and well.

• So, I ask:

  I know that D-wave claims to use some sort of quantum annealing. Is there (dis)proof of the D-wave actually using quantum annealing (with effect) in its computations?

  Has it been conclusively shown that the D-wave is (in)effective? If not, is there a clear overview of the work to attempt this?

There is proof that it is effective when used correctly for doing what it was designed to do:

"Blockchain platform with proof-of-work based on analog Hamiltonian optimisers" by Kirill P. Kalinin, Natalia G. Berloff, 27 Feb 2018.

University of Cambridge, "Polariton Graph Simulator (Optimizer): an analog Hamiltonian simulaton", Natalia Berloff.

"Performance of quantum annealing hardware" by Damian S. Steiger; Bettina Heim, 22 October 2015.

There exists important backers and some skeptics of D-Wave.

---

Address concerns expressed in comments - Update: 19 March 2018:

Here is an article from Nature.com entitled: "Triode for Magnetic Flux Quanta" which explain the use of Abrikosov vortices to hold quantized information bits, further clarified (or not) in the article: "Single Abrikosov vortices as quantized information bits".

An oversimplified analogy is that the quantum qubits are (not at all) like magnetic core memory, the difference is:

• A single magnetic core holds a binary digit, a bit, (like a fraction of a letter in a book, so you would use 8 bits to represent more than just a letter but all of the ASCII Alphabet, letters digits and control codes). A bit would have to be in one state or the other.

• A qubit, by utilizing quantum mechanics, allows the qubit to be in a superposition of both states at the same time, a property that is fundamental to quantum computing. A qbit can be in one state, the other, or both; think of it as trinary on steroids, because qubits can perform two calculations simultaneously (and that's why they are both comparable and incomparable, a superposition of both states; a new way if thinking).

Look at this image of a magnetic memory and a quantum processor - quite different from an x86 processor:

A simple explanation of the relevance and degree of proof is offered in this video by D-Wave called: "D-Wave Lab Tour Part 3 (of 3) - The D-Wave Processor".

https://www.youtube.com/watch?v=AGByZoYUlU0