Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Eigenvalue Kickback & Controlled Unitaries

The mechanism inside Deutsch, Shor and phase estimation.

Controlled-UU is block-diagonal in UU'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-UU" is not determined by UU 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\Lambda(U) = \sum_j P(2\pi\varphi_j)\otimes\Pi_j and derive the Hadamard test.
  • Show that phase estimation implements an approximate projective measurement of UU's eigenbasis, with explicit error bounds.
  • Derive generalized kickback with Fourier states and the eigenstructure behind Shor's order finding.
  • Explain why Λ(U)\Lambda(U) depends on UU's global phase and prove that controlled versions of unknown unitaries cannot be built by circuits.

Controlled-U in its eigenbasis

So Λ(U)\Lambda(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⟩\ket{\psi} = \sum_j c_j\ket{u_j} the control becomes entangled with the eigenspace label: Λ(U)∣+⟩∣ψ⟩=∑jcj 12(∣0⟩+e2πiφj∣1⟩)∣uj⟩\Lambda(U)\ket{+}\ket{\psi} = \sum_j c_j\,\tfrac{1}{\sqrt2}(\ket0 + e^{2\pi i\varphi_j}\ket1)\ket{u_j}, and the control alone is a mixture of phases.

DerivationThe Hadamard test
  1. ∣0⟩∣ψ⟩ →H 12(∣0⟩+∣1⟩)∣ψ⟩ →Λ(U) 12(∣0⟩∣ψ⟩+∣1⟩U∣ψ⟩)\ket{0}\ket{\psi}\ \xrightarrow{H}\ \tfrac{1}{\sqrt2}\big(\ket0 + \ket1\big)\ket\psi\ \xrightarrow{\Lambda(U)}\ \tfrac{1}{\sqrt2}\big(\ket0\ket\psi + \ket1 U\ket\psi\big)

    Prepare the ancilla in ∣+⟩\ket{+} and apply the controlled unitary.

  2. →H 12∣0⟩(I+U)∣ψ⟩+12∣1⟩(I−U)∣ψ⟩\xrightarrow{H}\ \tfrac12\ket0\big(\id + U\big)\ket\psi + \tfrac12\ket1\big(\id - U\big)\ket\psi

    Interfere the two branches.

  3. P(0)=14∥(I+U)∣ψ⟩∥2=12(1+Re ⟨ψ|U|ψ⟩)P(0) = \tfrac14\norm{(\id + U)\ket\psi}^2 = \tfrac12\Big(1 + \mathrm{Re}\,\mel{\psi}{U}{\psi}\Big)

    Expand the norm using unitarity.

  4. insert S† on the ancilla before the last H:P(0)=12(1+Im ⟨ψ|U|ψ⟩)\text{insert } S^\dagger \text{ on the ancilla before the last } H:\quad P(0) = \tfrac12\Big(1 + \mathrm{Im}\,\mel{\psi}{U}{\psi}\Big)

    The extra −i-i on the ∣1⟩\ket{1} branch rotates the real part into the imaginary part.

  5. Estimating ⟨ψ|U|ψ⟩\mel{\psi}{U}{\psi} to ±ε\pm\varepsilon costs O(1/ε2)\order{1/\varepsilon^2} repetitions. With ∣ψ⟩\ket{\psi} maximally mixed, the same circuit estimates Tr⁡U/2n\Tr U/2^n: the one-clean-qubit model DQC1 (Knill & Laflamme 1998).

Predict before you look

Hadamard test with U=TU = T and ∣ψ⟩=∣+⟩\ket{\psi} = \ket{+}. What is P(0)P(0) for the ancilla, in percent?

Show the answer

93 %

⟨+|T|+⟩=12(1+eiπ/4)\mel{+}{T}{+} = \tfrac12(1 + e^{i\pi/4}), with real part 12(1+12)≈0.854\tfrac12(1 + \tfrac{1}{\sqrt2}) \approx 0.854. So P(0)=12(1+0.854)≈0.927P(0) = \tfrac12(1 + 0.854) \approx 0.927.

Phase estimation as a measurement of U

By linearity, for an input ∑jcj∣uj⟩\sum_j c_j\ket{u_j} the outcome distribution is the mixture ∑j∣cj∣2∣Ft(φj−m/2t)∣2\sum_j \abs{c_j}^2\abs{F_t(\varphi_j - m/2^t)}^2, and after observing mm the target is (approximately) projected onto eigenvectors with φj≈m/2t\varphi_j \approx m/2^t. As tt grows, phase estimation becomes a von Neumann measurement of UU's eigenbasis, reporting the eigenphase as its outcome.

For ground-state energy estimation this means the success probability is ∣c0∣2=∣⟨u0∣ψ⟩∣2\abs{c_0}^2 = \abs{\braket{u_0|\psi}}^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⟩\sqrt{0.7}\,\ket{u_0} + \sqrt{0.3}\,\ket{u_1}, where the eigenphases φ0,φ1\varphi_0, \varphi_1 are well separated. What happens?

  1. You always obtain the average phase 0.7φ0+0.3φ10.7\varphi_0 + 0.3\varphi_1
  2. You obtain ≈φ0\approx\varphi_0 with probability 0.70.7 or ≈φ1\approx\varphi_1 with probability 0.30.3, and the target collapses to the corresponding eigenvector
  3. The outputs are uniformly random because the target is not an eigenstate
  4. You obtain both phases at once in the counting register
Show the answer

B. You obtain ≈φ0\approx\varphi_0 with probability 0.70.7 or ≈φ1\approx\varphi_1 with probability 0.30.3, and the target collapses to the corresponding eigenvector

Phase estimation is linear: each eigencomponent produces its own peak, weighted by ∣cj∣2\abs{c_j}^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)
  1. ∣s^⟩=1M∑y=0M−1e−2πisy/M∣y⟩,Xa∣y⟩=∣y+a mod M⟩\ket{\hat s} = \frac{1}{\sqrt M}\sum_{y=0}^{M-1}e^{-2\pi i sy/M}\ket{y}, \qquad X_a\ket{y} = \ket{y + a \bmod M}

    Fourier states of ZM\Z_M and the shift operator.

  2. Xa∣s^⟩=1M∑y′e−2πis(y′−a)/M∣y′⟩=e2πisa/M∣s^⟩X_a\ket{\hat s} = \frac{1}{\sqrt M}\sum_{y'}e^{-2\pi i s(y'-a)/M}\ket{y'} = e^{2\pi i sa/M}\ket{\hat s}

    Substitute y′=y+ay' = y + a. Every shift has every Fourier state as an eigenvector.

  3. Uf∣x⟩∣s^⟩=e2πisf(x)/M∣x⟩∣s^⟩,Uf∣x⟩∣y⟩=∣x⟩∣y+f(x)⟩U_f\ket{x}\ket{\hat s} = e^{2\pi i s f(x)/M}\ket{x}\ket{\hat s}, \qquad U_f\ket{x}\ket{y} = \ket{x}\ket{y + f(x)}

    A modular-addition oracle becomes a phase oracle. For M=2M = 2 and s=1s = 1, ∣1^⟩=∣−⟩\ket{\hat 1} = \ket{-} recovers Deutsch's trick.

DerivationThe eigenstructure behind Shor's algorithm
  1. Ua∣y⟩=∣ay mod N⟩,gcd⁡(a,N)=1,r=ord⁡N(a)U_a\ket{y} = \ket{ay \bmod N}, \qquad \gcd(a, N) = 1,\quad r = \operatorname{ord}_N(a)

    Multiplication by aa permutes the cycle 1,a,a2,…,ar−11, a, a^2, \dots, a^{r-1}.

  2. ∣us⟩=1r∑k=0r−1e−2πisk/r∣ak mod N⟩,Ua∣us⟩=e2πis/r∣us⟩\ket{u_s} = \frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi i sk/r}\ket{a^k \bmod N}, \qquad U_a\ket{u_s} = e^{2\pi i s/r}\ket{u_s}

    The Fourier states of the cycle are eigenvectors, by the same shift argument.

  3. 1r∑s=0r−1∣us⟩=∣1⟩\frac{1}{\sqrt r}\sum_{s=0}^{r-1}\ket{u_s} = \ket{1}

    The easy input ∣1⟩\ket{1} is a uniform superposition of eigenvectors, so phase estimation on ∣1⟩\ket{1} returns s/rs/r for a uniformly random ss.

  4. Λ(Ua2j)\Lambda(U_a^{2^j}) is controlled multiplication by a2j mod Na^{2^j} \bmod N, precomputed classically by repeated squaring, so all controlled powers cost poly⁡(log⁡N)\poly(\log N) gates. Continued fractions recover rr from s/rs/r whenever gcd⁡(s,r)=1\gcd(s, r) = 1, which happens with probability Ω(1/log⁡log⁡r)\Omega(1/\log\log r).

Controlled-U is not a function of U

Physically, UU and eiαUe^{i\alpha}U are the same operation. Their controlled versions are not:

Λ(eiαU)=(P(α)⊗I) Λ(U).\Lambda(e^{i\alpha}U) = \big(P(\alpha)\otimes\id\big)\,\Lambda(U).

The global phase of UU becomes a relative phase on the control. Every kickback algorithm therefore relies on a specific, fixed choice of phase for UU, usually supplied by an explicit gate decomposition.

Key takeaways

  • Λ(U)=∑jP(2πφj)⊗Πj\Lambda(U) = \sum_j P(2\pi\varphi_j)\otimes\Pi_j: a controlled unitary is a phase gate on the control within each eigenspace of UU.
  • The Hadamard test estimates Re\mathrm{Re} and Im\mathrm{Im} of ⟨ψ|U|ψ⟩\mel{\psi}{U}{\psi} with O(1/ε2)\order{1/\varepsilon^2} repetitions; phase estimation measures UU'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⟩=1r∑s∣us⟩\ket{1} = \tfrac{1}{\sqrt r}\sum_s\ket{u_s}.
  • Λ(eiαU)=(P(α)⊗I)Λ(U)\Lambda(e^{i\alpha}U) = (P(\alpha)\otimes\id)\Lambda(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=SU = S and ∣ψ⟩=∣+⟩\ket{\psi} = \ket{+}, what is the probability that the ancilla reads 00?

  1. 12\tfrac12
  2. 34\tfrac34
  3. 11
  4. 2+24\tfrac{2+\sqrt2}{4}
Show the answer

B. 34\tfrac34

⟨+|S|+⟩=12(1+i)\mel{+}{S}{+} = \tfrac12(1 + i), so Re=12\mathrm{Re} = \tfrac12 and P(0)=12(1+12)=34P(0) = \tfrac12(1 + \tfrac12) = \tfrac34. (With an S†S^\dagger inserted, the same probability would report Im=12\mathrm{Im} = \tfrac12.)

Question 2

How is Λ(eiαU)\Lambda(e^{i\alpha}U) related to Λ(U)\Lambda(U)?

  1. They are equal
  2. Λ(eiαU)=eiαΛ(U)\Lambda(e^{i\alpha}U) = e^{i\alpha}\Lambda(U)
  3. Λ(eiαU)=(P(α)⊗I) Λ(U)\Lambda(e^{i\alpha}U) = (P(\alpha)\otimes\id)\,\Lambda(U)
  4. Λ(eiαU)=(I⊗P(α)) Λ(U)\Lambda(e^{i\alpha}U) = (\id\otimes P(\alpha))\,\Lambda(U)
Show the answer

C. Λ(eiαU)=(P(α)⊗I) Λ(U)\Lambda(e^{i\alpha}U) = (P(\alpha)\otimes\id)\,\Lambda(U)

Only the control's ∣1⟩\ket{1} branch sees eiαe^{i\alpha}, so the global phase of UU becomes the phase gate P(α)P(\alpha) on the control.

Question 3

In order finding, phase estimation is run on the target ∣1⟩\ket{1}. What does it return (to tt-bit precision)?

  1. s/rs/r for a uniformly random s∈{0,…,r−1}s\in\{0,\dots,r-1\}
  2. 1/r1/r every time
  3. The order rr directly
  4. a/Na/N
Show the answer

A. s/rs/r for a uniformly random s∈{0,…,r−1}s\in\{0,\dots,r-1\}

∣1⟩=1r∑s∣us⟩\ket{1} = \tfrac{1}{\sqrt r}\sum_s\ket{u_s} is a uniform superposition of eigenvectors with phases s/rs/r, so each run samples one s/rs/r; continued fractions then extract rr.

Question 4

When φ\varphi has no exact tt-bit expansion, what lower bound holds for the probability that QPE outputs the nearest tt-bit value?

  1. 1/2t1/2^t
  2. 8/π28/\pi^2
  3. 1−2−t1 - 2^{-t}
  4. 4/π24/\pi^2
Show the answer

D. 4/π24/\pi^2

With ∣2tδ∣≤12\abs{2^t\delta} \le \tfrac12, ∣Ft(δ)∣2≥sin⁡2(π2tδ)/(π2tδ)2≥4/π2≈0.405\abs{F_t(\delta)}^2 \ge \sin^2(\pi 2^t\delta)/(\pi 2^t\delta)^2 \ge 4/\pi^2 \approx 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).