Shor's Algorithm

RSA starts by multiplying two primes. For a toy example, choose p = 5 and q = 11, so N = p * q = 55. The totient function counts the numbers below N that are coprime to N. For two primes, phi(N) = (p - 1)(q - 1), so phi(55) = 40.

GCD means greatest common divisor: the biggest whole number that divides two numbers. If gcd(e, phi(N)) = 1, then e works as the public exponent. Then d is the inverse of e modulo phi(N), which means e * d leaves remainder 1 when divided by phi(N).

p = 5, q = 11
N = p * q = 55
phi(N) = (p - 1)(q - 1) = 4 * 10 = 40
choose e = 3 because gcd(3, 40) = 1
find d so e * d = 1 mod 40
d = 27 because 3 * 27 = 81 = 1 mod 40
public key:  (N, e) = (55, 3)
private key: (N, d) = (55, 27)

Once the period r is even, compute a^(r/2). Then compare that number one step below and one step above against N using gcd. In the N = 15 example, the period is r = 4, so a^(r/2) = 2^2 = 4. The gcd calls reveal the factors.

a^(r/2) = 2^(4/2) = 2^2 = 4
gcd(4 - 1, 15) = gcd(3, 15) = 3
gcd(4 + 1, 15) = gcd(5, 15) = 5
factors found: 3 and 5

The R_theta gate changes the phase between |0> and |1>. It leaves the |0> part alone, but rotates the |1> part by an angle theta. That relative phase is one of the special things about qubits: amplitudes are not just amounts, they also carry wave-like direction.

A useful analogy is sound. When the peaks of a bass line and a drum hit line up, the sound can feel stronger. When waves are out of phase, they can partially cancel and feel weaker. Quantum algorithms use this same kind of constructive and destructive behavior, but with probability amplitudes.

R_theta(alpha|0> + beta|1>)
  = alpha|0> + e^(i theta) beta|1>

theta changes the relative phase between the two parts.
Later, good phases line up; bad phases cancel.

Start with |00>
Apply H to the first qubit:
(|00> + |10>) / sqrt(2)
Apply CNOT with first qubit as control:
(|00> + |11>) / sqrt(2)
This is a Bell state.

In the Shor toy example, the first register stores x. The second register stores the function value 2^x mod 15. Once the function is computed, the registers are entangled: knowing the second register narrows down which x values could be in the first register.

first register:  x
second register: f(x) = 2^x mod 15

x =  0 (0000): 2^0 mod 15 = 1 (0001)
x =  1 (0001): 2^1 mod 15 = 2 (0010)
x =  2 (0010): 2^2 mod 15 = 4 (0100)
x =  3 (0011): 2^3 mod 15 = 8 (1000)
x =  4 (0100): 2^4 mod 15 = 1 (0001)
x =  5 (0101): 2^5 mod 15 = 2 (0010)
x =  6 (0110): 2^6 mod 15 = 4 (0100)
x =  7 (0111): 2^7 mod 15 = 8 (1000)
x =  8 (1000): 2^8 mod 15 = 1 (0001)
x =  9 (1001): 2^9 mod 15 = 2 (0010)
x = 10 (1010): 2^10 mod 15 = 4 (0100)
x = 11 (1011): 2^11 mod 15 = 8 (1000)
x = 12 (1100): 2^12 mod 15 = 1 (0001)
x = 13 (1101): 2^13 mod 15 = 2 (0010)
x = 14 (1110): 2^14 mod 15 = 4 (0100)
x = 15 (1111): 2^15 mod 15 = 8 (1000)

If you measure the second register, you only see one of four values: 0001, 0010, 0100, or 1000. Once that happens, the first register collapses to the matching x values. Those surviving x values are spaced by 4, which is the period.

measure second register = |0001>
first register left alive: |0> + |4> + |8> + |12>

measure second register = |0010>
first register left alive: |1> + |5> + |9> + |13>

measure second register = |0100>
first register left alive: |2> + |6> + |10> + |14>

measure second register = |1000>
first register left alive: |3> + |7> + |11> + |15>

Each row is a comb with spacing 4.

The quantum Fourier transform is a quantum operator: a unitary matrix, just like the gates above. It is the DFT matrix acting on amplitudes. The QFT changes a state from a signal-like view into a frequency-like view, so periodic structure shows up as peaks.

Generic QFT formula:
QFT_N |x> = (1 / sqrt(N)) sum_{y=0}^{N-1} e^(2 pi i x y / N) |y>

For the 4 x 4 case:
QFT_4 |x> = (1 / 2) sum_{y=0}^{3} e^((i pi / 2) x y) |y>

Same idea: signal pattern in, frequency peaks out.