Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 39 ยท Quantum Algorithms

Quantum Phase Estimation

Learn quantum phase estimation (QPE): how controlled unitaries and an inverse QFT read out an eigenvalue phase, with a runnable NumPy simulation.

Every unitary operation U has eigenvectors |u> that it only multiplies by a phase: U|u> = e^(2*pi*i*phi)|u>. The number phi between 0 and 1 is the eigenphase. Quantum phase estimation (QPE) takes U and one of its eigenvectors and writes phi into a register of t qubits, with t bits of precision.

QPE is the bridge between the Fourier transform and real problems. It is the second half of Shor's algorithm (the eigenphases of modular multiplication contain the period), the core of quantum chemistry energy estimation (eigenphases of e^(-iHt) are energies), and the engine of quantum counting for Grover's search.

The circuit

Use two registers: t counting qubits (all start in |0>) and the eigenstate register holding |u>.

  1. Hadamard on every counting qubit.
  2. For counting qubit j (counting from the least significant), apply controlled-U^(2^j) with that qubit as control and the eigenstate register as target.
  3. Apply the inverse QFT to the counting register.
  4. Measure the counting register. The integer m you read gives phi ~ m / 2^t.

Why this works: because |u> is an eigenvector, each controlled-U^(2^j) does not change |u> but gives the control a phase kickback of e^(2*pi*i*phi*2^j) on its |1> component. After the Hadamard and all the controlled gates the counting register is

Text
(1/sqrt(T)) * sum over k of  e^(2*pi*i*phi*k) |k>        with T = 2^t

This is exactly the QFT of the basis state |T*phi>, so applying the inverse QFT returns |T*phi> itself.

flowchart TB
    A["t counting qubits in |0>"] --> B["Hadamard on all"]
    B --> C["Controlled U^(2^j) on eigenstate"]
    C --> D["Inverse QFT"]
    D --> E["Measure: m / 2^t ~ phi"]
    F["Eigenstate |u>"] --> C

Phase estimation: kickback writes the phase into the counting register, the inverse QFT reads it out.

Run it

Below, U is a single-qubit phase gate diag(1, e^(2*pi*i*phi)) with eigenstate |1>. All pieces are explicit: controlled powers of U, and the inverse QFT as a matrix applied to the counting qubits.

Python Estimating phi = 0.3125 with 4 counting qubits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because 0.3125 = 5/16 can be written with 4 bits, the answer is exact: m = 5 with probability 1.

When the phase isn't exactly representable

Most phases are not m / 2^t for any integer m. Then the probability spreads across neighbors, with most of it landing on the two closest values. The textbook guarantee: with t counting qubits you get the best t-bit approximation with probability at least 4/pi^2 ~ 0.405, and at least 8/pi^2 ~ 0.81 for the nearest one or the other neighbor. To reach accuracy epsilon with failure probability delta, use t = n + ceil(log2(2 + 1/(2*delta))) counting qubits for n bits of accuracy.

Python phi = 1/3 and growing precision

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each extra counting qubit halves the error, and the probability of the best outcome stays near 0.68.

Where QPE is used

  • Order finding (Shor). Choose U as multiplication by a modulo N. Its eigenphases are s/r for the unknown order r. See Shor's algorithm.
  • Quantum counting. Apply QPE to the Grover iteration, whose eigenphases depend on the number of marked items M. This tells you M before running Grover's search.
  • Energy estimation. Choose U = exp(-iHt). The eigenphase gives the energy of a molecule, if your input state overlaps well with the ground state. See VQE and variational algorithms for the near-term alternative.
  • HHL linear solver. QPE extracts eigenvalues of a matrix to invert them.

Practical issues

  • You need the eigenstate. If the input state is a mixture of eigenvectors, QPE returns one of the eigenphases at random, weighted by overlap. Preparing a state with large overlap with the right eigenvector is often the hard part.
  • Circuit depth. The controlled-U^(2^j) blocks grow exponentially in j unless you can compute U^(2^j) in closed form (as Shor's algorithm does with modular exponentiation). That depth requires error correction, which is why QPE is considered a fault-tolerant algorithm.
  • Iterative variants. Kitaev's and "semiclassical" QPE use a single counting qubit again and again, with classical feedback, trading qubits for time.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does QPE estimate?

    For U|u> = e^(2pii*phi)|u>, QPE writes phi into the counting register.
  2. 2. What is the role of the inverse QFT in QPE?

    The counting register holds the QFT of |Tphi>; the inverse QFT returns |Tphi>.
  3. 3. With 6 counting qubits, the phase estimate is a multiple of what?

    The estimate is m / 2^6 = m / 64.
  4. 4. What happens if the input register is not an eigenstate of U?

    A superposition of eigenvectors collapses to one eigenphase on measurement.

Summary

  • QPE reads the eigenphase phi of U into t counting qubits using controlled powers of U and an inverse QFT.
  • Phase kickback writes e^(2*pi*i*phi*k) into the counting register; the inverse QFT converts it to the integer m ~ phi * 2^t.
  • Exact t-bit phases are found with certainty; others with probability above about 0.4 for the best value.
  • It powers Shor's algorithm, quantum counting and energy estimation, but needs deep circuits and a good eigenstate.

Next: Shor's Algorithm