Breaking RSA Using Shor's Algorithm

Our implementation of Shor's algorithm uses a layout that is derived from the (nearly) reaction limited layouts. In these layouts, a lookup addition is performed as follows (see Figure 4). All data qubits are arranged into rows. The rows of qubits making up the target register of the addition are spread out into row pairs with gaps five rows wide in between. In these gaps there will be two rows for the lookup output register, and three rows for access hallways. This arrangement allows the lookup computation two ways to access each output row, doubling the speed at which it can run, while simultaneously ensuring the target register and the lookup output register are interleaved in a convenient fashion. 

After the lookup is completed, the rows of the lookup output register and the addition target register are packed tightly against the top (or equivalently bottom) of the available area. An operating area is prepared below them, and the data is gradually streamed through the operating area while the operating area gradually shifts upward. This performs the MAJ sweep of Cuccaro's ripple carry adder. Everything then begins moving in the opposite direction in order to perform the UMA sweep on the return stroke.

The lookup register is quickly uncomputed using measurement-based uncomputation, and the system is returned to a state where another lookup addition can be performed. 

In order to perform piecewise additions separated by oblivious carry runways, we simply partition the computation horizontally as shown in Figure 5 and Figure 7. The lookup before each addition prepares registers across the pieces, as shown in Figure 6, but the additions themselves stick to their own piece. 

The width of each piece is determined by the number of CCZ factories needed to run at the reaction limited rate. This number is 14, assuming a code distance of 27 and using the CCZ factories. Also, assuming a level 1 code distance of 17, the footprint of the factory is 15 × 8. The factories are laid out into 2 rows of 7, with single logical qubit gaps to allow space for data qubits to be routed in and out. The total width of a piece is 15 · 7 + 7 = 113 logical qubits. The height of the operating area is 33 rows of logical qubits (2 · 8 for the CCZ factories, three for the ripple-carry operating area, six for AutoCCZ fixup boxes, and eight for routing data qubits). The $c_{pad} +c_{sep}$ qubits from each register add another 30 rows (approximately). So, overall, when working on a problem of size n, the computation covers a $113w × 63$ grid of logical qubits where $w = n/c_{sep} = n/1024$.