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-1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\approx \exp [-{\phi }_{max}^2(n,b)/100]$ for $n<n_t(b)$ (non-exponential regime) and $P(n,b)\approx 2^{-{\xi }_b(n-8)}$ for $n>n_t(b)$ (exponential regime), 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$, ${\phi }_{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)/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.

45 pages, 11 captioned figures

References in corpus (7)

• Shor's quantum factoring algorithm on a photonic chip
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Fast Quantum Modular Exponentiation
• Scalability of Shor's algorithm with a limited set of rotation gates
• Effects of imperfections for Shor's factorization algorithm

Cited by in corpus (6)

• Automated optimization of large quantum circuits with continuous parameters
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
• Shor's Factoring Algorithm and Modular Exponentiation Operators
• Quantum Algorithms for Discrete Log Require Precise Rotations
• Symmetry boosts quantum computer performance