12
$\begingroup$

I read that a company called D-Wave Systems has and is manufacturing quantum computers of 128 qubits.

Can they or can they not use Shor's and Grover's algorithms for finding RSA-keys? If they can't then why not?

And how come it was so hard for the team at MIT to create and maintain a stable 5-qubit quantum computer ion trap if D-Wave has already succeeded in creating Q-computers with more qubits?

It feels like something with this D-Wave computer is off..? Would be extremly grateful if anyone could enlighten me.

$\endgroup$
  • $\begingroup$ You don't use Grover's algorithm to find RSA keys, you use Grover's algorithm to brute-force symmetric keys. $\endgroup$ – SEJPM Oct 22 '16 at 13:29
  • 2
    $\begingroup$ Possible duplicate of Now that quantum computers have been out for a while, has RSA been cracked? $\endgroup$ – SEJPM Oct 22 '16 at 13:30
  • 1
    $\begingroup$ @user128226: Welcome to crypto.se. I have reverted the question to its former revision (since there was an accepted answer to that, and answers must match questions, thus questions must not change too drastically); the duplicate has been removed. Feel free to post a new question for what was the short-lived, archived revision 3: "Is the 5-qubit Quantum computer created at MIT an all-purpose quantum computer?", an interesting but different question. $\endgroup$ – fgrieu Oct 22 '16 at 18:13
17
$\begingroup$

D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's algorithms, as these aren't quantum annealing problems. It's also still an open question whether D-Wave's machines even provide any speedup over classical simulated annealing systems.

$\endgroup$
  • 2
    $\begingroup$ Yes — the thing about D-wave’s machines is that they are computers that make use of quantum effects, but they are not “quantum computers” in the sense that’s usually meant by that phrase. $\endgroup$ – PLL Oct 22 '16 at 19:41
  • 2
    $\begingroup$ As far as I know, it is still open if D-Wave computers actually have any kind of advantage over classical computers for any problem - even the ones for which they are designed specifically. $\endgroup$ – tylo Feb 3 '17 at 17:54
  • $\begingroup$ I believe the big difference is Dwave uses just annealing, while general purpose quantum bits also require entanglement. $\endgroup$ – Hal Mar 11 '18 at 15:53
5
$\begingroup$

Even though the D-Wave machines can not be labelled as "general purpose", they are certainly research objects with new applications everyday. The capabilities of what they can do is only limited by our current developments, so the term general purpose is rather meaningless in the new QC realm.

Contrary to the previous answer, the latest D-Wave 2X (2000 qbits) can run pretty much any algorithm given that they are converted into a simulated annealing (SA) problem. This paper shows how this is done in practice, while the paper "Prime factorization using quantum annealing and computational algebraic geometry" [2016] show how factorization can be performed (on that machine). It's rather obvious that new technology require a translation from classical algorithms to what is required by the new.

The current limitations are due to the fact that only a fraction of the available qbits can be of utilized for the algorithm. The reason is that you need about ~12 physical qbits for error correction, for every logical qbit needed. So out of the 2000 qbits, you can only use ~166.

So to answer your question, at this moment, no you can't. But when they are able to reach about 2000 logical qbits, then we can use it to factor the lower RSA keys. This is also talked about in this answer.

And from this blog post:

The quantum Fourier transform is applied to a quantum circuit built just out of 1-Qbit and 2-Qbit gates, making the physical implementation of Shor’s algorithm one of the easiest tasks for a quantum computer.

Just one of the steps of Shor’s algorithm needs to be implemented on a quantum computer, while the rest can be done on a classical computer. The quantum subroutine will be performed and fed back to continue the calculation. A quantum computer will likely never be a standalone system, but together with a supercomputer, the time to break an RSA key will be quite reasonable.

$\endgroup$
  • $\begingroup$ Raouf Dridi and Hedayat Alghassi's Prime factorization using quantum annealing and computational algebraic geometry manages to factor 18-bit integers using the D-Wave 2X processor. That tends to illustrate that the D-Wave 2X processor is not competitive with classical processors for factorization. $\endgroup$ – fgrieu Feb 3 '17 at 17:32
  • $\begingroup$ @fgrieu In other words, quantum annealing can factor integers, but it cannot use Shor's algorithm to do so? Is the quantum annealing algorithm for factorization more efficient than GNFS? $\endgroup$ – forest Mar 12 '18 at 3:47
  • 1
    $\begingroup$ @forest: my understanding of the question is limited. I get D-Wave 2X can not (scalably) be used for Shor's algorithm. It is claimed it can be used for Quadratic Unconstrained Binary Optimization, which in turn can be used for factoring; but in the end efficiency suffers badly. Nothing comparable to GNFS (or even merely subexponential like CFRAC, QS, ECM) is reported. $\endgroup$ – fgrieu Mar 12 '18 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.