Qubits: what they do, and what a quantum computer still cannot
A reader asked what a qubit actually does, and what a quantum computer still cannot do. The short answer: a qubit carries two numbers, not one bit, and a quantum program steers those numbers so that wrong answers cancel and the right one adds up. That works spectacularly for a few problems and barely helps most others. No quantum computer has broken a code anyone uses, and in a 2024 survey the largest number honestly factored with Shor's algorithm on real hardware was 35.
What a qubit holds
An ordinary bit is 0 or 1. A qubit is described by two numbers called amplitudes, one attached to 0 and one to 1. When you measure it you never see the amplitudes: you get a plain 0 or 1, and the chance of each is the square of the size of its amplitude. Amplitudes can be negative (in general they are complex numbers), and that turns out to be the whole point.
The bookkeeping grows fast. Peter Shor's factoring paper spells it out: describing n ordinary bits takes n bits, but describing n qubits takes one amplitude for every one of the 2n possible bit patterns. Fifty qubits need about a million billion numbers. That is why simulating a quantum machine on an ordinary one gets out of hand so quickly.
The common slogan is that a quantum computer "tries every answer at once". That alone does not help, because a measurement hands you one pattern, picked at random by those squared amplitudes. Read a machine holding every answer equally and you get a random guess. The work is in making the useful answer likely before you look.
Interference is the trick
Because amplitudes carry signs, two paths to the same outcome can cancel or add, like ripples on water. A quantum algorithm is a sequence of steps arranged so that the amplitudes of wrong answers cancel and the right one grows. Lov Grover's 1996 search algorithm is the cleanest example, and it is what the figure below runs. Start with every one of N items equally likely. One step flips the sign of the item you want, which a checking circuit can do without anyone knowing in advance which item that is. A second step reflects every amplitude about their average. The flipped item sits far below the average, so it lands far above it. Repeat, and after about 0.785 times the square root of N rounds the item you want is close to certain. Go further and it overshoots and falls again.
Interactive Pick how many items to search, then press the two steps in turn (or tab to a button and press Enter). Watch the one item you want grow while the others shrink, and see where it peaks.
Every item starts equally likely: a look now is a 1-in-16 guess. Press "check" to flip the sign of the item you want.
That is a real speedup, but only a square root. Searching a million items takes about 785 rounds instead of up to a million checks. Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved in 1997 that for a search where the only thing you can do is check a candidate, no quantum method does better than that square root.
Where the big speedups are
A few problems have structure that interference can exploit far better. Shor showed in 1994 that a quantum computer could factor a whole number in a number of steps that grows only polynomially with its digits; the best known ordinary methods take far longer. The same paper breaks discrete logarithms, so the codes at risk are RSA, which rests on factoring, and the Diffie-Hellman and elliptic-curve methods used to agree keys and sign messages. NIST lists all of them as quantum-vulnerable. The other natural fit is simulating molecules and materials, which are themselves quantum systems: that 2n bookkeeping is the problem, and a quantum machine carries it natively.
What it still cannot do
It is not a faster computer for everything. John Preskill, who named today's noisy machines, wrote that physicists do not expect a quantum computer to solve the hard cases of problems like the travelling salesman efficiently; for those, the modest speedup on brute search is about what is on offer. Most everyday software, from spreadsheets to games, gains nothing.
It cannot yet run Shor's algorithm at any useful size. A 2024 survey by Dennis Willsch and colleagues found that the largest numbers factored honestly with Shor's algorithm on a real quantum computer were no bigger than 35. Many claims of larger ones, they note, rest on shortcuts that make the experiment no better than a coin flip.
The reason is noise. Qubits lose their amplitudes to the slightest disturbance, so long calculations need error correction: many physical qubits shared to hold one more reliable "logical" qubit. That only pays off if the hardware is already good enough. In 2024 Google showed it was: on its Willow chip, each step up in the size of a protected qubit cut its error rate by about half, down to 0.143% per cycle in the largest, built from 101 physical qubits. In 2025 the same chip ran a measurement of quantum chaos on 65 qubits that Google estimates would take the Frontier supercomputer about 13,000 times longer. It is a physics benchmark, not a commercial task.
How close the code-breakers are
What has moved fastest is the estimate of what breaking a code would take. In 2019 Craig Gidney and Martin Ekerå put RSA-2048 at 20 million noisy qubits. In 2025 Gidney brought it under a million, running for under a week, assuming qubits that err 0.1% of the time. In 2026 Madelyn Cain, Preskill and colleagues argued that a machine of movable neutral atoms could run Shor's algorithm at code-breaking sizes with as few as about 10,000 qubits, if slowly; their faster design for RSA-2048 uses about 102,000 qubits and some 97 days. These are designs on paper. The hardware they cite so far: arrays holding more than 6,000 good atoms, fault-tolerant operations below the error threshold, and computation on arrays of hundreds of qubits.
The replacement is already under way, because moving the world's software takes years. In August 2024 the US National Institute of Standards and Technology (NIST) approved its first three quantum-resistant standards and urged administrators to start switching at once. Its draft transition plan proposes that the vulnerable public-key methods be disallowed after 2035, with their weaker settings deprecated after 2030.
In one breath
A qubit holds amplitudes that can cancel, and a quantum algorithm arranges the cancelling so the right answer is likely when you look. That buys a square root on plain search, much more on factoring and on simulating nature, and nothing on most other work. Error correction now works in small, and code-breaking estimates keep shrinking, but no machine has come close to breaking a real key.
Where this comes from
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer linked only, not reproduced
arxiv.org/abs/quant-ph/9508027 - A fast quantum mechanical algorithm for database search linked only, not reproduced
arxiv.org/abs/quant-ph/9605043 - Strengths and Weaknesses of Quantum Computing linked only, not reproduced
arxiv.org/abs/quant-ph/9701001 - Quantum Computing in the NISQ era and beyond reuse permitted with attribution
arxiv.org/abs/1801.00862 - The State of Factoring on Quantum Computers linked only, not reproduced
arxiv.org/abs/2410.14397 - Quantum error correction below the surface code threshold reuse permitted with attribution
arxiv.org/abs/2408.13687 - How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits reuse permitted with attribution
arxiv.org/abs/1905.09749 - How to factor 2048 bit RSA integers with less than a million noisy qubits reuse permitted with attribution
arxiv.org/abs/2505.15917 - Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits linked only, not reproduced
arxiv.org/abs/2603.28627 - A verifiable quantum advantage linked only, not reproduced
research.google/blog/a-verifiable-quantum-advantage/ - NIST Releases First 3 Finalized Post-Quantum Encryption Standards linked only, not reproduced
www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards - Transition to Post-Quantum Cryptography Standards, NIST IR 8547 initial public draft linked only, not reproduced
csrc.nist.gov/pubs/ir/8547/ipd