How to show that amount of qubits needed to crack the RSA-2048 protocol using Shor's algorithm?

Question

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?

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.