Shor's Algorithm and QPE

With the prerequisites we have learned in previous posts, today we are going to discuss one of the most fundamental and crucial algorithms in quantum computing: Shor's Algorithm. So what makes it special? In brief, it demonstrates that quantum computing can dramatically reduce the time required to solve certain problems, changing the complexity from exponential to polynomial time. Let’s dive in.

Prime Factorization Problem

The heart of Shor's algorithm is that it solves the prime factorization problem. For example, if you are given the numbers 15 and 77, we can easily factor them into primes as:

• $15 \rightarrow 3 \times 5$
• $77 \rightarrow 7 \times 11$

However, if $N=10,670,053$, factoring it into its prime components becomes extremely difficult. This computational difficulty is what makes RSA encryption feasible and secure, provided the numbers are sufficiently large.

Here is the formal definition of the problem:

$$\text{Input:} \quad N, x \in \Z^+, \space x < N, \space gcd(x, N) = 1$$
$$\text{Output:} x^r = 1 \space \text{(mod N)}, \space r \in Z^+$$

Example:

$$N = 15, x = 2$$

$$2^1 = 2, \space 2^2 = 4, \space 2^3 = 8, \space 2^4 = 16 \space \space \text{mod} \space 15 = 1 \rightarrow r = 4$$

In classical computing, this problem requires exponential time, approximately $O(2^{n/2})$ to solve. With Shor’s algorithm, it is reduced to polynomial time, roughly $O(\log N)^3$. This demonstrates just how incredible and powerful quantum computing can be!

Shor's Algorithm

Peter Shor discovered that quantum computers can factor large integers efficiently in 1994. The core idea is to convert the problem into finding the period of a special function. That's it:

Factoring $N$ as:

$$f(x) = a^x \space \text{mod} \space N$$

where $a$ is a random number less than $N$.

If $r$ is found, we compute the factors of $N$ by using:

$$\text{gcd}(a^{r/2} - 1, N), \quad \text{gcd}(a^{r/2} + 1, N)$$

Such $r$ is extremely hard for classical computers to find, but for quantum computers, Quantum Parallelism and Quantum Fourier Transform helps us doing it super fast.

We use the same example to show how Shor's algorithm works.

$$N = 2, \space a = 2, \space f(x) = 2^x \text{mod} \space 15 \rightarrow 4$$

From number theory, we know that $a^r \equiv 1 \text{(mod N)}$ means $a^r - 1$ is divisible by N's factors. Next, $a^{r/2} \ne -1 \text{(mod N)}$,

$$a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1)$$

Above indicates at least one of these two numbers shares a non-trivial common divisor with $N$.

With the example:

$$p = \text{gcd}(2^2 - 1, 15) = \text{gcd}(3, 15) = 3$$
$$q = \text{gcd}(2^2 + 1, 15) = \text{gcd}(5, 15) = 5$$

Factors 3, 5 are found.

Quantum Phase Estimation (Kitaev's Algorithm)

An early quantum phase estimation method that turn the problem of finding a periodic pattern (Shor's Algorithm) into a measurable phase, which can be converted into period. Let's see how it works in detail.

First, why do we need such a method? The reason is that Shor’s algorithm for the period-finding problem can be reformulated as a phase estimation problem. This is precisely where Quantum Phase Estimation (QPE) becomes essential.

Here’s the formal problem definition:

Suppose:

• A unitary operator $U$
• An eigenvector $\lvert \psi \rangle$ with eigenvalue $e^{2πi\theta}$ where $\theta \in [0, 1)$

We want to find θ to high precision, meaning we aim to determine the number between 0 and 1 that appears in the complex eigenvalue of a quantum operation, accurate to the desired number of decimal places.

Phase

$$U\lvert \psi \rangle = e^{2πi\theta}\lvert \psi \rangle$$

The eigenvalue lies on the unit circle in the complex plane.

• $\theta = 0.25 \rightarrow 90°$
• $\theta = 0.50 \rightarrow 180°$
• $\theta = 0.75 \rightarrow 270°$

However, if $\theta = \dfrac{3}{7} \approx 0.428571$, if measurement give 0.43, one might think $\theta \approx \dfrac{3}{7}$ or $\dfrac{6}{14}$, this is ambiguous.

This is what QPE wants to solve. It works as follows:

• Quantum Control: apply controlled versions of $U, U^2, U^4, \cdots$
• Interference: encode $\theta$ into measurable qubit probabilities
• Classical Post-processing: use repeated measurements and the continued fraction algorithm to get $\theta$ to the required accuracy.

Relationship

$$f(x) = a^x \space \text{mod} \space N \equiv U\lvert y = \lvert ay \space \text{mod} \space N \rangle \equiv U\lvert u_s \rangle = e^{2πi\theta} \lvert u_s \rangle$$

Here is the simplied procedure:

Factor N
↓
Find period r of a^x mod N
↓
Reframe as finding phase θ = s / r of U's eigenvalue
↓
Use Kitaev’s (phase estimation) algorithm to get θ precisely
↓
Use continued fractions to find r
↓
Use GCD trick to get prime factors of N

In brief, such unitary $U$ is used because it is reversible when $\text{gcd}(a, N) = 1$. U has eigenvalues that contain the information
r we need in Shor’s algorithm, and these eigenvalues lie in the complex plane. Therefore, they correspond to rotations around the unit circle with their own period. That is:

$$\lvert y \rangle \xrightarrow{U} \lvert ay \space \text{mod N} \rangle \xrightarrow{U} \lvert a^2y \space \text{mod N} \rangle \rightarrow \cdots$$