QubitLab
IDELearnPlaygroundDocsCommunity
Log in
QubitLab
IDELearnPlaygroundDocsCommunity
Log in
QubitLab
IDELearnPlaygroundDocsCommunity
Log in
HomeLearnCatalogRanksPlaygroundDocs
04 · QFT and phase estimation0%

You are reading without signing in. Sign in or continue as guest to take quizzes and climb the ranks.

Learn/QC 202Quantum Algorithms·Lesson 4 of 5

QFT and phase estimation

The Fourier transform on amplitudes, and the routine that reads eigenphases: the engine inside Shor.

Intermediate14 min read6 sections · 2 questions+45
By the end you will be able to
  1. 01Read a QFT circuit: Hadamards and controlled phases in a triangle, then swaps.
  2. 02Explain what phase estimation outputs for an eigenstate.
  3. 03Relate precision to the number of counting qubits.
QFT∣x⟩=N​1​k=0∑N−1​e2πixk/N∣k⟩,N=2n
The same transform as classical DFT, but on amplitudes: n qubits need only O(n²) gates instead of O(N log N) operations. The catch is that you cannot read the amplitudes out directly.
Hands-on

QFT of |101⟩

Open the State tab: all eight basis states have equal probability but phases that advance in steps; the Line view shows the phase ramp. Then open Compile → Levels to see how many CPhase gates survive on hardware.

OpenQASM 3
OPENQASM 3.0;
include "stdgates.inc";
qubit[3] q;
x q[0];
x q[2];
barrier q;
h q[2];
cp(pi/2) q[1], q[2];
cp(pi/4) q[0], q[2];
h q[1];
cp(pi/2) q[0], q[1];
h q[0];
swap q[0], q[2];
Sign in to run (nothing is saved)
Open in the IDE Open in the Playground

01Phase estimation

Given a unitary U and an eigenstate |u⟩ with U|u⟩ = e^{2πiφ}|u⟩, phase estimation writes φ into a register of t counting qubits: controlled-U^{2^j} gates kick the phase back onto the counting qubits, and an inverse QFT turns the phase ramp into a binary number. With t qubits you read φ to t bits of precision with high probability.

Hands-on

Estimate φ = 1/4 with two counting qubits

U = P(π/2) on q2 (eigenstate |1⟩, φ = 1/4). Simulate: the counting register reads 01 = 1/4 in binary every time. Change the phase to π/3 and the answer spreads: 1/6 is not representable in two bits.

OpenQASM 3
OPENQASM 3.0;
include "stdgates.inc";
qubit[3] q;
bit[2] c;
x q[2];
h q[0];
h q[1];
cp(pi/2) q[0], q[2];
cp(pi) q[1], q[2];
barrier q;
swap q[0], q[1];
h q[0];
cp(-pi/2) q[0], q[1];
h q[1];
c[0] = measure q[0];
c[1] = measure q[1];
Sign in to run (nothing is saved)
Open in the IDE Open in the Playground
Knowledge check

2 questions · one try each counts

Question 1

Doubling the number of counting qubits in phase estimation…

Sign in to answer and climb the ranks; you will come back to this lesson.

Question 2

Why is the QFT not simply a faster FFT?

Sign in to answer and climb the ranks; you will come back to this lesson.

Key takeaway

The QFT is cheap on amplitudes but unreadable on its own; phase estimation uses it to turn an eigenphase into bits, one counting qubit per bit of precision.

Finished reading?

Knowledge check: 2 questions waiting above. Questions are optional. Mark it complete, or press Next: moving on marks it complete too.

Up next
Lesson 5 · 12 min
Shor's algorithm: the overview
Factoring reduces to period finding; period finding is phase estimation. What is quantum, what is classical, what it costs.
Further reading
  • Docs: QFT, QPE and IQPE benchmarks
More in Quantum Algorithms
  • Deutsch–Jozsa: one query instead of many
  • Bernstein–Vazirani: read a hidden string
  • Grover's search
Grover's searchShor's algorithm: the overview
In this lesson0%
  1. Introduction
  2. Try it: QFT of |101⟩
  3. Phase estimation
  4. Try it: Estimate φ = 1/4 with two counting qubits
  5. Knowledge check
  6. Key takeaway
QubitLab
IDELearnPlaygroundDocsCommunity
Log in
QubitLab
IDELearnPlaygroundDocsCommunity
Log in