shor's algorithm

Shor’s factoring algorithm is a quantum algorithm that can factor large numbers exponentially faster than any classical algorithm. The algorithm relies on the quantum Fourier transform (QFT) to find the period of a function related to the prime factors of the number being factored.

The importance of the algorithm lies in its ability to break the RSA public-key cryptosystem, which relies on the difficulty of factoring large numbers. If a quantum computer can efficiently factorize large numbers, then the security of RSA is compromised.

In addition to its cryptographic implications, Shor’s algorithm is an important example of a class of algorithms that solve the hidden subgroup problem. Many important problems in discrete mathematics, such as period finding, order finding, and discrete logarithms, are instances of the hidden subgroup problem.

Shor’s algorithm heavily uses the QFT, which is perfectly suited to investigating periodic signals. The algorithm ultimately leverages a classical program to retrieve the prime factors from the period learned with the QFT. This illustrates the importance of using quantum ideas only in those parts of a problem where they are well suited.

Shor’s algorithm is a hallmark example of how quantum computing can be used to solve difficult or impossible problems with classical computing.

In this post, we will explore Shor’s Algorithm and learn how to execute it on IBM’s quantum computers using Python and Qiskit.

Shor’s Algorithm is a quantum algorithm designed to factorize integers. Simply put, given an odd integer N, the algorithm is able to find its prime factors.

The algorithm comprises two parts:

Firstly, a classical part reduces the factorization to the problem of finding the function’s period. This is carried out using a classical computer.

Secondly, a quantum part uses a quantum computer to identify the period by implementing the Quantum Fourier Transform.

The algorithm follows these steps:

  1. Pick a random number, A, where A is less than N.
  2. Compute A and N’s greatest common divisor (GCD).
  3. If the GCD is not equal to 1, then we have found a factor of N.
  4. If not, run the quantum circuit that uses the Quantum Fourier Transform.
  5. If the period is odd, return to step 1.
  6. Otherwise, we have found the factors of N.

Β 

Implementing this algorithm using Qiskit’s built-in function for Shor’s Algorithm called Shor(N) is incredibly easy. Here, N represents the integer you wish to factorize. For instance, Shor (21) will discover the prime factors of 21, which is 7 and 3.

				
					
from qiskit import IBMQ
from qiskit.utils import QuantumInstance
from qiskit.algorithms import Shor

IBMQ.enable_account('XXXXXX') # Your API token here
provider = IBMQ.get_provider(hub='ibm-q')

# Specifies the quantum device
backend = provider.get_backend('ibmq_qasm_simulator') 

print('\nShor\'s Factorization Algorithm')
print('--------------------')
print('\nExecuting...\n')


factors = Shor(QuantumInstance(backend, shots=1000, skip_qobj_validation=False)) 
#The integer a needs to satisfy a < N and gcd(a, N) = 1
result_dict = factors.factor(N=21, a=2)
result = result_dict.factors

print(result)

[7,3]

Now let’s swiftly review what is happening under the hood: 

This diagram illustrates the process used in the period-finding step of Shor’s algorithm. The first register (known as the control register) consists of n qubits. The number of qubits in this register determines the precision of the bit value of 2𝑛𝑠/π‘Ÿ. The bottom register (known as the work register) consists of m qubits which are used to encode N.

The routine begins with the initialization of both the control and work registers. Next, conditional modular exponentiation is performed, which is represented in the diagram by a controlled unitary. After that, an inverse quantum Fourier transform is applied to the control register, followed by a standard computational basis measurement.

Essentially, the circuit is the QPE (Quantum Phase estimation) algorithm applied to the unitary matrix π‘ˆΜ‚π‘Ž.

This is a quantum circuit that has been designed for order-finding when 𝑁 is equal to 21 and π‘Ž is equal to 4. The circuit requires a total of five qubits, with three being used for the control register and two for the work register.

The purpose of the circuit is to determine 2𝑛𝑠/π‘Ÿ with a precision of three bits, which will allow for the extraction of the order. The gates used in the circuit include phase gates and πœ‹/8 gates. Specifically, up to a global phase, 𝑆=𝑅𝑧(πœ‹/2) and 𝑇=𝑅𝑧(πœ‹/4)

Back