QPE uses a register of n ancilla qubits initialized in superposition, each controlling a different power of U (U^1, U^2, U^4, ..., U^(2^(n-1))). Why are powers of 2 used?
APowers of 2 are computationally cheaper than other powers
BThe binary encoding means the j-th qubit picks up phase 2^j * phi, which the inverse QFT decodes into the binary representation of phi
COnly powers of 2 are implementable on quantum hardware
DThe algorithm works with any powers; powers of 2 are an arbitrary convention
The j-th control qubit, when in state |1>, applies U^(2^j), which maps |u> to e^(2*pi*i*2^j*phi)|u>. This means the j-th qubit acquires phase 2^j * phi — exactly the j-th bit's contribution to the binary expansion of phi. The inverse QFT then converts these phases into the binary representation of phi in the ancilla register. The powers of 2 are structurally necessary for the QFT to decode the phase into a bit string.
Question 2 True / False
If phi is not exactly representable in n bits, QPE still outputs the correct value with probability 1.
TTrue
FFalse
Answer: False
When phi is not an exact n-bit fraction, the inverse QFT produces a probability distribution peaked near the closest n-bit approximation of phi, but there is nonzero probability of getting neighboring values. The probability of getting the best n-bit approximation is at least 4/pi^2 ≈ 0.405. Using a few extra qubits and rounding, you can boost the success probability to 1 - epsilon for any desired epsilon.
Question 3 Short Answer
Explain how QPE connects to Shor's algorithm — specifically, what is the unitary U and what is the eigenvalue phase phi in the factoring context?
Think about your answer, then reveal below.
Model answer: In Shor's algorithm, U is the modular multiplication operator U|x> = |ax mod N>, and the eigenvalue phases are phi_s = s/r, where r is the order of a modulo N and s ranges from 0 to r-1. QPE estimates phi_s, giving a fraction close to s/r, from which r is extracted via the continued fraction algorithm. The period-finding step of Shor's algorithm is exactly a QPE applied to the modular exponentiation unitary.
The eigenstates of U|x> = |ax mod N> are |u_s> = (1/sqrt(r)) sum_{k=0}^{r-1} e^(-2*pi*i*s*k/r) |a^k mod N>, with eigenvalues e^(2*pi*i*s/r). QPE applied to U with input |1> (which is a superposition of the |u_s> states) yields a random s/r, from which r is recovered. This reframing of Shor's algorithm through QPE clarifies that factoring is fundamentally an eigenvalue estimation problem.