Foundations: What It Is, and What It Is Not

Why quantum computing (and what it is not)

The one real source of speedup, and the myth to unlearn first

~10 minLesson 1 of 24Written by Claude Fable 5

You have almost certainly heard that a quantum computer "tries every possible answer at the same time." Picture searching for one correct key among eight: the story goes that the machine checks all eight at once and hands you the winner. It is a wonderful image, and it is wrong in the one way that matters. Getting the picture right is the whole reason this course exists.

The myth to unlearn first

Here is the honest version. A quantum computer really can hold all eight answers at once, in what we will call a superposition. But the moment you look - the moment you measure - you get exactly one of them, chosen at random, and everything else vanishes. If holding all the answers were the whole trick, a quantum computer would be an extremely expensive way to return a random guess. Brute-force parallelism is not where the power comes from.^[1] Something has to happen before you measure.

That something is interference, and it is the single idea this entire course is built to explain. Before you play with a formula, play with the mechanism. Below are eight possible answers. First put them in an equal superposition and measure a few times: watch the results scatter at random across all eight. Then run interference and measure again.

Eight possible answers. Measure the equal superposition and watch the tally spread at random. Then run interference and measure again.

Amplitudes: all equal. Height is |amplitude|, so every bar is the same.

|000>

|001>

|010>

|011>

|100>

|101>

|110>

|111>

shots: 0

000

001

010

011

100

101

110

111

Equal superposition: every one of the 8 states has the same amplitude. Measure it and see what you get.

Measuring the equal superposition is a coin flip with eight faces - press it ten times and you get ten unrelated strings. Interference is what changes the game: it rearranges the answers so that the wrong ones cancel each other out and the right one reinforces, piling up until it is nearly the only outcome left. Only then is measuring worth anything. A quantum algorithm is a careful choreography that makes the wrong answers destroy themselves before you ever look.

The one new ingredient: amplitudes

How can answers cancel? In ordinary probability they never can. Roll a die and each face has some chance between 0 and 1; two different ways of landing on a six can only ever add up to make six more likely. There is no such thing as a negative chance. Quantum mechanics keeps almost all of this bookkeeping and changes exactly one rule.^[2]

Instead of attaching a probability to each outcome, it attaches an - a number that, crucially, can be positive or negative. You recover the everyday probability of an outcome by squaring the size of its amplitude:

P (outcome) = ∣ amplitude ∣^{2} The Born rule: an amplitude's size, squared, is the probability of that outcome.

This one change is the whole story. Because amplitudes carry a sign, two paths to the same answer can arrive as $+ \frac{1}{2}$ and $- \frac{1}{2}$ , and when they meet they sum to zero:

(+ \frac{1}{2}) + (- \frac{1}{2}) = 0 ⟹ P = ∣ 0 ∣^{2} = 0

An answer you could reach two separate ways becomes impossible. That is : same signs reinforce, opposite signs cancel. Nothing in classical probability can drive an outcome to zero by adding two ways of reaching it, and that gap is precisely the room a quantum computer works in. We are only stating these rules here; the next lessons build them up properly, from probability with amplitudes to complex numbers as rotation.

So where does the speedup come from?

Not from checking every answer in parallel. It comes from arranging the amplitudes so that the paths leading to wrong answers cancel, leaving the amplitude concentrated on the answer you want. Every quantum algorithm in this course - Deutsch-Jozsa, Grover, Shor - is a different way to orchestrate that cancellation. When you catch yourself thinking "parallel universes," swap in "interference" and you will stay honest.

Lock it in

"Tries every answer at once" is wrong: an equal superposition measured immediately gives one uniformly random answer and nothing more.
The real mechanism is interference - amplitudes for wrong answers cancel and the right answer reinforces, all before you measure.
Amplitudes are like probabilities but signed, so two contributions can add to zero; the probability of an outcome is its amplitude squared.
A quantum algorithm is choreography that makes wrong answers destroy themselves, so that measuring finally reveals something useful.

Check yourself

You place eight answers in an equal superposition and measure immediately, with no other operation. What do you get?

What is the actual source of a quantum computer's advantage?

Recall: why is 'tries all answers simultaneously' wrong, and what is the real mechanism?

The myth and its correction in one breath. Try to state it, then check.

A superposition does hold all answers at once, but measuring it returns a single uniformly random one, so parallel evaluation alone buys nothing. The real mechanism is interference: because amplitudes are signed, an algorithm makes the amplitudes of wrong answers cancel and the right answer reinforce, so that by the time you measure, the useful answer is almost the only outcome with any probability left.

Match each idea to what it does.

drop here

holds many answers, each with its own amplitude

drop here

collapses to one basis state, chosen at random

drop here

cancels wrong answers and reinforces the right one

drop here

gives the probability of that outcome

Primary source

Scott Aaronson - Why Is Quantum Computing So Hard to Explain? (Quanta, 2021)

The clearest short takedown of the parallelism myth, by one of the field's foremost complexity theorists. Read it for the same message in his words: the power is in the interference, not in trying everything at once.

Sources