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<nt(b) (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for
n>nt(b) (exponential regime), where
nt(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<nt(b) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for
n>nt(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<nt) and the ${2}^{\ensuremath{-}2b}$ scaling (
n>nt) 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.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to
N=557993 with up to
n=39 qubits, we confirm earlier, smaller-
n results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-
n implementations of quantum computers.
Entanglement has been termed a critical resource for quantum information processing and is thought to be the reason that certain quantum algorithms, such as Shor's factoring algorithm, can achieve exponentially better performance than their classical counterparts. The nature of this resource is still not fully understood: here we use numerical simulation to investigate how entanglement between register qubits varies as Shor's algorithm is run on a quantum computer. The shifting patterns in the entanglement are found to relate to the choice of basis for the quantum Fourier transform.
Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.
We develop simulation methods for matrix product operators, and perform simulations of the Quantum Fourier Transform, Shor’s algorithm and Grover’s algorithm using matrix product states and matrix product operators. By doing so, we provide numerical evidence that a constant number of QFTs can be efficiently classically simulated on any state whose Schmidt rank grows only polynomially with the number of qubits, and quantify the amount of entanglement present in Shor’s algorithm. The efficiency of the matrix product state and operator representation allows us to perform moderately large simulations of both Shor’s algorithm with Z errors and Grover’s algorithm with up to 15 X, Y and Z errors. While larger simulations have been performed, our results have been computed with little computational power and provide new methods to perform large-scale quantum algorithm simulations.
The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.