The Interference Machine: What Quantum Computing Actually Does
The Interference Machine
A quantum computer does not try every answer at once. It does something stranger, narrower and considerably more interesting — and knowing the difference is the only real defence against the next press release.
In December 2024 Google announced a processor called Willow, and the announcement contained two numbers. The first was that the chip had completed a benchmark in under five minutes that would take a classical supercomputer something on the order of 1025 years. That number travelled around the world. It is close to meaningless.
The second number was that when the researchers made their error-correcting code larger, the error rate went down — roughly halving with each step up in code size.[1] That one barely made the coverage. It is the only genuinely important result in the field in years.
The gap between those two numbers is the entire subject, and what follows is an attempt to close it. Most of it is mechanism — what a quantum computer actually does, worked through on problems small enough to check with arithmetic — and that is deliberate. The short list of things these machines are good for, and the provable reasons the list stays short, mean nothing until you can see the machinery. The closing section, on how to read the next announcement without being had, is useless without both.
The piece in one line
Superposition is not parallelism. The resource a quantum algorithm exploits is interference — arranging for wrong answers to cancel each other out — and that trick is only known to work on problems with a particular hidden structure.
The thing you have probably been told, which is wrong
The standard explanation goes: a classical bit is 0 or 1, a qubit is both at once, so n qubits explore 2n possibilities simultaneously, and that is where the speed comes from. Three hundred qubits, the version with a flourish adds, hold more states than there are atoms in the observable universe.
The arithmetic is right. 2300 is roughly 1090; the observable universe holds something like 1080 atoms. The conclusion does not follow, and the reason is measurement.
Start with what a quantum state is as a piece of bookkeeping. To describe 300 classical bits you write down 300 zeros and ones. To describe 300 qubits you have to write down one complex number — an amplitude — for every one of the 2300 possible bit strings: one for 000…0, one for 000…1, and so on down the list. The register genuinely carries that much description. Nobody disputes the size of the space. It is the reading that ruins everything.
Measurement is brutally lossy. Hand the machine 300 qubits and ask what they are, and you get back exactly 300 classical bits: one bit string, chosen at random, with probability equal to the squared magnitude of that string's amplitude. Not a summary of the 2300 numbers, not an average, not a best-of — one sample. And asking destroys the state, so the rest is not merely hidden but gone.
Now run the algorithm the popular account is implicitly describing. Put every candidate answer into superposition with equal weight — genuinely easy, it is the first circuit anyone learns to build. Then measure. Every candidate had the same amplitude, so every candidate has the same probability, and what comes out is a uniformly random string. Which is what you would have got from flipping a coin 300 times, without cooling anything to a hundredth of a degree above absolute zero.
The two-line demonstration that superposition is not just randomness
Take one qubit sitting at 0 and apply the standard “spread it out” operation, the Hadamard gate. Measure now and you get 0 or 1 with equal probability — a fair coin. So far nothing a coin cannot do.
Now apply the same operation twice, without measuring in between. A coin flipped twice is still 50/50. The qubit comes out 0 with certainty. Every time.
The first gate did not produce randomness; it produced two amplitudes. The second gate sends the qubit down two routes to each answer, and the two routes to “1” arrive with opposite sign: +½ and −½, which is zero. The two routes to “0” arrive in step and add. That is interference, in a two-gate experiment. Scaled up and aimed at a problem, it is the entire trick.
So the exponential space is real and almost entirely inaccessible. The whole discipline of quantum algorithm design is the problem of arranging matters before you look, so that the single sample you are allowed comes out overwhelmingly likely to be the answer you wanted.
A quantum algorithm is a choreography of cancellation. The wrong answers have to destroy each other before you are permitted to look.
What a qubit actually is
Amplitudes are complex numbers, and this is the detail that gets dropped in popular accounts even though it is the one that matters.
The difference in one line: a classical probability is a non-negative number, so two ways of reaching the same outcome always make it more likely — 0.3 and 0.2 make 0.5, and no two probabilities have ever made nothing. An amplitude carries a sign, and more generally a phase, an angle. Two ways of reaching the same outcome can therefore make it less likely, and +½ together with −½ makes exactly zero. Probability is what you get by squaring at the very end, once all the amplitudes for an outcome have been added up — and by then some outcomes have been added out of existence.
The physical picture is waves, and it is not a metaphor: the mathematics is the same one. Two water waves meeting crest to trough leave flat water. Noise-cancelling headphones work by emitting the exact opposite of the waveform in the room. A quantum algorithm does that to answers — it arranges the computation so that every route to a wrong answer is matched by another route arriving in antiphase, and the wrong answers flatten out. What survives the cancellation is what you measure. The resource is not breadth. It is cancellation.
| Classical bit | Qubit | |
|---|---|---|
| State | 0 or 1 | Two complex amplitudes, α and β, with |α|2 + |β|2 = 1 |
| Combining n of them | n bits of description | 2n amplitudes of description |
| What you can read out | All n bits | n bits, once, destructively |
| Copying | Trivial | Impossible in general (no-cloning) |
| The useful property | Reliability | Interference — amplitudes that cancel |
Two rows there do most of the damage to the popular story. What you can read out: the exponential description never leaves the machine, whatever is going on inside it. Copying: you cannot take a backup of a state before measuring it, so the ordinary classical escape from a probabilistic method — run it, keep a copy, try again — is not available. You can of course rebuild the state and re-run the whole circuit, and real algorithms do exactly that. But each repeat costs a full run, so repetition only rescues you if the right answer already had a decent probability, which puts you back where you started: everything depends on the cancellation you engineered before looking.
Entanglement, and how to check for it
The word is used loosely enough to be worth pinning down, and pinning it down takes four lines of algebra. Two qubits are entangled when the state of the pair cannot be written as one qubit's state combined with the other's. That is the whole definition, and it is something you can test rather than merely assert.
Start with a state that is not entangled — the uniform superposition produced by a Hadamard on each qubit:
Ask what the first qubit is doing on its own and there is a clean answer: (|0> + |1>)/√2, undecided, and nothing more to say. The pair is two independent things standing next to each other. All four amplitudes are nonzero and the entanglement is exactly zero — worth noticing, since this is the state every algorithm in this piece begins from.
Now take the equal mix of “both 0” and “both 1”:
Try to split it. If it factorised into (a|0> + b|1>) and (c|0> + d|1>), multiplying the brackets out would give ac|00> + ad|01> + bc|10> + bd|11>, so the four coefficients would have to satisfy all of this at once:
No such numbers exist. The state provably cannot be split, and that is not a shortcoming of the notation: there is no description of the first qubit by itself, because the first qubit by itself is not a thing that exists here. What exists is a relationship.
Measuring shows you what the relationship is:
| What you measure | Outcomes | Reading |
|---|---|---|
| Both qubits | 00 half the time, 11 half the time, 01 and 10 never | They always agree |
| One qubit alone | 0 half the time, 1 half the time | Indistinguishable from a fair coin |
Each qubit on its own is noise. The pair agrees every time. Every bit of information in the state lives in the agreement and none of it in either half, which is the operational meaning of “the parts cannot be described separately”.
What that table does not prove
Two coins glued to the same face would produce exactly those numbers, so the correlation on its own is nothing a classical arrangement could not manage. What has no classical account is the pattern of agreement when the two sides measure along different directions, chosen after the pair has separated. That is the content of Bell's theorem, and it is why the addendum at the end of this piece cites the experiments rather than resting on the table above.
That test settles something the section has so far only circled: whether entanglement is needed, or merely turns up. Rearranged, the condition above says a two-qubit state splits exactly when its amplitudes satisfy
— because in a product state those four amplitudes are (ac, ad, bc, bd), and both sides come to abcd whatever a, b, c and d happen to be. No unentangled state escapes it.
Now run a four-candidate quantum search through the test — spread the codes out, mark one of them with a minus sign, fold the amplitudes back:
| Step | Amplitudes (00, 01, 10, 11) | α00α11 − α01α10 | Verdict |
|---|---|---|---|
| After the Hadamards | 0.5, 0.5, 0.5, 0.5 | 0 | product |
| After the oracle | 0.5, 0.5, −0.5, 0.5 | +0.5 | entangled |
| After the fold | 0, 0, 1, 0 | 0 | product |
Product, then entangled, then product — entangled for precisely the one step that does the work. And it could not have gone otherwise. The oracle's job is to put a minus sign on one string out of four; a single sign flip breaks the equality above; therefore the marking step cannot be carried out inside product-state space at all. Entanglement is not a side effect of the oracle. It is what the oracle does.
Which is the general reason it is required. A state that factorises is a list of n independent qubits, and a list of n independent things costs 2n numbers to track rather than 2n — so a computation that never entangles is one an ordinary computer can follow gate by gate at the same price, and whatever it computed, the laptop computed too. The exponential description is only genuinely exponential while the register refuses to split.
One further thing entanglement is not: the source of the advantage. Clifford circuits generate as much of it as any state can carry, and a laptop simulates them in polynomial time — a theorem set out in the technical companion. Entanglement is machinery that every quantum algorithm requires and that no quantum algorithm can name as its reason for winning. Which by this point in the argument should sound familiar.
For most states of an n-qubit register there is no way to describe the parts separately at all, only the whole — and that failure to factorise is exactly why simulating quantum systems on classical hardware is expensive. If registers factorised, n qubits would need n small descriptions and a laptop would do. Because they do not, an exact classical simulation has to hold all 2n amplitudes and update every one of them at every step: fifty qubits is already some sixteen petabytes of memory just to store the state, and three hundred is more numbers than the universe has atoms to store them in. Nature runs the same system in real time, for free, using one molecule.
Which is where the whole idea started, and it was not about speed. Richard Feynman's 1982 argument was an observation about honesty:[2] nature runs quantum mechanics cheaply and we cannot, so if we want to simulate nature we should build the simulator out of the same stuff. David Deutsch turned that into a formal model of a universal quantum computer three years later.[3] Cryptography arrived a decade after that, and promptly took over the public story.
The mechanism, worked through
All of that is a claim about mechanism, and claims about mechanism ought to be checkable. So here is an entire quantum algorithm, beginning to end, on a problem small enough to hold in your head. It is Grover's algorithm on four candidates, and every number in it can be verified with arithmetic you learned before you were twelve.
The task. A two-bit code opens a padlock. Four candidates — 00, 01, 10, 11 — and you want the one that works. Classically you try codes, and bad luck costs you three attempts.
The qubits hold an address, not an answer
One piece of standard shorthand causes more confusion than anything else in this subject, so let us dispose of it first. When a textbook says the answer “is” |10>, nothing is inside anything. The four codes are numbered 0 to 3 and written in binary; the two qubits are a slip of paper on which a code is written. |10> means the slip currently reads 10. Superposition means the slip is indefinite as to what is written on it, with an amplitude attached to each of the four possibilities. The register addresses candidates. It does not contain them. What you get at the end is the address — two classical bits — and you go and open that padlock yourself, by hand, like a normal person.
The checker does not know the answer either
Nor is the checker an oracle in any mystical sense, despite the name the literature saddled it with. It is a circuit. To see that, drop the padlock and take a bare condition instead:
find the two-bit number x with 3x + 1 ≡ 3 (mod 4)
That is the entire specification, and it names no answer. Work through the candidates:
| x | In binary | 3x + 1 | mod 4 | Is it 3? |
|---|---|---|---|---|
| 0 | 00 | 1 | 1 | No |
| 1 | 01 | 4 | 0 | No |
| 2 | 10 | 7 | 3 | Yes |
| 3 | 11 | 10 | 2 | No |
The solution is 2, binary 10. But notice how you obtained it: by trying. The equation announced nothing, and it contains no stored copy of its own solution. That equation is the padlock — a fixed piece of arithmetic that happens to come out right for exactly one input, in the same way a lock is a fixed piece of metal that happens to turn for exactly one key. Your padlock does not know its own combination either.
Compiling it into gates is mechanical: multiply by three, add one, keep the low two bits, then AND those two bits together to test for 3. The output wire carries 1 for the winning code and 0 for the other three. Feed that wire into a controlled-NOT aimed at one spare qubit and the checker is complete: flip the spare qubit when the output wire says 1. There is no stored secret and no comparison against a known answer. There is a wire.
Which raises the objection that should have occurred to you
How did I know to write ≡ 3 rather than ≡ 2? Only by already knowing the answer was 10. Change that constant to 2 and the solution becomes 11; to 0 and it becomes 01. I picked the equation to fit an answer I had chosen in advance, which is precisely backwards from how a search problem works, and it makes the example honest about mechanism and dishonest about difficulty.
The flaw is not repairable at this size. With four candidates, checking all four is inverting the function — no problem small enough to print can be genuinely one-way. So the useful question is where real conditions come from, and the answer is never “from the answer”. They come from outside, carrying no hint of what satisfies them.
Suppose you are watching a key exchange. Two numbers are public, as they always are — a base of 2 and a modulus of 11 — and you observe the value that crosses the wire: 9. The secret is the exponent that produced it. Your condition is therefore:
find x with 2x ≡ 9 (mod 11)
Every number in that line — the 2, the 11, the 9 — you obtained by watching. None of it required knowing x, and a circuit that tests a candidate can be built from those three alone. Now look at the 9 and tell me what x is.
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2x mod 11 | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
You cannot read it off, and that is the entire point. x = 6, and you get there by walking the powers — nothing in the digit 9 pointed at 6, because the sequence 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 is scrambled. That scrambling is exactly the property that makes the function valuable to cryptographers and useless to you. Computing forwards is trivial; coming back is not. And a checker only ever needs the forward direction, which is why you can build one for a secret you do not have.
The test for whether you have a problem at all
If you cannot state the condition without naming the answer, you do not have a search problem — you have an answer.
“Find x with 2x ≡ 9 (mod 11)” passes: the 9 came off the wire. “Find the code that opens this padlock”, said of an actual lump of metal on an actual table, fails: there is no procedure that turns metal into arithmetic, and until somebody hands you the lock's specification there is nothing to compile and nothing a quantum computer can do for you.
So the two examples divide the labour: the equation shows you the mechanism, the exponentiation shows you the asymmetry between checking and finding that makes the mechanism worth building. Neither does the other's job — and the field's press releases have a habit of borrowing the credibility of the second while showing you the first.
How the minus sign gets there
The checker can only flip a bit. Turning a flip into a phase is a separate trick, and a pretty one. Prepare the spare qubit not as 0 or 1 but as the balanced state (|0> − |1>)/√2 — amplitudes +0.707 and −0.707.
Now flip it. Flipping swaps the two labels, producing amplitudes −0.707 and +0.707: the identical state, with every amplitude multiplied by −1. This is the one state a flip cannot actually change. It can only negate it.
So on the winning branch the checker flips the spare qubit, the spare qubit shrugs the flip off, and the surviving −1 multiplies that whole term instead. The spare qubit emerges exactly as it went in — unentangled, carrying no record of what it did — and the sign is left behind on the code register. The literature calls this phase kickback. It is the small piece of engineering on which the entire construction turns.
Where the four codes come from
First, how the four codes get into play at all, because the obvious guess is wrong and the wrongness matters. You do not enumerate the four possibilities and load them in one at a time. If you did, the cost would be proportional to the number of candidates and there would be no algorithm here worth discussing.
You build forks, not paths. Picture a road with two forks in a row: after the first there are two routes and after the second there are four, and nobody laid out four routes — four is simply what two forks make. Each qubit is one fork, and a Hadamard is what makes it one.
Build it a gate at a time. Both qubits start definitely at 0, so the register reads 00 and the other three codes have amplitude zero:
Apply a Hadamard to the first qubit only. That qubit becomes undecided; the second is untouched and still reads 0:
Two branches, and the second digit is still definitely 0 in both. Now apply a Hadamard to the second qubit, and each of those branches splits in two:
The second gate did not add two more codes to a list. It split the two that were already there — |00> became |00> and |01>, |10> became |10> and |11>. Splitting is what doubling means, and doubling n times is how n gates reach 2n.
Where the √2 comes from
It is not decoration. Probability is amplitude squared, and a state's probabilities must total exactly 1 — the condition in the qubit table above, that |α|2 + |β|2 = 1. For a qubit equally likely to read 0 or 1, carrying the same amplitude a on each:
a2 + a2 = 1 → 2a2 = 1 → a = 1/√2 ≈ 0.707
Half-and-half is a statement about the odds; the number written into the state is the square root of the odds. Writing (|0>+|1>)/2 instead would give probabilities of 0.25 each, totalling 0.5 — half the state simply missing. And the 0.5 on each of the four codes is the two factors multiplied: 1/√2 × 1/√2 = ½, with 4 × 0.52 = 1, as it has to be.
The reason two qubits reach four rather than two is that quantum descriptions multiply where classical ones add — and two is an unfortunate size at which to notice it, since 2 + 2 and 2 × 2 both make 4. Three breaks the coincidence:
| How many | Classical bits: numbers to write | Qubits: amplitudes needed |
|---|---|---|
| 2 | 2 | 4 |
| 3 | 3 | 8 |
| 10 | 10 | 1,024 |
| 300 | 300 | ≈ 2 × 1090 |
To say what three classical bits are doing you state three things. To say what three qubits are doing you must give an amplitude for every joint outcome — 000, 001, 010, and so on down — and there are eight of those. Joint outcomes are combinations, and combinations multiply.
Two costs are easy to confuse here and worth separating, because only one of them is the one that hurts. Gate count is how many operations in total: n. Circuit depth is how many sequential time-steps: one, no matter how large n is, because the gates act on separate physical qubits and can all be fired at once.
| Qubits | Gates | Depth | Codes in play | Amplitude on each |
|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 0.707 |
| 2 | 2 | 1 | 4 | 0.5 |
| 3 | 3 | 1 | 8 | 0.354 |
| 10 | 10 | 1 | 1,024 | 0.031 |
| 300 | 300 | 1 | ≈ 2 × 1090 | ≈ 7 × 10−46 |
Depth is what consumes wall-clock time and what decoherence eats into, so the last row is worth reading slowly: preparing a superposition over 2300 codes takes three hundred pulses fired simultaneously and costs one gate-time, exactly as much as preparing four. Notice also that the amplitudes shrink at precisely the rate the codes multiply, which is why the total stays at 1.
This is the one genuinely free thing in the entire subject, and free in a stronger sense than cheap. The state is not even entangled — it factorises perfectly, as the section above showed — so no distinctively quantum resource has been spent at all. Measure at this point and every code carries probability 2−300, exactly uniform: you would have built the largest-looking object in the universe in order to draw a random number out of it. Everything of value happens afterwards, in what gets done to the phases before you look.
The algorithm, in four numbers
So: a Hadamard on each qubit, all four codes in play at amplitude 0.5. Now follow what happens to them.
| Code | Step 0 spread out | Step 1 after one query | Step 2 after the fold | Probability of reading it |
|---|---|---|---|---|
00 | +0.5 | +0.5 | 0 | 0 |
01 | +0.5 | +0.5 | 0 | 0 |
10 | +0.5 | −0.5 | 1.0 | 1 |
11 | +0.5 | +0.5 | 0 | 0 |
Two columns there deserve to be stared at.
Step 1 gains you nothing you can see. The checker has already done its work — it has told the register which code opens the padlock — and every probability is still 0.25, because (−0.5)2 is exactly (+0.5)2. Measure at this point and you get a random code, as surely as if you had never asked. The answer is genuinely present in the machine, and it is sitting in a sign, where measurement cannot reach it.
Step 2 never touches the padlock. It is arithmetic on four numbers: take their average, and reflect each number through it. The single negative entry drags the average from 0.5 down to 0.25, which turns the reflection into the rule new = 0.5 − old. So 0.5 − (+0.5) = 0 for each wrong code, and 0.5 − (−0.5) = 1.0 for the right one. That is the entire step, and it costs no queries at all — the negative sign was needed only to move the average, and moving the average was the checker's whole contribution.
The three wrong answers did not become improbable. They were subtracted to exactly zero, and the survivor to exactly one. Measure now: the register reads 10, with certainty, after a single consultation of the checker. The choreography of cancellation, performed in full, on four numbers.
Structure, not breadth
Notice what the worked example did not actually depend on. Superposition was present from the first gate — all four codes in play at once — and it accounted for none of the advantage. It was free, it was automatic, and left to itself it produced a random guess. The advantage came from a sign, and from a step of arithmetic that turned the sign into a certainty.
That is worth isolating, because superposition is the thing everyone points at and it is the one thing that never varies. Every quantum algorithm has it. So do the useless ones. To see what does the varying, hold the problem fixed and change the checker instead.
The task. There is a hidden seven-bit string — 1001101, say, though naturally you do not know that. Find it.
| What the checker will tell you | Classical cost | Quantum cost | Why |
|---|---|---|---|
| “Is this the string?” | 64 tries on average, 127 at worst | 8 queries (Grover) | Each answer concerns one candidate out of 128 and says nothing about the rest |
| “What is the parity of my query against yours?” | 7 queries, one per position | 1 query (Bernstein–Vazirani) | Each answer is a statement about the whole hidden string at once |
| Nothing | Impossible | Impossible | With no way to test a candidate there is no problem, only a string somebody has |
Same hidden string, same seven bits, the same superposition in both quantum columns, and costs that diverge without limit as the string gets longer. The only thing that changed was what the checker was willing to say.
The middle row is Ethan Bernstein and Umesh Vazirani's, from 1993.[4] Their oracle takes a query string and returns a single bit: the parity of that query AND-ed against the hidden string. Classically there is nothing to be clever about — ask about position one, then position two, seven times. Quantumly it is one query. Put every possible query into superposition with a layer of Hadamards, ask once, then apply the same layer of Hadamards again. The sign pattern the oracle stamps on the register is precisely the pattern a layer of Hadamards produces, so the second layer folds it back up, every wrong string cancels, and the register is left reading the hidden string exactly. Measure and all seven bits come out at once, with certainty.
That is a strictly better result than Grover's, on a problem nobody has. The remark is not a throwaway: Bernstein–Vazirani exists to prove that quantum query complexity can beat classical query complexity, and it has no application whatever. The same holds for Deutsch and Jozsa's earlier separation. Clean theorems, invented problems, and they belong in the same mental drawer as random circuit sampling.
The difference between those two rows is not cleverness, and it is certainly not hardware. It is that Grover's checker is stingy. It confirms or denies one candidate and discloses nothing about the other 127, so no amount of choreography can pull more than one candidate's worth of information out of a query — which is exactly what Bennett, Bernstein, Brassard and Vazirani proved, and why √N is a floor rather than a current best. Bernstein and Vazirani's checker is generous: every answer it gives is a global fact about the string. And one global fact is precisely the shape of thing that a single destructive measurement is able to carry out of the machine.
Seven bits is too small to show what that difference is worth. Take the same two checkers up to sizes that matter:
| Hidden string | Stingy checker — “is this it?” | Generous checker — parity | ||
|---|---|---|---|---|
| Classical | Quantum (Grover) | Classical | Quantum (BV) | |
| 7 bits | 64 | 8 | 7 | 1 |
| 20 bits | 524,288 | 804 | 20 | 1 |
| 128 bits | 2127 | ≈ 264 | 128 | 1 |
Read the last row across, slowly. A classical computer given the generous checker finishes in 128 queries. A quantum computer given the stingy one needs about 1.8 × 1019 — worse by a factor of a hundred thousand trillion. The machine that wins is the one that was asked a better question, and it is not the quantum machine.
That is the argument of this section in a single row of a table. Which question the checker will answer settles the cost; whether the computer is quantum adjusts it. Anyone comparing quantum computers to classical ones without first stating what the oracle was permitted to say is comparing the wrong two things.
And the quantum column of that table is worth one more look, because halving an exponent is not the same as escaping one:
Which exposes the one thing that comparison is not: a menu. You never choose your checker. The problem hands you one, and the algorithm you are permitted follows from that. Nothing lets you approach a cipher and ask for parities of its key rather than yes-or-no verdicts on candidate keys — and if some cipher did offer that, it would already be broken on a laptop, since n linear equations in n unknowns is Gaussian elimination rather than cryptanalysis. No cipher does. Ensuring it does not is a large part of what block-cipher design consists of.
Read in that light, cryptography is the practice of handing an attacker the worst checker available. Symmetric ciphers manage it, which is why Grover's square root remains the best attack anyone has on them. Public-key cryptography cannot, because it needs structure the legitimate key-holder can exploit — and that structure is precisely what a later section shows Shor gripping.
Two different kinds of speedup, easily conflated
Grover turns 2n into 2n/2 — an enormous factor, about 1018 at 128 bits, arriving at an answer that is still unreachable. Bernstein–Vazirani turns n into 1 — a factor of merely 128, arriving instantly.
Both are chasing the same string. What differs is the exchange rate the checker offers. A “no” from the stingy one eliminates a single candidate out of 2n, which is very nearly no information at all; a parity answer eliminates half of everything still standing, which is exactly one bit. Since pinning down an n-bit string requires n bits of information, that alone fixes the classical costs at n queries and about 2n/2 respectively — a gap created entirely by the oracle, before any quantum machine enters the room.
Each algorithm then improves on its own starting point, and the starting points are incomparable. So Grover offers the far larger speedup and Bernstein–Vazirani the far lower cost, and neither fact makes one better than the other. It is the clearest available demonstration that “how large is the speedup” is close to a meaningless quantity on its own.
Superposition is the cheap part. Every algorithm has it, including the ones that do nothing at all.
Read the list that follows in that light and it stops looking like an arbitrary collection. Shor's algorithm wins because factoring conceals a period, and periodicity is a global property that a Fourier transform can expose by interference. Simulating a molecule wins because the problem is already quantum — the structure is not something we impose on it, the structure is the thing itself. Unstructured search gets a square root and not a step more, because “unstructured” is the literal statement that there is nothing there for interference to grip. And general optimisation has no proven speedup because nobody has located the structure, which is not the same as nobody having tried.
The question worth asking
When the next claim arrives, the useful question is not how many qubits it has, nor how large a state space that implies. It is: what structure in this problem is the interference exploiting?
A good answer names something specific — a period, a parity, a symmetry, a Hamiltonian you actually want the ground state of. A bad answer says the machine considers many possibilities at once. Every quantum computer considers many possibilities at once. It is the cheapest thing they do, and on its own it is worth precisely nothing.
The short list
Peter Shor's 1994 algorithm factors integers in polynomial time.[5] It works because factoring can be reduced to finding the period of a function, and periodicity is precisely the structure a quantum Fourier transform can expose by interference — every candidate period that is wrong contributes amplitudes that cancel; the right one survives. The speedup is not from breadth. It is from a very specific kind of hidden regularity.
Lov Grover's algorithm — the one worked through above — searches an unstructured list of N items in about √N steps.[6] That is a real speedup and a genuinely general one — and it is only quadratic. Worse, it is provably the best possible: Bennett, Bernstein, Brassard and Vazirani showed that no quantum algorithm can do unstructured search faster.[7] This is not a gap in our cleverness that a future paper will close. It is a theorem.
The consequence people skip
If brute-force search only gets a quadratic speedup, then quantum computers are not expected to solve NP-complete problems — scheduling, routing, protein folding, the travelling salesman — efficiently. Factoring is not NP-complete; it is a special case with unusual structure, and that is exactly why it breaks. Anyone selling a quantum machine as a general-purpose solver of hard optimisation problems is either confused or counting on you being.
| Problem class | Best known quantum advantage | Honest status |
|---|---|---|
| Factoring, discrete logarithm | Exponential (Shor) | Solid. Breaks RSA, Diffie–Hellman and elliptic-curve cryptography outright — once the hardware exists. |
| Simulating quantum systems | Exponential | Solid, and probably the real prize: catalysis, nitrogen fixation, superconductors, drug binding. The original motivation, and the least publicised. |
| Unstructured search | Quadratic (Grover) | Proven optimal, and modest. Error-correction overheads plausibly eat the gain for realistic problem sizes. |
| Linear systems, quantum machine learning | Claimed exponential, heavily caveated | Weak. The speedups assume you can load classical data into quantum states cheaply and read useful output cheaply — frequently neither holds. Several headline results were “dequantised”: Ewin Tang, then an undergraduate, produced classical algorithms matching the quantum ones.[8] |
| General optimisation, annealing | None proven | No rigorous general speedup. Case-by-case empirical claims, frequently overturned when someone tries harder classically. |
That is the list. It is not nothing — two exponential entries would justify the whole enterprise. But it is a list of five items, not a general accelerator for computing.
The noise problem, which is the actual problem
Qubits are fragile in a way that has no classical analogue. A stray photon, a vibration, a thermal fluctuation, a magnetic field twitching in the next room: any of these entangles the qubit with its environment and destroys the phase relationships the algorithm depends on. This is decoherence, and it is not an engineering annoyance to be polished away. It is what happens by default.
The best two-qubit gates today have error rates around one in a thousand. Shor's algorithm on a cryptographically relevant integer needs on the order of a billion gate operations. One error in a thousand, applied a billion times, is not a degraded answer — it is noise.
The escape is quantum error correction, and its theoretical foundation is the threshold theorem: if the physical error rate is pushed below a certain critical value, then encoding each logical qubit across many physical ones lets you suppress errors to any level you like, at only polylogarithmic overhead.[9] Below threshold, adding hardware makes the machine better. Above it, adding hardware adds noise faster than it removes it.
Which is why Willow's second number is the one that mattered. Google ran surface codes at increasing size — distance 3, then 5, then 7 — and the logical error rate fell by roughly half at each step.[1] That is the below-threshold regime, demonstrated rather than argued. It converts the remaining problem from “does this physics work” into “how many fridges, and who pays.”
That third figure deserves a pause. In 2019, Craig Gidney and Martin Ekerå estimated that factoring a 2048-bit RSA key would take about twenty million noisy qubits running for eight hours.[10] In 2025, Gidney published a revised estimate of fewer than a million, in under a week.[11] No new hardware was involved. The improvement came entirely from better algorithms and better error-correction schemes — a twenty-fold reduction in the requirement, from theory alone. Requirements estimates move, and they have been moving in one direction.
Where the hardware actually is
There is no consensus on what a qubit should be made of, and the honest summary is that every platform is winning at something and losing at something else.
| Platform | Strength | Weakness |
|---|---|---|
| Superconducting circuits (Google, IBM) | Fast gates, chip fabrication leverages existing industry | Millikelvin cryogenics; short coherence; wiring does not obviously scale |
| Trapped ions (Quantinuum, IonQ) | Highest fidelities; every qubit identical by physical law; all-to-all connectivity | Slow gates; scaling a single trap is hard |
| Neutral atoms (QuEra, Pasqal) | Thousands of atoms trappable; flexible geometry; fast recent progress | Gate fidelities behind ions; atom loss and reloading |
| Photonics (PsiQuantum, Xanadu) | Room temperature transport, natural networking | Deterministic two-photon gates are hard; loss is unforgiving |
| Topological (Microsoft) | Error resistance built into the physics rather than bolted on | The underlying quasiparticles remain contested; claimed demonstrations have drawn substantive scepticism |
The useful term for the period that is now ending is John Preskill's: NISQ, Noisy Intermediate-Scale Quantum.[12] Machines with tens to hundreds of physical qubits and no error correction — big enough to be hard to simulate, too noisy to be useful. He coined it in 2018 partly as a warning, and for seven years it described the field exactly.
It has stopped doing so, and the numbers that show it are not the ones in the headlines. Raw qubit counts have quietly ceased to be the metric: IBM's 2026 processor, Nighthawk, is specified at up to three 120-qubit modules and rated by gate count rather than qubit count — and at 360 qubits it is smaller than the 1,121-qubit Condor the same company built in 2023. Nobody is trying to beat Condor. The interesting number moved.
| System | Physical qubits | Logical qubits | What it demonstrates |
|---|---|---|---|
| Google Willow (2024) | 105 | 1 | Below-threshold error suppression, Λ ≈ 2.14[1] |
| Quantinuum Helios (Nov 2025) | 98, all-to-all | 48 error-corrected | A 2:1 encoding ratio, commercially available[13] |
| QuEra / Harvard / MIT | 256 neutral atoms | 48 | Logical qubits outperforming physical ones on benchmarks[14] |
| IBM Starling (planned 2029) | — | 200 | 100 million gates; the first machine specified as fault-tolerant |
Around fifty logical qubits, then, from one to two hundred physical ones. That is a genuine change of regime from the NISQ description and it is still nowhere near enough: the fourth row is where useful algorithms start, and it is three years out on the optimistic plan of the company proposing it. What has ended is the era in which error correction was a theoretical argument rather than a product specification.
The cryptography clock
This is the part with an actual deadline, and it is not the deadline people assume.
Public-key cryptography — RSA, Diffie–Hellman, elliptic curves — rests on factoring and discrete logarithms being hard. Shor's algorithm makes both easy. So every HTTPS handshake, every signed software update, every VPN key exchange currently in use has a quantum expiry date.
The deadline is not when the machine gets built. It is now, because of harvest now, decrypt later: an adversary can record encrypted traffic today and store it until a machine exists to open it. Anything you send today whose secrecy has to survive fifteen years is, for practical purposes, already at risk.
Why RSA falls and AES does not
It is worth seeing what Shor's algorithm actually does, because it is a great deal smaller than its reputation and because it explains the entire shape of the threat. The quantum computer performs exactly one task: it finds the period of the function ax mod N. Everything else is classical arithmetic, most of it older than calculus.
Take N = 15, and pick any a sharing no factor with it — 7 will do. Compute powers until the sequence returns to where it began:
70 = 1 71 = 7 72 = 4 73 = 13 74 = 1 (mod 15)
It repeats every four steps, so the period is 4. That is the only hard step in the whole algorithm, and the only quantum one. The remainder is Euclid: the period is even, so halve it in the exponent to get 72 = 4, then take two greatest common divisors.
gcd(4 − 1, 15) = 3 gcd(4 + 1, 15) = 5 3 × 5 = 15
Factored, by hand, without a computer anywhere in sight. The method is honestly probabilistic — start instead from a = 14 and both divisors come out useless, so you choose another a and go again, which works about half the time — but nothing else about it is subtle.
Now scale it. For a 2048-bit key the period is a number with hundreds of digits, and the classical way of finding a period — walking the sequence until it repeats — is exactly as hopeless as that sounds. Shor's cost instead grows with the number of digits rather than with the number. That is the whole of the exponential gap, and it exists for one reason: periodicity is a global property of the entire function, which is precisely the sort of thing a quantum Fourier transform can expose by cancelling every wrong candidate against itself.
Which yields the asymmetry that actually matters:
| Scheme | Structure it offers | Tool that applies | Cost | Verdict |
|---|---|---|---|---|
| RSA | Periodicity of ax mod N | Shor | Polynomial | Dead |
| Diffie–Hellman | Discrete logarithm | Shor | Polynomial | Dead |
| Elliptic curve | Discrete logarithm | Shor | Polynomial | Dead, and first in the queue |
| AES-128 | None | Grover only | 264 | Uncomfortable |
| AES-256 | None | Grover only | 2128 | Fine, indefinitely |
| SHA-256 | None | Grover only | 2128 | Fine |
Public-key cryptography is breakable because it is built out of structured mathematics, and it has no choice in the matter: the structure is what allows the legitimate holder of a key to do cheaply what an attacker cannot. The same regularity that makes RSA usable is the regularity Shor's algorithm grips. Symmetric ciphers and hash functions offer nothing of the kind — they are engineered to be a deliberate mess — so the only tool that reaches them is unstructured search, and unstructured search is provably no better than quadratic.
The elliptic-curve row is the one that surprises people. Smaller keys are a virtue everywhere else in cryptography, and here they are a liability: a smaller key means a smaller machine suffices to break it, so on most current estimates elliptic-curve cryptography falls before RSA rather than after it.
The practical bit
Symmetric encryption is fine. Grover halves the effective key length, so AES-256 retains a 128-bit security margin. Move off AES-128 and stop worrying about it.
Public-key needs replacing. NIST finalised the first post-quantum standards in August 2024: ML-KEM for key encapsulation, ML-DSA and SLH-DSA for signatures.[15] These are classical algorithms — they run on ordinary computers — built on lattice and hash problems with no known quantum attack.
The bottleneck is migration, not physics. Rewriting the world's cryptographic infrastructure takes a decade or more. That is the schedule the quantum computer is racing against, and it is why the standards were finished before the threat arrived.
How to read the next announcement
Four questions, in order of how often they catch something.
1. Physical qubits, logical qubits — and logical at what distance?
A headline count of 1,000+ almost always means physical qubits, and useful algorithms need logical ones. The press release rarely says which it is quoting.
The harder trap is newer, and it is the one to watch now that error correction works. “Logical qubit” has come to name two very different objects. A low-distance code is cheap: Quantinuum's Helios, launched commercially in November 2025, produces 48 error-corrected logical qubits from 98 physical ones — a ratio of 2:1 — and that is genuinely enough to beat break-even on shallow circuits.[13] A surface-code logical qubit at the distance needed to survive a billion gate operations, which is what factoring an RSA key requires, costs on the order of a thousand physical qubits. Those two figures differ by a factor of several hundred, and both are correctly called logical.
So the question has three parts: physical or logical, logical at what code distance, and how deep a circuit it can actually run before errors overwhelm it. A number quoted without the second and third has told you very little.
2. Is the task useful, or engineered to be hard?
Random circuit sampling — the Willow benchmark, and Sycamore's before it — is designed for one property: being difficult to simulate classically. It computes nothing anyone wants. It is a legitimate physics demonstration and an illegitimate proxy for utility.
3. Has anyone re-run the classical baseline?
Google's 2019 Sycamore result claimed 200 seconds against 10,000 classical years.[16] IBM answered within days that a better classical method would take about 2.5 days, and subsequent tensor-network work brought the classical simulation down to hours on GPU clusters.[17] Every quantum advantage claim so far has been met by classical algorithms improving. Sometimes they close the gap entirely.
4. Is the comparison to the best classical algorithm?
“Faster than brute force” is not an achievement if nobody uses brute force. This is the failure mode that killed most quantum machine learning claims, and it recurs constantly in optimisation benchmarks.
The verdict
Quantum computing is real physics with a real engineering path, and it is not close. Below-threshold error correction was the field's genuine inflection point and it happened only two years ago. The distance from “error correction works” to “a machine that factors your keys or designs your catalyst” is measured in millions of physical qubits and, on any honest reading, in a decade or more.
What it will most likely be used for is not what it is sold for. The cryptographic story is dramatic and, in a real sense, already resolved — the replacement algorithms are standardised and the work left is unglamorous migration. The quiet entry on the list is simulating quantum systems, which is where a working machine would do something no classical computer can: tell us how a molecule actually behaves, without approximation. Better catalysts and better batteries are a smaller headline than broken encryption and a much larger prize.
And the discipline that survives all of it is the one Feynman started with. A quantum computer is not a faster computer. It is a differently-shaped one, useful exactly where a problem's structure happens to match the shape of interference — and useless, or merely quadratically better, everywhere else. Whenever the next announcement blurs that distinction, the blur is the product.
Addendum: the physics underneath
Everything above has used amplitudes, phase and measurement as given, on the grounds that you can follow the argument without knowing where they come from. This addendum says where they come from. Nothing earlier depends on it, and you can stop here without having missed the point.
Nobody wanted this theory
Quantum mechanics was not proposed because it was elegant. It was forced on physics by a handful of measurements that classical physics got catastrophically wrong.
The first was the glow of hot objects. Classical thermodynamics predicted that a warm oven should radiate infinite energy at short wavelengths, which ovens conspicuously do not. In 1900 Max Planck found that the numbers came out right if he assumed energy was emitted only in discrete lumps proportional to frequency, E = hf. He described the assumption as an act of desperation and spent years trying to get rid of it. Einstein made it worse in 1905 by showing that light itself arrives in lumps, and Bohr worse again in 1913 by explaining atomic spectra the same way — electrons occupying only certain orbits, and nothing in between.
The full theory arrived in 1925–26, from Heisenberg and independently Schrödinger. What it produced was not a picture of small objects but a rule for computing a quantity — the state, or wavefunction — that evolves smoothly and predictably. In 1926 Max Born supplied the missing piece: the state is not itself observable, and what you measure occurs with probability equal to the squared magnitude of the corresponding amplitude.[18] Every piece of squaring in this article is that rule.
The experiment that contains the whole argument
Fire electrons, one at a time, at a barrier with two slits in it, and let them land on a screen behind. Each electron arrives as a single dot — a particle, unambiguously. Leave the apparatus running for hours and the accumulated dots form stripes: an interference pattern, of the kind waves make.[19]
Each electron travelled as an amplitude for both routes, and where the two amplitudes arrived out of phase they cancelled. The dark stripes are places an electron could have reached by either path and therefore reaches by neither. This is not an analogy for the subject of this article. It is the subject of this article, performed on a bench in 1989.
Now the part that matters most. Put a detector at the slits to record which one each electron used. The stripes disappear, and the screen fills in the way sand would. Not because the detector jostles anything — the effect survives every attempt to make the measurement gentler. Amplitudes interfere only while the paths remain indistinguishable: the moment anything anywhere holds a record of which route was taken, the cancellation stops.
Which is why, several sections ago, it mattered so much that the spare qubit came out of the checker unentangled and carrying no record of what it had done. Had it kept one, the four amplitudes would have stopped cancelling, exactly as the stripes vanish. The mechanism in this article and the mechanism in the double slit are not similar. They are the same one.
Three ideas, and what they are not
Superposition
Not “in two places at once” as a claim about reality. The state carries an amplitude for each possibility, and the only thing that statement ever cashes out to is that those contributions can add or cancel. Nobody has ever observed a particle in two places; what is observed is interference, which is the evidence that the description needs both.
Measurement
Smooth reversible evolution, then one abrupt irreversible step producing a single outcome with probability given by squaring. Nothing in the theory explains why that second kind of process exists or when exactly it happens. This is the measurement problem, it is a century old, and it is unsolved.
Entanglement
Correlations between separated systems that no shared prior cause can reproduce. In 1964 John Bell converted that vague claim into an inequality any classical explanation must satisfy and quantum mechanics violates.[20] Experiments have violated it, with the last significant loopholes closed in 2015, and the 2022 Nobel Prize went to Aspect, Clauser and Zeilinger for the programme.[21] It is not faster-than-light signalling: each side on its own sees nothing but noise, and the correlation is visible only when the two records are later compared.
Why the world does not look like this
The obvious objection to all of the above is that nothing in ordinary life behaves this way. The answer is decoherence, and it is the same fact as the vanishing stripes.
Interference requires that no record exist of which path was taken. Any object larger than an atom is in constant contact with its surroundings — air molecules, photons, thermal vibrations — and every one of those interactions is a record. A dust grain is measured by its environment billions of times a second, without anybody looking. The amplitudes stop being able to cancel, and the description collapses into ordinary probabilities that only add.[22]
Nothing switches off at some size threshold. The interference terms remain in the mathematics; they have simply been spread into the environment where no experiment can gather them back. The classical world is not a different regime of physics. It is this physics with the interference leaked away.
Which reframes the engineering problem in the honest way. A quantum computer is not exotic hardware doing something extra. It is ordinary matter held in sufficient isolation, for long enough, that the environment does not learn which path was taken before the algorithm has finished arranging its cancellations. Decoherence is not the obstacle to the machine. Decoherence is what normally happens, and the machine is the exception being fought for.
What remains genuinely unsettled
There is no agreement on what the theory means. Copenhagen treats collapse as a primitive fact and declines to elaborate. Many-worlds removes collapse entirely and accepts that every branch occurs. Pilot-wave theory gives particles definite positions guided by a real wave. There are others.
All of them predict identical results for every experiment ever performed, including every one described in this article. You may compute with whichever you find least uncomfortable and your answers will not change. Physicists disagree completely about the interpretation and agree completely about the predictions — an unusual arrangement, and worth remembering whenever a popular account presents one interpretation as settled fact, which is most of the time, and usually many-worlds because it makes the better copy.
None of that unsettlement reaches the practical question. Whether your keys are safe depends on gate fidelities, code distances and factoring runtimes, and on those the theory has been agreed for ninety years and tested to more decimal places than any other in science.
If you liked this, read next
Scott Aaronson's Quantum Computing Since Democritus for the complexity theory told properly and funnily; Nielsen & Chuang for the standard textbook; Preskill's NISQ paper for the most honest fifteen pages anyone in the field has written about its own limits.
References
- Google Quantum AI (2025). “Quantum error correction below the surface code threshold.” Nature 638, 920–926. nature.com
- Feynman, R. (1982). “Simulating Physics with Computers.” International Journal of Theoretical Physics 21(6/7), 467–488.
- Deutsch, D. (1985). “Quantum theory, the Church–Turing principle and the universal quantum computer.” Proceedings of the Royal Society A 400(1818), 97–117.
- Bernstein, E. & Vazirani, U. (1997). “Quantum Complexity Theory.” SIAM Journal on Computing 26(5), 1411–1473. Originally STOC 1993.
- Shor, P. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing 26(5), 1484–1509. (First presented at FOCS 1994.)
- Grover, L. (1996). “A fast quantum mechanical algorithm for database search.” Proceedings of STOC '96, 212–219.
- Bennett, C., Bernstein, E., Brassard, G. & Vazirani, U. (1997). “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26(5), 1510–1523.
- Tang, E. (2019). “A quantum-inspired classical algorithm for recommendation systems.” Proceedings of STOC 2019, 217–228. arXiv:1807.04271
- Aharonov, D. & Ben-Or, M. (1997). “Fault-Tolerant Quantum Computation with Constant Error.” Proceedings of STOC '97, 176–188. See also Knill, Laflamme & Zurek (1998), Science 279, 342–345.
- Gidney, C. & Ekerå, M. (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5, 433. quantum-journal.org
- Gidney, C. (2025). “How to factor 2048 bit RSA integers with less than a million noisy qubits.” arXiv:2505.15917
- Preskill, J. (2018). “Quantum Computing in the NISQ era and beyond.” Quantum 2, 79. quantum-journal.org
- Quantinuum (2025). “Helios.” System specifications and commercial launch, November 2025. quantinuum.com
- Bluvstein, D. et al. (2026). “Fault-tolerant quantum computation with a neutral atom processor.” Nature. Preprint: arXiv:2411.11822. See also the logical magic-state distillation result, Nature 2025.
- NIST (2024). FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA), finalised 13 August 2024. csrc.nist.gov
- Arute, F. et al. (2019). “Quantum supremacy using a programmable superconducting processor.” Nature 574, 505–510. nature.com
- Pan, F., Chen, K. & Zhang, P. (2022). “Solving the Sampling Problem of the Sycamore Quantum Circuits.” Physical Review Letters 129, 090502. arXiv:2111.03011
- Born, M. (1926). “Zur Quantenmechanik der Stoßvorgänge.” Zeitschrift für Physik 37, 863–867.
- Tonomura, A., Endo, J., Matsuda, T., Kawasaki, T. & Ezawa, H. (1989). “Demonstration of single-electron buildup of an interference pattern.” American Journal of Physics 57(2), 117–120.
- Bell, J. S. (1964). “On the Einstein Podolsky Rosen Paradox.” Physics 1(3), 195–200.
- Hensen, B. et al. (2015). “Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres.” Nature 526, 682–686. The 2022 Nobel Prize in Physics was awarded to Aspect, Clauser and Zeilinger for this programme of work.
- Zurek, W. H. (2003). “Decoherence, einselection, and the quantum origins of the classical.” Reviews of Modern Physics 75, 715–775.
This piece was written collaboratively with Claude Opus 5 (Anthropic): human specification and critical review, machine synthesis and drafting. Claims are cited to primary literature rather than to press releases, and the distinction is deliberate — several of the numbers that circulate most widely in this field come from announcements whose classical baselines were later revised downward by orders of magnitude. Where a result is contested (topological qubits) or where the speedup is disputed (quantum machine learning), that is stated rather than smoothed over.
Resource estimates in particular are moving targets: the qubit count needed to break RSA-2048 fell twenty-fold between 2019 and 2025 on algorithmic improvements alone. Any figure here should be read with a date attached.
Physicist & Developer
Comentários
Enviar um comentário