I've read that under current technology we would need around 20 million qubits to crack the RSA-2048 protocol. How would one prove this?


1 Answer 1


I assume you mean the result from this paper, where the authors (including 'our very own' Craig Gidney) have estimated that if you have $\sim20$ million noisy qubits it would take you around $8$ hours to 'run' Shor's algorithm for a $2048$ bit key.

For a 'proof' you can read the paper, but there are a few important things to realize here:

  • This is an estimate
  • This number is for physical qubits, that are noisy, and that are therefore combined into logical qubits using QECC
  • The estimate depends on (what where then) current noise levels - lower noise levels means less need for error correction, which means less overhead
  • There is no definite number of (logical) qubits, it's always a trade-off between the number of qubits needed and the number of gates needed. This is why the time that it takes to run the algorithm is included in the title of the above paper, because implementing gates takes time, and therefore it is of vital importance

If you care only about logical qubits, this question & answer might be what you are looking for. However, remember, that there is no definite single answer to this question.

  • $\begingroup$ In the end I think @CraigGidney might be better suited to answer this question $\endgroup$
    – JSdJ
    Dec 19, 2020 at 15:29
  • 4
    $\begingroup$ This answers states what I would have stated. $\endgroup$ Dec 21, 2020 at 11:48

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.