The 2021 resource estimate for factoring a -bit RSA modulus (Gidney and Ekerå,…
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · Open quantum systems, decoherence and error correction
Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm
Problem
The 2021 resource estimate for factoring a 2048-bit RSA modulus (Gidney and Ekerå, Quantum 5, 433) uses purpose-built modular arithmetic requiring about 0.3L3≈2.6×109 Toffoli gates in total, at a gate error rate of 10−3 and a 1μs cycle time. Suppose, unrealistically, that these Toffoli gates could be executed one at a time, one per cycle, with no error-correction overhead and no parallelism.
((a)) Estimate the total run time in hours under this assumption.
((b)) The same 2021 estimate quoted a run time of about 8 hours. Identify what the naive estimate in part (a) leaves out that accounts for the difference.