This is the eighth post of a series of posts about Quantum Computing with Qiskit. The area is very new and the SDK is changing constantly, but hopefully, the series can help you learn a bit about quantum and help me reinforce a couple concepts.

The goal of this post is to discuss Shor’s algorithm, an algorithm that can factorize big numbers quickly. For an integer \(N\), Shor’s algorithm can find a factor of it in \(O((\log_{} N)^{3})\) which is an almost exponential speedup over classical algorithms. This algorithm brought a lot of interest into building quantum computers, because if an ideal quantum computer could be built, then the widely used public-key cryptography RSA scheme could be broken.

A hybrid algorithm

Shor’s algorithm is hybrid becasuse it mixes a classical part and a quantum part. In this blog post, we will discuss the mathematics behind the classical part and assume the quantum part as a black box. Later on, we will see that the speed up from Shor’s algorithm comes from the quantum part, where it solves the order finding problem i.e. finding the smallest \(r\) such that \(a^{r} \equiv 1 \pmod N\) faster than classical computers.

Firstly, we need to define what the algorithm does. It solves the factorization problem: given an intenger \(N\), find two integers greater than one \(P\) and \(Q\) such that \(PQ = N\), or state that \(N\) is prime.

Secondly, we need to define what the input of the algorithm is: it is \(N\), an odd integer that is neither a prime nor the power of a prime. These assumptions are necessary for the algorithm to work, and when they are not respected factorizing is still easy.

If \(N\) is even, we can pick \(P = 2\) and \(Q = N/2\) so the even case is straightforward.

If \(N\) is prime, we can check with primality tests such as Miller-Rabin’s for primality in a reasonable time complexity so this case is also easier than solving general factorization.

If \(N\) is the power of a prime, we can check for every \(2 \leq k \leq \log_{3}N\) if \(N^{1/k}\) is an integer. If it is, then \(P = N^{1/k}\) and \(Q = N^{(k-1)/k}\) is a solution and the case for powers of primes is solved.

Let’s now analyse the case when \(N\) is odd, not a prime nor the power of a prime that happens on the algorithm.

Math concepts behind Shor’s algorithm

To understand Shor’s algorithm, first we need to review modular arithmetic. We use the quotient-remainder theorem to write :

\[ a = N \cdot k + r \iff a \equiv r \pmod N \iff N \mid (a - r) \]

Then, we need to recall that if \(a\) and \(N\) are coprime, i.e. \(\gcd(a, N) = 1\), there is a number \(r\) such that:

\[ a^{r} \equiv 1 \pmod N \]

Notice that the number \(r\) we defined so far is not unique: for example, if we take \(t = 2r\), then we have \(a^{t} \equiv 1\) as well.

To prove that \(r\) exists, mathematicians generally use \(\phi(N)\), the Euler’s totient function of \(N\). However, for Shor’s algorithm, we are not interested in an arbitrary \(r\): we want to find the smallest \(r\).

Why focus on the smallest \(r\) if it is easy to compute \(\phi(N)\)? The fact is that the smallest \(r\) has a nice property that is key in our analysis. First, let’s rewrite our equation:

\[ a^{r} - 1 \equiv 0 \pmod N \iff \]

\[ (a^{r/2} + 1)(a^{r/2} - 1) \equiv 0 \pmod N \iff \]

\[ N \mid (a^{r/2} + 1)(a^{r/2} - 1) \]

Here, we assumed that \(r\) is even, and that will be a requirement for our algorithm to work. Notice that \(N \nmid (a^{r/2} - 1)\), because that would imply \(a^{r/2} \equiv 1\) and violate our condition that \(r\) was the smallest. Thus, the prime factors of \(N\) are distributed among \(a^{r/2} - 1\) and \(a^{r/2} + 1\).

There are two cases. In the first one, we’re out of luck: if \(N \mid (a^{r/2} + 1)\), then it might be that all the factors are on \(a^{r/2} + 1\) and we can conclude nothing about the prime factorization of \(N\).

In the second case, \(N \nmid (a^{r/2} + 1)\) and we can make a conclusion: because \(N\) divides the product but not the numbers individually, at least one of \(\gcd(N, a^{r/2} + 1)\) or \(\gcd(N, a^{r/2} - 1)\) will be a non trivial factor of \(N\). Our factorization is done.

Thus, if finding \(r\) is done quickly, we can try multiple values for \(a\) until we found one that yields a factor. It can be shown that the probability that \(a\) works is at least \(1/2\), so with few attempts for \(a\) we will find a factor.

Algorithm and quantum subroutine

Given the math concepts behind Shor’s algorithm, we can write the pseudo-code for the algorithm. Notice that in this step we are not worrying about the implementation of other parts of the algorithm: we assume that the classical parts of \(\gcd\), primality-testing, checking if the k-th root is an integer are implemented and available for use. We also assume that the quantum subroutine for period finding is available for use. This yields the code:

def shor_algorithm(N):
    """Returns a pair of integers (P, Q) such that PQ = N for integer N"""

    if N % 2 == 0:  # even case
        return (N//2, 2)  # trivial factorization

    if is_prime(N):  # prime case
        return (N, 1)  # N is prime, factors cannot be found

    if is_power_k(N):  # prime power case
        k = find_power_k(N)  # we find a k such that N**(1/k) is an integer
        P = N**(1/k)
        Q = N//P
        return (P, Q)

    # Now we can assume that the criteria for Shor's algorithm is met

    while True:
        # Non-deterministic, we will try multiple values for a
        a = randint(2, N - 1)  # pick random a

        if gcd(a, N) != 1:  # Lucky case: a and N are not coprime!
            P = gcd(a, N)  # gcd yields a non-trivial factor
            Q = N//P
            return (P, Q)

        r = order_finding(a, N)  # quantum subroutine of the code

        if r % 2 == 0:
            continue  # r is not even, try another value for a

        P = gcd(a**(r//2) - 1, N)
        if P != 1:
            Q = N//P  # gcd yielded non trivial factor
            return (P, Q)

Implementing Shor’s algorithm

We can verify that Shor’s algorithm works using Python and running an experiment: in the Jupyter notebook below, we try to factorize some numbers. Notice that this code does not reach the optimal complexity, because order finding is done with classical computers instead of quantum computers. The code will be refined on the next blog posts.

Next step

The next step is to implement the quantum subroutine for period finding. To find the \(r\) for \(a^{r} \equiv 1 \pmod N\), we will need to learn two new things: the Phase Estimation algorithm and the Quantum Fourier Transform.