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. What follows is an attempt to close it: what a quantum computer actually is, the short list of things it is actually good at, why that list is short for reasons we can prove, and how to read the next announcement without being had.
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. The conclusion does not follow, and the reason is measurement.
Yes, the state of 300 qubits is described by 2300 complex numbers — amplitudes. But you cannot read them. When you measure, the machine gives you exactly 300 classical bits, one outcome, chosen at random with a probability equal to the squared magnitude of that outcome's amplitude. Everything else is gone. A quantum computer that merely put every candidate answer into superposition and then measured would be an extraordinarily expensive random number generator.
So the exponential space is real and almost entirely inaccessible. The whole discipline of quantum algorithm design is the problem of getting one useful bit of information out of a space you are not allowed to look at.
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. A classical probability is a non-negative number; probabilities add. Amplitudes have a phase, and phases can be opposite, so amplitudes can subtract. Two paths leading to the same wrong answer, arriving with opposite phase, annihilate.
| 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 |
Add entanglement and the description stops factorising: for most states of a multi-qubit system there is no way to say what qubit 3 is doing on its own, only what the whole register is doing. That non-factorisability is exactly why simulating quantum systems on classical hardware is expensive, which is where the whole idea started.
Because Richard Feynman's 1982 argument was not about speed at all.[2] It was an observation about honesty: nature runs quantum mechanics cheaply and we cannot, so if we want to simulate nature we should build our 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 short list
Peter Shor's 1994 algorithm factors integers in polynomial time.[4] 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 searches an unstructured list of N items in about √N steps.[5] 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.[6] 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.[7] |
| 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.[8] 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.[9] In 2025, Gidney published a revised estimate of fewer than a million, in under a week.[10] 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 |
Meanwhile the useful term for the present moment remains John Preskill's: NISQ, Noisy Intermediate-Scale Quantum.[11] Machines with tens to hundreds of physical qubits and no error correction — big enough to be hard to simulate, too noisy to be useful. Preskill coined it in 2018 partly as a warning, and it has aged into an accurate description of a period we are only now starting to leave.
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.
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.[12] 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 or logical qubits?
A headline count of 1,000+ almost always means physical qubits. Useful algorithms need logical qubits, each currently costing something in the range of a thousand physical ones. The two numbers differ by three orders of magnitude and the press release rarely says which it is quoting.
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.[13] 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.[14] 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.
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.
- 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
- 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
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