The qubit lab

The last chapter ended with a number that defeats every machine in this book. Describing fifty interacting electron spins takes $2^{50}$ complex numbers, petabytes of memory. Nature handles such systems in every molecule without storing anything at all. All our machines are built on bits. But physics allows another way of computing, and this chapter puts it to work, in simulation for now.

This chapter is a lab notebook. Each section is an experiment: a question, a setup, a result and a conclusion. We’ll build the setup ourselves, a qubit simulator in numpy that comes down to a few matrices and multiplications. There is no quantum computer in the sandbox, and our experiments don’t need one: as long as there are few qubits, an ordinary computer simulates them without any approximation. Why it falls short when there are many is one of the experiments too.

Experiment 1. A coin that remembers

We begin with a bet.

There is a qubit in the state “0” and an operation H. Apply H once and measure, and you get 0 or 1 half the time each, like a fair coin. What if you apply H twice in a row and only then measure?

0 and 1 half and half: two tosses in a row make the same coin 0 more often: three times out of four always 0 always 1

Always 0. A coin would give half and half: however many times you toss it, the result is random. But after the first H the qubit isn’t “0 or 1 with probability ½”; it is something else, and the second H returns it to where it started. Below is why.

A coin is described by probabilities: a column of two numbers, heads and tails, and a toss multiplies it by a matrix. Toss it as often as you like and it stays half and half. A qubit is described by different numbers, amplitudes, and they differ from probabilities in one respect: amplitudes can be negative, and in general complex. The probability of an outcome is the squared magnitude of its amplitude. After the first H the qubit’s amplitudes are $\tfrac{1}{\sqrt2}$ and $\tfrac{1}{\sqrt2}$: probabilities of ½ each, and a thousand measurements give about five hundred zeros. After the second H two contributions arrive at zero, $\tfrac12 + \tfrac12 = 1$, and two at one, $\tfrac12 - \tfrac12 = 0$. The paths leading to one have canceled each other out.

This is called interference, as with waves: crest meeting crest makes a higher wave, crest meeting trough leaves the water flat. Probabilities can’t do that: they are never negative, so they can only pile up. Write the main conclusion of the first experiment in the notebook, since the whole chapter rests on it: a quantum algorithm is a way of arranging for the paths to wrong answers to cancel each other and the paths to the right answer to add up.

Qubits, measurement, gates

Now the definitions. A qubit is a system with two basis states, written $|0\rangle$ and $|1\rangle$. Its state is a vector $\alpha|0\rangle + \beta|1\rangle$, that is, a column $(\alpha, \beta)$ of two complex numbers with $|\alpha|^2 + |\beta|^2 = 1$. A qubit whose amplitudes are both nonzero is said to be in a superposition. The word sounds intimidating, but there is only linear algebra behind it: $|0\rangle$ and $|1\rangle$ are a basis of a two-dimensional space, and a state is any vector of length 1 in that space.

You can’t read the amplitudes. The only way to learn anything about a qubit is measurement: it gives 0 with probability $|\alpha|^2$ and 1 with probability $|\beta|^2$, and afterward the qubit becomes $|0\rangle$ or $|1\rangle$, its old amplitudes gone. Measuring again shows the same thing. So a measurement yields a single bit, however much information the amplitudes held.

Everything else you can do to a qubit is done with quantum gates: multiplying the state vector by a matrix. Only a matrix that preserves the length of the vector will do, or else the probabilities would stop adding up to one. Such matrices are called unitary, and every one of them is invertible: up to the moment of measurement, a quantum computation can be run backward. We’ll need three gates from the start:

$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \qquad H = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$

$X$ is the quantum “not”: it swaps the amplitudes of $|0\rangle$ and $|1\rangle$. $Z$ flips the sign of the amplitude of $|1\rangle$ and leaves the probabilities alone. $H$, the Hadamard gate, turns $|0\rangle$ into $(|0\rangle + |1\rangle)/\sqrt2$ and $|1\rangle$ into $(|0\rangle - |1\rangle)/\sqrt2$. These two states are written $|{+}\rangle$ and $|{-}\rangle$. Measurement can’t tell them apart, since both give probabilities of ½. Interference can.

To a measurement $|{+}\rangle$ and $|{-}\rangle$ look the same, but after one more $H$ the first gives $|0\rangle$ and the second $|1\rangle$. What tells them apart is a sign, or, as physicists say, a phase. Phase is invisible to a direct measurement and decides everything in interference. The last line is a small identity that will come in handy later: put $Z$ between two $H$s and you get $X$.

The state of a single qubit is easy to draw. A common factor of the form $e^{i\gamma}$ on both amplitudes affects nothing, neither the probabilities nor the interference, and once it is dropped, any state can be written as $\cos\frac\theta2\,|0\rangle + e^{i\varphi}\sin\frac\theta2\,|1\rangle$. Two angles make a point on a sphere, called the Bloch sphere after the physicist Felix Bloch. $|0\rangle$ sits at the north pole, $|1\rangle$ at the south pole, and around the equator lie the equal superpositions, which differ only in phase. Gates are rotations of the sphere.

Experiment 2. Two qubits

Two bits have four states: 00, 01, 10, 11. Two qubits have four amplitudes, one for each: a vector $(a_{00}, a_{01}, a_{10}, a_{11})$. The index of an amplitude is the outcome written in binary, and we’ll treat qubit zero as the high bit, the one on the left. If the qubits are independent, the first in state $(\alpha, \beta)$ and the second in $(\gamma, \delta)$, their amplitudes multiply: $(\alpha\gamma, \alpha\delta, \beta\gamma, \beta\delta)$. This operation on vectors is called the tensor product, and in numpy it is np.kron. It also builds a gate for the whole system out of gates for single qubits: np.kron(H, I) is $H$ on qubit zero and nothing on qubit one.

What is new here are gates that act on two qubits at once. The chief of them, CNOT, is the “controlled not”: if the control qubit is 1, it flips the target qubit, and otherwise it does nothing. On basis states this is ordinary logic, the XOR of Chapter 29: $|a, c\rangle \mapsto |a, a \oplus c\rangle$. Things get interesting when the control qubit is in a superposition.

The result is $(|00\rangle + |11\rangle)/\sqrt2$, one of the four Bell states. Measurements give 00 and 11 at random, half and half, but never 01 or 10: the two qubits always agree. Yet each qubit on its own behaves like a coin, coming up zero and one equally often. And there is no way to give each qubit a state of its own.

A state of two qubits that doesn’t factor into a product of states of each is called entangled. Entanglement is why describing $n$ qubits takes $2^n$ amplitudes rather than $2n$: the state can’t be split into independent pieces. Build circuits like this yourself.

A line nobody can talk over

Matching coins alone are no miracle. You could put two identical notes in two envelopes and hand them to Alice and Bob, and their results would match too. What tells entanglement apart from notes prepared in advance is a game. It grew out of John Bell’s theorem (1964), in the form Clauser, Horne, Shimony and Holt gave it in 1969. Alice and Bob go to separate rooms, and each gets a random question bit: Alice gets $x$, Bob gets $y$. Each answers with a bit, $a$ and $b$, without conferring. They win if $a \oplus b = x \land y$: the answers must differ only when both questions are ones.

But if Alice and Bob each hold one qubit of a Bell pair, they can win $\cos^2\frac\pi8 \approx 85\,\%$ of the time: each turns their qubit by an angle that depends on the question, then measures. Try it.

No notes in envelopes can reach eighty-five percent, and experimental tests of entanglement are built on that. Such experiments have been run since the 1970s, closing the loopholes ever more tightly, and in 2022 John Clauser, Alain Aspect and Anton Zeilinger received the Nobel Prize in Physics for them. But no message can be sent over such a link, faster than light or slower: Alice’s answers on their own are a coin toss, whatever Bob does. The connection shows up only when the results are compared, and to compare them they have to be sent the ordinary way.

Experiment 3. Why this is hard to simulate

Our simulator stores every amplitude, and each new qubit doubles their number. To see how soon that becomes unmanageable, we’ll apply $H$ to all the qubits at once. A $2^n \times 2^n$ matrix isn’t needed: $H$ on qubit $k$ is a pass over the array that mixes pairs of amplitudes differing only in bit $k$.

Twenty qubits take 16 MiB and about a tenth of a second. Thirty take 16 GiB, which already calls for a serious server. Fifty take 16 PiB, and 300 qubits would need more bytes than there are atoms in the observable universe. Clever simulators get by with less memory when there is little entanglement, but in general nobody knows a way around the blowup. This was Feynman’s observation.

From it grew a popular shorthand: “a quantum computer tries all $2^n$ possibilities at once.” That is wrong. There are indeed $2^n$ amplitudes, but a measurement yields a single string of $n$ bits, chosen at random. If you “compute everything at once” and measure, you get a random answer, no better than a guess. There is a gain only when the problem can be arranged so that interference cancels the wrong answers, as in the first experiment. Few such problems are known; the next two experiments are about two of them.

Experiment 4. Deutsch–Jozsa: one call instead of half a million

You are given a function $f$ that takes an $n$-bit number and returns 0 or 1. You are promised one of two things about it: either it is constant, the same on every input, or it is balanced, 0 on exactly half of the inputs and 1 on the rest. Which is it? The function’s insides are hidden, and all you can do is call it. A hidden function like this is called an oracle, as in Chapter 56, except that this oracle doesn’t bluff and answers for any input. An ordinary deterministic algorithm may, in the worst case, need more than half of the inputs: you can see $2^{n-1}$ zeros in a row and still not know the answer. It takes $2^{n-1} + 1$ calls, which for $n = 20$ is more than half a million.

The quantum algorithm that David Deutsch and Richard Jozsa devised in 1992 needs one. An oracle in the quantum world works like this: it multiplies the amplitude of each $|x\rangle$ by $(-1)^{f(x)}$. The circuit is $H$ on every qubit, the oracle, $H$ on every qubit again, and a measurement.

A constant function gives $00\ldots0$ every time, a balanced one never. A single line shows why: after the second $H$ the amplitude of $|00\ldots0\rangle$ equals the average of all the signs, $\frac1N \sum_x (-1)^{f(x)}$. For a constant function all the signs are the same, and the average is $\pm 1$. For a balanced one there are as many pluses as minuses, and they cancel to zero. Interference again: the function was called once, but all $N$ amplitudes took part in that call, and the answer is a property of the whole function rather than of any single value.

The notebook needs a caveat as well. If randomness is allowed, an ordinary computer needs very little too: call $f$ on ten random inputs, and if the answers differ, the function is balanced; if they are all the same, it is constant, with an error of at most $2^{-9}$, like the Miller–Rabin primality test of Chapter 26. So Deutsch–Jozsa has no practical use. It is one of the first rigorous examples of a quantum algorithm outrunning every deterministic classical one exponentially, and its pattern of $H$, oracle, $H$ already contains the shape of later algorithms, Shor’s among them.

Experiment 5. Grover: the needle in √N steps

A problem that comes up in practice: among $N$ options a single one fits, checking an option is easy, and there is no structure beyond the check. Guessing a key, say, or finding the input on which a function says “yes.” An ordinary computer tries the options one by one, $N/2$ checks on average. In 1996 Lov Grover of Bell Labs devised a quantum algorithm that needs about $\frac{\pi}{4}\sqrt N$ calls to the check.

How many calls to the check does Grover’s algorithm need to find, almost surely, the one right option among a million?

about 20, like binary search about 800 about half a million, like trying them all one, like Deutsch–Jozsa

$\frac\pi4\sqrt{10^6} \approx 785$. That is far fewer than half a million but far more than twenty: binary search is helped by order, and Grover has no structure to lean on. Nor can it get by with one call; that has been proved.

A step of the algorithm consists of two actions. The oracle flips the sign of the right option’s amplitude. Then every amplitude is reflected about the mean of all of them: $a \mapsto 2\bar a - a$ (this is a unitary operation as well, built from the gates $H$, $X$ and a controlled $Z$). Suppose all $N$ amplitudes start out equal to $1/\sqrt N$. After the flip the right one is $-1/\sqrt N$, the mean drops slightly, and the reflection throws the right amplitude up to almost $3/\sqrt N$, while the others hardly change. At first each step adds about $2/\sqrt N$ to the right amplitude, then the gains shrink, and it reaches one after about $\frac\pi4\sqrt N$ steps.

Twenty-five steps instead of brute force’s five hundred on average, and a probability of 0.999. But then it falls: after fifty steps the right option almost never comes up. Geometrically, each step rotates the state vector by the same angle $2\theta$, where $\sin\theta = 1/\sqrt N$, in the plane spanned by the right option and the equal mix of all the others. After $k$ steps the probability of success is $\sin^2\bigl((2k+1)\theta\bigr)$: a rotation that isn’t stopped in time overshoots the target.

Grover can’t be beaten. As early as 1997 Bennett, Bernstein, Brassard and Vazirani proved that any quantum algorithm that knows nothing about the problem beyond the oracle’s answers needs on the order of $\sqrt N$ calls. So Grover won’t rescue us from hard problems. Problems in NP can be solved by trying every hint, and Grover speeds up the search only quadratically: $2^n$ becomes $2^{n/2}$, which is still exponential. For the symmetric ciphers of Chapter 59 it means that a quantum computer would cut a search through 128-bit AES keys to about $2^{64}$ steps, and the defense is a longer key, 256 bits.

Shor and RSA

We have met the most famous quantum algorithm already, in Chapter 60. In 1994 Peter Shor showed how to factor numbers and compute discrete logarithms in polynomial time, and so how to break RSA and Diffie–Hellman. At its heart is the same idea as in experiments 4 and 5. The quantum part looks for the period of the sequence $a, a^2, a^3, \ldots \bmod n$: all the powers are computed at once in superposition, and the quantum Fourier transform arranges the interference so that outcomes tied to the period are amplified and the rest cancel out. Ordinary modular arithmetic does the rest, and the math course takes it apart.

Two numbers keep the picture sober. The largest numbers factored on actual quantum hardware with Shor’s scheme are 15 (IBM, 2001, seven qubits) and 21 (2012), and even these experiments simplified the circuit by knowing the answer in advance. Meanwhile, by the estimate we quoted in Chapter 60, 2048-bit RSA needs fewer than a million noisy physical qubits and less than a week of running. The largest machines today have between a hundred and a little over a thousand qubits, three to four orders of magnitude fewer. The threat is real, though not immediate, and the response to it, post-quantum standards, has already been adopted.

What a quantum computer can’t do

The problems a quantum computer solves in polynomial time, erring at most a third of the time, form the class BQP. An error of a third can be made as small as you like by repeating the computation a few times and taking a vote. Here is what is known about the class’s place on the map of classes from Chapter 57. BQP contains P: an ordinary computation can be made reversible and run on qubits. BQP lies inside PSPACE: the amplitudes can be added up one at a time, in exponential time but with polynomial memory. Factoring is in BQP, and no fast classical algorithm for it is known.

Beyond that it is all “we don’t know.” Nobody knows whether a quantum computer solves NP-complete problems in polynomial time; most researchers think it doesn’t, and Grover’s limit hints at why: “trying everything at once” doesn’t work. Nobody even knows whether BQP is larger than P, because a proof would also separate P from PSPACE, and that is an open problem. One thing is known for sure. A quantum computer computes the same functions as a Turing machine, since an ordinary computer can simulate it, if exponentially slowly. So the undecidable problems of Chapter 56 stay undecidable, and quantum mechanics doesn’t overturn the Church–Turing thesis about what can be computed. Only how fast is in question.

Experiment 6. Noise and error correction

So far our qubits have been perfect. Qubits in a lab, whether superconducting circuits a few hundredths of a degree above absolute zero, ions in traps or atoms held in laser beams, interact with their surroundings all the time. Each such interaction is a small uncontrolled measurement: the amplitudes degrade little by little, and the superposition turns into an ordinary random coin, within fractions of a millisecond for superconducting qubits and within seconds for ions and atoms. This is called decoherence. Gates are imprecise too: on the best machines a two-qubit gate goes wrong about once in a thousand operations. Shor’s algorithm for RSA needs billions of gates. Without error correction it will never reach the end.

Ordinary bits are protected by repetition: keep three copies and take a vote. With qubits this looks impossible twice over. An unknown quantum state can’t be copied, which is a theorem, and measuring a qubit to check on it destroys it. Yet there is a way out, and the three-qubit code described below was published as early as 1985 by the physicist Asher Peres. No copying is needed: the state $\alpha|0\rangle + \beta|1\rangle$ can be encoded into three qubits as $\alpha|000\rangle + \beta|111\rangle$ with CNOTs, without knowing $\alpha$ and $\beta$. And what gets measured is the pairwise parities of the qubits: whether qubits 0 and 1 agree, and whether 1 and 2 do. $|000\rangle$ and $|111\rangle$ have the same parities, so measuring the parities reveals nothing about $\alpha$ and $\beta$ and doesn’t destroy them. But if one qubit has flipped, the parities show which one.

The three-qubit code survives any single flip and fails only if two or three qubits flip, which happens with probability $3p^2 - 2p^3$. At $p = 0.01$ that is three in ten thousand instead of one in a hundred. The amplitudes $0.6$ and $0.8i$ came through the correction untouched: we never learned them, yet we put them back in place. But a qubit can also go wrong in another way, by changing sign, as under a $Z$ gate. In 1995 Peter Shor, of the factoring algorithm, put together a nine-qubit code that guards against both kinds, the first code to correct any error in a single qubit: a triple of triples, with $H$ gates between the two levels. The codes in use today are laid out on a flat grid of qubits and are called surface codes.

A qubit encoded in many physical ones is called a logical qubit. The central result of the theory is the threshold theorem of the mid-1990s: if the physical qubits err less often than a certain threshold, then enlarging the code makes the logical qubit’s errors as rare as you like, and each step of enlargement cuts them several times over. If they err more often than the threshold, a bigger code only does harm. Our cell shows this in miniature: at $p = 0.3$ the code gains little, and at $p > \tfrac12$ it would start losing. That is why, of the fewer than a million physical qubits in the RSA estimate, only about 1,400 are logical, and all the rest are there to protect them.

How to read the news

Nobody cheated in this story: the 2019 experiment was a major scientific achievement. But readers took the headline “a quantum computer did in 200 seconds what a supercomputer would need 10,000 years for” differently from the way its authors meant it. Here is what to ask of any news about quantum computers.

1. Which task? A useful one (chemistry, materials, factoring), or one invented to suit the quantum machine? “Supremacy” has almost always been shown on the second kind.
2. Compared with what? With the best known classical algorithm, or with a convenient one? Classical methods improve too, and “10,000 years” records have more than once shrunk to days and seconds.
3. Which qubits? Physical or logical, and how often do they err? A hundred noisy qubits and a hundred logical ones belong to different eras.
4. Can the answer be checked? The output of a random circuit is hard to check even for its authors. That is why experiments with a checkable answer are so valuable: in October 2025 Google announced the first verifiable advantage, on a physics problem, about 13,000 times faster than a supercomputer.
5. What does it say about timelines? Promises of quick results have been heard in this field for a long time, and milestones (correction below the threshold, the first logical gate, the first useful task) are more reliable than dates.

And here is the sober picture as of fall 2026. The best machines built on superconductors and ions have around a hundred to a hundred and fifty physical qubits, and on the most accurate of them a two-qubit gate goes wrong about once in a thousand operations (once in ten thousand in a 2025 lab record); there are also machines with a thousand-odd qubits, but their qubits are noticeably noisier. The figures of several thousand you see in the news refer to something else: to D-Wave’s quantum annealers, which can run neither Shor nor Grover, or to an array of 6,100 atoms in laser traps (Caltech, 2025), where the qubits were held in superposition but no computation was run on the whole array. Error correction now works the way theory promises, for the first time: more code, fewer errors. But logical qubits still err about once in a thousand cycles, and large algorithms need them to err thousands of times less often. Running Shor on RSA-2048 takes roughly three orders of magnitude more qubits than the largest machines have. Neither “never” nor “soon” follows from these numbers: nobody knows the timeline. That is why ciphers are being switched to post-quantum ones already.

A headline: “A new quantum processor solved in five minutes a task that would take the fastest supercomputer $10^{25}$ years.” What follows from it for certain?

RSA will soon stop being secure quantum computers are now faster than ordinary ones at almost everything on one specially chosen task, the classical methods known today lag far behind it has been proved that quantum computers are more powerful than classical ones

That is how the Willow processor was announced in December 2024. Read literally, the claim is true: the task is sampling from a random circuit, and the estimate is for the best classical algorithms known today.

Tasks

Three tasks, three instruments for the lab: a simulator, a Bell-state generator with an identifier, and a Grover search that sixty-five thousand options don’t scare. The chapter’s convention holds throughout: in a two-qubit state the index of an amplitude is $2 q_0 + q_1$, and qubit 0 is the high bit.

Write two functions for a two-qubit state, a numpy array of four complex amplitudes $(a_{00}, a_{01}, a_{10}, a_{11})$. apply(state, gate, qubit) applies a gate, a 2 × 2 matrix, to qubit 0 or 1. cnot(state, control, target) applies a CNOT with control qubit control and target qubit target (0 and 1, in either order). Both functions return a new vector and leave the one passed in unchanged. The tests check basis states, complex phases and a hundred random gates.

Test the starter on something simple: apply(|00⟩, X, 0) should give $|10\rangle$, a one in amplitude number 2. In np.kron(A, B) the matrix A acts on the high bit of the index and B on the low one. Which of them is qubit 0?

CNOT is a permutation of the amplitudes. Go through the indices $i$ from 0 to 3 and pull out the bits: qubit 0 is (i >> 1) & 1, qubit 1 is i & 1. If the control bit is 1, the amplitude moves to the index with the target bit flipped. Don’t forget to make a copy, out = state.copy(), and to convert the type to complex right away.

The whole simulator is two operations: the tensor product for one-qubit gates and a permutation for CNOT. That is enough for any circuit: $H$, the phase gates and CNOT together are universal, and any unitary operation can be approximated from them, just as NAND built any logic in Chapter 29. The order inside np.kron is the main source of bugs in every homemade simulator; the Qiskit library, for one, uses the opposite order, with qubit 0 as the low bit.

Write bell_circuit(k): a circuit that prepares the $k$-th Bell state from $|00\rangle$, where 0 is $(|00\rangle + |11\rangle)/\sqrt2$, 1 is $(|00\rangle - |11\rangle)/\sqrt2$, 2 is $(|01\rangle + |10\rangle)/\sqrt2$ and 3 is $(|01\rangle - |10\rangle)/\sqrt2$. A circuit is a list of strings such as "H 0", "X 1", "Z 0", "CNOT 0 1", at most six gates long. A common factor on the whole vector (−1, say) changes nothing physically, and the tests forgive it. The second function, identify(state), gets one of the four states, possibly with such a common factor, and returns its number $k$.

The circuit “H on qubit 0, then CNOT” turns $|00\rangle$ into the first state. What does it do to $|01\rangle$, $|10\rangle$ and $|11\rangle$? Prepare the right basis input with $X$ gates, and one circuit gives you all four states.

For identify, run the circuit backward: CNOT, then $H$ on qubit 0. Each Bell state turns into a basis state, and its number can be read off the amplitude with the largest magnitude; a common factor doesn’t change magnitudes.

The circuit “H, CNOT” takes the basis $|ab\rangle$ to the Bell basis, and the reverse circuit takes it back; this is what a measurement in the Bell basis is. Quantum teleportation and superdense coding rest on it: acting with $X$ and $Z$ gates on her half of a Bell pair alone, Alice picks one of four states, which is two bits, and Bob, once he receives her qubit, reads both bits with a single measurement in this basis. The qubit still has to be sent, though: here too entanglement by itself carries no messages.

Write grover(n, marked, steps): starting from an equal superposition of $N = 2^n$ options, take steps Grover steps (the oracle flips the sign of option marked, then comes the reflection about the mean) and return the array of probabilities of all $N$ outcomes. Also write best_steps(n): the number of steps at which the probability of finding the marked option is highest. The tests start with $N = 4$, where one step gives the answer for certain, and end with $N = 65\,536$, which must be handled in under two seconds.

The reflection matrix for $N = 65\,536$ holds four billion numbers, 32 GiB. But there is no need to multiply by it: $\bigl(\tfrac2N J - I\bigr)\,a = 2\bar a - a$, where $\bar a$ is the mean of the amplitudes. One line of numpy.

The formula $\frac\pi4\sqrt N$ is an approximation. More precisely, after $k$ steps the probability is $\sin^2\bigl((2k+1)\theta\bigr)$, where $\sin\theta = 1/\sqrt N$. For $N = 4$ the angle is $\theta = 30^\circ$, and a single step already gives $\sin^2 90^\circ = 1$, while two give only $\tfrac14$. Find the $k$ nearest to $\frac{\pi}{4\theta} - \frac12$ and check its neighbors.

Reflection about the mean costs $O(N)$ rather than $O(N^2)$: on 65,536 options that makes 201 steps of a fraction of a millisecond each. On a quantum computer this step is built from $O(n)$ gates ($H$ on every qubit, $X$ on every qubit, a multiply-controlled $Z$, then $X$ and $H$ again), and each Grover step costs one call to the oracle. The starter’s mistake in best_steps is blind faith in asymptotics: $\frac\pi4\sqrt N$ is good for large $N$ but misses by a whole step for small ones, and for $N = 4$ that step costs three quarters of the probability.

What next

Time to close the notebook. A qubit is a vector of two complex amplitudes, a gate is a unitary matrix, a measurement is one random bit, and everything else in the chapter grew out of those three lines: interference; entanglement, which makes $n$ qubits need $2^n$ numbers; Deutsch–Jozsa; Grover; codes that correct errors without looking at the data. The limits are in view too: Grover is no faster than $\sqrt N$, NP-complete problems are, as far as anyone can tell, also beyond a quantum computer’s reach, and undecidable problems stay undecidable.

But the words “unknown” and “as far as anyone can tell” turned up at every step of this chapter. We don’t know whether BQP is larger than P, that is, whether there is anything at all a quantum computer can do quickly that no ordinary computer ever could. We don’t know whether factoring is easy even without qubits. We don’t know how BQP and NP are related. Nobody knows these answers, and science has more such gaps than you might think. The last chapter is a map of what remains unknown: the blank spots that roads from every part of this book lead to.