Reflection: Algorithmic Toolkit

You have now written, simulated, and verified a rich collection of quantum algorithms. Before moving on, it is worth stepping back to see the full landscape — what each algorithm achieves, why it works, and how the pieces fit together.

The algorithms at a glance

Deutsch and Deutsch–Jozsa

The simplest demonstrations of quantum advantage. A single query to the Hadamard-prepared oracle decides whether a Boolean function $f\colon\{0,1\}^n \to \{0,1\}$ is constant or balanced, whereas the best classical algorithm requires $2^{n-1}+1$ queries in the worst case. The key mechanism is phase kickback: the oracle flips the phase of input states where $f(x) = 1$ , and the final Hadamard layer turns global phase patterns into measurement outcomes.

Bernstein–Vazirani

A refinement of Deutsch–Jozsa that extracts a hidden $n$ -bit string $s$ in a single oracle call (the classical lower bound is $n$ queries). The oracle implements $f(x) = s \cdot x \pmod{2}$ , and the same phase-kickback-plus-Hadamard structure reads $s$ directly from the output register.

Simon's algorithm

The first algorithm to demonstrate an exponential separation for a structured problem. Given a promise that $f(x) = f(x \oplus s)$ for a hidden period $s$ , Simon's algorithm finds $s$ using $O(n)$ quantum queries and $O(n^2)$ classical post-processing (solving a linear system over $\mathbb{F}_2$ ). This is the conceptual ancestor of Shor's algorithm.

Quantum Fourier Transform

The QFT on $n$ qubits is the unitary

\mathrm{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} |k\rangle, \qquad N = 2^n.

It is implemented in $O(n^2)$ gates (Hadamards plus controlled phase rotations), compared with the $O(N \log N)$ gates a naive classical FFT would need if encoded gate-by-gate. The QFT underpins nearly every super-polynomial quantum speedup.

Quantum Phase Estimation

QPE uses the QFT in reverse to extract the eigenphase $\phi$ of a unitary $U$ with precision $\epsilon \approx 2^{-t}$ (for $t$ ancilla qubits) using $O(2^t) = O(1/\epsilon)$ controlled- $U$ applications in total (ancilla qubit $k$ drives $U^{2^k}$ , requiring $2^k$ applications of controlled- $U$ , and $\sum_{k=0}^{t-1}2^k = 2^t - 1$ ). Classically, finding $\phi$ to the same precision requires exponentially many samples. QPE is the kernel inside both Shor's algorithm and quantum chemistry simulations (HHL, VQE pre-processing).

Grover's search

Grover's algorithm finds a marked item among $N = 2^n$ candidates in $O(\sqrt{N})$ oracle calls, compared with $O(N)$ classically. Each iteration applies the oracle (phase-flip the marked state) followed by the diffuser (reflection about the equal superposition $|+\rangle^{\otimes n}$ ). After approximately $\tfrac{\pi}{4}\sqrt{N}$ iterations the amplitude on the marked item is close to 1. For $N = 4$ (two qubits) a single iteration achieves certainty.

Period finding and Shor's algorithm

Shor's algorithm factors an integer $N$ in polynomial time by reducing factoring to order finding: given $a$ coprime to $N$ , find the smallest $r$ such that $a^r \equiv 1 \pmod{N}$ . Order finding is solved by QPE applied to the modular-exponentiation unitary $U|y\rangle = |ay \bmod N\rangle$ . The QFT reveals the period $r$ , from which the factors follow via classical number theory.

Unifying themes

Complexity gains in one table

| Algorithm | Problem | Classical queries | Quantum queries | |---|---|---|---| | Deutsch–Jozsa | Constant vs. balanced | $2^{n-1}+1$ | $1$ | | Bernstein–Vazirani | Find hidden string | $n$ | $1$ | | Simon | Find hidden period (mod 2) | $\Omega(2^{n/2})$ | $O(n)$ | | Grover | Unstructured search | $O(N)$ | $O(\sqrt{N})$ | | Shor (order finding) | Find multiplicative order | $\exp(O(n^{1/3}))$ | $\mathrm{poly}(n)$ |

All separation results assume the oracle (black-box) model; Shor's gain is in the circuit model against the best known classical algorithm (GNFS).

Gate-set hierarchy

The circuits you built all fit inside the Clifford + $T$ universal gate set. Hadamards and CNOT gates are Clifford operations; the controlled phase rotations in the QFT — and the $T$ gate — are the non-Clifford gates that push beyond stabilizer circuits and unlock the full computational power.

What comes next

The advanced track builds on each of these algorithms:

Error correction makes QPE and Grover fault-tolerant.
Variational algorithms (VQE, QAOA) use the same circuit patterns in a hybrid classical-quantum optimization loop, targeting near-term devices.
Hamiltonian simulation uses Trotterized product formulas as building blocks, with QPE providing the energy readout.
Quantum machine learning leverages amplitude encoding and the HHL linear-systems algorithm, both of which rely on the QFT.

Every algorithm you have written is a working sub-routine of something larger. The toolkit is ready.