Quantum Phase Estimation

Estimate the eigenphase φ of a unitary U on one of its eigenstates — the core subroutine behind Shor's algorithm and energy estimation. It extracts a continuous quantity hidden in a phase into a binary number you can read directly.

The problem it solves

Any unitary U acting on one of its eigenstates |ψ⟩ only multiplies that state by a phase factor of unit modulus:

U|ψ⟩ = e^(2πiφ) |ψ⟩, 0 ≤ φ < 1

Looking at the target state alone, this eigenphase φ appears as an overall phase and cannot be read out by direct measurement; QPE uses controlled-U to transcribe it into a relative phase on the counting register. Many important problems reduce to this: in Shor's algorithm the phase of a modular-multiplication operator encodes a period, and in quantum chemistry the phase of the time-evolution operator e^(−iHt) encodes an energy eigenvalue.

The core idea — kicking the phase into bits

The trick is called phase kickback. When you use a target register that sits in an eigenstate to trigger a controlled U, the eigenphase does not stay on the target — it "kicks back" onto the counting qubit doing the controlling: that control goes from |0⟩ + |1⟩ to |0⟩ + e^(2πiφ)|1⟩.

If counting qubit k controls U^(2^k), it collects the phase 2^k·φ. Arranging all n counting qubits this way, the phases accumulated across the superposition lay out exactly the first n binary digits of φ — and that is a state in the Fourier basis. So a single inverse QFT collapses it back to an ordinary binary number j with φ ≈ j / 2ⁿ.

The precision / success-probability tradeoff

The number of counting qubits n sets both the precision and the reliability:

• Precision. n counting qubits quantise φ to a resolution of 1/2ⁿ. Each extra qubit doubles the precision by one binary digit.
• The exact case. If φ can be written exactly in n binary digits, the measurement returns the correct result with probability 1.
• The general case. If φ cannot be represented exactly in n bits, the measurement distribution forms a main peak at the integer closest to 2ⁿφ, with smaller side lobes; one can show the probability of landing on the best n-bit approximation is at least 4/π² (≈ 0.405).
• Boosting reliability. To reach success probability 1−ε for a target number of correct digits, add about log₂(1/ε) extra counting qubits. Taking more shots and using the mode works equally well.

What it is — and isn't — good for

• It is a universal building block. Shor's algorithm, the HHL linear-systems solver, and energy estimation in quantum chemistry are all phase estimation underneath.
• It needs an eigenstate. The algorithm assumes the input is already an eigenstate |ψ⟩ of U. Given a superposition of eigenstates, phase estimation randomly projects onto one of their eigenphases with the corresponding probability — sometimes exactly what you want (as in Shor), sometimes requiring you to prepare the eigenstate first.
• It needs powers of controlled U. You must implement U^(2^k) efficiently. For some operators this is cheap, for others very expensive — often dominating the whole circuit.
• It is demanding on coherence. The circuit is deep and long, so textbook phase estimation generally needs fault-tolerant hardware; near-term devices use iterative or variational alternatives instead.

Implementation

import qalgora

@qalgora.kernel
def qpe(counting: int):
    cq = qalgora.qvector(counting)
    eig = qalgora.qubit()
    x(eig)                       # eigenstate of a phase gate
    h(cq)
    # controlled-U^(2^j): here U = T (phase pi/4). MSB-first powers, since the
    # QFT above treats cq[0] as the most-significant qubit.
    for k in range(counting):
        for _ in range(2 ** (counting - 1 - k)):
            t.ctrl(cq[k], eig)
    qalgora.adjoint(qft, cq)     # inverse QFT
    mz(cq)

counts = qalgora.sample(qpe, 4)
# most-probable bitstring / 2^counting  ->  phi; counting=4 should peak at "0010" (=2/16=1/8)

Seeing it in code

Read the kernel against the theory above. Here U = T, a gate with phase π/4, so φ = 1/8; |1⟩ is its eigenstate, which is why x(eig) prepares the target in that eigenstate. |0⟩ is also an eigenstate of T, but with phase φ = 0; here x(eig) selects the non-trivial eigenphase of |1⟩. h(cq) spreads the counting register into superposition to receive the kicked-back phase. The double loop applies the controlled powers of U: the inner loop repeats t.ctrl(cq[k], eig) exactly 2^(counting−1−k) times, which is controlled U^(2^…), in most-significant-bit- first order to match the QFT's bit convention. Finally qalgora.adjoint(qft, cq) applies the inverse QFT to collapse the phase-spread information into a binary number; dividing the measured result by 2^counting gives the estimate of φ (here it should peak on the bitstring for 1/8). If a backend displays bit strings with a different endianness, the peak string may appear reversed; interpret the measurement in this page's MSB-first order when estimating φ.

With counting = 4, φ·2⁴ = 2 is exactly representable, so this example should peak deterministically at "0010", which serves as a regression assertion for the QFT bit-order convention (counting qubit cq[0] is the MSB) — if someone later changes the QFT's swaps or loop direction, this assertion breaks immediately.