7.4 Shor's algorithm: implementation and complexity analysis

Shor's algorithm revolutionizes factoring by using quantum computing to find the period of a function. This quantum approach offers exponential speedup over classical methods, making it possible to factor large numbers efficiently.

The algorithm's implementation involves quantum circuits with two registers and key operations like modular exponentiation and quantum Fourier transform. Its polynomial-time complexity threatens RSA encryption, spurring research into quantum-resistant cryptography.

Shor's Algorithm: Implementation and Complexity Analysis

Steps of Shor's factoring algorithm

1. Choose a random integer $a$ coprime to the composite number $N$ to be factored

2. Use a quantum computer to find the period $r$ of the function $f(x) = a^x \mod N$

   • If $r$ is odd, go back to step 1 and choose a new random integer $a$
   • If $a^{r/2} \equiv -1 \mod N$, go back to step 1 and choose a new random integer $a$

3. Compute $\gcd(a^{r/2} \pm 1, N)$ using the Euclidean algorithm (classical computation)

   • One of these GCDs will be a non-trivial factor of $N$ (e.g., $15$ and $21$ for $N = 315$)

• Shor's algorithm reduces the factoring problem to finding the period of a function $f(x)$
  • Classical part handles the setup and post-processing steps
  • Quantum part finds the period $r$ using quantum Fourier transform (QFT)

Implementation of Shor's algorithm

• Quantum circuit implementation involves two quantum registers
  • First register: $n$ qubits, where $N^2 \leq 2^n < 2N^2$ (e.g., $n = 10$ for $N = 315$)
  • Second register: $m$ qubits to store values of $f(x) = a^x \mod N$
• Apply Hadamard gates to the first register creating a superposition of all possible states
• Apply modular exponentiation operation $U_f$ to compute $f(x)$ and store result in second register
  • $U_f|x\rangle|0\rangle = |x\rangle|a^x \mod N\rangle$
• Apply quantum Fourier transform (QFT) to the first register
• Measure the first register obtaining an approximation of $\frac{s}{r}$, where $s$ is an integer
• Use continued fractions algorithm to find period $r$ from measured value (classical computation)
• QFT is a key component in finding the period $r$ efficiently on a quantum computer

Complexity of Shor's algorithm vs classical

• Shor's algorithm: quantum complexity of $O((\log N)^3)$
  • Polynomial time complexity with respect to input size $\log N$
• Best-known classical factoring algorithms: sub-exponential time complexity
  • General Number Field Sieve (GNFS): $O(e^{(\log N)^{1/3}(\log \log N)^{2/3}})$
  • Quadratic Sieve: $O(e^{(\log N)^{1/2}(\log \log N)^{1/2}})$
• Shor's algorithm provides exponential speedup compared to classical factoring algorithms
  • Makes factoring large numbers feasible on a quantum computer (e.g., 2048-bit RSA moduli)
  • Classical algorithms become impractical for large $N$ due to sub-exponential complexity

Implications for cryptography and RSA

• RSA cryptosystem widely used for secure communication and digital signatures
  • Security relies on difficulty of factoring large composite numbers (e.g., 2048-bit moduli)
• Shor's algorithm, if implemented on a large-scale quantum computer, could break RSA
  • Efficient factoring would render RSA insecure for key sizes used in practice
• Need for post-quantum cryptography resistant to quantum attacks
  • Lattice-based cryptography (e.g., NTRU, LWE-based schemes)
  • Code-based cryptography (e.g., McEliece, BIKE)
  • Multivariate cryptography (e.g., Rainbow, HFE)
• Upgrading existing cryptographic infrastructure to quantum-resistant algorithms
  • Ensuring security of sensitive data and communications in the presence of quantum computers
• Shor's algorithm highlights the potential impact of quantum computing on cryptography
  • Emphasizes the importance of researching and developing post-quantum cryptographic solutions