Quantum Phase Estimation

algorithmsLab

18 min read

Quantum Phase Estimation

Reading out a unitary's eigenvalue as a binary fraction, using controlled powers of U and an inverse QFT.

Suggested before this lesson

Recall from Unitary Matrices: every eigenvalue of a unitary $U$ has the form $e^{2\pi i\theta}$ for some real $\theta$ , since unitary matrices only ever rotate an eigenvector's phase, never scale its length. Quantum Phase Estimation (QPE) is the algorithm that reads $\theta$ back out, given $U$ and one of its eigenvectors, using the Quantum Fourier Transform from last lesson as its final step.

Why This Is Hard Classically

Nothing about $\theta$ is written down anywhere; it's an intrinsic property of how $U$ acts on a specific eigenvector, extractable only by actually applying $U$ (or its powers) and reading out interference patterns, exactly the kind of task quantum circuits are suited for and classical linear algebra on an exponentially large matrix is not. QPE is also the engine inside Shor's algorithm (two lessons from now): the "hidden number" Shor's algorithm extracts turns out to be exactly the $\theta$ that QPE estimates, for a specific, cleverly chosen $U$ .

The Circuit

Two registers: $n$ counting qubits (start at $|0\rangle$ , will hold the answer), and an eigenstate register holding $|\psi\rangle$ , an eigenvector of $U$ with $U|\psi\rangle = e^{2\pi i\theta}|\psi\rangle$ .

$H$ on every counting qubit: uniform superposition, same starting move as every algorithm so far.
From counting qubit $k$ (weight $2^k$ ), apply controlled- $U^{2^k}$ onto the eigenstate register. Since $|\psi\rangle$ is an eigenvector, this doesn't change $|\psi\rangle$ itself at all, it kicks back a phase of $e^{2\pi i\theta\cdot2^k}$ onto counting qubit $k$ 's $|1\rangle$ amplitude, the exact same phase-kickback mechanism Deutsch-Jozsa was built on, just with a real (not just $\pm1$ ) phase this time.
Apply the inverse QFT to the counting register. The forward QFT (last lesson) turns a phase pattern into basis-state amplitudes; running it backwards does the opposite, turning the phase pattern step 2 just wrote onto the counting register back into a readable basis state.
Measure the counting register: the result is $\theta$ , written out as an $n$ -bit binary fraction (exact, if $\theta$ happens to be expressible in $n$ bits; an approximation otherwise).

Worked Example: $\theta = 1/4$ , Exactly

Let $U = P(\pi/2)$ (the $S$ gate) and $|\psi\rangle = |1\rangle$ : $P(\pi/2)|1\rangle = e^{i\pi/2}|1\rangle = e^{2\pi i(1/4)}|1\rangle$ , so $\theta = 1/4$ , exactly representable in 2 bits ( $0.01_2 = 1/4$ ). Use 2 counting qubits ( $q_0$ , $q_1$ ) and 1 eigenstate qubit ( $q_2$ , prepared in $|1\rangle$ with $X$ ):

Controlled- $U^{2^0}$ from $q_0$ : a single $CP(\pi/2)$ .
Controlled- $U^{2^1}$ from $q_1$ : applying $U$ twice is the same as applying $U^2 = P(\pi)$ once (both times, only on the branch where the control is $|1\rangle$ ), so a single $CP(\pi)$ .
Inverse QFT on ( $q_0$ , $q_1$ ): the last lesson's QFT circuit, run in reverse with every angle negated: $SWAP$ , $H$ , $CP(-\pi/2)$ , $H$ .

QPE Estimating

θ = 1/4

Step through gate by gate. Check the final Measurement Probabilities: the counting register (qubits 0, 1) lands on

q_1=0

q_0=1

with certainty, reading out

0.01_2 = 1/4

, exactly

\theta

. Qubit 2 (the eigenstate) never leaves

|1\rangle

, exactly as an eigenvector should.

Circuit

swap

Step through the circuit: after gate 9 of 9

10 / 10

Measurement Probabilities

$∣000 ⟩$

0.0%

$∣001 ⟩$

0.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

0.0%

$∣100 ⟩$

0.0%

$∣101 ⟩$

100.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

0.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0	0.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0	0.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	1.000	100.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	0	0.0%

Exercise

Build the 3-qubit QPE circuit above, estimating

\theta=1/4

for

U=P(\pi/2)

with eigenstate

|1\rangle

on qubit 2: prepare the eigenstate (

X

on qubit 2), put the counting register (qubits 0, 1) in superposition (

H

on each), apply the controlled-

U

powers (

CP(\pi/2)

from qubit 0,

CP(\pi)

from qubit 1, both onto qubit 2), then the inverse QFT on the counting register (

SWAP

H

on qubit 0,

CP(-\pi/2)

from qubit 0 to qubit 1,

H

on qubit 1).

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

Throughout the QPE circuit above, qubit 2 (the eigenstate register) never changes from

|1\rangle

. Why?

It's a coincidence specific to this example.

|1\rangle

is an eigenvector of

U

, so applying any power of

U

to it can only ever multiply it by a phase (an eigenvalue), never move it to a different state.

The controlled-

U

gates only fire when the counting qubits are

|0\rangle

Qubit 2 is never actually targeted by any gate.

See the precision/qubit-count tradeoff

Pick a $\theta$ that doesn't land on a clean binary fraction, then drag $t$ up and watch the measurement distribution sharpen around the best $n$ -bit estimate instead of spreading across several outcomes.

$True phase θ (as a fraction of 2 π)$

0.370

$Counting qubits t$

3 (8 outcomes)

Probability of measuring each m/8

$0/8$

0.0%

$1/8$

0.1%

$2/8$

0.2%

$3/8$

99.5%

$4/8$

0.2%

$5/8$

0.0%

$6/8$

0.0%

$7/8$

0.0%

The best estimate is $m = 3$ (that is, $\theta \approx 3/8 = 0.375$ ), hit with probability 99.5%. Push $t$ up: more counting qubits means more possible outcomes $m$ , so the distribution concentrates tighter around the true $\theta$ instead of spreading probability across neighboring values.

Check your understanding

\theta

isn't exactly representable in

n

bits (e.g.

\theta = 1/3

with only 2 counting qubits), what does QPE return?

An error; QPE only works for exactly representable

\theta

The single closest

n

-bit approximation, with certainty.

A probability distribution over

n

-bit strings, concentrated near the best

n

-bit approximation of

\theta

, most likely (but not certainly) returning the closest one.

Always 0, since

\theta

can't be represented.

Why This Is Hard Classically

Nothing about

\theta

is written down anywhere; it's an intrinsic property of how

U

acts on a specific eigenvector, extractable only by actually applying

U

(or its powers) and reading out interference patterns, exactly the kind of task quantum circuits are suited for and classical linear algebra on an exponentially large matrix is not. QPE is also the engine inside Shor's algorithm (two lessons from now): the "hidden number" Shor's algorithm extracts turns out to be exactly the

\theta

that QPE estimates, for a specific, cleverly chosen

U

The Circuit

Two registers:

n

counting qubits (start at

|0\rangle

, will hold the answer), and an eigenstate register holding

|\psi\rangle

, an eigenvector of

U

with

U|\psi\rangle = e^{2\pi i\theta}|\psi\rangle

H

on every counting qubit: uniform superposition, same starting move as every algorithm so far.

From counting qubit

k

(weight

2^k

), apply controlled- $U^{2^k}$ onto the eigenstate register. Since

|\psi\rangle

is an eigenvector, this doesn't change

|\psi\rangle

itself at all, it kicks back a phase of

e^{2\pi i\theta\cdot2^k}

onto counting qubit

k

|1\rangle

amplitude, the exact same phase-kickback mechanism Deutsch-Jozsa was built on, just with a real (not just

\pm1

) phase this time.

Apply the inverse QFT to the counting register. The forward QFT (last lesson) turns a phase pattern into basis-state amplitudes; running it backwards does the opposite, turning the phase pattern step 2 just wrote onto the counting register back into a readable basis state.

Measure the counting register: the result is

\theta

, written out as an

n

-bit binary fraction (exact, if

\theta

happens to be expressible in

n

bits; an approximation otherwise).

Worked Example:

\theta = 1/4

, Exactly

Let

U = P(\pi/2)

(the

S

gate) and

|\psi\rangle = |1\rangle

P(\pi/2)|1\rangle = e^{i\pi/2}|1\rangle = e^{2\pi i(1/4)}|1\rangle

, so

\theta = 1/4

, exactly representable in 2 bits (

0.01_2 = 1/4

). Use 2 counting qubits (

q_0

q_1

) and 1 eigenstate qubit (

q_2

, prepared in

|1\rangle

with

X

Controlled-

U^{2^0}

from

q_0

: a single

CP(\pi/2)

Controlled-

U^{2^1}

from

q_1

: applying

U

twice is the same as applying

U^2 = P(\pi)

once (both times, only on the branch where the control is

|1\rangle

), so a single

CP(\pi)

Inverse QFT on (

q_0

q_1

): the last lesson's QFT circuit, run in reverse with every angle negated:

SWAP

H

CP(-\pi/2)

H

Python

QPE Estimating

θ = 1/4

Step through gate by gate. Check the final Measurement Probabilities: the counting register (qubits 0, 1) lands on

q_1=0

q_0=1

with certainty, reading out

0.01_2 = 1/4

, exactly

\theta

. Qubit 2 (the eigenstate) never leaves

|1\rangle

, exactly as an eigenvector should.

Circuit

swap

Step through the circuit: after gate 9 of 9

10 / 10

Measurement Probabilities

$∣000 ⟩$

0.0%

$∣001 ⟩$

0.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

0.0%

$∣100 ⟩$

0.0%

$∣101 ⟩$

100.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

0.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0	0.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0	0.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	1.000	100.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	0	0.0%

Exercise

Build the 3-qubit QPE circuit above, estimating

\theta=1/4

for

U=P(\pi/2)

with eigenstate

|1\rangle

on qubit 2: prepare the eigenstate (

X

on qubit 2), put the counting register (qubits 0, 1) in superposition (

H

on each), apply the controlled-

U

powers (

CP(\pi/2)

from qubit 0,

CP(\pi)

from qubit 1, both onto qubit 2), then the inverse QFT on the counting register (

SWAP

H

on qubit 0,

CP(-\pi/2)

from qubit 0 to qubit 1,

H

on qubit 1).

Python

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

Throughout the QPE circuit above, qubit 2 (the eigenstate register) never changes from

|1\rangle

. Why?

It's a coincidence specific to this example.

|1\rangle

is an eigenvector of

U

, so applying any power of

U

to it can only ever multiply it by a phase (an eigenvalue), never move it to a different state.

The controlled-

U

gates only fire when the counting qubits are

|0\rangle

Qubit 2 is never actually targeted by any gate.

See the precision/qubit-count tradeoff

$True phase θ (as a fraction of 2 π)$

0.370

$Counting qubits t$

3 (8 outcomes)

Probability of measuring each m/8

$0/8$

0.0%

$1/8$

0.1%

$2/8$

0.2%

$3/8$

99.5%

$4/8$

0.2%

$5/8$

0.0%

$6/8$

0.0%

$7/8$

0.0%

Check your understanding

\theta

isn't exactly representable in

n

bits (e.g.

\theta = 1/3

with only 2 counting qubits), what does QPE return?

An error; QPE only works for exactly representable

\theta

The single closest

n

-bit approximation, with certainty.

A probability distribution over

n

-bit strings, concentrated near the best

n

-bit approximation of

\theta

, most likely (but not certainly) returning the closest one.

Always 0, since

\theta

can't be represented.