Scaling laws for Shor's algorithm with a banded quantum Fourier transform

We investigate the performance of a streamlined version of Shor’s algorithm in which the quantum Fourier transform is replaced by a banded version that for each qubit retains only coupling to its $b$ nearest neighbors. Defining the performance $P(n,b)$ of the $n$-qubit algorithm for bandwidth $b$ as the ratio of the success rates of Shor’s algorithm equipped with the banded and the full bandwidth ($b=n-1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\approx \exp [-{\phi }_{max}^2(n,b)\mathrm{/}100]$ for $n < n_t(b)$(non-exponentialregime)and$P(n,b) \approx 2^{-\xi_b (n-8)}$for$n>n_t(b)$(exponentialregime),where$n_{t}(b)$, the location of the transition, is approximately given by $n_{t}(b)\approx b+5.9 + \sqrt{7.7(b+2)-47}$for$b\gtrsim 8$,$\varphi_{max} (n,b) = 2\pi[2^{-b-1} (n-b-2) + 2^{-n}]$,and$\xi_b\approx 1.1 \times 2^{-2b}$. Analytically we obtain $P(n,b)\approx \exp [-{\phi }_{max}^2(n,b)\mathrm{/}64]$ for $n<n_t(b)$ and $P(n,b)\approx 2^{-{\xi }_b^{(a)}n}$ for $n>n_t(b)$, where $\xi_{b}^{(a)} \approx \frac{\pi^2}{12 \ln(2)} \times 2^{-2b} \approx 1.19 \times 2^{-2b}$. Thus, our analytical results predict the ${\phi }_{max}^2$ scaling ($n<n_t$) and the $2^{-2b}$ scaling ($n>n_t$) of the data perfectly. In addition, in the large-$n$ regime, the prefactor in ${\xi }_b^{(a)}$ is close to the results of our numerical simulations and, in the low-$n$ regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that $b=8$ is sufficient for factoring RSA-2048 with a 95% success rate.