Shor’s Factoring Algorithm

Table of Contents

1. Introduction
2. Background: Integer Factorization Problem
3. Classical Complexity
4. Quantum Advantage and Shor’s Breakthrough
5. Problem Statement
6. High-Level Overview of Shor’s Algorithm
7. Mathematical Foundations
8. Role of Modular Arithmetic
9. Reduction to Order Finding
10. Quantum Order Finding Subroutine
11. Phase Estimation Connection
12. Quantum Circuit Layout
13. Initialization and Superposition
14. Modular Exponentiation Circuit
15. Quantum Fourier Transform (QFT)
16. Measurement and Period Extraction
17. Classical Post-Processing
18. Finding Factors from the Period
19. Example: Factoring 15
20. Success Probability and Repetition
21. Assumptions and Oracle Use
22. Practical Challenges
23. Impact on Cryptography (RSA)
24. Experimental Implementations
25. Conclusion

---

1. Introduction

Shor’s Algorithm, developed by Peter Shor in 1994, is a quantum algorithm for integer factorization. It revolutionized cryptography by demonstrating that quantum computers can solve problems in polynomial time that are intractable for classical computers.

---

2. Background: Integer Factorization Problem

Given an integer \( N \), the task is to find its non-trivial prime factors. For large \( N \), such as those used in RSA encryption, no efficient classical algorithm is known.

---

3. Classical Complexity

The best-known classical algorithms for factoring, such as the General Number Field Sieve, operate in sub-exponential time:

\[
\exp\left((\log N)^{1/3}(\log \log N)^{2/3}\right)
\]

---

4. Quantum Advantage and Shor’s Breakthrough

Shor’s algorithm can factor integers in polynomial time:

\[
\mathcal{O}((\log N)^2 (\log \log N)(\log \log \log N))
\]

This poses a serious threat to RSA encryption.

---

5. Problem Statement

Given a composite number \( N \), find a pair of non-trivial factors \( p, q \) such that \( N = p \cdot q \).

---

6. High-Level Overview of Shor’s Algorithm

The algorithm has two parts:

1. Classical Part:

• Randomly select an integer \( a \)
• Use quantum subroutine to find the order \( r \) of \( a \mod N \)
• Use \( r \) to compute non-trivial factors

1. Quantum Part:

• Find the period \( r \) of the function \( f(x) = a^x \mod N \) using a quantum circuit

---

7. Mathematical Foundations

The algorithm uses properties of periodicity:

• \( f(x) = a^x \mod N \) is periodic with period \( r \)
• If \( r \) is even and \( a^{r/2} \not\equiv -1 \mod N \), then:
  \[
  \gcd(a^{r/2} \pm 1, N)
  \]
  gives a non-trivial factor of \( N \)

---

8. Role of Modular Arithmetic

All calculations are modulo \( N \), especially the function \( f(x) = a^x \mod N \), which is efficiently implementable on a quantum circuit.

---

9. Reduction to Order Finding

The key insight is: factoring reduces to finding the order \( r \), the smallest integer such that:

\[
a^r \equiv 1 \mod N
\]

Quantum computers can find this efficiently using phase estimation.

---

10. Quantum Order Finding Subroutine

To find \( r \), use two registers:

• First register: holds input superposition \( |x\rangle \)
• Second register: holds \( a^x \mod N \)

Compute:

\[
\frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |a^x \mod N\rangle
\]

---

11. Phase Estimation Connection

Apply Quantum Fourier Transform (QFT) to the input register. The resulting measurement yields a value close to:

\[
\frac{k}{r}
\]

Use continued fractions to extract \( r \) from the measured result.

---

12. Quantum Circuit Layout

1. Hadamard gates on input register
2. Modular exponentiation as a controlled operation
3. Inverse QFT
4. Measurement of input register

---

13. Initialization and Superposition

Apply Hadamards to create uniform superposition:

\[
\frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle
\]

where \( Q = 2^n \), for some \( n > \log^2 N \)

---

14. Modular Exponentiation Circuit

Controlled unitary gates compute \( a^x \mod N \). These circuits use:

• Controlled multipliers
• Modular adders
• Modular multipliers

---

15. Quantum Fourier Transform (QFT)

The QFT transforms basis states:

\[
|x\rangle \rightarrow \frac{1}{\sqrt{Q}} \sum_{k=0}^{Q-1} e^{2\pi i xk/Q} |k\rangle
\]

Used to extract periodicity encoded in the amplitudes.

---

16. Measurement and Period Extraction

Measure the first register. With high probability, the outcome is close to a rational approximation of \( k/r \). Using continued fractions, we recover \( r \).

---

17. Classical Post-Processing

Once \( r \) is found:

• Check if \( r \) is even
• Compute \( a^{r/2} \)
• Use:
  \[
  \gcd(a^{r/2} \pm 1, N)
  \]
  to get the factors

---

18. Finding Factors from the Period

If \( r \) is valid:
\[
\gcd(a^{r/2} – 1, N) \quad \text{and} \quad \gcd(a^{r/2} + 1, N)
\]
yield the non-trivial divisors.

---

19. Example: Factoring 15

Let \( a = 2 \)

• \( a^1 = 2 \mod 15 \)
• \( a^2 = 4 \)
• \( a^3 = 8 \)
• \( a^4 = 1 \Rightarrow r = 4 \)

\[
a^{r/2} = 2^2 = 4 \Rightarrow \gcd(4 – 1, 15) = 3, \quad \gcd(4 + 1, 15) = 5
\]

Thus, 15 = 3 × 5.

---

20. Success Probability and Repetition

Algorithm may fail if:

• \( r \) is odd
• \( a^{r/2} \equiv -1 \mod N \)

Repeating with different \( a \) increases success probability.

---

21. Assumptions and Oracle Use

• Assumes modular exponentiation is efficiently implementable
• Oracle here is the modular function \( a^x \mod N \)

---

22. Practical Challenges

• Large number of qubits required
• Precision of QFT and modular arithmetic
• Error correction in realistic settings

---

23. Impact on Cryptography (RSA)

RSA’s security is based on factoring being hard classically. Shor’s algorithm shows that with a scalable quantum computer, RSA can be broken.

---

24. Experimental Implementations

Shor’s algorithm has been demonstrated on small numbers (e.g., 15, 21) using:

• Ion trap qubits
• Superconducting circuits
• Photonic systems

But scaling to large \( N \) remains an engineering challenge.

---

25. Conclusion

Shor’s Algorithm represents a pivotal achievement in quantum computing. It offers exponential speedup over classical factoring, has profound implications for modern cryptography, and is a key motivation behind the race to build scalable quantum hardware.

---