Quantum Algorithms from First Principles

A quantum algorithm is a fixed sequence of quantum gates that shapes interference so that a final measurement is likely to reveal the answer to a computational question. Most textbook quantum algorithms are stated in the query model: they count how many times you must call a black-box function, not how many seconds the computation takes — and the two can disagree badly.

A register of n qubits in uniform superposition carries 2^n amplitudes at once, but a measurement returns exactly one n-bit string, sampled at random — you never get to read the whole list. Quantum algorithms win only when interference concentrates probability onto answer-revealing strings before the measurement happens.

Deutsch–Jozsa decides whether a promised black-box function is constant or balanced in a single quantum query, where any classical algorithm demanding certainty needs up to 2^(n−1)+1 evaluations. It was the first provable quantum–classical separation, and its mechanism — phase kickback — powers Bernstein–Vazirani, Grover, and the phase estimation inside Shor.

The Bernstein–Vazirani algorithm recovers a hidden n-bit string s from a black-box function f(x) = s·x mod 2 in exactly one quantum query, where any classical strategy needs n queries. A 4-qubit circuit reads the secret 101 directly off the measurement, deterministically.

Grover's algorithm finds a marked item among N candidates using about (π/4)·√N oracle calls instead of the classical average of N/2, by repeatedly reflecting amplitudes so that probability piles up on the marked item. On 2 qubits a single iteration succeeds with probability exactly 1, and you can run that circuit — and a 3-qubit version with success probability exactly 25/32 — below.

Grover's speedup is quadratic, not exponential — √N oracle queries instead of N — and the BBBV theorem proves no quantum algorithm can do unstructured search with fewer queries. In practice the advantage is usually consumed by the cost of building the oracle circuit and by quantum oracle queries that are tens of thousands of times slower than a CPU's memory checks, so no Grover run to date has beaten a classical computer on a real search.

The QFT converts patterns in a quantum state's amplitudes — especially repeating, periodic patterns — into probability peaks at the corresponding frequencies, using only about n²/2 gates on n qubits where a classical FFT of the same data needs on the order of n·2ⁿ steps. The catch is that its input and output live in amplitudes you cannot read directly, so the QFT is an engine inside algorithms like phase estimation and Shor's, not a drop-in FFT accelerator.

Quantum phase estimation reads out the eigenphase φ of a unitary operation as a binary fraction: t counting qubits deliver a t-bit estimate of φ, exactly and deterministically when φ is a t-bit binary fraction. It is the engine inside Shor's algorithm and quantum-chemistry proposals, and below you can run a 2-counting-qubit instance that reads out φ = 1/4 with probability 1.

Shor's algorithm factors large numbers by converting factoring into period finding, a job the quantum Fourier transform does efficiently. The mathematics is proved theory, but every hardware demonstration so far (such as 15 = 3 × 5) has been a compiled special case, and published engineering estimates put RSA-2048 at millions of physical qubits running for hours — far beyond any machine that exists today.

Variational algorithms pair a small parameterized quantum circuit with a classical optimizer: the quantum processor prepares trial states, measurement samples estimate a cost, and the classical loop adjusts the circuit's rotation angles to push that cost down. They are the algorithms most often run on today's hardware — and, as of 2026, none has demonstrated an end-to-end advantage over the best classical methods.

Quantum teleportation moves the exact state of one qubit onto a distant qubit, consuming one shared entangled pair and two classical bits; superdense coding is the reverse trade, delivering two classical bits with one transmitted qubit. Both are proved theory, both are demonstrated on real hardware, and neither sends any information faster than light.

The capstone ties the course together with three mini-projects whose every number you can recompute by hand: query counting for Bernstein–Vazirani, a Grover iteration-scaling table for N = 4, 8, and 16, and phase-estimation precision as a function of counting qubits. Each project pairs the arithmetic with a runnable circuit whose exact output distribution the arithmetic predicts.