Table of Contents
- Introduction
- Background: Integer Factorization Problem
- Classical Complexity
- Quantum Advantage and Shor’s Breakthrough
- Problem Statement
- High-Level Overview of Shor’s Algorithm
- Mathematical Foundations
- Role of Modular Arithmetic
- Reduction to Order Finding
- Quantum Order Finding Subroutine
- Phase Estimation Connection
- Quantum Circuit Layout
- Initialization and Superposition
- Modular Exponentiation Circuit
- Quantum Fourier Transform (QFT)
- Measurement and Period Extraction
- Classical Post-Processing
- Finding Factors from the Period
- Example: Factoring 15
- Success Probability and Repetition
- Assumptions and Oracle Use
- Practical Challenges
- Impact on Cryptography (RSA)
- Experimental Implementations
- 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:
- 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
- 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
- Hadamard gates on input register
- Modular exponentiation as a controlled operation
- Inverse QFT
- 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.
.
