Skip to content

Shors algo

Key Steps in Shor’s Algorithm

The process of Shor's algorithm can be divided into the following steps:

Step 1: Choose the Integer to Factor (N)

  • Select the composite integer \( N \) you want to factor.
  • For example, let \( N = 15 \). Your goal is to find its prime factors.

Step 2: Choose a Random Integer (a)

  • Select a random integer \( a \) in the range \( [2, N-2] \).
  • Example: Choose \( a = 7 \) for \( N = 15 \).

Step 3: Calculate the Greatest Common Divisor (GCD)

  • Compute \( \text{GCD}(a, N) \) using the Euclidean algorithm.
  • If \( \text{GCD}(a, N) > 1 \), \( a \) is already a factor. Otherwise, proceed.
  • Example: For \( a = 7 \) and \( N = 15 \), \( \text{GCD}(7, 15) = 1 \), so we continue.

Step 4: Initialize Quantum Registers

  • Prepare two quantum registers:
  • Register 1: Encodes the potential periods \( x \).
  • Register 2: Stores results of modular exponentiation.

Step 5: Quantum Period Finding

This step is the heart of Shor's algorithm and is achieved through quantum computation.

  1. Superposition Creation: Create a superposition of all possible \( x \) values in the first register: \([|x\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle]\)

  2. Modular Exponentiation (Oracle): Compute \( a^x \mod N \) and store the results in the second register.

  3. Quantum Fourier Transform (QFT): Apply the QFT to the first register. The QFT identifies the periodicity \( r \) of the function \( f(x) = a^x \mod N \).

  4. Period \( r \): The QFT yields the period \( r \), the smallest integer such that \( a^r \mod N = 1 \).

Step 6: Classical Post-Processing

  • Measure the first quantum register to obtain \( r \), a candidate for the period.

Step 7: Compute Factors

  • Use \( r \) to calculate the factors of \( N \):
  • Compute \( \text{GCD}(a^{r/2} - 1, N) \).
  • Compute \( \text{GCD}(a^{r/2} + 1, N) \).

Step 8: Repeat or Output

  • If non-trivial factors are not found, repeat with a different \( a \).
  • Otherwise, output the factors.

3. Example Walkthrough

Factorizing \( N = 15 \):

1. Choose \( N = 15 \), \( a = 7 \):

  • Compute \( \text{GCD}(7, 15) = 1 \).

2. Period Finding:

  • \( 7^0 \mod 15 = 1 \),
  • \( 7^1 \mod 15 = 7 \),
  • \( 7^2 \mod 15 = 4 \),
  • \( 7^3 \mod 15 = 13 \),
  • \( 7^4 \mod 15 = 1 \).
  • Period \( r = 4 \).

3. Classical Post-Processing:

  • Compute \( 7^{4/2} - 1 = 49 - 1 = 48 \).
  • \( \text{GCD}(48, 15) = 3 \).
  • Compute \( 7^{4/2} + 1 = 49 + 1 = 50 \).
  • \( \text{GCD}(50, 15) = 5 \).

4. Factors Found: \( 15 = 3 \times 5 \).