The mechanism inside Deutsch, Shor and phase estimation.
Controlled-U is block-diagonal in U's eigenbasis, acting on each eigenspace as a phase gate on the control. The Hadamard test, phase estimation and Shor's order finding are all corollaries. So is a subtle fact: "controlled-U" is not determined by U alone, which is why no circuit can add a control to an unknown black box.
What you’ll learn
Prove the spectral form Λ(U)=∑jP(2πφj)⊗Πj and derive the Hadamard test.
Show that phase estimation implements an approximate projective measurement of U's eigenbasis, with explicit error bounds.
Derive generalized kickback with Fourier states and the eigenstructure behind Shor's order finding.
Explain why Λ(U) depends on U's global phase and prove that controlled versions of unknown unitaries cannot be built by circuits.
Controlled-U in its eigenbasis
So Λ(U) never moves the target between eigenspaces: on each eigenspace it is a phase gate on the control. For an eigenstate the control simply rotates (kickback). For a superposition ∣ψ⟩=∑jcj∣uj⟩ the control becomes entangled with the eigenspace label: Λ(U)∣+⟩∣ψ⟩=∑jcj21(∣0⟩+e2πiφj∣1⟩)∣uj⟩, and the control alone is a mixture of phases.
DerivationThe Hadamard test
∣0⟩∣ψ⟩H21(∣0⟩+∣1⟩)∣ψ⟩Λ(U)21(∣0⟩∣ψ⟩+∣1⟩U∣ψ⟩)
Prepare the ancilla in ∣+⟩ and apply the controlled unitary.
H21∣0⟩(I+U)∣ψ⟩+21∣1⟩(I−U)∣ψ⟩
Interfere the two branches.
P(0)=41∥(I+U)∣ψ⟩∥2=21(1+Re⟨ψ∣U∣ψ⟩)
Expand the norm using unitarity.
insert S† on the ancilla before the last H:P(0)=21(1+Im⟨ψ∣U∣ψ⟩)
The extra −i on the ∣1⟩ branch rotates the real part into the imaginary part.
Estimating ⟨ψ∣U∣ψ⟩ to ±ε costs O(1/ε2) repetitions. With ∣ψ⟩ maximally mixed, the same circuit estimates TrU/2n: the one-clean-qubit model DQC1 (Knill & Laflamme 1998).
Predict before you look
Hadamard test with U=T and ∣ψ⟩=∣+⟩. What is P(0) for the ancilla, in percent?
Show the answer
93 %
⟨+∣T∣+⟩=21(1+eiπ/4), with real part 21(1+21)≈0.854. So P(0)=21(1+0.854)≈0.927.
Phase estimation as a measurement of U
By linearity, for an input ∑jcj∣uj⟩ the outcome distribution is the mixture ∑j∣cj∣2∣Ft(φj−m/2t)∣2, and after observing m the target is (approximately) projected onto eigenvectors with φj≈m/2t. As t grows, phase estimation becomes a von Neumann measurement of U's eigenbasis, reporting the eigenphase as its outcome.
For ground-state energy estimation this means the success probability is ∣c0∣2=∣⟨u0∣ψ⟩∣2. Phase estimation is only as good as the trial state, and preparing states with large ground-state overlap is not possible in general: the local Hamiltonian problem is QMA-complete.
Check your understanding
You run phase estimation with many counting qubits on the target 0.7∣u0⟩+0.3∣u1⟩, where the eigenphases φ0,φ1 are well separated. What happens?
You always obtain the average phase 0.7φ0+0.3φ1
You obtain ≈φ0 with probability 0.7 or ≈φ1 with probability 0.3, and the target collapses to the corresponding eigenvector
The outputs are uniformly random because the target is not an eigenstate
You obtain both phases at once in the counting register
Show the answer
B. You obtain ≈φ0 with probability 0.7 or ≈φ1 with probability 0.3, and the target collapses to the corresponding eigenvector
Phase estimation is linear: each eigencomponent produces its own peak, weighted by ∣cj∣2. Measuring the register selects one peak and leaves the target in (approximately) the matching eigenvector.
Generalized kickback and order finding
DerivationFourier states diagonalize addition (Cleve, Ekert, Macchiavello & Mosca 1998)
∣s^⟩=M1y=0∑M−1e−2πisy/M∣y⟩,Xa∣y⟩=∣y+amodM⟩
Fourier states of ZM and the shift operator.
Xa∣s^⟩=M1y′∑e−2πis(y′−a)/M∣y′⟩=e2πisa/M∣s^⟩
Substitute y′=y+a. Every shift has every Fourier state as an eigenvector.
The Fourier states of the cycle are eigenvectors, by the same shift argument.
r1s=0∑r−1∣us⟩=∣1⟩
The easy input ∣1⟩ is a uniform superposition of eigenvectors, so phase estimation on ∣1⟩ returns s/r for a uniformly random s.
Λ(Ua2j) is controlled multiplication by a2jmodN, precomputed classically by repeated squaring, so all controlled powers cost poly(logN) gates. Continued fractions recover r from s/r whenever gcd(s,r)=1, which happens with probability Ω(1/loglogr).
Controlled-U is not a function of U
Physically, U and eiαU are the same operation. Their controlled versions are not:
Λ(eiαU)=(P(α)⊗I)Λ(U).
The global phase of U becomes a relative phase on the control. Every kickback algorithm therefore relies on a specific, fixed choice of phase for U, usually supplied by an explicit gate decomposition.
Key takeaways
Λ(U)=∑jP(2πφj)⊗Πj: a controlled unitary is a phase gate on the control within each eigenspace of U.
The Hadamard test estimates Re and Im of ⟨ψ∣U∣ψ⟩ with O(1/ε2) repetitions; phase estimation measures U's eigenbasis with Heisenberg-scaling cost.
Fourier states turn addition oracles into phase oracles, and order finding is phase estimation of modular multiplication on ∣1⟩=r1∑s∣us⟩.
Λ(eiαU)=(P(α)⊗I)Λ(U), so controlled versions of unknown black boxes cannot be built by circuits.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
In the Hadamard test with U=S and ∣ψ⟩=∣+⟩, what is the probability that the ancilla reads 0?
21
43
1
42+2
Show the answer
B.43
⟨+∣S∣+⟩=21(1+i), so Re=21 and P(0)=21(1+21)=43. (With an S† inserted, the same probability would report Im=21.)
Question 2
How is Λ(eiαU) related to Λ(U)?
They are equal
Λ(eiαU)=eiαΛ(U)
Λ(eiαU)=(P(α)⊗I)Λ(U)
Λ(eiαU)=(I⊗P(α))Λ(U)
Show the answer
C.Λ(eiαU)=(P(α)⊗I)Λ(U)
Only the control's ∣1⟩ branch sees eiα, so the global phase of U becomes the phase gate P(α) on the control.
Question 3
In order finding, phase estimation is run on the target ∣1⟩. What does it return (to t-bit precision)?
s/r for a uniformly random s∈{0,…,r−1}
1/r every time
The order r directly
a/N
Show the answer
A.s/r for a uniformly random s∈{0,…,r−1}
∣1⟩=r1∑s∣us⟩ is a uniform superposition of eigenvectors with phases s/r, so each run samples one s/r; continued fractions then extract r.
Question 4
When φ has no exact t-bit expansion, what lower bound holds for the probability that QPE outputs the nearestt-bit value?
1/2t
8/π2
1−2−t
4/π2
Show the answer
D.4/π2
With ∣2tδ∣≤21, ∣Ft(δ)∣2≥sin2(π2tδ)/(π2tδ)2≥4/π2≈0.405, with the worst case halfway between grid points.
Further reading
R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339 (1998).
A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem", arXiv:quant-ph/9511026 (1995).
P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Comput. 26, 1484 (1997).
M. Araújo, A. Feix, F. Costa & Č. Brukner, "Quantum circuits cannot control unknown operations", New J. Phys. 16, 093026 (2014).
E. Knill & R. Laflamme, "Power of one bit of quantum information", Phys. Rev. Lett. 81, 5672 (1998).