Quantum Algorithms from First Principles

A quantum algorithm is a fixed list of quantum gates. The gates are chosen so their effects add up on the right answer and cancel on the wrong ones. Then one measurement is likely to show the answer. Most textbook quantum algorithms count how many times you must ask a hidden function a question. They do not count seconds. Those two counts can be very different.

A group of n qubits in an even blend holds 2^n amplitudes at once. But a measurement gives back just one n-bit string, picked at random. You never get to read the whole list. Quantum algorithms win only when interference piles the chance onto strings that reveal the answer, before you measure.

Deutsch–Jozsa tells whether a hidden function is constant or balanced with one quantum query. A normal program that must be certain needs up to 2^(n−1)+1 queries. It was the first proved gap between quantum and normal computers. Its key trick, called phase kickback, also drives Bernstein–Vazirani, Grover, and the phase estimation inside Shor.

The Bernstein–Vazirani algorithm finds a hidden n-bit string s with exactly one quantum query. The hidden function is f(x) = s·x mod 2. Any normal method needs n queries. A 4-qubit circuit reads the secret 101 straight off the measurement, every time.

Grover's algorithm finds one marked item among N choices. It uses about (π/4)·√N oracle calls, instead of the N/2 tries a normal search needs on average. It works by flipping and reflecting amplitudes over and over, so the chance piles up on the marked item. On 2 qubits, one round succeeds with a chance of exactly 1. You can run that circuit below, plus a 3-qubit version that succeeds with a chance of exactly 25/32.

Grover's speedup is a square root, not an exponential one. It needs √N oracle queries instead of N. The BBBV theorem proves no quantum algorithm can do unstructured search with fewer. In practice, the gain is usually eaten up by two costs. Building the oracle circuit is costly. And each quantum query is tens of thousands of times slower than a CPU's memory check. So no Grover run so far has beaten a normal computer on a real search.

The quantum Fourier transform (QFT) takes patterns in a quantum state's amplitudes, especially repeating ones, and turns them into chance peaks at matching frequencies. It uses only about n²/2 gates on n qubits. A normal FFT on the same data needs about n·2ⁿ steps. The catch: 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. It is not a faster FFT you can just plug in.

Quantum phase estimation reads out the eigenphase φ of a quantum operation as a binary fraction. The eigenphase is the hidden turn angle the operation adds to a special state. With t counting qubits you get a t-bit estimate of φ. The answer is exact and certain when φ fits in t binary digits. It is the engine inside Shor's algorithm and quantum chemistry plans. Below you can run a version with 2 counting qubits that reads out φ = 1/4 with a chance of 1.

Shor's algorithm factors large numbers by turning factoring into period finding. Period finding means finding how often a pattern repeats, and the quantum Fourier transform does that job well. The math is proved theory. But every hardware demo so far (such as 15 = 3 × 5) has been a pre-simplified special case. Published engineering estimates put RSA-2048 at millions of physical qubits running for hours. That is far beyond any machine that exists today.

Variational algorithms pair a small quantum circuit that has adjustable knobs with an optimizer on a normal computer. The quantum processor makes trial states. Measurement samples give an estimate of a cost. Then the normal computer adjusts the circuit's turn angles to push that cost down. These are the algorithms run most often on today's hardware. As of 2026, none has shown a start-to-finish advantage over the best normal methods.

Quantum teleportation moves the exact state of one qubit onto a faraway qubit. It uses up one shared entangled pair and two normal bits. Superdense coding is the reverse trade. It delivers two normal bits by sending one qubit. Both are proved theory. Both have been shown on real hardware. And neither one sends any information faster than light.

The capstone ties the course together with three mini-projects. You can redo every number in them by hand. Project 1 counts queries for Bernstein–Vazirani. Project 2 builds a table of how Grover's chance of success grows for N = 4, 8 and 16. Project 3 shows how the precision of phase estimation depends on the number of counting qubits. Each project pairs the arithmetic with a circuit you can run, and the arithmetic predicts its exact output.