Breaking RSA Using Shor's Algorithm

Because our implementation is dominated almost entirely by the cost of performing lookup additions, its runtime is approximately equal to the number of lookup additions times the runtime of a single lookup addition. 

During the lookup phase of a lookup addition, the computation is code depth limited. Assuming a code depth of $d = 27$ and a surface code cycle time of 1 microsecond, it takes $1μs·d/2·2^{c_{exp}+c_{mul}} ≈ 14$ milliseconds to perform the lookup using double-access hallways. 

During the addition phase of a lookup addition, the computation is reaction limited. Given a reaction time of 10 microseconds, it takes $2(c_{sep} + c_{pad}) · 10μs ≈ 22$ milliseconds to perform the addition. The remaining bits of a lookup addition, such as uncomputing the lookup and rearranging the rows, take approximately 1 millisecond. Thus one lookup addition takes approximately 37 milliseconds. Given this fact, i.e. that we perform quantum lookup additions slower than most video games render entire frames, we can approximate the total runtime: 

$\text{TotalRuntime}(n, n_e) ≈ \text{LookupAdditionCount}(n, n_e) · 37 \text{milliseconds}$

$≈ 4n_en \text{milliseconds}$ (5) 

Though we caution the reader that this estimate ignores the fact that, at larger problem sizes, lookups become slower due to the minimum code distance increasing. 

This estimate implies that factoring a 2048 bit integer will take approximately 7 hours, assuming only one run of the quantum part of the algorithm is needed. Note that in our reported numerical estimates we achieve lower per-run numbers by using more precise intermediate values and by more carefully selecting parameters.

Figure 5: Data layout during a parallel addition. Corresponds to one of the "addition" columns from Figure 4. To scale, assuming a 2048 bit number is being factored. The left and right halves of the computer run completely independently and in parallel. The factories (red boxes and pink boxes) are feeding AutoCCZ states into the blue area, which is rippling the carry bit back and forth as the offset and target register data (green and yellow rows) is routed through gaps between the factories to the other side.

Figure 6: Data layout during a table lookup. To scale, assuming a 2048 bit number is being factored. Corresponds to the center "lookup" column from Figure 4. The factories (red boxes and pink boxes) are feeding AutoCCZ states into the dark gray region, which is performing the unary iteration part of a table lookup computation. There are enough factories, and enough work space, to run the lookup at double speed, made possible by the fact that every qubit in the lookup output register (yellow) is adjacent to two access hallways. The target register (green rows) and factor register (blue rows) are idle, except that a few qubits from the factor register are being used as address bits in the table lookup.

Figure 7: Spacetime layout during part of an addition. Time moves upward and has been truncated. Corresponds to one of the "addition" columns from Figure 4. Tiny gray squares are the size of one logical qubit. Yellow and green rows are qubits from the target and input registers of the addition. Dark blue rows are qubits from an idle register. Red boxes are CCZ magic state factories, turned into AutoCCZ states by the pink boxes. Light blue boxes are the MAJ operation of Cuccaro's adder, arranged into a spacelike sweep to keep ahead of the control software). The full adder is formed by repeating this pattern, with the operating area gradually sweeping up and then down through the green/yellow data. The diagram is to scale for $n = 2048$ with a level 2 code distance of $d = 27$ and a level 1 code distance of 17, and fits on a 225 × 63 rectangular grid of logical qubits.