3 ms·

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

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).)

rsln-s 7y ago
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 7y ago
  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 7y ago
    My understanding is that it is exactly the case D-wave probability distributions can be sampled classically.
bjornsing 7y ago
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/smallint_expcomp_draft_02_1.pdf https://hal.inria.fr/file/index/docid/451604/filename/smalli...
- dcposch 7y ago
  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.
- itcrowd 7y ago
  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 7y ago
    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?
    - j1vms 7y ago
      > 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 7y ago
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 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 https://arxiv.org/abs/1411.5693.
- bjornsing 7y ago
  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?
  - sanxiyn 7y ago
    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 7y ago
      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.
  - jessriedel 7y ago
    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.
    - deleted 7y ago

rsln-s 7y ago

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 7y ago
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 7y ago
  My understanding is that it is exactly the case D-wave probability distributions can be sampled classically.

bjornsing 7y ago

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/smallint_expcomp_draft_02_1.pdf https://hal.inria.fr/file/index/docid/451604/filename/smalli...

dcposch 7y ago
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.
itcrowd 7y ago
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 7y ago
  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?
  - j1vms 7y ago
    > 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 7y ago

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 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 https://arxiv.org/abs/1411.5693.

bjornsing 7y ago
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?
- sanxiyn 7y ago
  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 7y ago
    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.
- jessriedel 7y ago
  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.
  - deleted 7y ago