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

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.