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

Abstract

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\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for $n<{n}_{t}(b)$ (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for $n>{n}_{t}(b)$ (exponential regime), where ${n}_{t}(b)$, the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for $n<{n}_{t}(b)$ and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for $n>{n}_{t}(b)$, where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling ($n<{n}_{t}$) and the ${2}^{\ensuremath{-}2b}$ scaling ($n>{n}_{t}$) of the data perfectly. In addition, in the large-$n$ regime, the prefactor in ${\ensuremath{\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.