Lesson B: Why ordinary computers can’t keep up

A list that doubles with every qubit, Feynman’s idea, and the first algorithms

7 partsbest after lesson A

The interactive version checks every answer, gives hints and saves your progress in this browser. This page is the same lesson on one page, with the answers folded away.

1 / 7 · Learn

Before you start

Lesson A ended by counting amplitudes. This lesson follows that count much further, to see why ordinary computers can’t keep up with quantum systems and how that gave people the idea of a quantum computer. The only math is multiplying by 2.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

In Lesson A you met amplitudes: numbers that, unlike chances, can cancel. A group of qubits has one amplitude for every combination of 0s and 1s it can give when measured: 2 for one qubit, 4 for two, 8 for three. To describe the group exactly, an ordinary computer has to store them all. Roughly how many amplitudes is that for 300 qubits?

AMore than there are atoms in the observable universe
BAbout a trillion: a 1 followed by 12 zeros
CAbout 90,000: 300 × 300
DAbout 600: two for each qubit

Show the answer

Answer: A. More than there are atoms in the observable universe

An exact description needs one amplitude for every combination of 0s and 1s, and each added qubit doubles the number of combinations. 300 doublings give about 2 followed by 90 zeros, while the observable universe holds roughly a 1 followed by 80 zeros atoms.

Why not the others

B. Doubling grows faster than it feels. The list reaches a trillion after only 40 doublings, at 40 qubits, and 300 qubits are 300 doublings. By then the list is longer than the number of atoms in the observable universe.
C. The count grows much faster than that. Each added qubit doubles it: 3 qubits need 8 amplitudes, 10 need 1,024, and 20 already need about a million. By 300 qubits the list is longer than the number of atoms in the observable universe.
D. Two per qubit would be enough if each qubit could be described on its own. In general it can’t: an exact description needs one amplitude for every combination of 0s and 1s, and each added qubit doubles the number of combinations. Already at three qubits that is 8, not 6, and for 300 qubits it is more than the atoms in the observable universe.

2 / 7 · Learn

Feynman’s question

In May 1981, at a conference near Boston on the physics of computation, the physicist Richard Feynman asked a question that sounds simple: can an ordinary computer simulate nature? For planets, weather or bridges, yes, given time. Feynman was asking about the quantum world: atoms, molecules, the electrons in a material, and photons like those in Lesson A.

Recall Lesson A: every way an event can happen has an amplitude, and amplitudes, unlike chances, can cancel. To predict a quantum system, a computer has to keep track of all its amplitudes. For one photon that is easy: two routes, two amplitudes. But the list grows far faster than the number of particles, so a few hundred particles would need more numbers than any computer could store. The next part counts them.

So Feynman turned the problem around. Quantum objects don’t store their amplitudes anywhere: they simply have them. A computer built from quantum parts would have amplitudes too, so it could imitate other quantum systems without storing the list. As he put it in the paper that grew out of the talk:

Check yourself

Why would a computer built from quantum parts get around the problem Feynman described?

AQuantum parts are tiny, so far more of them fit on a chip
BAt the end it can show you every amplitude at once
CIts parts switch much faster than an ordinary chip’s
DIts parts have amplitudes of their own, so nothing has to write down the whole list

Hints

What stops an ordinary computer here: its speed, or the length of the list it has to store?
A photon in Lesson A had an amplitude for each route without anything writing them down. What would a machine made of such parts have to store?

Show the answer

Answer: D. Its parts have amplitudes of their own, so nothing has to write down the whole list

An ordinary computer has to store every amplitude as a number. A machine made of quantum parts doesn’t: its parts have amplitudes that add and cancel as nature’s do. That was Feynman’s idea.

Why not the others

A. Size isn’t the point: the list for a few hundred particles is too long for any memory, however small its parts. What helps is that quantum parts carry amplitudes themselves.
B. Lesson A’s rule still holds: a measurement gives one outcome, never the list of amplitudes. The gain is in what the machine doesn’t have to store along the way, not in what it can show you.
C. Speed isn’t the obstacle. For a few hundred particles the list of amplitudes is too long to store at all, however fast the chip. Quantum parts help because they carry amplitudes themselves, so the list never has to be written down.

3 / 7 · Worked example

Each qubit doubles the list

A qubit is a quantum object that gives 0 or 1 when measured, with an amplitude for each. To describe several qubits exactly, a computer needs an amplitude for every outcome they can give together. Here is the count, one qubit at a time.

Worked example

Counting amplitudes

1 qubit
The outcomes are 0 and 1: 2 amplitudes.
2 qubits
Each qubit gives 0 or 1, so together they give 00, 01, 10 or 11: 4 amplitudes, one per outcome.
3 qubits
Take each of the 4 two-qubit outcomes and add a 0 or a 1 for the third qubit: 000, 001, 010, 011, 100, 101, 110, 111. That makes 4 × 2 = 8 amplitudes.
Why not just two amplitudes for each qubit, 6 in all? Because qubits can be linked in ways that a separate description of each one can’t capture (Lesson 7 calls this entanglement). One amplitude for every joint outcome covers every case.
The pattern
Each new qubit splits every old outcome in two, one ending in 0 and one ending in 1. So each added qubit doubles the list. For n qubits that is 2 × 2 × … × 2, with n twos, written $2^n$ .
Your turn
Now add a fourth qubit.
Your turn
How many amplitudes does an exact description of 4 qubits need?
Hints
1. How many amplitudes did 3 qubits need?
2. The fourth qubit splits each of those outcomes in two.
Show the answer
Answer: $16$
3 qubits need 8 amplitudes, and the fourth qubit doubles that: 8 × 2 = 16, one for each outcome from 0000 to 1111.
Common slips
- $8$ : 8 is the count for 3 qubits, and also 2 for each of 4 qubits. The fourth qubit splits each of the 8 three-qubit outcomes in two: 8 × 2 = 16.
- $10$ : That adds 2 for the new qubit: 8 + 2. But the new qubit splits every one of the 8 outcomes in two, so the list doubles: 8 × 2 = 16.
- $4$ : That is one per qubit. Even one qubit needs two amplitudes, and each added qubit doubles the list: 2, 4, 8, 16.

Doubling adds up quickly. Ten doublings give $2^{10} = 1{,}024$ , about a thousand. So every 10 extra qubits multiply the list by about a thousand:

10 qubits: about a thousand amplitudes
20 qubits: about a million
30 qubits: about a billion
40 qubits: about a trillion

Check yourself

An exact description of some qubits lists their amplitudes. You add 3 more qubits. How many times longer is the list now?

Hints

What does adding a single qubit do to the list?
Double the list 3 times: 2 × 2 × 2.

Show the answer

Answer: $8$

Each new qubit doubles the list, so 3 new qubits double it 3 times: 2 × 2 × 2 = 8.

Common slips

$6$ : That counts 2 for each new qubit and adds them up: 3 × 2 = 6. But each new qubit doubles the whole list, so the 2s multiply: 2 × 2 × 2 = 8.
$3$ : That makes the list 3 times longer, one step for each new qubit. But each new qubit doubles it, so 3 new qubits double it 3 times: 2 × 2 × 2 = 8.
$4$ : Each new qubit doubles the list, so the 3 new ones double it 3 times: 2 × 2 × 2 = 8.
$16$ : That doubles the list 4 times, once too often. Each of the 3 new qubits doubles it once: 2 × 2 × 2 = 8.

4 / 7 · Learn

Out of reach

Now turn amplitudes into computer memory. In general an amplitude is an arrow that can point in any direction (Lesson A), so a computer stores it as two ordinary numbers: how far the arrow reaches across, and how far up. A standard simulation uses 8 bytes for each number: 16 bytes per amplitude.

30 qubits have about a billion amplitudes ( ${2^{30} = 1{,}073{,}741{,}824}$ ), which take 16 gigabytes. That is about the memory of a laptop, so around 30 qubits is where a laptop runs out. Every 10 more qubits need 1,024 times the memory: 16 terabytes for 40 qubits, and 16 petabytes for 50 (a petabyte is about a million gigabytes).

Memory for an exact description. Each gridline is $2^{10} = 1{,}024$ times the one below, so the memory line climbs one gridline every 10 qubits. A laptop runs out at about 30 qubits, and a supercomputer with 10 petabytes at 49.

Check yourself

A laptop can hold the exact description of about 30 qubits. A computer with 8 times as much memory runs the same kind of simulation. About how many qubits can it describe exactly?

Hints

How many times must the memory double to become 8 times as much?
Each doubling of the memory holds exactly one more qubit.

Show the answer

Answer: $33$

8 is $2^{3}$ , so the memory doubles 3 times, and each doubling holds one more qubit: 30 + 3 = 33.

Common slips

$240$ : That makes the qubits grow in step with the memory. But each extra qubit doubles the memory needed. 8 is $2^{3}$ , so the memory doubles 3 times: room for 3 more qubits, 33 in all.
$38$ : That adds one qubit for each extra laptop’s worth of memory. But one more qubit already needs twice the memory, two more need four times, and so on. 8 is $2^{3}$ , so the memory doubles 3 times: 33 qubits.
$31$ : One more qubit needs twice the memory, and this computer has more than that. 8 is $2^{3}$ , so the memory doubles 3 times, and each doubling holds one more qubit: 33.
$60$ : Going from 30 to 60 qubits would mean doubling the memory 30 times, about a billion times as much. 8 is $2^{3}$ , so the memory doubles 3 times: 33 qubits.

Now go all the way to 300 qubits. That is thirty steps of 10 qubits, and each step multiplies the list by about a thousand. Multiplying by a thousand thirty times gives a 1 followed by 90 zeros, and the exact count, $2^{300}$ , is about twice that.

For comparison, the number of atoms in the observable universe is estimated at about a 1 followed by 80 zeros.

Qubits from 0 to 300, where each step to the right doubles the list of amplitudes, up to $2^{300}$ of them. Everything an ordinary computer can describe exactly sits in the sliver at the left. By about 266 qubits the list has more amplitudes than the observable universe has atoms.

5 / 7 · Learn

Hard to simulate isn’t the same as useful

Feynman’s argument shows that a quantum computer could do something ordinary computers can’t keep up with. That alone isn’t a reason to build one. There are two catches.

First, you can’t read the list out. A measurement gives one outcome (Lesson A). Each qubit gives one bit, 0 or 1, so measuring 300 qubits gives a string of 300 zeros and ones, not $2^{300}$ amplitudes.

Check yourself

A quantum computer with 50 qubits finishes a run. An exact description of its qubits would list about a million billion amplitudes. You measure all 50 qubits. What do you get?

AThe million billion amplitudes
BEvery possible string of 50 zeros and ones
CA string of 50 zeros and ones: one outcome
DThe string with the largest amplitude, every time

Show the answer

Answer: C. A string of 50 zeros and ones: one outcome

Each qubit gives one bit when measured, so 50 qubits give 50 bits: one outcome. The huge list of amplitudes decides which outcomes are likely, but you never see the list.

Why not the others

A. A measurement never reads out amplitudes. Each qubit gives 0 or 1, so 50 qubits give one string of 50 zeros and ones. The amplitudes only set how likely each string is.
B. There are about a million billion such strings, and a measurement gives just one of them, picked at random with chances set by the amplitudes.
D. That string is the most likely one, not a certain one. Any string whose amplitude isn’t 0 can come up.

Second, being hard to simulate isn’t the same as being useful. A quantum computer running random steps is very hard to simulate, yet all it gives you is a random string. To be useful it needs an algorithm: steps chosen so that, as in Lesson A, the amplitudes of wrong answers cancel and those of the right answer add up. Then the one outcome you read is very likely the answer.

After 1981 the question became: are there any such algorithms? The first ones were found with pencil and paper, long before any machine could run them.

1985: David Deutsch, at Oxford, described a universal quantum computer, one machine that could be programmed, like an ordinary computer, to do the work of any other quantum computer, and gave a first, tiny problem on which it could have an edge. Lesson 9 runs an improved version.
1994: Peter Shor showed that a quantum computer could find the prime factors of a large number (for 15, they are 3 and 5) far faster than any known ordinary method. Much of the encryption on the internet relies on problems like this being hard, so the idea suddenly mattered far beyond physics.
1996: Lov Grover found a quantum way to search an unsorted list: under a thousand steps for a million entries, where checking them one by one takes half a million on average.

Check yourself

Someone argues: “Ordinary computers can’t simulate a 300-qubit machine, so a 300-qubit machine will beat them at every task.” What is missing from this argument?

AOnly qubits: 300 are too few, but 3,000 would beat them at every task
BAn algorithm for each task, making interference produce the answer; for many tasks none is known
CNothing: a machine that is hard to simulate is faster at everything
DOnly a way to read out all the amplitudes at the end

Hints

A measurement of 300 qubits gives one string of 300 zeros and ones. What decides whether that string is the answer to your task?
Recall Lesson A: for the answer to come out, the amplitudes of wrong answers have to cancel. What arranges that?

Show the answer

Answer: B. An algorithm for each task, making interference produce the answer; for many tasks none is known

Being hard to simulate shows the machine does something ordinary computers can’t copy, not that it does something useful. Usefulness needs an algorithm that turns interference into an answer, and those are known only for some problems.

Why not the others

A. More qubits make the machine harder to simulate, not useful for more tasks. Without an algorithm for a task, a bigger machine still gives a random outcome.
C. A machine running random steps is hard to simulate but answers nothing. Doing a task faster needs an algorithm for that task, and Lesson C shows these are known only for some problems.
D. No such way exists: measuring 300 qubits gives 300 bits, as Lesson A’s rule says. That is why an algorithm has to make the right answer likely before the measurement.

An example from 2019

In October 2019 Google reported that its chip, with 53 working qubits, had run a sampling task in about 200 seconds, and estimated that a top supercomputer would need about 10,000 years for it. By 2022 a team in China had done the task in about 15 hours on 512 graphics processors, with a method that exploits the structure of that kind of circuit. Lesson D looks at how to read such claims.

6 / 7 · Mastery check

Mastery check

Check yourself

An exact description of 40 qubits lists about a trillion amplitudes. About how many does it list for 41 qubits?

AAbout 2 trillion
BStill about a trillion: one qubit more out of 40 hardly matters
CA trillion and 2: two more for the new qubit
DAbout a trillion trillion: the list is multiplied by itself

Show the answer

Answer: A. About 2 trillion

The 41st qubit splits each of the trillion outcomes in two, one ending in 0 and one ending in 1, so the list doubles to about 2 trillion.

Why not the others

B. If the list grew in step with the number of qubits, one more out of 40 would add only a fortieth. It grows by doubling instead: the new qubit splits every outcome in two.
C. Two per qubit would be enough if each qubit could be described on its own. In general there is one amplitude for each joint outcome, and the new qubit splits every outcome in two, so the list doubles.
D. Multiplying the list by itself is what 40 more qubits would do: 40 more doublings. One more qubit doubles it once.

Check yourself

An old supercomputer could just hold the exact description of 45 qubits. Its replacement has 1,024 times as much memory, about a thousand times. About how many qubits can the new one describe exactly?

AAbout 45,000
BAbout 55
CAbout 46: memory makes almost no difference
DAbout 90

Show the answer

Answer: B. About 55

$1{,}024 = 2^{10}$ : ten doublings of memory, and each doubling holds one more qubit. 45 + 10 = 55.

Why not the others

A. That grows the qubits in step with the memory. Each extra qubit doubles the memory needed, so 1,024 times the memory, ten doublings, buys only 10 more qubits.
C. Memory does help, just slowly: each doubling of memory holds one more qubit, and 1,024 is ten doublings, so 55.
D. Going from 45 to 90 qubits would mean doubling the memory 45 times, vastly more than 1,024 times as much. 1,024 is ten doublings, so ten more qubits: 55.

Check yourself

Why did Feynman expect a computer built from quantum parts to simulate nature better than an ordinary computer?

AQuantum parts switch faster, so they get through the list sooner
BQuantum parts have amplitudes themselves, so the huge list never has to be stored
CQuantum events are random, and ordinary computers can’t produce random numbers
DA quantum computer can show you every amplitude of the system it imitates

Show the answer

Answer: B. Quantum parts have amplitudes themselves, so the huge list never has to be stored

The list of amplitudes doubles with every qubit, so ordinary computers run out of memory at around 50 qubits. A machine made of quantum parts has amplitudes itself and never needs to store them.

Why not the others

A. Speed isn’t the issue: for a few hundred particles the list is too long to store at all. A machine made of quantum parts avoids storing it.
C. Ordinary computers produce random-looking numbers easily, and computing chances isn’t hard once you have the amplitudes. The obstacle is the length of the list of amplitudes, which at least doubles with each particle.
D. A measurement gives one outcome, never the list of amplitudes. The gain is in what the machine doesn’t have to store.

Check yourself

A lab announces a quantum chip whose behavior no supercomputer can currently simulate. What does that show, on its own?

AThat it can solve any problem faster than a supercomputer
BThat no ordinary computer will ever be able to simulate it
CThat the chip does something hard to copy, not yet that it can solve a useful problem faster
DThat it can now break the encryption that protects internet traffic

Show the answer

Answer: C. That the chip does something hard to copy, not yet that it can solve a useful problem faster

Being hard to simulate shows the chip does something ordinary computers can’t easily copy. Usefulness needs an algorithm that makes interference produce an answer someone cares about, and classical methods sometimes catch up anyway.

Why not the others

A. Hard to simulate isn’t the same as useful. Solving a problem faster needs an algorithm for that problem, and those are known only for some problems.
B. Not necessarily. The doubling is the cost of the general method, and clever classical methods have caught up with such claims before, as with a 53-qubit chip in 2019.
D. Breaking that encryption needs Shor’s algorithm, running on a far larger and more reliable machine than any built so far. Being hard to simulate shows nothing of the kind.

7 / 7 · Recap

Recap

Key ideas

An exact description of qubits needs one amplitude for every joint outcome. Each added qubit doubles the list: 2 for one qubit, 4 for two, 8 for three, about a thousand for ten.
At 16 bytes per amplitude, a laptop runs out at about 30 qubits and the biggest supercomputers at about 50. Ten more qubits need about a thousand times the memory. A list for 300 qubits would outnumber the atoms in the observable universe.
Feynman’s idea (talk 1981, paper 1982): to simulate nature, build the computer from quantum parts, which have amplitudes themselves.
Hard to simulate isn’t the same as useful. A measurement gives one outcome, so a quantum computer needs an algorithm that makes interference produce the answer. Deutsch, Shor and Grover found the first ones between 1985 and 1996.
The doubling is the cost of the general, exact description. Many particular quantum processes have classical shortcuts.

Go further

Free resources for when you want more than this lesson covers.

Tomorrow’s computer, yesterdaySimson Garfinkel, MIT Technology Review · Article
The story of the 1981 meeting near Boston where Feynman asked whether computers could simulate nature.
New record on JUPITER: simulating a 50-qubit quantum computerForschungszentrum Jülich · Article
How a supercomputer simulated a full 50-qubit quantum computer in 2025, and why each extra qubit doubles the cost.
Quantum computing 40 years laterJohn Preskill · Article
A leading physicist looks back at Feynman’s proposal and at how far the field has come; the later sections get technical.

Start the interactive lesson