The research team successfully constructed the quantum universal gate for Shor’s algorithm and derived the cost of this quantum circuit to estimate the complexity. In this circuit design, several modules were developed to perform integer operations such as addition and controlled addition on a quantum computer. These integer operations are achieved by using single-qubit logic gates and CNOT logic gates that are then combined into the quantum circuit for Shor’s algorithm. To reduce the number of qubits required to decompose composite numbers, the research team adopted an adder using quantum Fourier transform and introduced a semi-classical quantum computer model to handle the multiplication operation. Using the circuit design to crack the widely used 1024-bit RSA encryption, both the space complexity and time complexity are approximately 1014. Finally, the research team implemented Shor’s factorization of the composite number 15 through IBM’s platform. If the hardware can be improved in the future, the quantum circuit design proposed in this paper can be used to decompose larger composite numbers.

Quantum Information Science (QIS) is an emerging science that uses qubits to store and process information. Quantum computers have special physical properties and two characteristics of qubits:

1. quantum parallelism
2. quantum entanglement

which allow QIS to have better performance in dealing with certain problems than traditional computers. It can even handle problems that traditional computers cannot solve. The areas of opportunity to apply quantum computers are as follows:

1. Computational Chemistry, Drug Design
2. Machine Learning
3. Communication, encryption and decryption

In 1994, the mathematician Peter Shor developed a quantum algorithm that could decompose a positive integer N to get prime factors, and then cracked the RSA encryption. This was the first specific quantum algorithm. It is very simple to multiply two numbers, but it is quite difficult to decompose a large number into prime factors. This algorithm can decompose the prime factors of a large number on an ideal quantum computer with exponential acceleration. In theory, Shor's algorithm can easily crack the cryptographic systems on the market. Therefore, this theory has also attracted considerable interest from researchers in related fields around the world. At present, the relevant literature is constantly being updated.

The RSA encryption algorithm is based on the problem of prime factor decomposition. If hackers want to crack RSA, they must first find a way to decompose the large number to prime factors to obtain the key. Hackers cannot easily decompose a large number to achieve a secure encryption method. Therefore, if they want to crack the RSA encryption algorithm, the key is to decompose N into the product of two prime factors p and q, which is exactly what Shor's algorithm aims to achieve.

The focus of this research is to construct a quantum circuit of Shor’s algorithm that can actually be implemented. Furthermore, the depth of the circuit and the number of qubits should be reduced as much as possible. In this research, traditional computers have been added to help the calculation of multiplication, so that quantum computers can implement Shor's algorithm with less cost, and use universal logic gates to construct the circuit functions required by Shor's algorithm, including:

1. Quantum Fourier Transform
2. Quantum inverse Fourier transform
3. Adder
4. CNT-(b+ax) mod N

It can be operated on a real quantum computer.

The research team successfully factored 15 by using the constructed modules on IBM’s platform. It is the first research in the world to actually implement the quantum circuit of Shor's algorithm; instead of simplifying the circuit, every module is able to run. Although the noise generated by quantum computer operations is very large, the depth of the circuit and the number of logic gates may cause errors. How to reduce the noise generated by the quantum circuit due to the hardware will be the focus of the future research.

Quantum computers are one of the development priorities of all countries in the world in the next few decades, and the reason is that they have computing power far surpassing traditional computers. As quantum computers and related technologies mature, they will bring about tremendous changes to human society and life. Shor's algorithm is the first algorithm designed specifically for quantum computers. It makes full use of the characteristics and specialties of quantum computers and provides valuable experience for the development of quantum algorithms in the future.