The sign is what cancels

The Hadamard gate, written H, rewrites the two amplitudes of a single qubit. From a state that is certain to read 0, H produces two equal amplitudes of the same sign, a state written with a plus, and a measurement then returns 0 or 1 with equal chance. Apply H again and the qubit is once more certain to read 0, because each amplitude is sent along two routes that meet, and the contributions to a reading of 1 cancel.

The arithmetic is small enough to do on graph paper. Start with amplitude 1 for 0 and amplitude 0 for 1, and after one H both amplitudes are about 0.707. The second H multiplies each route by 0.707 again, which turns each arriving number into a half. The amplitude for 0 is then a half plus a half, which is 1, and the amplitude for 1 is a half minus a half, which is 0. The minus sign is part of the gate’s rule, so arriving numbers that agree reinforce each other and arriving numbers that disagree cancel.

Keith once lettered a poster saying that a quantum computer tries every answer at once, and Malcolm took it down before the glue was dry. A classical search that checked every candidate would spend one run on each candidate, while the circuit just described still has two amplitudes at the end, the second gate having made one of them zero by subtraction. Grover’s search, which Lov Grover published in 1996, keeps that same habit at a larger size, arranging the adding and the cancelling so that a marked answer grows and the others shrink, after which the final measurement is more likely to show the marked one.

Malcolm keeps that poster in a drawer, glue side down. He will get it out for anyone who wants the slogan on the same desk as the sum that replaced it.

The Z gate is how a sign gets written in on purpose. It leaves the chances of 0 and 1 exactly as they were, and it flips the sign of the amplitude for 1. On a qubit that is certain to read 1, Z only puts a minus in front of the whole state, which no measurement can see. On the equal superposition with matching signs, Z produces the one with opposite signs. A following H turns that hidden disagreement into a certain reading of 1.

Phase is the general name for this sign, or for an angle when the amplitudes are complex numbers, meaning numbers that carry a real part and an imaginary part. One bare measurement in the usual arrangement does not report the phase. A gate that rotates the phase into the chances makes it visible, which is why the bench under this note locks the flip gate in a drawer and leaves you H and Z. Three of those, in the right order, are enough to finish certain of a 1.