Quantum Computing Hardware
Which is the most appropriate main reason why quantum computers as of the mid-2020s cannot break RSA-2048 with Shor's algorithm?
- AShor's algorithm in principle stops working once the number of qubits exceeds 1,000
- BIt has been mathematically proven that classical computers are faster at breaking RSA-2048
- CA huge number of gates must be executed without error, which requires many logical qubits built by error correction and an enormous number of physical qubits to support them
Show answer and explanation
Answer: C. A huge number of gates must be executed without error, which requires many logical qubits built by error correction and an enormous number of physical qubits to support them
Breaking RSA-2048 requires executing gates on the order of billions in sequence on roughly one thousand to several thousand logical qubits. The logical error rate must therefore be extremely low, and error correction requires several hundred or more physical qubits per logical qubit. Estimates made in the 2020s put the requirement at roughly hundreds of thousands to tens of millions of physical qubits with error rates of about 0.1% (the figures vary greatly with the assumptions), orders of magnitude beyond the scale of current devices. However, these estimates have been shrinking as the algorithms improve, so preparations for migrating cryptography need to start early.
- A. There is no such fundamental limit. What is needed is, if anything, many more qubits.
- B. There is no such proof. The security of RSA rests on the fact that no efficient classical method of solving it is known.
- C. Correct. It requires an error-corrected machine orders of magnitude larger.