Quantum Algo: Shor Algorithm
How to find factors of a given number?
In the previous article, we have discussed about the Quantum Period Finding using Quantum Phase Estimation.
In this article, we discuss about the Shor’s quantum algorithm for factoring an Integer N by using the Quantum phase estimation, Quantum period finding, Quantum Fourier Transform, Greatest Common Divisor and Continued Fractions.
We implement the quantum shor’s factoring algorithm using qiskit for N =21 and Cirq for N =15.
Setup:
Given an composite number N, having factors as 1, p, q, p.q here N = p.q where p and q are two primes.
The goal is to find a non-trivial divisor(either p or q) of N which shall be less than N.
The problem can be approached, as two parts:
- A reduction, which can be done in a classical computer of the factoring problem to the problem of period (or) order finding problem.
- A quantum algorithm to solve the order (or) period finding problem.
Let’s define our problem in the following steps:
In the following discussion, we try to understand each and every step mentioned above in detail,
point1: choose any random integer number which shall be in the interval of (1, N), where 1 and N both are excluded in the range.
point2: compute gcd(a, N) the greatest common divisor of a and N.
Let’s understand GCD in the following with Modular Arithmetic, Quotient Remainder Theorem and then Greatest Common Divisor with an example.
Modular Arithmetic:
we are interested in remainder when divide A by B, we can use an operator called modular operator.
An example, as shown below
Quotient Remainder Theorem:
Given any integer A, and a positive integer B, there exists unique integers Q and R such that
example:
Greatest Common Divisor:
Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.
The Euclidean Algorithm for finding GCD(A,B) is as follows:
- If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
- If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
Write A in quotient remainder form as A = B * Q + R
Here R is A mod B, then find GCD(B,R) or GCD(B, A mod B). since GCD(A,B) = GCD(B,R) until we reach to any one of the steps mentioned above.
example:
GCD of 270, 192 is ?
GCD of 192, 78 is ?
GCD of 78, 36 is ?
GCD of 36, 6 is ?
GCD of 6, 0 is ?
Finally,
point3: if gcd(a,N) is not equals to 1 then gcd(a,N) is a non-trivial factor of N, and the problem solved, we stop. From the above GCD(270, 192) we can see 6 is the factor.
If the greatest common factor is 1, then one of the two numbers must be a prime number. Their least common multiple must be the product of the two numbers.
Example:- we know 5 and 7 are prime numbers because their only factors are 1 and themselves. If you multiply these numbers, you get the product of 35, which is their least common multiple.
To use the quantum period finding algorithm, we choose the value of a such that gcd(a, N) shall be equal to 1.
point4: Two numbers are called relatively prime or coprime, if there GCD equals to 1, then use Quantum period-finding algorithm to find r(period).
we use the Quantum Period Finding algorithm as mentioned in this article.
point 5: If the period r we calculated through the quantum period finding algorithm is odd, it cannot be used in the following steps. Go back to step 1 and repeat the above steps with different a until an even r is obtained. If a is even, proceed to next step.
point 6: since r is even, it holds that
which is
if the below condition occurs
then go back to step 1 and try with different a.
what is this triple equal to means?
Congruence modulo:
the above expression is not having equal to sign and cannot be same as below
well, the expression means as shown below
example:
point 7: from the above condition
the gcd gives us either p or q, are the non-trivial factors of N and factorization is done.
classical algorithm:
classical order finding function returns period of the function
randomly generates the value of a
comparison: classical vs. quantum factoring algorithms (source: IBM qiskit textbook)
Implement Shor’s Factoring Algorithm using qiskit and Cirq:
In this section we implement Shor’s Factoring Algorithm circuit using cirq for N = 15 which have factors as 1, 3, 5, 15 and using qiskit for N = 21 which have factors as 1, 3, 7, 21.
Implement Shor’s Factoring Algorithm using cirq:
the below function generates initial conditions for the SFA algorithm
the below function generates Controlled Unitary circuit for the given function.
the below function prepares psi wave function for the SFA algorithm.
the below function generates Inverse Quantum Fourier Transform.
the below function generates the Quantum period finding circuit using quantum phase estimation.
the below function captures the period and the phase of the given result using continued fractions algorithm as shown below.
the below function generates value of a for the given function.
the below block initializes the qubits, captures the period and phase of the Shor’s factoring algorithm
the result shows the factors of the given N as shown below
Implement Shor’s Factoring Algorithm using qiskit:
As shown in the below qiskit1, generates initial conditions for the SFA algorithm
As shown in the below qiskit2, prepares a^x mod N for the QPF algorithm.
As shown in the below qiskit3, generates Controlled U circuit for the given function.
As shown in the below qiskit4, prepares psi wave function for the QPF algorithm.
As shown in the below qiskit5, generates Inverse Quantum Fourier Transform.
As shown in the below qiskit6, generates Quantum Period Finding circuit for the given function.
As shown in the below qiskit7, generates value of a for the given function.
After the circuit running over simulator, capture the period of the function using continued fractions algorithm
As shown in the below qiskit8, initializes the circuit, number of qubits, generates the SFA circuit.
the result shows the factors of the given N as shown below
references: qiskit textbook, cirq tutorials, IITM course by (@Prabha M, Anil Prabhakar, @Valliamai Ramanathan, and @chandrashekar radhakrishnan), Qubit by Qubit(The Coding School) course, IBM Quantum Challenge 2021, QWorld (QSilver 2021), Umesh Vazirani’s explanation of Shor’s algorithm, Textbook by Isaac Chuang and Michael Nielsen, Wikipedia, stack exchange and open source materials.
