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)≈exp[-φₘₐₓ²(n,b)/100] for n<nₜ(b) (nonexponential regime) and P(n,b)≈2^-ξb(n-8) for n>nₜ(b) (exponential regime), where nₜ(b), the location of the transition, is approximately given by nₜ(b)≈b+5.9+√7.7(b+2)-47 for b8, φₘₐₓ(n,b)=2π[2^-b-1(n-b-2)+2^-n], and ξb≈1.1×2^-2b. Analytically we obtain P(n,b)≈exp[-φₘₐₓ²(n,b)/64] for n<nₜ(b) and P(n,b)≈2^-ξb⁽ᵃ⁾n for n>nₜ(b), where ${{ξ}}b⁽ᵃ⁾{≈}{{{π}}²}{12ln(2)}×{}{2}^{{-}2b}{≈}1.19×{}{2}^{{-}2b}$. Thus, our analytical results predict the ${{φ}}ₘₐₓ²$ scaling ($n<{n}ₜ$) and the ${2}^{{-}2b}$ scaling ($n>{n}ₜ$) of the data perfectly. In addition, in the large-$n$ regime, the prefactor in ${{ξ}}b⁽ᵃ⁾$ 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.