Simple Algorithm
Quantum Computing · Excited State · 22 min

Phase Kickback & Phase Estimation

How a control qubit learns the eigenvalue of an operation.

A controlled operation acts on its target, yet when the target is an eigenstate it is the control that changes. That reversal, phase kickback, followed by one layer of interference, lets a register of qubits read off an eigenvalue digit by digit. It is the engine of Shor's algorithm and of energy estimation on future fault-tolerant machines.

What you’ll learn

  • Derive phase kickback: a controlled-UU on ∣+⟩∣u⟩\ket{+}\ket{u} with U∣u⟩=e2πiφ∣u⟩U\ket{u} = e^{2\pi i\varphi}\ket{u}.
  • Explain Deutsch's algorithm as kickback plus interference.
  • Derive the phase-estimation register state and show that the inverse QFT returns φ\varphi exactly when it has a tt-bit expansion.
  • Compute the outcome distribution for general φ\varphi and the number of counting qubits needed for a given precision and success probability.
  • Relate the cost of phase estimation to 1/N1/N (Heisenberg) scaling.

The control learns the eigenvalue

Let ∣u⟩\ket{u} be an eigenstate of a unitary UU, with U∣u⟩=e2πiφ∣u⟩U\ket{u} = e^{2\pi i\varphi}\ket{u}. The eigenvalue is a global phase for the target alone, so measuring the target could never reveal it. Put a control qubit in superposition and watch where that phase goes.

DerivationPhase kickback
  1. Λ(U)=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗U\Lambda(U) = \dyad{0}\otimes\id + \dyad{1}\otimes U

    Controlled-UU: apply UU to the target only on the ∣1⟩\ket{1} branch of the control.

  2. Λ(U) 12(∣0⟩+∣1⟩)∣u⟩=12(∣0⟩∣u⟩+∣1⟩ U∣u⟩)\Lambda(U)\,\tfrac{1}{\sqrt2}\big(\ket{0}+\ket{1}\big)\ket{u} = \tfrac{1}{\sqrt2}\big(\ket{0}\ket{u} + \ket{1}\,U\ket{u}\big)

    Linearity.

  3. =12(∣0⟩+e2πiφ∣1⟩)⊗∣u⟩= \tfrac{1}{\sqrt2}\big(\ket{0} + e^{2\pi i\varphi}\ket{1}\big)\otimes\ket{u}

    The eigenvalue factors out of the target and becomes a relative phase of the control. The target is untouched and stays unentangled.

  4. H 12(∣0⟩+e2πiφ∣1⟩):P(1)=sin⁡2(πφ)H\,\tfrac{1}{\sqrt2}\big(\ket0 + e^{2\pi i\varphi}\ket1\big):\qquad P(1) = \sin^2(\pi\varphi)

    A final Hadamard turns the phase into a bias: this is the Mach–Zehnder formula with 2πφ2\pi\varphi as the arm phase.

Deutsch's algorithm is kickback

A bit oracle Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)} acts on the target as Xf(x)X^{f(x)}. Since X∣−⟩=−∣−⟩X\ket{-} = -\ket{-}, the state ∣−⟩\ket{-} is an eigenvector with eigenvalue (−1)f(x)(-1)^{f(x)}:

Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩.U_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-}.

With the control in ∣+⟩\ket{+}, the oracle writes (−1)f(0)∣0⟩+(−1)f(1)∣1⟩(-1)^{f(0)}\ket0 + (-1)^{f(1)}\ket1 (up to normalization) onto the control, and HH maps that to ±∣f(0)⊕f(1)⟩\pm\ket{f(0)\oplus f(1)}. One query determines f(0)⊕f(1)f(0)\oplus f(1), which classically needs two. Every hidden-string algorithm (Deutsch–Jozsa, Bernstein–Vazirani, Simon) starts with this move.

Check your understanding

In Deutsch's algorithm the target register is ∣−⟩\ket{-} both before and after the oracle. How, then, does the circuit learn anything about ff?

  1. It doesn't; the answer comes from measuring the target
  2. The oracle's eigenvalue (−1)f(x)(-1)^{f(x)} is kicked back into the control's relative phase, and the final HH converts that phase into a bit
  3. The oracle secretly entangles control and target
  4. The control qubit is copied into the target and read later
Show the answer

B. The oracle's eigenvalue (−1)f(x)(-1)^{f(x)} is kicked back into the control's relative phase, and the final HH converts that phase into a bit

Because ∣−⟩\ket{-} is an eigenvector of every Xf(x)X^{f(x)}, the target factors out unchanged, and all information about ff ends up in the control's relative phase (−1)f(0)⊕f(1)(-1)^{f(0)\oplus f(1)}, which HH makes measurable.

Phase estimation

One kickback gives one blurry bit. To read φ\varphi to tt binary digits, use tt counting qubits, each in ∣+⟩\ket{+}, and let counting qubit jj control U2jU^{2^j}. It picks up e2πi 2jφe^{2\pi i\,2^j\varphi}: doubling the power shifts the binary expansion of φ\varphi one place to the left.

DerivationThe counting register
  1. ⨂j=0t−1∣0⟩+e2πi 2jφ∣1⟩2=12t∑k=02t−1e2πiφk∣k⟩\bigotimes_{j=0}^{t-1}\frac{\ket{0} + e^{2\pi i\,2^j\varphi}\ket{1}}{\sqrt2} = \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}\ket{k}

    Expand the product with k=∑jkj2jk = \sum_j k_j 2^j. The amplitudes are a discrete plane wave with frequency φ\varphi.

  2. QFT∣m⟩=12t∑ke2πimk/2t∣k⟩\mathrm{QFT}\ket{m} = \frac{1}{\sqrt{2^t}}\sum_{k}e^{2\pi i mk/2^t}\ket{k}

    The quantum Fourier transform produces exactly such plane waves.

  3. φ=m2t=0.φ1φ2…φt  ⇒  QFT−1(12t∑ke2πiφk∣k⟩)=∣m⟩\varphi = \frac{m}{2^t} = 0.\varphi_1\varphi_2\ldots\varphi_t \;\Rightarrow\; \mathrm{QFT}^{-1}\Big(\tfrac{1}{\sqrt{2^t}}\textstyle\sum_k e^{2\pi i\varphi k}\ket{k}\Big) = \ket{m}

    If φ\varphi has a tt-bit expansion, the inverse QFT returns its digits with certainty: all paths to wrong outcomes cancel.

  4. The cost is 1+2+⋯+2t−1=2t−11 + 2 + \dots + 2^{t-1} = 2^t - 1 applications of UU for precision 2−t2^{-t}. Precision ∝1/N\propto 1/N for NN uses of UU is the Heisenberg scaling; repeating a single kickback NN times and averaging gives only 1/N1/\sqrt{N}.

Predict before you look

φ=0.3\varphi = 0.3 and t=3t = 3 counting qubits, so outcomes are integers m=0,…,7m = 0,\dots,7 with estimate m/8m/8. Which mm is the most likely outcome?

Show the answer

2

2tφ=2.42^t\varphi = 2.4, so the nearest grid point is m=2m = 2 (estimate 0.250.25), with probability about 58%58\%; the next is m=3m = 3 with about 26%26\%. Check it in the simulator.

How many counting qubits?

DerivationThe outcome distribution
  1. P(m)=∣12t∑k=02t−1e2πikδ∣2=sin⁡2(π2tδ)4tsin⁡2(πδ),δ=φ−m2tP(m) = \Bigg|\frac{1}{2^t}\sum_{k=0}^{2^t-1}e^{2\pi i k\delta}\Bigg|^2 = \frac{\sin^2(\pi 2^t\delta)}{4^t\sin^2(\pi\delta)}, \qquad \delta = \varphi - \frac{m}{2^t}

    Apply QFT−1\mathrm{QFT}^{-1} and sum the geometric series.

  2. ∣2tδ∣≤12:P(m)≥sin⁡2(π2tδ)(π2tδ)2≥4π2≈0.405\abs{2^t\delta} \le \tfrac12:\quad P(m) \ge \frac{\sin^2(\pi 2^t\delta)}{(\pi 2^t\delta)^2} \ge \frac{4}{\pi^2} \approx 0.405

    For the nearest mm: use sin⁡x≤x\sin x \le x in the denominator, then the fact that sin⁡x/x≥2/π\sin x / x \ge 2/\pi on [0,π/2][0,\pi/2].

  3. P(one of the two nearest)≥8π2≈0.81P(\text{one of the two nearest}) \ge \frac{8}{\pi^2} \approx 0.81

    The same bound applied to both neighbors, minimized at 2tδ=122^t\delta = \tfrac12.

  4. t=n+⌈log⁡2 ⁣(2+12ε)⌉t = n + \left\lceil \log_2\!\left(2 + \frac{1}{2\varepsilon}\right)\right\rceil

    Counting qubits sufficient to get φ\varphi to nn bits with probability at least 1−ε1 - \varepsilon (Nielsen & Chuang §5.2.1). The tail of P(m)P(m) falls off like 1/(2tδ)21/(2^t\delta)^2, so a few extra qubits buy a lot of confidence.

Check your understanding

Using the formula above, how many counting qubits suffice to estimate φ\varphi to n=10n = 10 bits with success probability at least 0.90.9?

  1. 1010
  2. 1111
  3. 1313
  4. 2020
Show the answer

C. 1313

ε=0.1\varepsilon = 0.1 gives log⁡2(2+5)=log⁡27≈2.81\log_2(2 + 5) = \log_2 7 \approx 2.81, rounded up to 33, so t=13t = 13.

Uses, and going deeper

ApplicationUnitary UUEigenphase reveals
Shor's order finding∣y⟩↦∣ay mod N⟩\ket{y}\mapsto\ket{ay \bmod N}s/rs/r for random ss; continued fractions give the order rr
Energy estimatione−iHte^{-iHt}−Ejt/2π-E_jt/2\pi for an eigenvalue EjE_j of the Hamiltonian
Quantum countingGrover iteratethe rotation angle, hence the number of marked items
Hidden-string problemsphase oracle (−1)f(x)(-1)^{f(x)}a global property of ff via one round of kickback

Kitaev's original formulation (1995) measured the bits one at a time with a single control qubit, feeding earlier results forward as classical phase corrections. Griffiths and Niu (1996) showed that the inverse QFT followed by measurement can always be done this way, with one-qubit gates and classical control. This "iterative" phase estimation needs only one ancilla, which matters on small or early fault-tolerant machines.

Key takeaways

  • Λ(U)∣+⟩∣u⟩=12(∣0⟩+e2πiφ∣1⟩)∣u⟩\Lambda(U)\ket{+}\ket{u} = \tfrac{1}{\sqrt2}(\ket0 + e^{2\pi i\varphi}\ket1)\ket{u}: an eigenvalue becomes a relative phase on the control, and the target is untouched.
  • Deutsch, Deutsch–Jozsa and Bernstein–Vazirani are kickback onto ∣−⟩\ket{-} followed by Hadamard interference.
  • Phase estimation writes 12t∑ke2πiφk∣k⟩\tfrac{1}{\sqrt{2^t}}\sum_k e^{2\pi i\varphi k}\ket{k}; the inverse QFT returns φ\varphi exactly if it has tt bits, otherwise the nearest tt-bit value with probability ≥4/π2\ge 4/\pi^2.
  • nn bits with probability 1−ε1-\varepsilon need t=n+⌈log⁡2(2+1/2ε)⌉t = n + \lceil\log_2(2 + 1/2\varepsilon)\rceil counting qubits, and precision scales as 1/(uses of U)1/(\text{uses of }U): Heisenberg scaling.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

U∣u⟩=eiλ∣u⟩U\ket{u} = e^{i\lambda}\ket{u}. What does Λ(U)\Lambda(U) do to ∣+⟩∣u⟩\ket{+}\ket{u}?

  1. ∣+⟩⊗eiλ∣u⟩\ket{+}\otimes e^{i\lambda}\ket{u}, a global phase that changes nothing
  2. 12(∣0⟩∣u⟩+eiλ∣1⟩∣u⟩)\tfrac{1}{\sqrt2}\big(\ket{0}\ket{u} + e^{i\lambda}\ket{1}\ket{u}\big), an entangled state
  3. 12(∣0⟩+eiλ∣1⟩)⊗∣u⟩\tfrac{1}{\sqrt2}\big(\ket{0} + e^{i\lambda}\ket{1}\big)\otimes\ket{u}: the control acquires a relative phase
  4. ∣+⟩⊗U∣u⟩\ket{+}\otimes U\ket{u}, with the control unchanged
Show the answer

C. 12(∣0⟩+eiλ∣1⟩)⊗∣u⟩\tfrac{1}{\sqrt2}\big(\ket{0} + e^{i\lambda}\ket{1}\big)\otimes\ket{u}: the control acquires a relative phase

Only the ∣1⟩\ket{1} branch receives eiλe^{i\lambda}, so the phase is relative between the control's branches. The target factors out unchanged; the state is a product state.

Question 2

A controlled-TT acts on ∣+⟩∣1⟩\ket{+}\ket{1}, then HH is applied to the control. What is the probability that the control reads 11?

  1. 00
  2. sin⁡2(π/8)≈0.15\sin^2(\pi/8) \approx 0.15
  3. 12\tfrac12
  4. cos⁡2(π/8)≈0.85\cos^2(\pi/8) \approx 0.85
Show the answer

B. sin⁡2(π/8)≈0.15\sin^2(\pi/8) \approx 0.15

T∣1⟩=eiπ/4∣1⟩T\ket{1} = e^{i\pi/4}\ket{1} kicks back the phase π/4\pi/4, and HH then gives P(1)=sin⁡2(π/42)=sin⁡2(π/8)P(1) = \sin^2(\tfrac{\pi/4}{2}) = \sin^2(\pi/8).

Question 3

Textbook phase estimation with tt counting qubits uses how many applications of UU in total?

  1. tt
  2. t2t^2
  3. 22t2^{2t}
  4. 2t−12^t - 1
Show the answer

D. 2t−12^t - 1

Counting qubit jj controls U2jU^{2^j}, and ∑j=0t−12j=2t−1\sum_{j=0}^{t-1}2^j = 2^t - 1. Precision 2−t2^{-t} for about 2t2^t uses is Heisenberg scaling.

Question 4

φ=0.625\varphi = 0.625 exactly and t=3t = 3. What does phase estimation output?

  1. 101101 with certainty
  2. 101101 with probability at least 4/π24/\pi^2
  3. a uniformly random 3-bit string
  4. 110110 with certainty
Show the answer

A. 101101 with certainty

0.625=5/8=0.10120.625 = 5/8 = 0.101_2 is a 3-bit fraction, so the register state is exactly QFT∣5⟩\mathrm{QFT}\ket{5} and the inverse QFT returns ∣101⟩\ket{101} deterministically.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §5.2 (Cambridge, 10th anniv. ed., 2010).
  • 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).
  • R. B. Griffiths & C.-S. Niu, "Semiclassical Fourier transform for quantum computation", Phys. Rev. Lett. 76, 3228 (1996).