Breaking RSA Using Shor's Algorithm

Elsewhere in this paper we frame our hardware assumptions in terms of a physical gate error rate. For a physical gate error rate of 10⁻³, the probability of error in a logical qubit of distance d, per surface code cycle, is approximately $10^{−[d/2+1]}$. We base our cost estimates on the assumption that this scaling relationship holds. Each time the code distance is increased by two, the logical error suppression must jump by at least a factor of 10. We believe a physical error rate of 10⁻³ is sufficient to achieve this scaling relationship. 

Now that we know the number of logical qubits, the runtime of the algorithm, and the relationship between code distance and logical error rates, we can approximate the probability of a topological error occurring within the surface code during the execution of the algorithm. This will allow us to verify our initial assumption that a code distance of 27 is sufficient in the case where $n = 2048$. Larger computations will require larger code distances. 

When factoring an $n = 2048$ bit RSA integer we are using a board of $226 · 63$ logical qubits. Approximately 25% of these qubits are being used for distillation, which we already accounted for, and so we do not count them in this calculation. The remaining qubits are kept through $4n_en · 1000 ≈ 25$ billion surface code cycles, which implies that the probability of a topological error arising is approximately $10^{−[27/2+1]} · 226 · 63 · 0.75 · 25 · 10^9 ≈ 27 \%$. 

This is a large error rate. Using a code distance of 27 is pushing the limits of feasibility. We would need to repeat the computation roughly 1.4 times, on average, to factor a number. If our goal is to minimize the expected spacetime volume of the computation, perhaps we should increase the code distance to 29. Doing so would increase the physical qubit count by 15%, but the error rate would drop by approximately a factor of 10 and so the expected number of runs would be much closer to 1. Ultimately the choice comes down to one's preferences for using more space versus taking more time.