Classical bits are switches: 0 or 1, definite at every instant. A qubit is a quantum object whose state is a continuous combination — a superposition — of 0 and 1, collapsing only when measured.
Definite. Copyable. One state at a time.
Probabilistic until measured. |α|² + |β|² = 1.
Quantum advantage rides on two phenomena no classical machine can fake. Together they let an n-qubit register encode 2ⁿ amplitudes in parallel — and steer them with interference.
A single qubit lives on a continuum between |0⟩ and |1⟩. n qubits explore 2ⁿ possibilities at once — though we only get one classical answer when we look.
Qubits can share a joint state that cannot be written as a product of parts. Measuring one instantly constrains the other — Einstein's "spooky action."
Every pure single-qubit state is a point on the surface of a unit sphere. The north pole is |0⟩, the south is |1⟩, and the equator is equal superposition. Operations are rotations; measurement collapses the vector to a pole.
"Nature isn't classical, dammit." Simulating molecules and materials on classical hardware demands resources that grow exponentially with system size. Feynman's proposal: build a computer out of quantum stuff to model quantum stuff.
It would take another decade for the field to take shape — but every quantum algorithm that followed traces back to this lecture.
In 1994 Peter Shor showed a quantum computer can factor an n-bit integer in polynomial time — exponentially faster than the best known classical method. RSA, which secures most of the internet, derives all its strength from factoring being hard.
General number field sieve. Sub-exponential, still ruinous at large n.
Polynomial. A 2048-bit RSA key falls in hours, given enough fault-tolerant qubits.
Recent estimates for breaking RSA-2048 with realistic error rates. We are not there yet.
Two years after Shor, Lov Grover showed how to find a marked item in an unsorted database of N entries using only ≈√N queries. Not exponential — but a quadratic speedup that applies to a vast class of search-shaped problems.
Brute-force AES-256 drops from 2²⁵⁶ to 2¹²⁸ — still infeasible. The win is in optimization, satisfiability, ML kernels.
No consensus on the right physical substrate. Every approach trades coherence time, gate fidelity, connectivity and clock speed differently. The race is wide open.
Fast gates, scalable lithography. Needs millikelvin dilution refrigerators.
Long coherence, high fidelity, all-to-all connectivity. Slower clock.
Room-temperature, networking-friendly. Probabilistic gates, high losses.
Reconfigurable arrays, recently scaled past 1000 atoms. Newest contender.
Decoherence, gate errors, readout errors — physical qubits today have error rates around 10⁻³ per operation. Useful algorithms need ~10⁻¹⁵. The fix is quantum error correction: encode one logical qubit across many noisy physical ones.
For the first time, logical qubits are outperforming their underlying physical components. Crossing this threshold means scaling adds reliability — error correction is no longer theoretical.
Surface-code distance-7 logical qubit shows error suppression that improves as code distance grows.
Trapped-ion processor entangles 12 high-fidelity logical qubits with magic-state distillation.
Neutral-atom array runs algorithms on dozens of logical qubits — largest demo to date.
There are demonstrations where quantum hardware solves a contrived task faster than any known classical method — sampling random circuits, boson sampling, certain spin-glass problems. Whether they are useful is a separate question. Classical algorithms keep catching up too.
53 qubits. First claimed "supremacy." Subsequent classical methods narrowed the gap.
Independent demonstration on a fundamentally different platform.
Larger, harder-to-spoof random circuit sampling on the Willow chip.
No public, scientifically-significant problem yet solved faster on a quantum machine end-to-end.
Quantum computing is over-hyped on the short horizon and arguably under-appreciated on the long one. The realistic timeline for broadly useful machines is measured in years to a decade-plus, not quarters. The prize, if it lands, is genuinely transformational.
A field still being built. Pick a thread and pull.