Steven GellerQuantum Computing, End to End

Book contents

Type at least two characters.

    Current section

    Part IV. Protocols and Algorithms

    1. Bell Tests and Nonclassical Correlations
    2. Superdense Coding
    3. Teleportation
    4. Quantum Key Distribution
    5. Oracles and Query Complexity
    6. Deutsch, Deutsch-Jozsa, and Bernstein-Vazirani
    7. Simon and Hidden Structure
    8. Grover and Amplitude Amplification
    9. Quantum Fourier Transform
    10. Phase Estimation
    11. Shor as Period Finding
    12. Hamiltonian Simulation
    13. Variational Algorithms and Their Limits
    All chaptersGlossaryLabsSourcesAbout

    Part IV. Protocols and Algorithms · Chapter 32

    Phase Estimation

    Phase estimation turns "this unitary has structure" into a number: it reads eigenphases at a precision you choose and pay for, one counting qubit at a time.

    Steven Geller
    Lab
    In this chapter 9 sections

    Reader question. How does quantum phase estimation convert an eigenphase into a bit string, and what controls its precision and success probability?

    Controlled powers of a unitary accumulate binary-weighted phase on a counting register, and an inverse QFT converts that phase pattern into a sampled estimate; counting-register width, input eigenstate overlap, controlled-U cost, and approximation determine the useful precision.

    Scope and non-goals.
    • Eigenstate preparation and controlled powers remain explicit resource costs.
    • A t-bit register yields a distribution whose accuracy depends on the phase and success criterion, rather than t guaranteed correct bits.
    The phase estimation circuit Controlled powers write the phase; inverse QFT reads it |0> |0> |psi> H H U U^2 QFT†inverse m-bit estimate |psi> feeds every power Precision is 1/2^m for m counting qubits; the bill is dominated by the controlled powers of U.
    Figure 32.1. Notice the two registers doing different jobs: the counting register only records phase, while the eigenstate register powers every controlled operation. That is why the cost of U; not the inverse QFT; usually dominates the budget.

    The eigenphase contract

    Specify U|u>=e^{2πiφ}|u> and input overlap.

    Every unitary has eigenstates that it leaves alone except for a phase:

    U∣ψ⟩=e2πiθ∣ψ⟩U\lvert\psi\rangle=e^{2\pi i\theta}\lvert\psi\rangle(32.1)

    Phase estimation is the algorithm that measures θ\theta. Prepare the eigenstate on one register, put mm counting qubits into superposition on another, apply controlled powers of UU—UU, U2U^2, U4U^4, and so on, each controlled by one counting qubit—and finish with the inverse QFT. The counting register then holds an mm-bit estimate of θ\theta, readable by an ordinary measurement.

    This single subroutine is the engine room of the algorithms that made the field famous. Factoring, discrete logarithms, quantum chemistry energies, linear-systems solvers; all can be reframed as "learn a phase of a structured unitary." Learn to read a phase-estimation circuit and you can read most of the heavyweight algorithm literature.

    Evidence boundary. Phase estimation estimates an eigenvalue phase using controlled powers and inverse QFT. Kitaev's Abelian stabilizer formulation is a primary source for the phase-estimation method; the textbook and lecture notes provide later systematic treatments. [A. Yu. Kitaev] [Michael A. Nielsen] [John Preskill]

    Binary-weighted powers write a phase gradient

    Trace each counting qubit after controlled U^{2^j}.

    If U|psi>=exp(2 pi i phi)|psi>, controlled powers U^(2^j) write phases exp(2 pi i 2^j phi) on the control register. The inverse QFT converts that gradient into an m-bit estimate. Counting m controlled operations can conceal exponential evolution time: expanded base-U use totals 2^m-1 applications.

    Evidence boundary. Finite counting-register width produces a probability distribution whose concentration depends on phase representability and precision. [John Watrous] [Don Coppersmith]

    Inverse QFT decodes the exact-grid case

    Derive a deterministic representable phase.

    The counting register sets the resolution:

    resolution≈2−m\text{resolution}\approx2^{-m}(32.2)

    Each additional counting qubit doubles the resolution; and demands controlled applications of ever-higher powers of UU. The inverse QFT that gets all the attention is, by comparison, a modest tail of Hadamards and controlled phase gates:

    QFT⁡N∣x⟩=1N∑y=0N−1e2πixy/N∣y⟩\operatorname{QFT}_N\lvert x\rangle=\frac1{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi ixy/N}\lvert y\rangle(32.3)

    The accounting is the lesson: how many counting qubits do you need? is simultaneously a question about the precision your application requires and about the deepest, most expensive part of the circuit. Precision is not a footnote to phase estimation. It is the budget.

    Evidence boundary. Resource cost depends on controlled powers of U and eigenstate preparation, not only counting qubits. [Peter W. Shor] [National Academies of Sciences]

    ϕ∈[0,1),U∣u⟩=e2πiϕ∣u⟩\phi\in[0,1),\qquad U\lvert u\rangle=e^{2\pi i\phi}\lvert u\rangle(32.4)

    Notation contract: φ∈[0,1); U|u>=e^{2πiφ}|u>; t counting qubits; bit significance and inverse-QFT convention declared.

    Off-grid phases spread probability

    Calculate the nearest estimates and success mass.

    When 2^m phi is not an integer, the inverse-QFT amplitudes form a Dirichlet-kernel distribution rather than a single basis state. The nearest integer is most likely, but success within a requested error needs enough precision bits and repetitions. Report the complete distribution or a confidence bound; a rounded binary string alone hides the algorithm's probabilistic contract.

    Resource account: precision carries a controlled-evolution bill

    Account for qubits, maximum power, synthesis, and repetitions.

    Phase estimation is a subroutine with a sharp interface:

    • Input: an eigenstate of UU, or a state with useful overlap on one;
    • Operation: controlled powers of UU, up to 2m−12^m-1;
    • Register: mm counting qubits;
    • Transform: inverse QFT;
    • Output: a sampled mm-bit phase estimate;
    • Post-processing: interpret the bits, with a confidence statement.

    The interface is only as useful as its feasibility conditions. Textbook diagrams assume the input is an eigenstate. Real workflows often prepare a superposition of eigenstates, so the measurement samples from several phases at once; still useful, but the output is evidence with probabilities attached, and the state-preparation cost belongs in the budget next to the controlled unitaries.

    Eigenstate preparation is a separate algorithm

    Expose overlap and postselection consequences.

    Phase estimation preserves an eigenstate and reports its phase only when that eigenstate is supplied. A superposition of eigenstates produces the corresponding mixture of phase estimates and projects onto one component. Preparing appreciable overlap with the desired eigenstate can dominate chemistry or simulation workflows, so it belongs as its own resource and success assumption.

    Phase-estimation precision workbench

    Acceptance contract for Phase-estimation precision workbench
    FieldReader-visible record
    FormatStatevector simulator with exact/off-grid cases and controlled-power ledger
    VerificationTests exactly representable phases, off-grid distributions, inverse-QFT ordering, precision scaling, and explicit controlled-U call counts.
    AvailabilitySource-embedded acceptance record; no separate download is claimed
    {
  "artifact": "Phase-estimation precision workbench",
  "format": "Statevector simulator with exact/off-grid cases and controlled-power ledger",
  "acceptance_test": "Tests exactly representable phases, off-grid distributions, inverse-QFT ordering, precision scaling, and explicit controlled-U call counts.",
  "publication_state": "source-embedded contract and worked fixture"
}

    Executable reference fixture

    Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

    import cmath

def phase_distribution(bits, theta):
    if type(bits) is not int or bits < 1 or not 0.0 <= theta < 1.0:
        raise ValueError("bits must be positive and phase must be in [0, 1)")
    size = 2 ** bits
    probabilities = []
    for outcome in range(size):
        amplitude = sum(cmath.exp(2j * cmath.pi * k * (theta - outcome / size))
                        for k in range(size)) / size
        probabilities.append(abs(amplitude) ** 2)
    return probabilities

def estimate(bits, theta):
    probabilities = phase_distribution(bits, theta)
    peak = max(range(len(probabilities)), key=probabilities.__getitem__)
    return {"bits": bits, "peak": peak, "phase": peak / (2 ** bits),
            "peak_probability": probabilities[peak], "mass": sum(probabilities)}

exact = estimate(3, 3 / 8)
coarse = estimate(3, 1 / 3)
fine = estimate(5, 1 / 3)
invalid_rejected = False
try:
    estimate(3, 1.0)
except ValueError:
    invalid_rejected = True
assert exact["peak"] == 3 and abs(exact["mass"] - 1.0) < 1e-12
assert abs(fine["phase"] - 1 / 3) < abs(coarse["phase"] - 1 / 3)
assert invalid_rejected and exact["peak_probability"] > 1.0 - 1e-12
print(f"PASS: 32 phase estimation exact={exact['peak']:03b} coarse_error={abs(coarse['phase']-1/3):.6f} fine_error={abs(fine['phase']-1/3):.6f}")

    Scope boundary

    • Eigenstate preparation and controlled powers remain explicit resource costs.
    • A t-bit register yields a distribution whose accuracy depends on the phase and success criterion, rather than t guaranteed correct bits.

    Depth commitment. One exact derivation, one off-grid case, one overlap boundary, and one resource ledger.

    Practice problem

    Run three-bit phase estimation for φ=3/8 and φ=0.3; derive the first output exactly and compare the second with simulated probabilities.

    Deliverable
    Controlled-phase states, inverse-QFT result, probability table, and controlled-U ledger.
    Pass condition
    The workbench asserts output 011 for 3/8 under the declared bit order and reproduces the off-grid distribution.

    Verification record

    Expected solution form. Exact-grid derivation plus off-grid numerical report.

    Model answer. For three bits and phi=3/8, phase estimation returns 011 with probability one. For phi=0.3, the distribution follows the squared Dirichlet-kernel amplitudes and peaks at y=2 (phase 0.25), with y=3 next. The largest controlled power is U^4; powers 1,2,4 represent seven base-U applications if expanded.

    Model result and check. CI compares analytic and simulated probabilities and recomputes maximum power/query cost.

    Acceptance test. The workbench asserts output 011 for 3/8 under the declared bit order and reproduces the off-grid distribution.

    Companion work

    Artifacts for this chapter

    These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.

    1. Reproduce or test

      python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts

    Provenance

    Sources and review

    1. A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arXiv. 1995primary preprint
    2. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
    3. John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
    4. John Watrous. The Theory of Quantum Information. Cambridge University Press / University of Waterloo. 2018textbook
    5. Don Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research report / arXiv. 2002primary paper
    6. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing. 1997primary paper
    7. National Academies of Sciences, Engineering, and Medicine. Quantum Computing: Progress and Prospects. National Academies Press. 2019consensus study report

    The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.

    External review: Open.

    How review worksRevision historyReport or inspect errata

    Dependency graph

    Prerequisites for this chapter

    1. Quantum Fourier TransformPart IV. Protocols and Algorithms · Chapter 31
    2. Oracles and Query ComplexityPart IV. Protocols and Algorithms · Chapter 27

    Continue the thread

    1. Shor as Period FindingPart IV. Protocols and Algorithms · Chapter 33
    2. Grover and Amplitude AmplificationPart IV. Protocols and Algorithms · Chapter 30
    3. Hamiltonian SimulationPart IV. Protocols and Algorithms · Chapter 34

    Cite this chapter