15
$\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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You don't use Grover's algorithm to find RSA keys, you use Grover's algorithm to brute-force symmetric keys. $\endgroup$
    – SEJPM
    Commented Oct 22, 2016 at 13:29
  • 2
    $\begingroup$ Possible duplicate of Now that quantum computers have been out for a while, has RSA been cracked? $\endgroup$
    – SEJPM
    Commented Oct 22, 2016 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 ♦
    Commented Oct 22, 2016 at 18:13

3 Answers 3

Reset to default
21
$\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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Oct 22, 2016 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
    Commented Feb 3, 2017 at 17:54
  • $\begingroup$ I believe the big difference is Dwave uses just annealing, while general purpose quantum bits also require entanglement. $\endgroup$
    – Hal
    Commented Mar 11, 2018 at 15:53
7
$\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.

Improve this answer
$\endgroup$
7
  • 1
    $\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 ♦
    Commented Feb 3, 2017 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
    Commented Mar 12, 2018 at 3:47
  • 2
    $\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 ♦
    Commented Mar 12, 2018 at 6:32
  • 1
    $\begingroup$ I don't think that D-Wave has demonstrated any form of error correction as this answer implies. $\endgroup$
    – tparker
    Commented Jan 2, 2022 at 4:33
  • $\begingroup$ I don't think is sufficient to achieve 2000 logical qubits, they also need to have all-to-all connectivity. The latest D-Wave computer only has 15 way-qubits connectivity: techcrunch.com/2020/09/29/… $\endgroup$
    – bubakazouba
    Commented Mar 10, 2022 at 8:38
-1
$\begingroup$

Both Grover's and Shor's factorization algorithms can be realized by quantum annealing during the same time of computation as in gate-based algorithms. The explicit examples can be found in https://arxiv.org/abs/2110.12354

However, this article shows that the currently used by D-Wave calculation schedules are not suitable for these algorithms, and substantial hardware advances are still needed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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