60

The media are reporting the commercially sold 128-bit quantum computer from D-Wave

http://news.google.com/news?ned=us&hl=us&q=d-wave+quantum&cf=all&scoring=n

which of course sounds amazing. The gadget is described as something capable of doing quantum annealing

http://en.wikipedia.org/wiki/Quantum_annealing

which looks less convincing. I want to ask you what classes of problems the D-Wave computer can actually solve or perform. It can't run Shor's algorithm on 128 qubits, can it?

Luboš Motl
  • 179,018
  • 1
    "Here we use quantum annealing to find the ground state of an artificial Ising spin system comprising an array of eight superconducting flux quantum bits with programmable spin–spin couplings." -- from the abstract of their recent Nature paper (http://www.nature.com/nature/journal/v473/n7346/full/nature10012.html). It seems unlikely to me that their commercial product actually uses 16-fold more qubits. – Mark Betnel May 27 '11 at 19:13
  • 1
    this means this is the end of all existing public key cryptography as forecasted? – lurscher May 27 '11 at 19:32
  • 11
    D-Wave has an absolutely terrible PR department, which at one point even claimed quantum computers could solve NP-complete problems in polynomial time by evaluating all possibilities at the same time. This claim is plain wrong. For their recent claim, I suggest the blog of Scott Aaronson. He also has a Q&A out here: http://blogs.forbes.com/alexknapp/2011/05/24/q-and-a-with-prof-scott-aaronson-on-d-waves-quantum-computer/ – Lagerbaer May 27 '11 at 20:26
  • Oh, and it's definitely not a universal quantum computer, i.e. it won't run Shor's algorithm afaik – Lagerbaer May 27 '11 at 20:27
  • They did not promise to do Shor algorithm http://www.dwavesys.com/en/publications.html – Alex 'qubeat' May 27 '11 at 21:04
  • ok, thanks. I will not run to not take all my money in cash from the banks just yet – lurscher May 27 '11 at 21:11
  • 1
    Google d-wave site:scottaaronson.com – Pratik Deoghare May 28 '11 at 00:14
  • Thanks for your replies, Ladies and Gentlemen, although they're are tame as I expected! ;-) – Luboš Motl May 28 '11 at 04:18
  • 1
    There is not very boring stuff in list I mentioned, e.g.: Does adiabatic quantum optimization fail for NP-complete problems? N. G. Dickson et al. Phys. Rev. Lett. 106, Issue 5, 050502 http://arxiv.org/abs/1010.0669 – Alex 'qubeat' May 28 '11 at 12:50
  • @Lagerbaer: I think D-wave has a fantastic PR department, for exactly the same reason. They make a lot of incorrect claims and hype their system, which is exactly what a PR department is supposed to do. As a scientist, I find the whole thing highly disturbing. – emarti Jan 21 '13 at 02:42
  • @lurscher All existing public key cryptography forecasted? Not at all. There exists post-quantum cryptography, that is, classical algorithms resistant to an attack by a quantum computer (and classical computer). And this is a post-quantum public key crypto-stuff example. =) – Physicist137 Jul 23 '17 at 00:14

2 Answers2

40

The DWave machine stirred up quite an amount on controversy in the community when it was first announces. The machine basically attempts to solve an NP-complete optimization problem (MAX-2SAT) by encoding it as a ground state of a Hamiltonian, and tries to reach this ground state by moving adiabatically to it from the ground state of an efficiently coolable Hamiltonian.

In general, the adiabatic algorithm is not known to be able to find ground states efficiently as the proximity of low lying levels to the ground state means that the transition between Hamiltonians has to be performed slowly, and the speed at which this can occur is governed by the gap between the ground state and the lowest excited levels. It is commonly believed within the community, but not proved, that no quantum algorithm can efficiently solve NP-complete problems.

In general the ground state of a Hamiltonian can be used to encode a wider variety of problems than NP (know QMA-complete problems), and so decision to focus on NP optimization problems has led to restrictions which prevent the device from being used for general purpose quantum computing (even if noise was not an issue). Thus you can't run Shor's algorithm on the device. Further, you -can- factor any number that you could fit on a 128 qubit device by classical means. The general number field sieve puts 128 bits within reach of modern personal computers.

Noise is a real issue with DWave's device, and although there have been a number of technical papers from them playing down the issue and trying to demonstrate quantum effects, the coherence times for the individual qubits are much shorter than the time scale for the algorithm. Thus the common view within the community seems to be that this is basically an expensive classical special purpose computer.

There is an interesting subtlety as regards noise: If you add noise to the adiabatic algorithm, it degrades gracefully into one of the best classical algorithms for the same problem. Thus you can obtain the same result either way, and the only difference is in the assymptotics for large systems (which are obviously not observables). Thus even if they produce a valid answer for every problem you throw at such a device, this is not enough information to determine if you are actually performing quantum computation.

Let me add that the adiabatic model can encode universal quantum computation, however the limitations of DWave's implementation means that specific machine cannot.

Joe Fitzsimons
  • 8,425
  • If it can solve one NP complete problem then it should be able to solve any NP complete problem, including factoring. I highly doubt it can solve an NP complete problem though. – Jus12 Sep 12 '11 at 19:29
  • 6
    AFAIK Factoring is not NP complete – Lagerbaer Sep 12 '11 at 22:24
  • In fact, if factoring were a NP-complete problem, then quantum algorithms could efficiently solve them, and we wouldn't need bright people to argue about BQP vs. NP... because we could finally replace mathematicians with quantum computers. – wsc Sep 13 '11 at 01:15
  • 5
    @Lagerbaer: Factoring is not known to be NP-complete, but this can't be proven without first proving that P$\neq$NP. – Joe Fitzsimons Sep 13 '11 at 03:18
  • 4
    @Jus12: Solving an NP-complete problem would mean that it could solve any problem in NP (drop the -complete), and as factoring is in NP, you are correct that it could solve it. However, you will notice that nowhere in my answer do I say it could sole NP-complete problems in polynomial time, and DWave has backed away from making such claims. Thus, even if it works as advertised, there is no reason to believe it would be could at factoring. There is a generic polynomial speed-up from quantum mechanics, and that is what they are counting on, even for exponential time algorithms. – Joe Fitzsimons Sep 13 '11 at 03:23
  • 1
    @joe Fitzsimons: true. My bad. I meant NP. Though, the first part of the claim is not entirely wrong. NP complete is part of NP. – Jus12 Sep 13 '11 at 04:26
  • 1
    @Jus12: Yes, I know. I just thought I should point out that the statement needed is slightly stronger. – Joe Fitzsimons Sep 13 '11 at 04:30
  • I feel it's important to say this here: factoring is not known for certain to be outside of P. As http://en.wikipedia.org/wiki/Integer_factorization points out, the evidence for that claim is only "we've tried to do it efficiently but can't figure it out". – Emilio Pisanty Apr 30 '12 at 19:13
  • @episanty: That is true of every problem in PSPACE. It might be that P=PSPACE, but we're pretty sure it's not true. But again, the only real evidence is that we can't prove equality. – Joe Fitzsimons May 01 '12 at 18:51
  • It's not just the number field sieve that makes factoring 128 bits easy on classical computers; 128 bits is comparatively very small and lots of factoring algorithms work for that size number. – Peter Shor May 27 '13 at 18:26
  • @PeterShor: Indeed. I didn't mean to suggest that it was the only algorithm that works. It seems even trial division is possible with a few months and a few dozen GPUs on your hands. – Joe Fitzsimons May 31 '13 at 09:12
  • 1
    @JoeFitzsimons: I don't get "Factoring is not known to be NP-complete, but this can't be proven without first proving that P≠NP". NP-complete problems are known, you don't need to prove P≠NP for that. – Blaisorblade Oct 08 '13 at 20:36
  • @JoeFitzsimons: I wonder if "noise" you talk about is what usually (and probably here) causes decoherence. – Blaisorblade Oct 08 '13 at 20:49
  • @Blaisorblade: I meant that the converse can't be shown easily (i.e. that it is not NP-complete). Regarding noise, I use "noise" as a synonym of "decoherence". – Joe Fitzsimons Oct 09 '13 at 12:06
  • Thanks for this very insightful discussion. This is the best reference I have found so far that clarifies that D-Wave cannot solve NP hard problems. I tried to create a bit of an easy to read overview of what quantum computers can and what they cannot do, where I am citing this very helpful answer, here: https://medium.com/twodigits/3-reasons-quantum-computing-is-overrated-9d87d11aa248 – Falk Tandetzky Nov 17 '20 at 15:47
6

It mentions: Finding a global minimum where the function of jumping from one minimum to another is handled by quantum tunneling.

I have the feeling that in order to just get an idea of what it can practically do one could look at the mentioned example of spin glasses. In other words, the spin coupling physics close to the actual hardware implementation itself

http://en.wikipedia.org/wiki/Spin_glass.

Relevant may be the work of Giorgio Parisi (Yes, the one of the Altarelli–Parisi parton evolution equations) and his co-workers Mezard and Virasoro.

See the text of the Boltzmann 1992 Medal:

Parisi's deepest contribution concerns the solution of the Sherrington-Kirkpatrick mean field model for spin glasses. After the crisis caused by the unacceptable properties of the simple solutions, which used the "replication trick", Parisi proposed his replica symmetry breaking solution, which seems to be exact, although much more complex than anticipated. Later, Parisi and co-workers Mezard and Virasoro clarified greatly the physical meaning of the mysterious mathematics involved in this scheme, in terms of the probability distribution of overlaps and the ultrametric structure of the configuration space. This achievement forms one of the most important breakthroughs in the history of disordered systems. This discovery opened the doors to vast areas of application. e.g., in optimization problems and in neural network theories.

http://en.wikipedia.org/wiki/Giorgio_Parisi#Awards

Hans de Vries
  • 4,407
  • 22
  • 25