Breaking RSA Using Shor's Algorithm

Following Zalka, the first improvement we make over the reference implementation is to switch from the usual representation of integers to the coset representation of modular integers. The usual representation of an integer k in a quantum computer is the computational basis state $|k〉$. 

The coset representation is different: It uses a periodic superposition with period $N$ and offset $k$. In ideal conditions, the integer $k \text{(mod N)}$ is represented by the state $\sqrt {2^{−c_{pad}}} ∑^{2^{c_{pad}} −1}_{ j=0} | jN + k〉$ where $c_pad$ is the number of additional padding qubits placed at the end of the register after the high order bits. The key idea is that the periodicity of the superposition causes a non-modular adder to perform approximate modular addition on this representation, and the error of the approximation can be exponentially suppressed by adding more padding to the register. 

As we will discuss later, the amount of padding required is logarithmic in the number of operations. This small cost enables the large benefit of using non-modular adders instead of modular adders. It is possible to perform a controlled non-modular addition in $4n$ Toffolis, significantly cheaper than the $10n$ we assumed for a controlled modular adder. Therefore switching to the coset representation reduces the leading asymptotic term of the Toffoli count of the reference implementation from $20n_en^2$ to $8n_en^2$.