Overview of Shor's Algorithm

Abstract:

It is well known that Shor's algorithm is a revolutionary quantum algorithm designed to find the two prime factors of a large integer that is a product of these primes. Since then, several research groups have worked on implementing this algorithm, but for factorizing numbers like 15, 21, 35, etc., because of quantum hardware's limitations in efficiently handling many qubits. All these examples are similar in the sense that they are expressible as the product of two distinct prime factors. However, in this paper, we attempt to implement Shor's algorithm for a perfect square, say, 49, and present our observations. 

Keywords: Shor's algorithm, Oracle, Prime factorization, period-finding problem.

Introduction 

Shor's algorithm is a quantum algorithm designed to find the prime factors of a large integer which is a product of these factors. It is the first quantum that has demonstrated an advantage over its classical counterparts, that allowed one to find the prime decomposition of a large integer, 𝑁, in 𝑂(𝑙𝑜𝑔𝑁)³ time and 𝑂(log 𝑁) space. And this revolutionary result has put the entire network security system under threat as the internet's security relies mainly on the RSA encryption scheme, which involves encryption using a large integer that is a product of two large prime numbers. Consequently, finding the two large prime numbers is essential for decrypting these messages. Since Shor's algorithm takes advantage of properties of quantum superposition, entanglement and interference to find such prime numbers, it is anticipated that it could break RSA encryption much faster and more efficiently than the classical case. However, this goes possible once we have a quantum computer with sufficient qubits capable of withstanding the quantum noise and quantum-decoherence phenomena. 

Attempts made in the direction of implementing Shor's algorithm on the quantum hardware are as follows: Vandersypen et al. factored the number 15 as 3×5 using an NMR (Nuclear magnetic resonance) implementation of the quantum computer using 7 qubits. Later Lu et al. and Lanyon et al. used photonic qubits to run Shor's algorithm circuit and observed the entanglement phenomenon in their implementation. Subsequently, Lucero et al. factorized the number 15 with solid-state qubits. Martin et al. could successfully factorize the number 21 using the concept of qubit recycling. In 2019, Amico et al. attempted to factorize the numbers 15, 21, and 35 using an IBMqx5 chip with 16 superconducting qubits. Their results on period-finding were in excellent agreement with the theoretical results for the number 15 but then slightly deviated for 21. However, the authors reported failure for 35 due to accumulating errors resulting from the increase in the number of two-qubit gates required for the process. Nevertheless, it is anticipated that with efficient quantum hardware, factorizing large numbers using this algorithm would soon be in place. Recently Daniel and Luis presented a strategy to run the algorithm on a classical computer and computed the probability of success of Shor's algorithm. They have reported that the probability of success is at least $1 − \dfrac{1}{2^𝑘}$, where 𝑘 is the number of distinct prime factors that divide 𝑁. 

Continuing the efforts, in the present work, we attempt to implement Shor's algorithm on QISKIT to factorize perfect squares such as 49. The paper is organized as follows: Section A presents the problem statement and the step-by-step procedure to implement the algorithm. Section B presents the implementation part, and the remarks are presented in Section C, followed by conclusions.

Section A: Problem Statement and Methodology

Problem Statement: Given an integer 𝑁 obtained by multiplying two prime numbers 𝑝 and 𝑞, i.e., 𝑁 = 𝑝𝑞, Find 𝑝 and 𝑞. 

Methodology:

Step 1: Reduce the Factor- finding problem 𝑁 = 𝑝𝑞 into a period-finding problem 𝑓(𝑥) = 𝑎^𝑥𝑀𝑜𝑑 𝑁, where 𝑎 is any integer co-prime to 𝑁. 

Step 2: Use Shor's algorithm to find the period '𝑟' of the problem derived in step 1. 

Step 3: If 𝑟 is odd, GOTO step 1 else 

If 𝑟 is even and 𝑎^𝑟/2 ≠ 1 𝑀𝑜𝑑 𝑁 

Use the Euclidean algorithm to find the factors 𝑝 and 𝑞 of 𝑁 given by 

$p, q \in\left\{\begin{array}{l}\operatorname{gcd}\left(a^{\frac{r}{2}}+1, N\right) \\\operatorname{gcd}\left(a^{\frac{r}{2}}-1, N\right)\end{array}\right.$

Section B: Implementation

Algorithm: 

For Step 1: Pick a random number 1 < 𝑎  < 49 

Find if 𝑎 is co-prime to 𝑁 

We took 𝑎 as 19, and thus the equivalent period finding problem is 𝑓(𝑥) = 19^𝑥𝑀𝑜𝑑 49

For Step 2: Design a unitary gate 𝑈. For this, we computed the values of 𝑓(𝑥) for each 𝑥 and presented in Table 1. 

Table 1: Values of the 𝑓(𝑥)

Now, we have to design the unitary gate such that 

𝑈 (1) = 19 

𝑈 (19) = 18 

𝑈 (18) = 48 

𝑈 (48) = 30 

𝑈 (30) = 31 

𝑈 (31) = 1 

This part of the work is crucial for going further to the next steps. As such, it was not easy to design a gate with this definition; hence, we used the properties of the congruence modulo operator to rewrite the definition of the unitary gate and presented it in Table 2. 

Table 2: Values of the 𝑓(𝑥) used to design U

Using this definition, we have designed the unitary gate 𝑈. A snapshot of the quantum circuit is in Fig 1. 

Fig 1. Code to generate the unitary gate U

In Fig. 2, we see the output of the circuit when the input number is 18. Since quantum computers cannot identify the global phase, the output is 1 instead of -1. Thus, when we find the period using Shor's algorithm, it has to be taken twice the output.

Fig 2. Output of the circuit when the input is 18. 

The next step is implementing Shor's algorithm, shown in the following circuit, Fig. 3. 

Fig 3. Circuit to implement Shor's algorithm

The output of the code is shown in Fig. 4 below. We understand that the period is '3', which occurs with a probability near 0.5, in tune with the remarks noted by Daniel and Luis. that "the probability of success is at least $1 − \dfrac{1}{2^𝑘}$, 𝑘 is the number of distinct prime factors that divide 𝑁". It is to be noted that the period for the present problem is 𝑟 = 6.

Fig 4. Output of the Shor's algorithm

Step 3: Use the Euclidean algorithm to find the factors 49. Fig 5 shows that output. 

Fig 5. Output of Euclidean algorithm

• a is 19
• N is 49
• 6 is the period

to check if 𝑎^𝑟/2 = 1 𝑀𝑜𝑑 𝑁, and should not be +1 here ans = 1

We may not get distinct factors!

Finding the prime factors

49 1.0 are the prime factors

We see that through 𝑟 is even, since 𝑎^𝑟/2 = 1 𝑀𝑜𝑑 𝑁, the output is 49 and 1 in place of 7 and 7.

Section C: Remarks

Thus, the above process was not successful in factorizing 49. Hence we tried repeating the algorithm on the classical computer and found another 𝑎 that gave an even period.

Fig 6. Output of classical algorithm for a = 13

• a is 13
• N is 49
• 14 is the period

to check if 𝑎^𝑟/2 = 1 𝑀𝑜𝑑 𝑁, and should not be +1 here ans = 1

We may not get distinct factors!

Finding the prime factors

49 1.0 are the prime factors

Yet again, the attempt was unsuccessful. The process was repeated for 𝑎 = 3, 5, 6, 10, 17, 21, 24, 13, 19, 20, 34, 41, for which 𝑓(𝑥) has an even period. But in all these cases, as before, it turned out to be, 𝑎^𝑟/2 = 1 𝑀𝑜𝑑 𝑁. Thus, we conclude that Shor's algorithm could not provide factors for 49 for any choice of 𝑎 that is a co-prime. It made us work on other perfect squares of primes 9 and 25, where, as before, we converted the factor-finding problem to the period- finding one and presented the values of the function 𝑓(𝑥) for a chosen 𝑎 in Tables 3 and 4. (The number in the bracket results from applying modular arithmetic). 

Table 3: Values of the 𝑓(𝑥) = 2^𝑥𝑀𝑜𝑑 9

Table 4: Values of the 𝑓(𝑥) = 7^𝑥𝑀𝑜𝑑 25

Here again, we observed a unique behaviour of the function 𝑓(𝑥); out of the entire set of values, it assumed the first half of them are simply the negative of the other half occurring in the same sequence. This pattern specific to perfect squares of primes motivated us to extend Shor's algorithm to identify such numbers. 

As per Shor's algorithm presented in Section A, we understand that if the period of 𝑓(𝑥) is an odd number, we have to go back to step 1, where we identify another integer 𝑎 that is co-prime to 𝑁 and repeat steps 2 and 3. However, in the proposed algorithm, if the period 𝑟 is odd, we see if 𝑎^𝑟 = −1 𝑀𝑜𝑑 𝑁. If this expression is true, we conclude that the given number is a perfect square of primes; otherwise, we go back to step 1. 

Noting from the results presented in Section B and Tables 3 and 4, the period obtained by implementing Shor's algorithm with the designed oracle is always odd for a perfect square (of prime numbers).

Shor's Algorithm to Check if N is the Square of a Prime Number

Fig 7. Flow chart to check if N is a perfect square or not

Conclusions:

In this paper, we implemented Shor's algorithm for factorizing 49 and inferred it to be unsuitable for this number. It is because the algorithm has been proposed for the specific purpose of factorizing a number that is a product of two distinct prime numbers. However, on noting the unique pattern exhibited by the function 𝑓(𝑥) = 𝑎^𝑥𝑀𝑜𝑑 𝑁 for 𝑁, which is a perfect square of primes, we proposed an extension of Shor's algorithm for the present problem. We trust this work would attract the quantum computing fraternity for the following reasons: Though we find excellent classical algorithms of complexity 𝑂(log 𝑁) for the problem of identifying perfect squares, we believe that our work primarily recognized the competency of Shor's algorithm in solving two different problems, the factor-finding and the perfect square identification problems. Though designed for the first problem, the solution to the second could be achieved with only a few additional steps in the original algorithm with no added time complexity. On the other hand, in the classical world, the factor-finding problem has an exponential time complexity; also, we believe that no single algorithm solves these two problems as elegantly as Shor's.

Source: Radhika T.S.L. and Raja R.T., https://assets.researchsquare.com/files/rs-2564168/v1_covered_b3c6e796-cbcd-48fd-959f-95f2f6155bce.pdf?c=1693489952
This work is licensed under a Creative Commons Attribution 4.0 License.