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.
Quantum computers hold the promise to solve some hard problems that are intractable for even the most powerful current supercomputers. One of the most famous examples is Shor's algorithm for factorizing large numbers, which has exponential speedup compared to its best classical counterparts. However, running such an algorithm will require to build a large-scale quantum computer consisting of thousands or even millions of qubits that include quantum error correction (QEC) and fault-tolerant (FT) mechanisms. Quantum computing is already a reality with the so-called Noisy Intermediate-Scale Quantum (NISQ) processors, some of them available in the cloud. Noisy refers to the imperfect control over the qubits and intermediate-scale to the relatively low number of quits (from fifty to a few hundred). Although current and near-term quantum devices will not have enough qubits for implementing large and fully corrected quantum computations, the use of small quantum error correction codes may extend the computation lifetime of NISQ devices. In this context and as a first step, it is important to test and demonstrate the fault-tolerance of these QEC codes. In this thesis, we explore the fault-tolerance of two small quantum correction codes that are good candidates to be applied to NISQ processors, the [[4,2,2]] code and the [[7,1,3]] Steane code. To this purpose, by following the FT criterion prosed by Daniel Gottesman in 2016, we tested both codes using two simulators, the stabilizer formalism simulator that includes quite simple error models and a full density matrix simulator called quantumsim, which includes more realistic noise. The simulations are performed under reasonable noise parameter values. For the [[4,2,2]] code, 235 circuits are tested based on the two simulators. The results show that in the stabilizer formalism simulation, the FT criterion is satised for all circuits, while not fully satisfied in the full density matrix simulation. For the [[7,1,3]] Steane code, we use a parallel-flag error correction implementation which is tested using the full density matrix simulator. Our results show that without applying any QEC cycle, for all circuits (84 circuits for 1 logical qubit simulation and 452 circuits for 2 logical qubits simulation), the error rate of the encoded circuits is lower than the unencoded ones. Adding a quantum error correction (QEC) cycle will in general increase the error rate of the computation.