Breaking RSA Using Shor's Algorithm

We have now described all the details necessary to estimate the cost of our implementation in the abstract circuit model. The cost depends on the two parameters specified by the problem (the input size \(n\) and the number of exponent qubits \(n_e\)) and also the four controllable parameters we have discussed (the exponentiation window size \(c_{exp}\), the multiplication window size \(c_{mul}\), the runway separation \(c_{sep}\), and the padding/runway length \(c_{pad}\)). 

Although we do consider alternate values when producing tables and figures, in general we have found that the settings \(c_{exp} = c_{mul} = 5, c_{sep} = 1024, c_{pad} = 2 lg \; n + lg \; n_e + 10 ≈ 3 lg \; n + 10\) work well. In this overview we will focus on these simple, though slightly suboptimal, values. 

Recall that an exponentiation may be reduced to a sequence of \(n_e\) multiplications, which we process in groups of size \(c_{exp}\). For each multiplication, we do two multiply-adds. Each multiply add will use several small additions to temporarily reduce the runway registers to single qubits. The multiply-add then needs to perform a sequence of additions controlled by the n main register qubits, the \(O(lg \; n)\) coset padding qubits, and the \(n/c_{sep}\) reduced runway qubits. Using windowed arithmetic, these additions are done in groups of size \(c_{mul}\) with each group handled by one lookup addition. Therefore the total number of lookup additions we need to perform is 

\(\text{LookupAdditionCount}(n, n_e) =\dfrac{2nn_e}{c_{exp}c_{mul}} · \dfrac{c_{sep} + 1}{c_{sep}} + O (\dfrac{n_e lg \; n}{c_{exp}c_{mul}})\)

\( → \dfrac{2nn_e}{25} · \dfrac{1025}{1024} + O (n_e lg n)\)

\( ≈ 0.1n_en\) (1) 

The lookup additions make up essentially the entire cost of the algorithm, i.e. the total Toffoli count is approximately equal to the Toffoli count of a lookup addition times the lookup addition count. This works similarly for the measurement depth. Ignoring the negligible cost of uncomputing the lookup, the Toffoli count of a lookup addition is \(2n + nc_{pad}/c_{sep} + 2^{c_{exp}+c_{pad}}\) and the measurement depth is \(2c_{sep} + 2c_{pad} + 2^{c_{exp}+c_{mul}}\). Therefore 

\(\text{ToffoliCount}(n, n_e) ≈ \text{LookupAdditionCount}(n, n_e) · ( 2n + c_{pad} \dfrac{n}{c_{sep}} + 2^{c_{exp}+c_{pad}} )\)

\( ≈ 0.2n_en^2 + 0.0003n_en^2 \; lg \; n\) (2) 

\(\text{MeasurementDepth}(n, n_e) ≈ \text{LookupAdditionCount}(n, n_e) · (2c_{sep} + 2c_{pad} + 2^{c_{exp}+c_{mul}} )\)

\( ≈ 300n_en + 0.5n_en \; lg \; n\) (3) 

These approximate upper bounds, with \(n_e\) set to \(1.5n\), are the formulae we report in the abstract and in Table 1 for the cost of factoring RSA integers.