[bjornsing]

I have the greatest respect for Scott, but I do think he’s being a bit too enthusiastic here in comparison with the D-wave. At the very least I think he should have included this question in his list:

Q: Why can the D-wave not be used to illustrate “quantum supremacy” in a similar way?

(As I understand it the D-wave can sample from the solutions to ”ising model-like” problems, which I assume would be extremely difficult for a classical computer to do (but probably possible to verify).)

[sanxiyn]

In principle, there is no reason why D-wave also can't achieve quantum supremacy. It is just that D-wave hasn't, so far.

As for Ising model, D-wave didn't outperform classical algorithm after classical algorithm was tuned (it was a new problem, so existing classical algorithm wasn't the best possible), see https://arxiv.org/abs/1401.1084, also there are reasons to suspect why Ising model will not provide any quantum speedup, see https://arxiv.org/abs/1411.5693.

[bjornsing]

Well D-wave is evaluated on an optimization task. This Google thing isn’t even trying to solve a real problem. What says you can’t get some very hard to replicate random bits out of a D-wave?

[jessriedel]

If D-Wave could achieve quantum supremacy, they definitely would, and would heavily publicize it. They haven't, which gives us strong evidence that they can't right now.

[sanxiyn]

Do you retract the claim Ising model problems are "extremely difficult" for classical computers? I replied with practical and theoretical considerations why it is not so.

[bjornsing]

I made no claim at all, I just stated an assumption that motivated my question. But you also misrepresent my assumption. My assumption was that the D-wave could sample from the solutions to “ising model-like problems” much more efficiently than a classical computer. A quick glance at your references gave me the impression they where about finding a single ground state / global minima of the hamiltonian. That’s a very different problem.

[rsln-s]

Unfortunately, the same complexity considerations do not hold for Ising problems. While many NP-hard problems can be formulated in Ising form, it is often not hard to get a “pretty good” solutions to these problems. DWave and collaborators have spent a decade trying to come up with exactly the same thing as demonstrated here — namely, a problem specifically designed to demonstrate quantum advantage of any sort — and as of now did not succeed.

To answer your question specifically: DWave does not allow the same level of control over qubits.

[bjornsing]

I’m aware of D-wave’s struggles, but my impression was that they had failed at finding a “deterministic” problem where they could show quantum advantage. I’ve never heard a claim that whatever probability distribution the D-wave can sample from a classical computer can also sample from. I’d love to read about it if you have a reference!

[sanxiyn]

My understanding is that it is exactly the case D-wave probability distributions can be sampled classically.

[bjornsing]

Another reason I feel this is oversold: This quantum “computer” cannot run Shores factorization algorithm. But if it could it would only be able to factor integers up to 2^53. The time required to factor a 2^60 to 2^80 integer on a classical computer is measured in milliseconds [1]...

Quantum supremacy in any reasonable sense of the word supremacy is a long way off.

1. https://hal.inria.fr/file/index/docid/451604/filename/smalli...

[itcrowd]

You may not agree with the authors' or Aaronsons' definition of quantum supremacy, that's ok. I think his definition is very reasonable. Aaronson argues that this experiment will prove quantum computing supremacy in great length and defined it in the first entry of the FAQ as follows:

> [quantum computing supremacy] term refers to the use of a quantum computer to solve some well-defined set of problems that would take orders of magnitude longer to solve with any currently known algorithms running on existing classical computers

.. and continues to explain why this setup does exactly that.

[bjornsing]

Yea... I’m not suggesting of course that Scott is wrong about this being an illustration of “quantum supremacy”... (Did you think I was...?)

But comparing it to manned flight or the first nuclear reactor... In those two cases there was a clear path to something very useful. I’m my mind this experiment changes very little as to how probable it is that we will soon have useful quantum computers, or even that we will ever have them. I guess that’s another question for Scott’s list:

Q: If what we care about is computing solutions to difficult real world problems, in what way is this a meaningful milestone?

[itcrowd]

Well I don't want to answer for him but you could make the same point with the airplane:

The first flight was 2 people in a plane that lasted very short. I could have ridden my horse more quickly over that distance! How is this a meaningful milestone?!

Well.. it demonstrates something that cannot be done on a horse (classical computer) but that can be done with a plane (quantum computer).

Is the application useful today? Probably not. But that shouldn't discourage anyone.

[j1vms]

> But comparing it to manned flight or the first nuclear reactor (...) this experiment changes very little as to how probable it is that we will soon have useful quantum computers, or even that we will ever have them.

Not a lot of people directly own & operate their own airplane, let alone a nuclear reactor, and yet both have had a significant impact on modern life. As for this experiment & QC, only time will tell of course.

[sanxiyn]

I think you misinterpreted "we will ever have them" part. bjornsing is not talking about whether there will be personal quantum computers. It is about whether there will be useful quantum computers at all. That is still open, for example because of issues related to quantum error correction.

[sanxiyn]

> This experiment changes very little as to how probable it is that we will soon have useful quantum computers, or even that we will ever have them.

I completely agree with this statement. This is mainly about Extended Church-Turing Thesis.

[dcposch]

The claim here is that they're about to demonstrate QC on a specific hard sampling problem , where one small quantum computer will produce a result in minutes that takes a months on a big cluster of classical computers.

That is still clearly quantum supremacy, even if Shor's algorithm is not yet implementable.