Experiments and Resource Analysis of Shor’s Factorization Using a Quantum Simulator

Abstract

Shor’s algorithm on actual quantum computers has succeeded only in factoring small composite numbers such as 15 and 21, and simplified quantum circuits to factor the specific integers are used in these experiments. In this paper, we factor 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. The largest composite number $N=511$ was factored in approximately 2 h on the simulator. In our experiments, we implement Shor’s algorithm with basic circuit construction, which does not require complex tricks to reduce the number of qubits, and we give some improvements to reduce the number of gates, including MIX-ADD method. This is a flexible method for selecting the optimal ADD circuit which minimizes the number of gates from the existing ADD circuits for each of the many ADD circuits required in Shor’s algorithm. Based on our experiments, we estimate the resources required to factor 2048-bit integers. We estimate that the Shor’s basic circuit requires $2.19 \times 10^{12}$ gates and $1.76 \times 10^{12}$ depth when 10241 qubits are available, and $2.37 \times 10^{14}$ gates and $2.00 \times 10^{14}$ depth when 8194 qubits are available.

Appendices

Appendix 1. Examples of Greedy Method

Figure 6 shows an example of our greedy method for $k=4, c=1$, and Fig. 7 for $k=5, c=1, 2$. The number of Toffoli gates is 6 for $k=4, c=1$, 8 for $k=5, c=2$, and 10 for $k=5, c=1$, which matches $4k-8-2c$.

Appendix 2. Effectiveness of Greedy Method

In order to show the superiority of our greedy method, we factored RSA-type composite numbers up to 7-bit with 1-node, without and with the greedy method for GT-ADD. Results are summarized in Table 5, where results in the ‘Greedy’ column coincide with the results shown at ‘GT-ADD’ column in Table 2. As shown in the table, the greedy method reduces the number of gates to about 66–71%, and the depth to about 45–56%. Since the generated Toffoli gates by the greedy method can be parallelized easily, the effect on the depth is much larger than that on the number of gates. Our analysis in Sect. 3.2 shows that the greedy method reduces the number of gates to about $56.25\%$ (calculated as $3/(16/3) \times 100$) when n is sufficiently large.

Appendix 3. Data for Circuit Estimation in Sect. 4.3

Figure 8 shows the average values and the approximation polynomials described in Sect. 4.3. Table 6 summarizes the average values, lowest values, and highest values for the R-ADD case. There is virtually no difference between them.

Fig. 6.

Conversion from a C$^4$-NOT to C$^2$-NOTs with 1 clean qubit

Fig. 7.

Conversion from a C$^5$-NOT to C$^2$-NOTs

Table 5. Factorization of N with GT-ADD without and with the greedy method

Fig. 8.

Average values of the number of gates and the depth of Shor’s circuit for n-bit integers. The dashed lines represent approximation polynomials.

Table 6. Resources of optimized Shor’s circuit with R-ADD