Questions: Shor's Algorithm

Question 1

Shor's algorithm reduces integer factoring to which mathematical problem that a quantum computer can solve efficiently?

• A. Discrete logarithm over finite fields
• B. Finding the period of modular exponentiation f(x) = a^x mod N
• C. Computing the greatest common divisor of two numbers
• D. Solving systems of linear equations modulo N

Answer: (B)

The key insight is that factoring can be reduced to order finding (period finding): the period r of f(x) = a^x mod N gives a^r = 1 (mod N), from which gcd(a^(r/2) +/- 1, N) often yields a nontrivial factor. The quantum part efficiently finds r using the quantum Fourier transform applied to the periodic state created by modular exponentiation. GCD computation is classical and already efficient (Euclidean algorithm); the hard part that requires a quantum computer is finding r.

Question 2

Shor's algorithm always succeeds in factoring N on the first attempt.

• T. True
• F. False

Answer: False

The algorithm is probabilistic. Several things can go wrong: the random a might share a factor with N (easy case, but rare), the period r might be odd, or a^(r/2) might equal -1 (mod N). In these cases, the attempt fails and you retry with a different random a. Each attempt has at least a constant probability of success, so O(1) repetitions suffice to factor N with high probability. The quantum subroutine (period finding) also has a small failure probability from the QFT measurement.

Question 3

Explain why the quantum Fourier transform is essential to Shor's algorithm. What does the state look like before and after the QFT, and how does the measurement outcome reveal the period?

Model answer: After modular exponentiation, the first register is in a periodic superposition with period r (states at x_0, x_0+r, x_0+2r, ...). The QFT converts this periodic state into one with amplitude peaks at multiples of 2^n/r. Measuring gives a random value close to some multiple c * 2^n/r. From the ratio c/2^n, the continued fraction algorithm extracts r. Without the QFT, the periodic structure would be hidden in the amplitudes and inaccessible through direct measurement.

The QFT is performing Fourier analysis of the periodic quantum state. Just as the classical Fourier transform of a periodic signal has peaks at the signal's frequency, the QFT maps a state periodic in the computational basis to one with peaks in the Fourier basis. The measurement samples from these peaks, and classical post-processing (continued fractions) recovers the frequency — which is the period r. This is the same pattern as Simon's algorithm but over the cyclic group Z_N rather than Z_2^n.