Lecture: Grover's Algorithm, Quantum Fourier Transform, Quantum Phase Estimation and Resource Estimates

Introduction

In the first part of this course, we explored the physical implementations of quantum computing: neutral atoms in optical tweezers, trapped ions, superconducting circuits cooled to millikelvin temperatures, photons, and electron spins in quantum dots.
Each platform offers different engineering trade-offs, coherence times, and scalability prospects.

Last week, we took our first deep dive into quantum algorithms with Shor's factoring algorithm, the poster child for exponential quantum speedup.
We saw how factoring an integer $N$ reduces to the problem of finding the period $r$ of the function $f(x)=a^{x}modN$, and how quantum computers can solve this period-finding problem exponentially faster than any known classical algorithm.
Along the way, we briefly mentioned two powerful quantum subroutines that made this possible: the Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE).
In that lecture, we treated QFT and QPE primarily as black box tools that we plugged into Shor's algorithm to extract the period.
We didn't fully unpack how they worked or why they're so powerful beyond this specific application.
Today's lecture aims at opening those black boxes, as well as another well known quantum algorithm, and understand the quantum primitives that power not just Shor's algorithm, but the landscape of quantum algorithms:

• Grover's Algorithm: Last week we mentioned that Grover provides (only) a quadratic speedup (vs Shor's exponential) for unstructured search.
  We'll see exactly how amplitude amplification works by relying on a geometric rotation in Hilbert space.
• Quantum Fourier Transform (QFT): We'll go beyond using QFT as a subroutine and understand its circuit implementation, its connection to classical Fourier analysis, and why it achieves an exponential speedup.
• Quantum Phase Estimation (QPE): We'll formalize this eigenvalue extraction technique and see why it's the workhorse behind not just Shor's algorithm, but also quantum chemistry simulations, solving linear systems, and many other applications.

Beyond understanding these individual algorithms in depth, we'll step back to survey the broader (but partial) quantum algorithm landscape: What classes of problems admit quantum speedups?
Where are the boundaries?
Which real-world applications might actually benefit from quantum hardware in the near term?

Finally, we'll confront the resource estimation reality check.
Shor's algorithm can in theory factor a 2048-bit RSA key but how many physical qubits does that actually require?
How long would it take?
What error rates can we tolerate?
These aren't just academic questions but determine whether quantum advantage is achievable with current or near-term hardware.
Spoiler alert: the resource estimates will reveal that we cannot run most of these algorithms on today's noisy devices without bridging the gap between current machines' error rates vs what is required for high-level applications.
This sets the floor for the quantum error correction lectures that will follow, where we'll see exactly how to bridge this gap between the imperfect physical qubits from our first lectures and the pristine logical qubits that algorithms require.
Error correction isn't a just nice-to-have feature, it's the essential bridge from quantum computing theory to quantum computing reality.

These notes were written for the Experimental Quantum Computing and Error Correction course of M2 Master QLMN, see the course's website for more information.
The notebooks used to illustrate the algorithms are adapted from the now archived Qiskit/textbook GitHub repository (see IBM Quantum Learning for the new URL).

Let's begin by diving into Grover's algorithm, the quintessential example of quadratic quantum speedup.

Grover's Algorithm

Quiz

Last time, we asked you to read the paper 2.
Let's test our understanding of this pioneering (from 1998!) NMR implementation of Grover's algorithm with some questions covering the physical implementation, experimental techniques, and the specific dynamics of the $N=4$ case.

Introduction

Grover's algorithm addresses one of the most fundamental problems in computer science: searching through an unstructured database.
Let's start by explaining the problem at stake.
Imagine you have a list of $N=2^m$ items, and somewhere in that list is a special element that we call $w$ (aka the "winner") that satisfies some unique property.
Classically, finding this needle in items haystack requires checking them one by one: on average $N/2$ queries, and in the worst case, all $N$ items.

Grover's algorithm 3 provides a quadratic speedup, finding the winner in only $O(\sqrt{N})$ queries.
While this may seem modest compared to the exponential speedup of Shor's algorithm, Grover's approach is widely applicable which make it so valuable.
The underlying technique of amplitude amplification serves as a general subroutine for any problem where solutions can be verified efficiently.

Algorithm Overview

The algorithm consists of three main components that work together to concentrate probability amplitude on the winning state:

• State Preparation: We initialize the quantum register in a uniform superposition over all possible items in our search space.
• Oracle: A black-box operation that "marks" the correct answer by flipping its phase (without revealing which state it is).
• Diffusion Operator: An amplification step that increases the probability of measuring the marked state while suppressing all others.

See Fig. for the circuit structure for Grover's algorithm.
The circuit begins by the state preparation phase in red with Hadamard gates creating the uniform superposition, followed by the oracle (yellow) marking the winner state, and then the diffusion operator (blue) that amplifies the marked state's amplitude.
For small databases like $N=4$ as we will see later, a single iteration achieves near-perfect success probability.
For other settings, we need to repeat Oracle+Diffuser.
Let's go through all the steps of this algorithm one by one.

The Initial Superposition

Since we have no prior knowledge about which item is the winner, we begin by preparing a uniform superposition over all $N$ basis states.
This is achieved by applying Hadamard gates, introduced in the first lecture, to each of the $m$ qubits initialized to $|0⟩$:

At this stage, if we were to measure immediately, each outcome $|x⟩$ would appear with equal probability $1/N$.
The probability of successfully finding the winner in a single shot is therefore $1/N$, no better than classical random guessing.
To see why this is problematic, consider that the expected number of queries $X$ to find the item classically is:

Our goal is thus to transform this uniform distribution into one heavily concentrated on $|w⟩$, so that measurement yields the correct answer with high probability after only $O(\sqrt{N})$ iterations.

The Oracle or the Yes/No Verifier Blackbox Function

Grover's algorithm does not "look inside" the database.
Rather, it relies on an oracle, a black-box function that can recognize the winner when presented with it.
The oracle's job is simple: given any state $|x⟩$, flip its phase if and only if $x=w$.

This distinction between finding and verifying is fundamental in complexity theory.
Recall from lecture 1 that many problems in the class NP (Non-deterministic Polynomial time) are hard to solve but easy to verify.
One example to understand this subtle difference is to consider Sudoku.
Checking whether a completed grid is valid takes seconds, but finding the solution from scratch can be much harder.
Grover's algorithm exploits this asymmetry, working for any problem where verification is efficient.
To get some intuition of what the oracle is, let's go through multiple definitions and interpretations.

Mathematical Definition of the Oracle

As we just mentioned, the oracle $U_w$ acts on computational basis states as follows:

This can be written compactly as $U_w=\mathbb{I}-2|w⟩⟨w|$, which is a reflection operator about the vector state $|w⟩$.
In matrix form, for a 2-qubit system where the winner is $|10⟩$, we can write:

Notice that only the diagonal entry corresponding to the winner state carries a $-1$.
This phase flip is invisible if you measure immediately (the probabilities $|\text{amplitude}{|}^2$ are unchanged), but it sets the stage for interference in the next step.

Building the Oracle from a Classical Function

Another way to get intuition on this oracle function is to express it from a classical function.
Indeed, in practice, we construct the oracle from a classical boolean function $f(x)$ that identifies the winner:

The oracle's action can then be written as $U_w|x⟩=(-1{)}^{f(x)}|x⟩$.
But how do we actually implement this phase flip using quantum gates?

The standard approach uses phase kickback.
Suppose we have a quantum circuit $U_f$ that computes $f$ in the usual way: $|x⟩|0⟩\stackrel{U_f}{\to }|x⟩|f(x)⟩$.
The trick is to prepare the target qubit not in $|0⟩$, but in a particular state, for instance $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$, that turns out to be an eigenstate of the unitary transformation.
When we apply $U_f$ with this special target state, the following happens.
If $f(x)=0$, the target remains $|-⟩$.
But if $f(x)=1$, the XOR operation flips $|-⟩$ to $-|-⟩$, introducing a global phase of $-1$.
The result is:

The phase has been "kicked back" onto the input register, while the target qubit is left unchanged (up to a phase we can ignore).
This is the standard technique for converting any classical verification function into a quantum phase oracle.
Let's explain it in more details.

Phase Kickback: The Underlying Oracle Mechanism

To understand this more generally, consider a controlled-$U$ gate where the target is prepared in an eigenstate $|\psi ⟩$ satisfying $U|\psi ⟩=e^{i\varphi }|\psi ⟩$.

If the control qubit starts in a superposition:

The target qubit remains in $|\psi ⟩$, but the control qubit has acquired a new relative phase $e^{i\varphi }$.
This mechanism allows us to extract information about $U$ (its eigenvalue) and encode it as a phase on another register (here the control register), a principle that underlies not just Grover's oracle, but also quantum phase estimation and many other algorithms, we will thus mention it again below.

Geometric Interpretation of Grover's Algorithm

We have not yet covered all the 3 steps of Grover's algorithm, we are still missing the Diffuser one.
But before diving into this last part, we take a moment to focus on a geometric interpretation that will help us introduce this last part.
Grover's algorithm is indeed best understood through geometry.
The key insight that we will discover is that two reflections compose to give a rotation, a fact from elementary geometry that becomes the engine of Grover's quantum speedup.

See Fig. for an step-by-step illustration of how amplitudes evolve during Grover's algorithm.
Before the oracle, all states have equal positive amplitude.
After the oracle, the winner state's amplitude becomes negative, creating an asymmetry.
The diffusion operator then reflects all amplitudes about their mean, dramatically boosting the winner's amplitude while slightly decreasing all others.

Setting Up the 2D Subspace

Let's focus on the top row of Fig..
Although our Hilbert space has dimension $N=2^m$, the entire algorithm takes place in a two-dimensional subspace spanned by just two states:

• $|w⟩$: the target state we wish to find
• $|s^{\prime }⟩$: the uniform superposition over all non-winner states, defined as $|s^{\prime }⟩=\frac{1}{\sqrt{N-1}}\sum _{x\ne w}|x⟩$

The initial state $|s⟩$ lies in this plane because it can be written as a linear combination of $|w⟩$ and $|s^{\prime }⟩$.
Since $|s⟩$ has only a tiny component along $|w⟩$ (amplitude $1/\sqrt{N}$), it starts almost parallel to $|s^{\prime }⟩$.
More precisely, we can write any state in this subspace as:

For the initial state, the angle from the $|s^{\prime }⟩$ axis is:

This tiny angle (roughly $1/\sqrt{N}$ radians) is the starting point of our journey toward $|w⟩$.

Step 1: the Oracle as a Reflection

Now let's switch to the second row of Fig..
We mentioned several interpretations for the oracle $U_w$, the final one we will use is its geometric one.
The oracle $U_w=I-2|w⟩⟨w|$ performs a reflection about the hyperplane perpendicular to $|w⟩$.
Geometrically, if you picture $|w⟩$ as the vertical axis in our 2D subspace, see Fig., the oracle flips the state vector across the horizontal axis $|s^{\prime }⟩$.
The effect is simple: if the state was at angle $\theta$ above the $|s^{\prime }⟩$ axis, after the oracle it sits at angle $-\theta$ (below the axis).
The distance to $|w⟩$ hasn't changed, but the state has been "flipped" to the other side of $|s^{\prime }⟩$.

Step 2: The Diffusion Operator as a Second Reflection

Now we briefly mention the diffuser's geometric action to understand its effect intuitively.
As can be seen in the last row of Fig., the diffuser is a second reflection, now performed about the initial state $|s⟩$ itself.

The Diffusion Operator: Amplifying the Marked State

After applying the oracle, our quantum state looks similar to where we started, at least on the surface.
Indeed, if we measured at this point, we would still get each outcome with equal probability, since $|1/\sqrt{N}{|}^2=|-1/\sqrt{N}{|}^2$.
But what is crucial is that every amplitude remains $1/\sqrt{N}$ in magnitude, except the winner, which now carries a negative sign!

The final step is the diffusion operator $U_s$, also known as the Grover diffusion or "inversion about the mean."
As we just saw geometrically, this operator reflects all amplitudes about their average value $|s⟩$, which has the effect of boosting the marked state (whose amplitude is below the mean) while suppressing all others.
Mathematically, the diffusion operator is defined as:

where $|s⟩$ is still the uniform superposition.
The full Grover's algorithm is composed of the oracle and diffuser, but how many times?
We repeat it to get as close as possible to the winner state $|w⟩$.

Iteration and Optimal Stopping

The following Fig. builds on Fig. and depicts the geometric view of the full Grover's algorithm in the 2D subspace spanned by $|w⟩$ and $|s^{\prime }⟩$ where Oracle and Diffuser are repeated.
Composing these two reflections produces a rotation by $2\theta$ towards the target state $|w⟩$. After $k$ iterations, the state has rotated through angle $(2k+1)\theta$.
The amplitude of the winner state grows while all other amplitudes shrink, this is the amplification we sought.

We want to stop when this angle reaches approximately $\pi /2$, at which point the state is nearly aligned with $|w⟩$ and measurement succeeds with high probability.
This can be see as $k^{\ast }=\lfloor \frac{\text{Total distance}}{\text{Step size}}\rfloor =\lfloor \frac{\pi /2}{\theta }\rfloor$.
Solving $(2k^{\ast }+1)\theta \approx \pi /2$ for large $N$ (where $\theta \approx 1/\sqrt{N}$):

This is the origin of the $\sqrt{N}$ scaling.
Each iteration rotates by a tiny angle $\sim 1/\sqrt{N}$, and we need $\sim \sqrt{N}$ such rotations to traverse a quarter-circle.

Generalization: Multiple Winners

We briefly mention the case where multiple states are considered as winners.
The algorithm extends naturally to the case where there are $m$ solutions rather than just one.
We redefine the "winner state" as the uniform superposition over all solutions:

The geometric picture remains the same, but now the initial angle is larger: $\sin \theta =\sqrt{m/N}$ instead of $1/\sqrt{N}$.
Since we start closer to the target subspace, fewer iterations are needed:

This makes sense: if half the items are winners ($m=N/2$), we only need about one iteration.

Oracle = (CZ on qubits that detect |101⟩) + (CZ on qubits that detect |110⟩)

Understanding the Amplitude Dynamics: Inversion About the Mean

The geometric picture is clear, but it's also helpful to see how the amplitudes evolve algebraically.
This reveals the mechanism of "inversion about the mean" that gives the diffusion operator its amplifying power.
The final state after one iteration is:

After applying the oracle, the state becomes $|s_w⟩=\frac{1}{\sqrt{N}}\sum _x(-1{)}^{f(x)}|x⟩$, where $f(x)=1$ only for the winner.
Let's compute what happens when we apply the diffusion operator $U_s=2|s⟩⟨s|-I$:

Using the fact that $⟨s|x⟩=\frac{1}{\sqrt{N}}$, the full expression for the amplitude becomes:

The key observation is that $⟨s|s_w⟩=\frac{1}{N}\sum _x(-1{)}^{f(x)}=\frac{N-2}{N}$ (since $N-1$ terms contribute $+1$ and one term contributes $-1$).
After some algebra, the amplitude of state $|x⟩$ becomes:

The winner's amplitude roughly triples with each iteration (for large $N$), while loser amplitudes decrease slightly.
This is the quantitative manifestation of "inversion about the mean": the winner amplitude, being far below the mean, gets reflected far above it.

The Physical Origin of Interference

To finish discussing the algorithm and before switching to examples and experimental realisations, let's wonder where the quantum interference takes place.
You remember from previous lecture that a quantum computer's advantage does not rely in running the same calculation in parallel over all the superposed states.
Rather, you only want a single state in your final state distribution.
The speedup in Grover's algorithm comes from this quantum interference, and it's worth understanding where this interference arises:

• The Oracle Step:
  • By flipping the winner's phase to negative, the oracle creates a situation where the winner amplitude is now "out of step" with all the others.
  • The mean amplitude drops slightly because of this negative contribution.
• The Diffusion Step: The diffusion operator reflects all amplitudes about this new (lower) mean.
  • For the loser states, which sit just above the mean, reflection barely moves them.
  • But the winner state sits far below the mean, so reflection pushes it upward, effectively collecting constructive contributions from all the other states, the $\times 3$ factor we saw in the previous section.

This is constructive interference for the winner and destructive interference for the losers, achieved not by path differences (as in optical interference) but by manipulation of quantum phases.

Example: 2-Qubit Search ($N=4$)

Let's work through Grover's algorithm for the smallest non-trivial case: searching among 4 items with 2 qubits.
In this example, we'll suppose the winner is $|w⟩=|11⟩$.

Initial Setup

The starting angle is ${\theta }_0=\arcsin (1/\sqrt{4})=\arcsin (1/2)=\pi /6$ (30 degrees).
Since we need to rotate from $\pi /6$ to $\pi /2$, the optimal number of iterations is $k^{\ast }=1$.
This is a special case where a single Grover iteration gives perfect success probability.

The Oracle

For winner state $|11⟩$, the oracle flips only this state's phase:

In matrix form, this oracle is simply the controlled-Z gate: $U_w=CZ$, seen in lecture 1:

Implementing the Diffusion Operator

The diffusion operator $U_s=2|s⟩⟨s|-I$ might look complicated, but there's a clear circuit decomposition.
The key insight is that reflecting about $|s⟩$ is equivalent to:

1. Rotating $|s⟩$ to $|0⟩$: $H^{\otimes n}$
2. Reflecting about $|0⟩$: $U_0$
3. Rotating back: $H^{\otimes n}$

Where $U_0$ flips the sign of $|00...0⟩$ and leaves all other states unchanged.
The operator $U_0$ can be implemented as a multi-controlled Z gate (flip sign when all control qubits are 0).
For 2 qubits, this decomposes to $U_0=Z_1{Z}_2\cdot CZ$:

The complete circuit has three stages: Initialization (Hadamards to create $|s⟩$), Oracle (CZ gate marking the winner), and Diffuser (H-Z-CZ-H sequence), see Fig..

A more complex example with 5 qubits and one winner can be seen using Quirk.

Qiskit Examples

Let's look at examples that you can run yourself.

Examples with 2 And 3 Qubits

First go to Colab, a colaborative jupyter notebook website.
Then click on "Open Notebook" for a new Colab notebook and paste the Github url from a Grover implementation edited from the official qiskit release: qiskit-demo/presentations/grover.ipynb at main · francois-marie/qiskit-demo.

Application: Sudoku

How would you encode a $2\times 2$ Sudoku puzzle as a Grover search problem?
Let's do this using Qiksit and Colab!

Experimental Implementations

We end this first part of the lecture by looking at some experimental implementations.
Grover's algorithm has been demonstrated on many quantum computing platforms: historically NMR but also superconducting (SC), trapped ions, photonics, and spins.
The table below summarizes key experimental results, showing the gap between theoretical and achieved success probabilities, a measure of hardware quality.

Notice that silicon spin qubits achieve high fidelities, approaching theoretical limits.
The gap between achieved and theoretical success rates reflects gate errors and decoherence in current hardware.

Quantum Fourier Transform and Phase Estimation

Having explored Grover's quadratic speedup for unstructured search, we now turn back to last week's lecture, to a different class of algorithms that achieve exponential advantages.
The Quantum Fourier Transform and Quantum Phase Estimation are the workhorses behind Shor's factoring algorithm but also quantum chemistry simulations, and many other applications.
While Grover taught us about amplitude amplification through geometric rotations, QFT and QPE reveal how quantum computers can extract hidden periodicities and eigenvalues exponentially faster than classical approaches.

Classical Fourier Transform

Let's start by recalling some intuition on the Fourier transform.
The Fourier transform is one of the most powerful tools in mathematics and engineering.
It converts signals from the time domain to the frequency domain, revealing hidden periodicities, see Fig. that illustrates the concept of Fourier transformation, adapted from Wikipédia's page on the Fourier transform.
A time-domain signal $f$ containing multiple frequency components (in black, top row) is decomposed into its constituent frequencies (red, green and blue, middle row).
The Fourier transform reveals the amplitude and phase of each frequency component (bottom row), making hidden periodicities visible.
The key insight is that periodic structure in the time domain becomes localized peaks in the frequency domain.
Mathematically, the transform $\hat{f}(\xi )$ tells us "how much" of each frequency $\xi$ is present in the original signal:

The quantum version performs this transformation on quantum amplitudes rather than classical signals but the idea remains the same.

Discrete Fourier Transform (DFT)

For computational purposes, we can work with discrete vectors rather than continuous functions.
Given an input vector $(x_0,x_1,\dots ,x_{N-1})$, the DFT produces an output vector $(y_0,y_1,\dots ,y_{N-1})$ where:

The quantity ${\omega }_N$ is the primitive $N$th root of unity, a complex number that, when raised to the $N$th power, equals 1.

The Quantum Fourier Transform

Going from DFT to QFT is simply switching from vectors to vector states: the QFT performs the DFT on the amplitudes of a quantum state.
If we start with a state $|\psi ⟩=\sum _{j=0}^{N-1}{x}_j|j⟩$, the QFT produces:

For a computational basis state $|j⟩$, this becomes:

The QFT creates a superposition where each basis state $|k⟩$ acquires a phase that depends on both $j$ (the input) and $k$ (the output index).

Matrix Representation

Mathematically, the QFT can be expressed as an $N\times N$ unitary matrix:

Each row represents a different "frequency", and the entries oscillate faster as you move down the matrix.

Key Properties

For the sake of completeness, we briefly mention some key properties of the QFT.
The QFT is a unitary transformation: $F_N{F}_N^{†}=I$.
This means it preserves probability (as all quantum operations must) and is reversible.
The inverse QFT is simply $F_N^{†}$, obtained by taking the complex conjugate of all entries.

Building Intuition: How the QFT Encodes Information

Before diving into the circuit representation of the QFT, we build some intuition by looking at an example of QFT on basis states.
A feature of the QFT is that when applied to a basis state $|j⟩$ (eg $|j⟩=|5⟩=|101⟩$), the output can be written as a tensor product of single-qubit states.
As we will see explicitly by taking the example of 3 and 4 qubits, each output qubit is in a superposition $|0⟩+e^{i{\varphi }_k}|1⟩$, where the phase ${\varphi }_k$ depends on the input $j$:

In binary notation, where $j=j_1{j}_2\cdots j_n$ and $0.j_j{j}_{j+1}\cdots j_n$ denotes the binary fraction, this becomes:

The different qubits rotate at different "frequencies":

• The least significant output qubit rotates by $\pi$ between consecutive inputs (fastest oscillation) hence oscillates between $|+⟩$ and $|-⟩$,
• The next qubit rotates by $\pi /2$ (half the frequency), hence oscillates between $|+⟩,|i⟩,|-⟩,|-i⟩$
• Each subsequent qubit rotates half as fast

This hierarchical structure of phases is what makes the QFT useful for detecting periodicity (on what relies Shor's algorithm): if the input state has period $r$, the output will have peaks at multiples of $N/r$.

As shown in Fig., the QFT output states can be visualized on the Bloch sphere with their phase relationships. Let's map explicitly input number states to their binary representations and QFT outputs in the following table:

The first qubit oscillates from $|+⟩,|T_1⟩,\dots ,|-i⟩,|T_4⟩$.
In Fig. and Fig., we can see this even more clearly on 4 qubits, where the first qubit oscillates between $2^4=16$ states:

The pattern reveals how the input number $j$ gets encoded into the relative phases of the output qubits.

Let's write the full explicit tensor product form for QFT on $|5⟩$: