Quantum Phase Estimation

Derivation

Quantum Phase Estimation

D-414 Home PU-404 Threads waves · symmetry · chance Depends on The Quantum Fourier Transform Circuit

Statement

Given a unitary \(U\) and one of its eigenstates \(|u\rangle\) satisfying \(U|u\rangle = e^{2\pi i \varphi}|u\rangle\) with unknown eigenphase \(\varphi \in [0,1)\), the quantum phase estimation circuit prepares an \(n\)-qubit counting register in a uniform superposition, applies the controlled powers \(U^{2^{0}}, U^{2^{1}}, \dots, U^{2^{n-1}}\) each conditioned on one counting qubit, applies the inverse quantum Fourier transform, and on measurement returns an integer \(b\) whose reading \(\tilde\varphi = b/2^{n}\) is the best \(n\)-bit approximation to \(\varphi\), exact when \(2^{n}\varphi \in \mathbb{Z}\) and otherwise correct to \(n\) bits with probability at least \(4/\pi^{2}\).

Why it matters

Phase estimation is the computational heart of quantum algorithms that achieve super-polynomial speedups. Shor's factoring algorithm is order-finding, which is phase estimation of the modular-multiplication operator; quantum simulation reads energy eigenvalues by estimating the phase of the evolution operator \(e^{-iHt}\); the HHL linear-systems algorithm inverts eigenvalues obtained the same way. In every case the primitive being invoked is exactly this circuit.

Conceptually it is where three physics threads meet: waves, because eigenphases are read out by Fourier analysis of an interference pattern; symmetry, because \(U\) is diagonalised by its eigenbasis and the phase is the invariant label of an eigenspace; and chance, because a non-representable phase collapses onto a probability distribution sharply peaked at its nearest binary fraction.

Assumptions

The input register holds a genuine eigenstate \(|u\rangle\) of \(U\).If \(|u\rangle=\sum_u c_u|u\rangle\) is a superposition of eigenstates, the circuit still runs but returns eigenphase \(\varphi_u\) with probability \(|c_u|^2\) while collapsing the register to \(|u\rangle\); the "single answer" reading is lost and replaced by a sampling statement.

Controlled-\(U^{2^{j}}\) can be realised, ideally efficiently.If only controlled-\(U\) is available, the powers must be built by \(2^{j}\) sequential applications, costing \(O(2^{n})\) gates and destroying the exponential precision advantage; efficient phase estimation needs a fast way to exponentiate \(U\).

The eigenphase \(\varphi\) is stationary during the run and \(U\) acts exactly.Gate errors, decoherence, or a drifting Hamiltonian smear the interference comb, broadening the output distribution and lowering the success probability below the ideal \(4/\pi^{2}\) floor.

The inverse quantum Fourier transform is available as a prior primitive.Without it the accumulated phases \(e^{2\pi i \varphi k}\) remain encoded in an unmeasurable relative-phase pattern; the QFT\(^{-1}\) is precisely the operation that converts that pattern into a computational-basis label that can be read by projective measurement.

Derivation

\[ |\psi_0\rangle = |0\rangle^{\otimes n}\otimes|u\rangle \]

Initialise the \(n\)-qubit counting register to the all-zeros state and load the target register with the eigenstate. A

\[ |\psi_1\rangle = H^{\otimes n}|0\rangle^{\otimes n}\otimes|u\rangle = \frac{1}{2^{n/2}}\sum_{k=0}^{2^{n}-1}|k\rangle\,|u\rangle \]

A Hadamard on each counting qubit sends \(|0\rangle\to(|0\rangle+|1\rangle)/\sqrt2\); the product over \(n\) qubits is the uniform superposition over all integers \(k=\sum_{j}k_j 2^{j}\). A

\[ U^{2^{j}}|u\rangle = \left(e^{2\pi i\varphi}\right)^{2^{j}}|u\rangle = e^{2\pi i\varphi\, 2^{j}}|u\rangle \]

Eigenvalue relation raised to the power \(2^{j}\): the eigenstate is invariant, only the phase compounds. This is what makes the target register a fixed "phase source." B

\[ \text{c-}U^{2^{j}}\;\frac{|0\rangle+|1\rangle}{\sqrt2}\,|u\rangle = \frac{|0\rangle+e^{2\pi i\varphi\,2^{j}}|1\rangle}{\sqrt2}\,|u\rangle \]

Phase kickback: the controlled gate leaves \(|0\rangle\) alone and multiplies \(|1\rangle\) by the eigenvalue. Because \(|u\rangle\) is unchanged, the phase is transferred entirely onto the control qubit. B

\[ |\psi_2\rangle = \frac{1}{2^{n/2}}\bigotimes_{j=0}^{n-1}\!\left(|0\rangle+e^{2\pi i\varphi\,2^{j}}|1\rangle\right)\otimes|u\rangle = \frac{1}{2^{n/2}}\sum_{k=0}^{2^{n}-1} e^{2\pi i\varphi k}\,|k\rangle\,|u\rangle \]

Apply c-\(U^{2^{j}}\) for every counting qubit \(j\). Since \(k=\sum_j k_j 2^{j}\), the accumulated phase factorises: \(\prod_j e^{2\pi i\varphi\,2^{j}k_j}=e^{2\pi i\varphi k}\). The target register factors out cleanly. B

\[ \text{QFT}\,|x\rangle = \frac{1}{2^{n/2}}\sum_{k=0}^{2^{n}-1} e^{2\pi i\, x k/2^{n}}\,|k\rangle \]

Recall the quantum Fourier transform from the prior result. Comparing, if \(\varphi=x/2^{n}\) for integer \(x\) then \(|\psi_2\rangle=(\text{QFT}\,|x\rangle)\otimes|u\rangle\): the counting register is literally the Fourier transform of the answer. B

\[ |\psi_3\rangle = \left(\text{QFT}^{-1}\otimes I\right)|\psi_2\rangle \;\xrightarrow{\;2^{n}\varphi=x\in\mathbb{Z}\;}\; |x\rangle\,|u\rangle,\qquad x=\varphi_1\varphi_2\cdots\varphi_n \]

Apply the inverse QFT to the counting register. When \(\varphi\) has an exact \(n\)-bit binary expansion \(0.\varphi_1\varphi_2\cdots\varphi_n\), the transform undoes step 6 exactly and deposits the bit string in the computational basis. B

\[ \alpha_b = \langle b|\,\text{QFT}^{-1}|\psi_2\rangle = \frac{1}{2^{n}}\sum_{k=0}^{2^{n}-1} e^{2\pi i k\left(\varphi-b/2^{n}\right)} = \frac{1}{2^{n}}\,\frac{1-e^{2\pi i\,2^{n}\delta}}{1-e^{2\pi i\,\delta}},\quad \delta\equiv\varphi-\frac{b}{2^{n}} \]

For general \(\varphi\), expand the measurement amplitude of outcome \(b\); the sum is geometric with ratio \(e^{2\pi i\delta}\). This is a finite Dirichlet-kernel interference sum. C

\[ P(b)=|\alpha_b|^{2} = \frac{1}{2^{2n}}\,\frac{\sin^{2}\!\left(\pi 2^{n}\delta\right)}{\sin^{2}\!\left(\pi\delta\right)} \;\ge\; \frac{4}{\pi^{2}}\quad\text{for the nearest }b\ \text{with}\ |\delta|\le 2^{-(n+1)} \]

Take the modulus squared using \(|1-e^{i\theta}|^{2}=4\sin^{2}(\theta/2)\). Bounding the numerator below by \(\sin^2(\pi 2^n\delta)\) and the denominator above by \((\pi 2^n\delta)^2\)-type estimates over the peak gives the standard \(4/\pi^{2}\approx0.405\) floor for the best \(n\)-bit estimate. C

Result

\[ \tilde\varphi=\frac{b}{2^{n}},\qquad P\!\left(\left|\tilde\varphi-\varphi\right|\le 2^{-n}\right)\ge \frac{4}{\pi^{2}}\approx 0.405,\qquad P(b)=\frac{\sin^{2}\!\left(\pi 2^{n}\delta\right)}{2^{2n}\sin^{2}\!\left(\pi\delta\right)} \]

Reading. Running the circuit and measuring the counting register returns an \(n\)-bit integer \(b\); dividing by \(2^{n}\) gives an estimate of the eigenphase. If \(\varphi\) is exactly representable in \(n\) bits the answer is deterministic; otherwise the output distribution is a sharp interference comb peaked at the nearest binary fraction, and a single shot lands within \(2^{-n}\) of the true phase with probability at least \(4/\pi^{2}\). To guarantee \(m\) correct bits with success probability \(1-\epsilon\), run with \(n=m+\lceil\log_2(2+\tfrac{1}{2\epsilon})\rceil\) counting qubits.

Units check. Every quantity is dimensionless: \(\varphi\) is a fraction of a full turn (radians of phase divided by \(2\pi\)), \(b\) and \(2^{n}\) are pure counts, and \(P(b)\) is a probability. The argument of every exponential and sine is a dimensionless phase in radians, and \(\sum_b P(b)=1\) as required for a normalised measurement distribution.

Limiting cases

Exact phase, \(2^{n}\varphi\in\mathbb{Z}\): \(\delta=0\) gives \(P(b)=1\); the reading is deterministic and error-free.
Worst case, \(\delta=\pm 2^{-(n+1)}\): the peak flattens to its minimum, \(P(b)=4/\pi^{2}\approx 0.405\), the floor of the success guarantee.
\(n=1\): the circuit reduces to a Hadamard test, distinguishing \(\varphi\) near \(0\) from \(\varphi\) near \(1/2\) — one bit of phase.
\(n\to\infty\): the comb narrows without bound; the estimate converges to \(\varphi\) and the transform approaches the continuous Fourier limit.
Add one extra qubit (\(n\to n+1\)): precision doubles, \(2^{-n}\to 2^{-(n+1)}\), the exponential resolution scaling.

Breaks when

The input is not an eigenstate. For a superposition \(\sum_u c_u|u\rangle\) there is no single \(\varphi\) to report; the circuit samples eigenphases with weights \(|c_u|^{2}\), so the deterministic reading fails and must be reinterpreted as a measurement over the eigenspectrum.
Controlled powers are inexact or decohere. Gate error \(\varepsilon\) per controlled-\(U^{2^{j}}\) accumulates over the \(\sum_j 2^{j}\approx 2^{n}\) applications; once the total error is order one the interference comb washes out and the \(4/\pi^{2}\) floor no longer holds.
The phase is degenerate to the target resolution. Two eigenphases separated by less than \(2^{-n}\) cannot be resolved into distinct output bins; the peaks overlap and the readout cannot tell them apart without more qubits.
\(U\) cannot be efficiently exponentiated. If \(U^{2^{j}}\) must be built by \(2^{j}\) repetitions of \(U\), the gate count grows as \(2^{n}\) and the exponential-precision advantage over classical estimation disappears.

Failure modes

Bit-order inversion: confusing the little-endian control assignment (qubit \(j\) drives \(U^{2^{j}}\)) with the big-endian output of a naively-wired QFT\(^{-1}\); this reverses the bit string and reports \(1-\tilde\varphi\) or a scrambled value.
Forgetting the target register is entangled during sampling: assuming a superposition input yields the average phase \(\sum_u|c_u|^2\varphi_u\); it does not — each shot returns one eigenphase.
Using QFT instead of QFT\(^{-1}\): applying the forward transform produces the complex conjugate reading and estimates \(-\varphi \bmod 1\).
Treating \(4/\pi^{2}\) as the typical rather than worst-case probability: the floor applies only at the most unfavourable \(\delta\); for most phases the success probability is much higher, so pessimistically over-provisioning qubits wastes resources.
Normalisation slip: writing the uniform superposition with \(1/2^{n}\) instead of \(1/2^{n/2}\), which breaks unitarity of the state and every downstream probability.
Assuming eigenstate preparation is free: in practice \(|u\rangle\) is often unknown, and preparing it can be as hard as the problem being solved.

Discussion

The mechanism is best read as controlled interference. The Hadamard layer opens \(2^{n}\) coherent "paths" indexed by \(k\); the controlled powers imprint a linear phase ramp \(e^{2\pi i\varphi k}\) along those paths; and the inverse QFT is a diffraction grating that focuses the ramp onto the single output bin whose frequency matches \(\varphi\). The whole circuit is a quantum spectrometer, and its resolving power \(2^{-n}\) scales exactly like the reciprocal of the "aperture" \(2^{n}\) — the same Fourier-limited resolution that governs a diffraction grating with \(2^{n}\) slits.

The phase-kickback step is where the physics is most economical. Because \(|u\rangle\) is an eigenstate, the controlled operation never disturbs the target register — it only stamps a number onto the control. This is why one copy of \(|u\rangle\) suffices to answer a question about a \(2^{n}\)-dimensional interference pattern, and why the target and counting registers factorise at step 5. Symmetry is doing the work: the eigenbasis of \(U\) is a set of invariant one-dimensional subspaces, each carrying a single conserved label \(\varphi\).

The success probability is a manifestation of the Fejér/Dirichlet kernel that appears whenever a finite phase ramp is Fourier-analysed. The \(4/\pi^{2}\) floor is the minimum of \(\operatorname{sinc}^2\)-type leakage at the half-bin offset, identical in structure to scalloping loss in a classical FFT and to the central-fringe visibility of an \(N\)-slit interference pattern. The tail of \(P(b)\) decays only as \(1/\delta^{2}\), which is why guaranteeing many correct bits with high confidence requires a logarithmic number of extra qubits rather than a constant — the same trade between spectral leakage and window length familiar from signal processing.

Common misconceptions. Phase estimation does not "measure the phase of a state"; global phase is unobservable. It measures the relative eigenphase of a unitary, converted into an observable relative phase between the branches of the counting register by kickback. Nor does it give unbounded precision for free: each additional bit doubles the number of applications of \(U\), so precision is bought with circuit depth, and on noisy hardware that depth is the binding constraint.

Worked examples

\[ U=\begin{pmatrix}1&0\\0&e^{2\pi i/8}\end{pmatrix},\quad |u\rangle=|1\rangle,\quad \varphi=\tfrac18,\quad n=3 \]

A phase gate with eigenstate \(|1\rangle\); estimate its exactly-representable eigenphase. A

\[ 2^{n}\varphi = 8\cdot\tfrac18 = 1 \in\mathbb{Z}\ \Rightarrow\ x=1=(001)_2,\qquad \varphi = 0.001_2 \]

The phase has an exact 3-bit binary expansion, so step 7 applies with \(\delta=0\). A

\[ |\psi_2\rangle=\frac{1}{\sqrt8}\sum_{k=0}^{7}e^{2\pi i k/8}|k\rangle\,|1\rangle \;\xrightarrow{\text{QFT}^{-1}}\; |001\rangle\,|1\rangle \]

The counting register is the Fourier transform of \(|1\rangle\); the inverse QFT recovers it exactly. B

\[ \boxed{\ \tilde\varphi = \tfrac{1}{8}=0.125\ \text{with}\ P=1\ } \]

Reading. Measurement is deterministic: outcome \(b=1\), reading \(\varphi=1/8\), no error. Units: dimensionless phase.

\[ \varphi=\tfrac13,\quad n=3,\quad 2^{n}=8 \]

A non-representable phase; find the most likely outcome and its probability. B

\[ 2^{n}\varphi=\tfrac{8}{3}=2.667\ \Rightarrow\ b=3\ \text{is nearest},\qquad \delta=\varphi-\frac{b}{2^{n}}=\frac13-\frac38=-\frac{1}{24} \]

Round \(2^n\varphi\) to the nearest integer to identify the peak bin; compute the offset \(\delta\). B

\[ P(3)=\frac{\sin^{2}\!\left(\pi\cdot 8\cdot(-\tfrac{1}{24})\right)}{8^{2}\,\sin^{2}\!\left(\pi\cdot(-\tfrac{1}{24})\right)} = \frac{\sin^{2}(\pi/3)}{64\,\sin^{2}(\pi/24)} = \frac{0.7500}{64\,(0.017037)} \]

Substitute into the probability formula from step 9; \(\sin^2(\pi/3)=3/4\), \(\sin(\pi/24)=\sin 7.5^\circ=0.13053\). C

\[ \boxed{\ P(b=3)\approx 0.688,\qquad \tilde\varphi=\tfrac38=0.375\ } \]

Reading. The nearest 3-bit estimate \(0.375\) (true value \(0.333\)) is returned with probability about 69% in a single shot, comfortably above the \(4/\pi^{2}\approx0.405\) worst-case floor; the remaining probability leaks mostly to the adjacent bin \(b=2\). Units: all dimensionless.

Problems

Show explicitly that applying controlled-\(U\) to \(\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)\otimes|u\rangle\), where \(U|u\rangle=e^{2\pi i\varphi}|u\rangle\), produces \(\tfrac{1}{\sqrt2}(|0\rangle+e^{2\pi i\varphi}|1\rangle)\otimes|u\rangle\), and state in one sentence why the target register is unchanged.
Solution
Controlled-\(U\) acts as \(|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U\). On \(|0\rangle|u\rangle\) it gives \(|0\rangle|u\rangle\); on \(|1\rangle|u\rangle\) it gives \(|1\rangle U|u\rangle = e^{2\pi i\varphi}|1\rangle|u\rangle\). By linearity \(\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)|u\rangle \mapsto \tfrac{1}{\sqrt2}(|0\rangle+e^{2\pi i\varphi}|1\rangle)|u\rangle\). The target is unchanged because \(|u\rangle\) is an eigenstate, so \(U\) acts as a scalar and factors out — the phase is kicked back onto the control.
To estimate an eigenphase to \(m=6\) bits of accuracy with success probability at least \(1-\epsilon=0.99\), how many counting qubits \(n\) are required? Use \(n=m+\lceil\log_2(2+\tfrac{1}{2\epsilon})\rceil\).
Solution
With \(\epsilon=0.01\): \(2+\tfrac{1}{2\epsilon}=2+\tfrac{1}{0.02}=2+50=52\). Then \(\log_2 52 = 5.70\), so \(\lceil 5.70\rceil = 6\). Therefore \(n = 6+6 = \boxed{12}\) counting qubits. The six extra qubits buy the confidence margin against spectral leakage into neighbouring bins.
An operator has eigenphase \(\varphi=5/16\). With \(n=4\) counting qubits, what outcome is measured and with what probability?
Solution
\(2^{n}\varphi = 16\cdot\tfrac{5}{16}=5\in\mathbb{Z}\), so the phase is exactly 4-bit representable: \(5=(0101)_2\), i.e. \(\varphi=0.0101_2\). Here \(\delta=0\), the interference comb collapses to a single spike, and the inverse QFT deposits \(|0101\rangle\) deterministically. Outcome \(b=5\), reading \(\tilde\varphi=5/16=0.3125\), with probability \(P=1\).
For \(\varphi=1/5\) and \(n=3\), identify the most probable outcome \(b\) and compute \(P(b)\) from \(P(b)=\dfrac{\sin^{2}(\pi 2^{n}\delta)}{2^{2n}\sin^{2}(\pi\delta)}\).
Solution
\(2^{n}\varphi = 8\cdot 0.2 = 1.6\), nearest integer \(b=2\), so \(\tilde\varphi=2/8=0.25\) and \(\delta=0.2-0.25=-0.05\). Then \(2^{n}\delta = 8(-0.05)=-0.4\), giving numerator \(\sin^{2}(\pi\cdot(-0.4))=\sin^{2}(72^\circ)=0.90451\). Denominator: \(\sin(\pi\cdot(-0.05))=\sin(-9^\circ)=-0.15643\), squared \(=0.024472\), times \(2^{2n}=64\) gives \(1.5662\). Thus \(P(2)=0.90451/1.5662=\boxed{0.578}\), about 58% — still above the \(4/\pi^{2}\) floor, with most of the remainder in bin \(b=1\).
Suppose the target register is prepared in \(|\phi\rangle=c_1|u_1\rangle+c_2|u_2\rangle\), a superposition of two eigenstates with phases \(\varphi_1,\varphi_2\) and \(|c_1|^2+|c_2|^2=1\). Describe the joint state before measurement and the statistics of the counting-register readout.
Solution
The circuit is linear, so it processes each eigenstate branch independently. After the inverse QFT the joint state is \(c_1|\tilde\varphi_1\rangle|u_1\rangle + c_2|\tilde\varphi_2\rangle|u_2\rangle\) (taking the exact-phase case for clarity), an entangled state correlating each estimate with its eigenstate. Measuring the counting register returns \(\tilde\varphi_1\) with probability \(|c_1|^2\) and \(\tilde\varphi_2\) with probability \(|c_2|^2\), and collapses the target register onto the corresponding \(|u_k\rangle\). The circuit thus samples the eigenphase spectrum weighted by the input overlaps — this is exactly the mechanism exploited in order-finding, where the required uniform superposition of eigenstates is prepared implicitly by starting from a computational-basis state.