Breaking RSA Using Shor's Algorithm

The multiplication circuits that we are using have a Toffoli count that scales quadratically (up to polylog factors). There are multiplication circuits with asymptotically better Toffoli counts. For example, the Karatsuba algorithm has a Toffoli count of $O(n \; lg \; 3)$ and the Schönhage–Strassen algorithm has a Toffoli count of $O(n \; lg \; n \; lg \; lg \; n)$. However, there are difficulties when attempt- ing to use these asymptotically efficient algorithms in the context of Shor's algorithm. 

The first difficulty is that efficient multiplication algorithms are typically classical, implemented with non-reversible computation in mind. They need to be translated into a reversible form. This is not trivial. For example, a naive translation of Karatsuba multiplication will result in twice as many recursive calls at each level (due to the need to uncompute), and increase the asymptotic Toffoli count from $O(n^{lg \; 3})$ to $O(n^{lg \; 6})$. Attempting to fix this problem can result in the space complexity increasing, though it is possible to solve this problem. 

The second difficulty is constant factors, both in workspace and in Toffoli count. Clever multiplication circuits have better Toffoli counts for sufficiently large n but, when we do back-of-the- envelope estimates, "sufficiently large" is beyond $n = 2048$. This difficulty is made worse if the multiplier is incompatible with optimizations that work on naive multipliers, such as windowed arithmetic and the coset representation of modular integers. Clever multiplication circuits also tend to use additional workspace, and it is necessary to contrast using the better multiplier against the opportunity cost of using the space for other purposes (such as distillation of magic states). For example, the first step of the Schönhage–Strassen algorithm is to pad the input up to double length, then split the padded register into $O(√n)$ pieces and pad each piece up to double length. The target register quadruples in size before even getting into the details of performing the number theoretic transform! This large increase in space means that the quantum variant of the Schönhage–Strassen algorithm is competing with the many alternative opportunities one has when given 6000 more logical qubits of workspace (at $n = 2048$). For example, that's enough space for fifty additional CCZ factories. 

Can multipliers with asymptotically lower Toffolis counts help at practical sizes, such as $n = 2048$ bits? We believe that they do not, but only a careful investigation can properly determine the answer to this question.