Quantum Interference
Flip a coin and you get heads or tails. Flip it again and you still get heads or tails, because a second random step does not undo the first. A qubit does not behave that way. One Hadamard gate leaves it at even odds, and a second returns it to where it started, with certainty, every time. The thing that makes the difference is that amplitudes can be negative and can therefore cancel, which no probability can do. That cancellation is the whole subject, so it is the last thing that should be taken on trust, and here it is not: every amplitude on this page is a whole number over a power of the square root of two, every probability is an exact fraction, and the number 0.7071 appears nowhere in the arithmetic.
New to qubits? Start here
A bit is a thing that is either 0 or 1. A qubit is a thing that carries a number for each of those outcomes, called an amplitude, and the chance of seeing an outcome is its amplitude squared. Squaring is what makes the difference: an amplitude is allowed to be negative, and a probability never is.
That single permission is the whole subject. Two routes to the same outcome can arrive with amplitudes of opposite sign and add to nothing, which is called interference. Nothing built out of probabilities can do it, because adding two chances always gives you more chance, never less.
One phrase to keep straight. This page says an amplitude cancels. It does not mean it becomes very small. It means the two contributions are a number and its negative, and their sum is the integer zero, which is why every value on this page is written as a whole number rather than as a decimal.
Everything is a switch
Underneath all of it is one part: a switch that is either on or off, and that can be operated by another switch rather than by a finger. That is the whole of the hardware vocabulary. AND is two switches in a row, so both must be on. OR is two side by side, so either will do. NOT turns the answer around.
There is nothing else in the box. Adding, remembering, choosing and counting are all arrangements of those three, and the machines in this topic are those arrangements, in the order somebody had to think of them.
The machine for this idea on its own is Flip-Flop, if you would rather press it than read about it.
Machines here that come first: Bit, Nibble, Byte, Flip-Flop.
The same step twice gives one answer every time
1 One qubit and one gate, with the amplitudes kept as whole numbers over a power of root two
The state is two integers and an exponent. The gate is addition and subtraction, so nothing here is rounded and nothing needs a tolerance.
After 1 gate the amplitudes are [1, 1] / (root 2)^1. They are whole numbers, so the page can compare them without a tolerance and can say exactly rather than about.
2 Those amplitudes squared, giving probabilities as exact fractions rather than 0.7071
A probability is an amplitude squared, which here is an integer over a power of two. One half is written as one half.
The two probabilities sum to exactly one, checked as integers rather than to within a tolerance.
3 The same gate a second time, where one amplitude becomes the integer zero a coin cannot reach
A coin flipped twice is still a coin. Compare the two columns: one of these amplitudes is the integer zero, and the other process has no way to produce one.
Two steps in, the coin is still even and the qubit is back to certainty. The qubit's second amplitude is the integer 0, reached by 1 minus 1. A probability cannot do that, because probabilities are never negative and so never cancel.
4 Deutsch's question settled from a single evaluation, and the speedup he proved you do not get
Deutsch's question is whether f agrees with itself, not what f returns. One evaluation settles it, and neither value of f is ever learned.
f(x) = x is balanced. The machine reads f 1 time and the outcome is certain: it says balanced. A classical machine needs 2 reads for the same question. Neither value of f is ever learned.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| one gate leaves it exactly fifty-fifty, as a fraction and not a decimal | yes | amplitudes [1, 1] over root two to the 1, so the probabilities are 1/2 and 1/2. Whole numbers throughout; 0.7071 never appears |
| the same gate twice returns it to certainty, and the other amplitude is 0 | yes | amplitudes [2, 0] over root two to the 2. The second amplitude is the integer 0, not a small number: 1 - 1 = 0. A coin flipped twice is still a coin |
| probabilities sum to exactly one at every step | yes | 3 states checked as integers, 0 failed. No tolerance is used anywhere in this check |
| after two steps the coin is still even and the qubit is certain | yes | coin 1/2 and 1/2; qubit 1 and 0. Both computed, from the same start, over the same two outcomes |
| Deutsch's question is answered for all four functions, with one read each | yes | 4 functions, each decided with certainty from a single evaluation. 0 wrong |
| a classical machine needs two reads for the same question | yes | after one value, both a constant and a balanced function remain consistent with what was read, so the kind is undetermined. Needed: 2 |
| neither value of f is ever learned, which is the whole trick | yes | the final state is [0, 2]: all of the amplitude is on one outcome, and that outcome names whether f(0) and f(1) AGREE. It does not name either of them. The speed comes from asking a question about both at once, not from reading both |
What is real here, and what is not
Whole numbers throughout, so exactly means exactly
Any state reachable from a starting qubit by Hadamard gates and sign flips has amplitudes that are whole numbers over a power of the square root of two. So this page keeps a pair of integers and an exponent, and the gate becomes addition and subtraction. A probability is then an integer over a power of two and is printed as a fraction. Nothing is rounded, no comparison uses a tolerance, and the cancellation the page is about is the integer zero rather than a very small decimal. That is the difference between showing the phenomenon and asserting it.
The coin is a real comparison, not a rhetorical one
The third panel runs a fair coin beside the qubit through the same number of steps, from the same starting point. The coin's distribution after two flips is still even; the qubit's is certainty. Both columns are computed. The point is not that quantum mechanics is strange, it is that a negative amplitude has an arithmetic consequence a probability cannot have, and the two columns are where that consequence becomes visible.
What this page does not claim about speed
It does not say a quantum computer tries every answer at once and is therefore fast. Deutsch's 1985 paper introduces quantum parallelism and, in the same section, proves a limit on it: for a function of many values, the mean time to get all of them out is not better than computing them one at a time. The gain in his algorithm comes from asking a question whose answer is a property of both values, and then arranging for the wrong answers to cancel. The page's last panel is that distinction, and it is the reason the machine is called interference rather than parallelism.
One qubit, deliberately
Everything here is a single qubit with two outcomes. Deutsch's algorithm is usually drawn with a second register holding the function's output, and the phase-kickback that follows is a good thing to understand and is not this page's subject. A phase oracle on one qubit gives the identical arithmetic with half the bookkeeping, and the sign flip it applies is exactly the thing the page is trying to make visible. The simplification is stated here rather than hidden.
The word qubit is younger than the paper
Deutsch's paper is from 1985 and does not use the word as a term. Qubit is Schumacher, Quantum Coding, Physical Review A 51, in 1995. The page uses the modern word because that is what a reader will search for, and records here that it is an anachronism applied to the 1985 paper. The archived copy does contain the string twice, both times inside the email domain qubit.org in a header added long afterwards, and the test that holds this claim checks that every occurrence is part of that address rather than simply counting to zero.
No sound, and no animation of a collapsing wave
Measurement is the one place where a dramatic flourish would be easy and would teach nothing. The claim is about two numbers being equal or one of them being zero, and a table shows that better than a transition does. There is also nothing to hear: the outcome is a fraction, not a duration or a frequency, so a tone would decorate the measurement rather than carry it. Both answers are written down so the question is not reopened.
The archived copy is a 1999 re-typesetting, not the 1985 original
The file this page cites is the version on Deutsch's own site, and its own header says it was edited and converted to LaTeX by Wim van Dam in the summer of 1999. It is the author's chosen copy and it carries the argument faithfully, but it is not a facsimile of the Proceedings of the Royal Society pages, and page numbers quoted from it should be treated as the journal's rather than this document's. Saying so is cheaper than discovering it later.
Sources
- David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society A 400(1818), July 1985, pages 97 to 117, from the author's own site. Section 3 introduces quantum parallelism and also proves the limit on it that the last panel describes. The copy archived here is the 1999 LaTeX re-typesetting by Wim van Dam that the author publishes, not a scan of the journal.
- Logical Art, the studio this belongs to.