Breaking RSA Using Shor's Algorithm

To minimize the spacetime volume for a given choice of \(n\) and \(n_e\), we consider all combinations of level 1 and 2 surface code distances \(d_1 ∈ {15, 17, . . . , 23}\) and \(d_2 ∈ {25, 27, . . . , 51}\) used during distillation and computation, window sizes \(c_{mul} ∈ {4, 5, 6}\) and \(c_{exp} ∈ {4, 5, 6}\), runway spacings \(c_{sep} ∈ {512, 768, 1024, 1536, 2048}\), and padding offsets \(δoff ∈ {2, 3, . . . , 10}\) where \(δoff = c_{pad} − 2 \; lg \; n − lg \; n_e\). Furthermore, we consider two different magic state distillation strategies: the CCZ factory and the T factory. For each combination of parameters we estimate the execution time t and physical qubit count s, and upper bound the overall probability of errors occurring (to obtain the "retry risk" ). 

To derive an upper bound on the overall probability of errors occurring, we separately estimate the probabilities of topological errors occurring due to a failure of the surface code to correct errors, of approximation errors occurring due to using oblivious carry runways and the coset representation of modular integers, of magic state distillation errors, and of the classical post-processing algorithm failing to recover the solution from a correct run of the quantum algorithm. We combine these error probabilities, assuming independence, to derive an upper bound on the overall probability of errors occurring.

We chose to optimize the quantity \( s^{1.2} · t/(1 − \epsilon ) \), which we refer to as the "skewed expected spacetime volume". The \(t/(1 − \epsilon )\) factor is the expected runtime, and the \(s^{1.2}\) factor grows slightly faster than the space usage. We skew the space usage when optimizing because we have a slight preference for decreasing space usage over decreasing runtime. We consider all combinations of parameters \((d_1, d_2, δoff, c_{mul}, c_{exp}, c_{sep})\), choose the set that minimizes the skewed expected space- time volume, and report the corresponding estimated costs.