2
$\begingroup$

After posting this question to Physics, it became pretty clear I should have posted here. So:

How might a (e.g.) 72-bit crypto-relevant quantum computer attack RSA-2048?

Bonus: how might that be characterized? (e.g., nn-qubit requires xxx passses, run time ~yyy)

Shor's algorithm appears to allow for parallel execution or iterative runs with a combination step. Assumption is that smaller-qubit QC might be able to perform those pieces.

However, it is suggested that a 4000-qubit/100m-gate quantum computer would be necessary. As the quantum piece of Shor's is a large transform, I assume that sets the constraint for qubit-size

Side note: there also appear to be possible speedups that may reduce the run time, such as qubit recycling? or the 4-8 passes vs. the 20-30 passes (by David McAnally)

$\endgroup$
3
$\begingroup$

Even with qubit recycling, 72 qubits will not be enough to do RSA-2048. Table 1 of the paper:

https://www.nature.com/articles/nature12290

Tells you that 1154 qubits are needed to do RSA-768 (which is much smaller than RSA-2048). This is without error correction.

Sure you can use your 72-qubit quantum computer to do a little sub-routine of Shor's algorithm, but this will not help if you have to do the rest of the algorithm on a classical computer. For any benefit, the quantum computer has to be doing the "rate-limiting step"

$\endgroup$

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.