What a quantum computer is, and is not

Does a quantum computer try every answer at once?

A quantum computer manipulates amplitudes and produces a measurement result.

Take n quantum bits, qubits. Together they carry 2ⁿ numbers, called amplitudes, one for every answer you could write down with n bits. Fifty qubits juggle 2⁵⁰ of them. That is where the "every answer at once" story comes from.

Amplitudes can have different signs and phases. When two routes lead to the same answer, their amplitudes add and can cancel. It is the same trick as a pair of noise-cancelling headphones, where a sound wave meets its mirror image and the two leave silence. A quantum algorithm is a recipe for steering the amplitudes so that wrong answers cancel and the right one is left standing.

Measurement returns one answer from the 2ⁿ possibilities. The chance of seeing a given answer is its amplitude squared. If the cancelling worked, the right answer is nearly certain. If you skipped the cancelling, you get a random answer, which is no better than a guess.

Guess first You run a quantum computer with 50 qubits and read it out at the end. How many bits of answer do you get back?

Fifty. Exactly as many as a 50-bit ordinary register would give. The 2⁵⁰ amplitudes shape the answer, but reading them out hands you only n bits, and Alexander Holevo proved in 1973 that no cleverer way of reading does better.

That is why quantum computers are specialists. Cancellation needs structure to work with. For a few problems we know how to build it: finding the hidden pattern in a number that lets you factor it, searching an unsorted list, simulating how molecules and materials behave, which is quantum physics to begin with. For most problems anyone cares about, nobody knows any way to make the wrong answers cancel, and a quantum computer is no faster than an ordinary one.

Quantum coherence is also fragile. The cancelling only works while the amplitudes stay undisturbed. A stray bit of heat, a passing photon, a vibration: anything that nudges the machine and records the nudge somewhere else counts as a measurement, and the delicate pattern collapses. Physicists call this decoherence. Thermal noise can disrupt coherence. Suppressing it requires cooling and isolation, with their own energy costs.

Both constraints apply to the Vigil. In 2540 its computing nodes in zone C come in reversible, quantum and archival kinds. The quantum ones are specialists, and they run cold, for the reason above. Quantum hardware does not provide a general speedup for every computation a mind performs. Speed is a question of energy and distance, which How fast can anything think? covers, and quantum nodes help only on the problems whose structure lets the wrong answers cancel.

How much does it actually buy?

First the gap between what goes in and what comes out. The number of amplitudes doubles with every qubit you add; the number of bits you can read back goes up by one.

Qubits	Amplitudes held	Bits read out
53 (a 2019 research chip)	9.0 × 10¹⁵	53
300	2.0 × 10⁹⁰	300

The second row has far more amplitudes than there are atoms in the visible universe, and it still hands back 300 bits. That is the Holevo bound, derived below.

Does search get a square-root speedup?

Take a list of N items, one of them marked, where the only way to find it is to check items. An ordinary computer checks about N/2 of them on average. Lov Grover showed in 1996 that a quantum computer needs only about √N rounds; the best count is close to (π/4)√N.

For a list of 1,000,000 items, the ordinary search takes 500,000 checks on average. Grover's takes 785 rounds, which is 637 times fewer.

Step through the toy and watch the marked item's amplitude grow, then keep going past the best count and watch it shrink.

Grover search over sixteen possible answers, drawn as amplitudes. Marking flips the target's sign, reflecting about the mean lifts it and shrinks the rest, and a few rounds leave nearly all the weight on the right answer.

With JavaScript on, this steps Grover's algorithm on a list of 4 to 32 items, one reflection at a time. A list of a million items needs 785 rounds, against 500,000 checks on average for a classical search. Four items need one round and are found with certainty.

A square root only halves the exponent. A search over 2⁶⁴ keys takes 9.2 × 10¹⁸ checks on average the ordinary way and 3.4 × 10⁹ rounds the quantum way. For 2¹²⁸ keys the figures are 1.7 × 10³⁸ and 1.4 × 10¹⁹. A quantum computer turns a 128-bit lock into something like a 64-bit one, with the snag that Grover's rounds must run one after another. Longer keys increase the search required.

Does factoring speed up by more than a square root?

Peter Shor's 1994 algorithm gives a much larger improvement for factoring. The best known ordinary method for a 2,048-bit number is the number field sieve, whose cost is roughly 2^117 operations, or 1.5 × 10³⁵. Shor's needs a number of gates that grows about as the cube of the bit length, which for 2,048 bits is of order 8.6 × 10⁹.

The hardware requirements remain substantial. Craig Gidney and Martin Ekerå estimated in 2021 that the job needs 2.0 × 10⁷ noisy qubits running for 8 hours. Gidney's 2025 revision brought it under 1.0 × 10⁶ noisy qubits and under 7 days. Neither machine existed in 2026.

Why must a quantum computer be cold?

A typical superconducting qubit flips between its two states with a photon of about 5.0 × 10⁹ hertz and works at about 0.020 K (figures from a 2019 review by Krantz and colleagues). The photon's energy as a temperature is hf/k = 0.24 K. Surroundings hotter than that are full of such photons, each a chance to flip the qubit by accident. The average number in the qubit's mode is 1 / (e^(hf/kT) − 1):

Surroundings	Temperature	Stray photons in the mode
A warm room	300 K	1,200
The Vigil's radiators	30 K	120
A typical dilution refrigerator	0.020 K	6.2 × 10⁻⁶

The refrigerator is 136 times colder than the 2.7 K glow of deep space, and about 2.0 × 10⁸ times quieter than a warm room. Lifting heat from 0.020 K up to 300 K costs at least 14,999 joules of work for every joule lifted, even with a perfect refrigerator. It is the same logic as the price of forgetting in The cost of forgetting: operating at low temperature reduces some costs, while refrigeration consumes work.

Open everything

Why does cancelling help, and why can't we read it all out?Deutsch-Jozsa, Grover's rotation and the Holevo bound

Interference in one query: Deutsch and Jozsa

One early demonstration of quantum speedup uses a deliberately constructed mathematical problem. You are given a function f that takes an n-bit input and returns 0 or 1, and you are promised that it is either constant (the same answer for every input) or balanced (0 for exactly half of the inputs, 1 for the other half). Which is it?

An ordinary computer has to ask. In the worst case it asks 2ⁿ⁻¹ + 1 times: if the first half of the inputs all say 0, the next one still decides. The quantum computer asks once.

Start with all n qubits in the state |0…0⟩. The Hadamard gate, applied to every qubit, spreads the amplitude evenly over all 2ⁿ inputs:

$|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle$

One call to f, done as a phase, multiplies each input's amplitude by $(-1)^{f(x)}$ :

$|\psi'\rangle = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{f(x)} |x\rangle$

Now apply the Hadamard gates again. The amplitude that lands on the all-zeros state is the sum of all the input amplitudes, each carried over with the same sign:

$a_{0\dots 0} = \frac{1}{2^n} \sum_x (-1)^{f(x)}$

If f is constant, every term has the same sign, and the amplitude is +1 or −1. If f is balanced, half the terms are +1 and half are −1, and they cancel exactly, so the amplitude is 0. Measure: all zeros means constant, anything else means balanced, and it never errs. This example shows how interference produces a useful measurement result. David Deutsch and Richard Jozsa set the puzzle and solved it in 1992, with an exponential gap against deterministic ordinary computers; the one-query form shown here is the 1998 refinement by Richard Cleve, Artur Ekert, Chiara Macchiavello and Michele Mosca. (A randomized ordinary computer can answer the same puzzle with a handful of queries and a tiny chance of error, so the gap is real but narrow.)

Grover's rotation

Let |w⟩ be the marked item, and let |s⟩ be the even superposition of all N items, so that ⟨w|s⟩ = 1/√N. Pick the axis |s′⟩, the part of |s⟩ with the marked item removed (normalized). The state lives in the flat plane spanned by |w⟩ and |s′⟩, and it starts at an angle θ from |s′⟩ with

$\sin\theta = \frac{1}{\sqrt N}$

Each Grover round is two reflections. The oracle flips the sign of the |w⟩ part, which is a reflection about the |s′⟩ axis. The diffusion step reflects every amplitude about the average, which is a reflection about |s⟩ (this is what the toy's second button does). Two reflections across lines a small angle θ apart make a rotation by twice the angle between them, 2θ, toward |w⟩. After k rounds the state sits at angle (2k + 1)θ from |s′⟩, and the chance of finding the marked item is

$P_k = \sin^2\big((2k+1)\,\theta\big)$

The best count is the k where (2k + 1)θ = π/2, which is

$k = \frac{\pi}{4\theta} - \frac12 \approx \frac{\pi}{4}\sqrt N \quad (N \gg 1)$

Check it on small cases. For N = 4, θ = 30°, k = 1, and 3θ = 90°: the answer is found with certainty in one round, as the toy shows. For N = 16, θ = 14.5°, k = 3, and the chance is 0.96. For a million items, k = 785, which is 0.785 × √N, the π/4 coming out right.

Rotation is also why overshooting hurts. Past k the state turns beyond |w⟩ and back toward |s′⟩. Run the million-item search twice as long and the chance of finding the marked item is 3.5 × 10⁻⁷. The iteration count must therefore be chosen to maximize the success probability.

Why the square root is the best possible

Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved in 1997 that no quantum algorithm can find a marked item among N, with only the ability to check items, using a number of checks that grows more slowly than √N. The intuition is the rotation above: each check can turn the state by only a small angle, and you need to turn through a fixed one.

The Holevo bound

Alice encodes a message by choosing one of several quantum states, with probabilities p_i, and sends it to Bob, who can measure it any way he likes. In 1973 Alexander Holevo proved that the most Bob can learn about which state she chose is

$I \le S(\rho) - \sum_i p_i\, S(\rho_i) \le \log_2 d$

where ρ is the average state, S is the von Neumann entropy (the quantum cousin of the entropy in Entropy is missing information) and d is the size of the space. For n qubits, d = 2ⁿ, so the last term is exactly n bits. The 2ⁿ amplitudes give the state room to hold a very rich pattern, but a measurement cannot get more out of it than an n-bit register could hold. That is why an algorithm has to concentrate the right answer before the readout, and why the exponential number of amplitudes does not translate into an exponential amount of readable output.

Where do the claims stand?BQP and NP, error correction, and quantum advantage

What class of problems is it?

Computer scientists call the problems a quantum computer can solve in a reasonable amount of time, with a small chance of error, BQP. Every problem an ordinary computer solves quickly is in it. Factoring is in it, by Shor. But BQP is not believed to contain the hard core of NP, the problems like the travelling salesman, where a proposed answer is easy to check and finding one seems hard.

The best evidence is the Bennett, Bernstein, Brassard and Vazirani result of 1997: relative to a random oracle, NP cannot be solved by a quantum computer in time much less than 2^(n/2), and Grover's algorithm meets that bound. The oracle assumption limits how directly this result applies to real problems. A proof that NP is not in BQP would also prove P ≠ NP, because P sits inside BQP, so nobody expects one soon. Factoring is not thought to be NP-complete either, which is why it can be easy for a quantum computer while the hard problems stay hard. frontier

Keeping it cold and correct

Quantum error correction reduces the effect of noise. The leading design is the surface code, which spreads one logical qubit over a square grid of physical qubits, with measuring qubits alongside. Austin Fowler and colleagues gave the standard account of it in 2012 and noted that it tolerates an error rate per operation as high as about 1 percent, far looser than other codes. That figure is the threshold. Below it, making the grid bigger makes the logical qubit better. Above it, bigger is worse.

Google Quantum AI demonstrated operation below that threshold in 2024. Their distance-7 code, on 101 physical qubits, made a logical error of 0.143 percent per cycle, and each step up in the grid size cut the error by a factor of 2.14.

Assume that factor holds and extend the line. To reach a logical error of 1.0 × 10⁻¹² per cycle, one slip in a trillion, takes a grid of distance 63, about 7,900 physical qubits (2d² − 1) for one logical one. Nobody has shown that the factor holds that far; rare bursts of correlated errors, which the same paper found about once an hour in its repetition-code runs, are the known threat. The factoring estimates earlier on the page assume a better machine: a gate error of 0.10 percent on every qubit, ten times below the threshold. frontier

Quantum advantage, and who has it

In 2019 Google's group reported that its 53-qubit Sycamore chip sampled a quantum circuit a million times in about 200 seconds, a job they estimated would take the best ordinary supercomputer about 10,000 years. IBM researchers replied the same year with an analysis showing that, using disk storage, the Summit supercomputer could simulate such circuits in days. In 2022 Feng Pan, Keyang Chen and Pan Zhang sampled the same circuit with a new tensor-network method in about 15 hours on a cluster of 512 GPUs, and estimated that an exascale machine would beat the quantum chip's time.

The sampling task was designed to challenge classical simulation and had no direct practical use. Improved classical algorithms reduced a claimed gap of 10,000 years to hours.

John Preskill's 2018 essay gave the era its name, NISQ, for noisy intermediate-scale quantum. Machines of 50 to 100 qubits might do things ordinary computers cannot, he argued, but noise would limit how large a circuit could run reliably, and such machines would not change the world right away. Whether a quantum computer had beaten ordinary ones on any useful problem by 2026 was still argued, claim against counter-claim. frontier