Part 2: How They Work 10 min read

The Exponential Advantage

Adding one more qubit doubles the state space of a quantum computer. This sounds modest until you realize it means 300 qubits can hold more states simultaneously than there are atoms in the observable universe.

The state space of n qubits

With one classical bit, you have two possible states: 0 or 1. With two bits, four states: 00, 01, 10, 11. With n bits, 2ⁿ possible states - but a classical computer only occupies one of them at any given moment, the way a light switch is either on or off, never tracking every possible switch combination at once.

With one qubit in superposition, you have amplitudes for two states. With two qubits, four amplitudes. With n qubits, the quantum state is described by 2ⁿ complex amplitudes - one for each possible combination of 0s and 1s across all qubits. Applying gates manipulates all these amplitudes simultaneously.

This is the heart of the quantum advantage: a quantum computer operating on n qubits processes information in a 2ⁿ-dimensional space. At 50 qubits, that is over a quadrillion dimensions. At 300 qubits, it exceeds the number of atoms in the visible universe.

Quantum state space by qubit count - hover each bar

1Q2Q3Q4Q5Q 6Q7Q8Q9Q10Q

Each qubit added doubles the state space. By 50 qubits that is over a quadrillion states. By 300 qubits it exceeds the number of atoms in the observable universe.

The catch: you can only extract limited information

The 2ⁿ amplitudes represent an enormous amount of information - but you cannot read it all out. Measurement collapses the entire state to one of the 2ⁿ basis states, giving you n classical bits. Just n bits of output, even though the computation touched 2ⁿ states during the process. It is like baking a cake with thousands of ingredients interacting in the oven, then being allowed to taste only the single finished slice that lands on your plate - all that complexity collapses down to one outcome.

This is why quantum advantage is not as simple as "n qubits = 2ⁿ processing lanes." A quantum computation must be designed so that the interference pattern at the end leaves the correct answer with high probability when you measure. The 2ⁿ states are not all independently readable - they are woven together by the computation and only partially visible at the end.

This constraint explains why quantum computers are not simply "faster at everything." They are faster only for specific types of problems where the quantum interference structure can be engineered to highlight the correct answer.

Quantum speedup: how much faster?

The advantage quantum computers provide is measured in computational complexity - how the runtime grows as the problem size increases, the same way you'd judge whether a search method scales well by asking how much longer it takes when the haystack gets ten times bigger, not just how fast it is on today's haystack. Three categories of speedup are known:

The landscape of quantum advantage is still being mapped. Researchers continue discovering new problem types where quantum algorithms outperform the best known classical alternatives.

Exponential Speedup

The most powerful class - problem of n takes 2ⁿ steps classically, polynomial steps quantumly

Shor's algorithm for factoring large numbers and Harrow-Hassidim-Lloyd (HHL) for certain linear algebra problems achieve exponential speedup. A classical algorithm might take time proportional to 2ⁿ; the quantum algorithm takes time proportional to n² or similar.

This is a genuine game-changer. A problem that takes the world's fastest classical computer millions of years could, in principle, run in hours on a fault-tolerant quantum computer. Cryptography, chemistry simulation, and optimization are the primary targets.

Quadratic Speedup

Still significant - N steps becomes √N steps

Grover's search algorithm achieves a quadratic speedup for unstructured search. If a classical search requires checking N items, Grover's requires only √N quantum queries.

For a database with a trillion entries, classical search takes a trillion steps on average. Grover's takes about a million. That is a million times faster - enormous in practice, even though it is not exponential. Quadratic speedups apply surprisingly broadly, touching any problem reducible to searching.

Constant-Factor Improvement

Some problems get faster by a fixed multiplier, not a scaling advantage

For some problems, quantum algorithms simply use resources more efficiently by a fixed constant amount, with no asymptotic scaling advantage.

A constant-factor speedup is still useful in practice - if quantum hardware is 10x faster on a specific computation, that translates directly to cost and energy savings. But it is not a breakthrough in the same sense as exponential or quadratic speedups. The true quantum revolution targets the first two categories.

Try it in the Sandbox

Watch the state space grow as you add qubits

Start with 2 qubits in Expert mode. Apply H to both and see 4 states at 25% each.
Click + to add a third qubit, apply H to it. Now 8 states at 12.5% each.
Add a fourth qubit with H. 16 states at 6.25%. Each qubit doubles the state space.
Keep adding qubits. Watch the basis state count double every time.
Apply CNOT gates between adjacent qubits. Entanglement reshapes the distribution.

Quantum simulation: the original motivation

Richard Feynman, one of the greatest physicists of the 20th century, proposed the idea of quantum computing in 1981. His argument was simple: classical computers cannot efficiently simulate quantum systems, because the state space grows exponentially. To simulate a quantum system, you need a quantum computer.

This is still one of the most compelling applications. Simulating molecular chemistry quantum-mechanically - including all electron interactions without classical approximations - could enable drug discovery, materials science, and catalysis research at a level currently impossible. The 2019 Google quantum supremacy demonstration was a simulation-style benchmark.

Quantum advantage vs. quantum supremacy

Quantum supremacy (or quantum advantage, as some prefer to call it) refers to a quantum computer performing a specific computation faster than any classical computer could. Google's 2019 claim was this kind of benchmark - a very specific, artificial problem where quantum hardware excels.

The more important milestone is practical quantum advantage: a quantum computer solving a real-world problem of genuine interest faster or better than any available classical method. As of 2024, no machine has definitively achieved this for a problem that matters outside the lab. The field expects this to happen within the decade - but the precise timeline and first application remain open questions.

Key takeaway

n qubits live in a 2ⁿ-dimensional state space, giving quantum computers exponentially more processing "width" than classical bits. But measurement only extracts n classical bits of output - so the quantum advantage comes from cleverly engineering interference so that the correct answer has high probability at the end, not from simply reading out all 2ⁿ states.

Knowledge check · Question 1 of 5

A quantum computer has 10 qubits all in superposition. How many basis states does its state vector have amplitudes for simultaneously?

With n qubits, there are 2ⁿ possible combinations of 0s and 1s across all qubits. Each has a complex amplitude. For 10 qubits: 2¹⁰ = 1024 basis states.

Knowledge check · Question 2 of 5

Why can't a quantum computer simply "read out" all 2ⁿ amplitudes it computed with?

Measurement forces the system to collapse to one of its 2ⁿ basis states, so you only ever get n classical bits of output - the rest of the information is never directly observed.

Knowledge check · Question 3 of 5

Grover's search algorithm, which turns an N-step classical search into roughly √N quantum queries, is an example of which category of speedup?

Grover's algorithm reduces N steps to about √N steps, which is the defining signature of a quadratic speedup - smaller than exponential, but still a major practical gain at large N.

Knowledge check · Question 4 of 5

What was Richard Feynman's original 1981 argument for why quantum computers should exist?

Feynman observed that simulating a quantum system classically requires tracking exponentially many amplitudes, so only a quantum computer can efficiently simulate quantum nature itself.

Knowledge check · Question 5 of 5

What distinguishes "practical quantum advantage" from the kind of "quantum supremacy" Google demonstrated in 2019?

Google's 2019 result was a quantum supremacy benchmark - a specific, artificial problem designed to favor quantum hardware. Practical quantum advantage, solving a problem people actually care about better than classical methods, has not yet been definitively achieved.