The map of the quantum computing field

1 / 11 · Learn

Before you start

This last lesson steps back and maps the field around what you have learned. Summaries come first, and details sit in disclosures you can open.

By the end you should be able to:

sort the main quantum algorithms by family and by kind of speedup;
say what complexity theory has proved about quantum computers, and what is open;
put the field’s milestones in order;
explain why perfectly identifying $\ket0$ versus $\ket+$ would allow cloning, and compute the error with $N$ copies;
state what teleportation and superdense coding trade.

Check yourself

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

A list of $N = 1{,}000{,}000$ unsorted entries contains one marked entry. The only way to learn about an entry is to ask a black box “is entry $x$ the marked one?” A classical computer needs about 500,000 questions on average. Roughly how many does the best quantum algorithm need?

AAbout 1
BAbout 20
CAbout 1,000
DAbout 500,000, the same as classically

Show the answer

Answer: C. About 1,000

Grover’s algorithm needs about $\sqrt N \approx 1{,}000$ queries (more precisely about $\tfrac{\pi}{4}\sqrt N \approx 785$ ), a quadratic gain over the classical 500,000. It has been proved that no quantum algorithm can do much better.

Why not the others

A. A popular picture is that the computer checks all 1,000,000 entries in one go. A query on a superposition does involve every entry, but measuring the result in the 0/1 basis returns one random entry, no better than one classical guess. The best quantum search needs about $\sqrt N \approx 1{,}000$ queries.
B. That would be an exponential speedup: $\log_2 N \approx 20$ queries. Unstructured search has no such speedup: it has been proved that about $\sqrt N \approx 1{,}000$ queries are needed.
D. There is a quantum speedup here, though only a quadratic one: Grover’s algorithm needs about $\sqrt N \approx 1{,}000$ queries instead of about 500,000.

Check yourself

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

Someone gives you a single qubit and promises it is either $\ket0$ or $\ket+$ . Can any measurement tell you which one, with certainty?

AYes: measure it in the 0/1 basis.
BYes: measure it in the ± basis.
CNo, but more copies can make the error as small as you like.
DNo, and no number of copies would help either.

Show the answer

Answer: C. No, but more copies can make the error as small as you like.

$\abs{\braket{0}{+}}^2 = \tfrac12$ : the states are not orthogonal, so every measurement has some outcome that both can produce. More copies help: the error can fall like $(\tfrac12)^N$ .

Why not the others

A. In the 0/1 basis, both states can give the outcome 0: $\ket0$ with probability $1$ and $\ket+$ with probability $\tfrac12$ . Seeing 0 cannot tell you which one you had.
B. In the ± basis, both states can give the outcome +: $\ket0$ with probability $\tfrac12$ and $\ket+$ with probability $1$ . Seeing + cannot tell you which one you had.
D. Copies do help. Measure each copy in the basis of one of the states; the chance that every copy misleads you falls like $(\tfrac12)^N$ , because $\abs{\braket{0}{+}}^2 = \tfrac12$ .

2 / 11 · Learn

Three families of algorithms

The known quantum algorithms fall into three families.

Fourier-transform algorithms. Deutsch–Jozsa is the simplest. The famous ones are Shor’s algorithms for factoring and discrete logarithms, which run in polynomial time where the best classical algorithms known take superpolynomial time.
Quantum search. Grover’s algorithm finds a marked item among $N$ with about $\sqrt N$ queries, where a classical search needs about $N$ . Only a quadratic gain, but it applies very widely.
Quantum simulation. Feynman’s original idea: simulate a quantum system with a quantum computer. For many physical systems this takes exponentially fewer resources than any known classical method.

Check yourself

Match each algorithm to the kind of speedup it gives.

Match each of these…

Shor’s factoring algorithm
Grover’s search
Deutsch–Jozsa
Simulating a quantum system

…with one of these

Exponential, but only against exact classical algorithms
Exponential for many physical systems
Quadratic: about √N instead of about N
Superpolynomial, compared with the best classical algorithm known

Hints

Which speedup disappears once the classical computer may make a small, controlled error? Think back to the randomized method in Lesson 9.
Only one of the four is a square-root gain.
Shor’s comparison is with the best classical algorithm known, because no one has proved factoring is hard classically.

Show the answer

Shor’s factoring algorithm	Superpolynomial, compared with the best classical algorithm known
Grover’s search	Quadratic: about √N instead of about N
Deutsch–Jozsa	Exponential, but only against exact classical algorithms
Simulating a quantum system	Exponential for many physical systems

Shor: superpolynomial over the best classical algorithm known. Grover: quadratic. Deutsch–Jozsa: exponential only against exact classical algorithms. Simulation: exponential for many physical systems.

Check yourself

Deutsch–Jozsa decides constant or balanced with one query, while an exact classical algorithm needs up to $2^{n-1}+1$ queries. Does that make it exponentially faster than every classical method?

ANo. The gap is exponential only against classical algorithms that must never err.
BNo: the quantum algorithm secretly needs $2^n$ queries too, one for each branch of the superposition.
CYes: no classical method of any kind comes close to one query.

Hint

The randomized method from Lesson 9 allows the classical algorithm a small probability of error. How many queries does it then need?

Show the answer

Answer: A. No. The gap is exponential only against classical algorithms that must never err.

The randomized method: query $k$ random inputs and answer “constant” if they all agree. A balanced $f$ fools this with probability at most $2^{1-k}$ , whatever $n$ is. So the exponential separation holds only against exact (zero-error) algorithms.

Why not the others

B. The algorithm calls $U_f$ once; the superposition doesn’t hide extra queries. The speedup over exact classical algorithms is real. What shrinks it is the comparison with randomized classical algorithms, which need only a few queries for a small error.
C. That holds only if the classical computer must never err. Query $k$ random inputs and answer “constant” if they all agree: a balanced $f$ fools this with probability at most $2^{1-k}$ . With $k = 11$ that is under 1 in 1,000, for every $n$ .

3 / 11 · Worked example

Counting steps: FFT versus QFT

One concrete calculation shows what “exponential speedup” means in numbers. The discrete Fourier transform turns $N$ complex numbers $x_j$ into $N$ new ones,

y_k = \frac{1}{\sqrt N}\sum_{j=0}^{N-1} e^{2\pi i jk/N}\, x_j .

With $N = 2^n$ , the classical fast Fourier transform (FFT) needs about $n\,2^n$ steps. The quantum Fourier transform (QFT) acts on $n$ qubits, whose $2^n$ amplitudes play the role of the $x_j$ , and needs only about $n^2$ gates. Both counts drop constant factors: what matters is how they grow with $n$ .

Worked example

From $n = 10$ to $n = 20$

At $n = 10$ the transform acts on $N = 2^{10} = 1{,}024$ numbers.
FFT: about $n\,2^n = 10 \times 1{,}024 = 10{,}240$ steps.
QFT: about $n^2 = 10^2 = 100$ gates, roughly a hundred times fewer.
Your turn
Now $n = 20$ , so $N = 2^{20} = 1{,}048{,}576$ . About how many steps does the FFT need? (An expression such as 7*2^9 is fine.)
Hint
1. The formula is $n\,2^n$ . What are $n$ and $2^n$ here?
Show the answer
Answer: $20971520$
$20 \times 1{,}048{,}576 = 20{,}971{,}520$ , about 21 million steps.
Common slips
- $1048576$ : That is $2^{20}$ , the number of inputs. The FFT needs about $n$ steps per input: $20 \times 2^{20}$ .
- $400$ : That is $n^2$ , the QFT’s gate count. The FFT needs $n\,2^n$ .
- $20480$ : That uses $2^{10}$ from the example. At $n = 20$ , $2^n = 1{,}048{,}576$ .
Your turn
And the QFT at $n = 20$ : about how many gates?
Hint
1. The QFT count grows as $n^2$ . What is $n$ here?
Show the answer
Answer: $400$
$20^2 = 400$ gates against about 21 million FFT steps: a ratio of about 52,000.
Common slips
- $20$ : That is $n$ , the number of qubits. The gate count grows as $n^2$ .
- $40$ : That is $2n$ . The count is $n^2 = 20 \times 20$ .
- $20971520$ : That is the FFT’s count. The QFT needs only about $n^2$ gates.

Here is one more worked example with different numbers.

Another worked example

One more: $n = 16$

At $n = 16$ there are $N = 2^{16} = 65{,}536$ numbers.
FFT: about $16 \times 65{,}536 = 1{,}048{,}576$ steps.
QFT: about $16^2 = 256$ gates.
Ratio: $1{,}048{,}576 / 256 = 4{,}096$ . The FFT count grows like $n\,2^n$ , the QFT count like $n^2$ .

Check yourself

At $n = 32$ , the FFT needs about $n\,2^n$ steps and the QFT about $n^2$ gates. How many times more steps does the FFT need? (An expression such as 3*2^5/7 is fine.)

Hints

Write both counts at this $n$ , then divide.
The ratio simplifies: $n\,2^n / n^2 = 2^n / n$ .
Compute $2^{32} / 32$ .

Show the answer

Answer: $134217728$

$n\,2^n / n^2 = 2^n / n = 2^{32}/32 = 134{,}217{,}728$ .

FFT: $32 \times 2^{32} = 137{,}438{,}953{,}472$ steps. QFT: $32^2 = 1024$ gates. Ratio: $137{,}438{,}953{,}472 / 1024 = 2^{32}/32 = 134{,}217{,}728$ . The gap grows almost like $2^n$ .

Common slips

$4294967296$ : That divides $n\,2^n$ by $n$ only. The QFT count is $n^2$ , so the ratio is $n\,2^n / n^2 = 2^n / n = 134{,}217{,}728$ .
$137438952448$ : That is the difference, not the ratio. Divide instead: $n\,2^n / n^2 = 2^n/n = 134{,}217{,}728$ .
$137438953472$ : That is the FFT count itself. Divide it by the QFT count $n^2 = 1024$ : $2^n/n = 134{,}217{,}728$ .

The exact gate count

The standard QFT circuit uses $n$ Hadamards and $n(n-1)/2$ controlled phase gates, $n(n+1)/2$ gates in all (210 at $n = 20$ ), plus about $n/2$ swaps to reverse the qubit order. The constant differs from “ $n^2$ ”; the growth is the same.

Check yourself

After the QFT, the $2^{20}$ Fourier coefficients sit in the amplitudes of 20 qubits. Can you now read them all out?

AYes: measure each of the 20 qubits once, in the 0/1 basis.
BYes: measure the register over and over until you have them all.
CNo. A measurement returns one 20-bit outcome, at random; the amplitudes themselves stay hidden.

Show the answer

Answer: C. No. A measurement returns one 20-bit outcome, at random; the amplitudes themselves stay hidden.

A measurement in the 0/1 basis gives one outcome with probability $\abs{\text{amplitude}}^2$ (Lesson 1). So the QFT does not simply replace the FFT: its gate count is tiny, but its output cannot be read out directly. It pays off only inside algorithms, like Shor’s, that need one global property of the coefficients rather than all of them.

Why not the others

A. Measuring 20 qubits gives 20 bits: one outcome out of $2^{20}$ , not $2^{20}$ complex numbers. The coefficients only set the probabilities of the outcomes.
B. After the first measurement the state has collapsed, so measuring again in the same basis repeats the same result. Fresh samples would each need a fresh run of the QFT, and a vast number of runs. Even then the counts estimate only the sizes $\abs{y_k}^2$ , never the phases, and the speedup is gone.

4 / 11 · Learn

What is proved, and what is open

Complexity theory sorts problems by the resources needed to solve them. Three classes matter here:

P: solvable by a classical computer in polynomial time;
BQP: solvable by a quantum computer in polynomial time, with a bounded probability of error;
PSPACE: solvable by a classical computer with polynomial memory, however long it takes.

What is proved:

\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}.

What is open: whether BQP is strictly larger than P. Proving that would also prove $\text{P} \neq \text{PSPACE}$ , a famous unsolved problem. Factoring is in BQP (Shor), but it is not known to be hard classically, or to be NP-complete.

Check yourself

Which of these have been proved?

Select all that apply.

ABQP is strictly larger than P
B $\text{BQP} \subseteq \text{PSPACE}$
CQuantum computers can solve NP-complete problems in polynomial time
D $\text{P} \subseteq \text{BQP}$
EFactoring is NP-complete

Hints

If a statement would settle a famous open problem, could it already have been proved?
The proved results follow from simulation in each direction: what can a quantum computer do with a classical algorithm, and what can a classical computer do, slowly, with a quantum one?
Proving “BQP is strictly larger than P” would also prove $\text{P} \neq \text{PSPACE}$ . Nobody has done that, so it is still open.

Show the answer

Answers: B. $\text{BQP} \subseteq \text{PSPACE}$ ; D. $\text{P} \subseteq \text{BQP}$

$\text{P} \subseteq \text{BQP}$ because a quantum computer can run any classical algorithm with reversible gates (Lesson 6). $\text{BQP} \subseteq \text{PSPACE}$ because a classical computer can add up the amplitudes with polynomial memory, given enough time. Everything else on the list is open.

Why not the others

A. Open. Proving it would also prove $\text{P} \neq \text{PSPACE}$ , which no one has managed.
C. Open, and no known quantum algorithm does it. Factoring and discrete logarithms are not known to be NP-complete.
E. Not known, and widely believed false. Factoring is in NP, but no one has shown that every NP problem reduces to it.

Check yourself

What makes a good qubit hard to build?

AQubits need temperatures close to absolute zero, which can’t be reached.
BMeasuring a qubit disturbs it, so the hardware can never be checked.
CIt must be shielded from its surroundings, yet coupled to them so it can be controlled and measured.
DA qubit stores an infinite amount of information, which no device can hold.

Show the answer

Answer: C. It must be shielded from its surroundings, yet coupled to them so it can be controlled and measured.

Isolation protects the superposition; control and measurement require interaction. The two demands pull in opposite directions, and every platform built so far is a compromise between them.

Why not the others

A. Many platforms do run cold, and cooling is a real engineering cost, but it isn’t the core conflict, and not every platform needs it. The deeper problem is isolation against control.
B. Measurement does change the state, but that is part of every quantum algorithm, not a barrier to building one. The tension is between keeping the qubit isolated and being able to act on it.
D. A qubit’s amplitudes are continuous, but measuring it in any basis yields one bit (Lesson 1), and the Holevo bound limits $n$ qubits to $n$ bits of retrievable classical information. The difficulty is physical: isolation against control.

5 / 11 · Learn

Milestones in order

The history of the field can be told as four threads that came together: computer science (what can be computed, and how fast), information theory (how far a message can be compressed and protected), quantum mechanics (controlling single quantum systems), and cryptography. You don’t need to memorize the names and dates. Putting a few milestones in order is a quick way to see how the threads connect, and most of them are landmarks you will meet again if you study further.

Check yourself

Put these milestones in order, earliest first.

Put these in order.

Feynman argues that simulating quantum systems looks hard for classical computers, and suggests computers built on quantum mechanics.
Bennett and Brassard propose a key-distribution protocol whose security rests on quantum mechanics.
Shannon founds information theory: how far a message can be compressed, and how to send it reliably over a noisy channel.
Shor finds efficient quantum algorithms for factoring and discrete logarithms.
Turing describes a universal machine that can run any algorithm.
Bennett and Wiesner show that one qubit, plus a shared entangled pair, can carry two classical bits (superdense coding).
Grover finds a quantum algorithm that searches $N$ unsorted items with about $\sqrt N$ queries.
Moore observes that the number of transistors on a chip doubles at a steady rate.
Deutsch defines a universal quantum computer and asks whether it could beat classical ones.

Hints

Which events don’t involve quantum mechanics at all? They come first.
Feynman’s suggestion came before Deutsch’s universal quantum computer, and Bennett and Brassard’s protocol sits between the two.
Of the last three, superdense coding comes first, and Shor’s algorithm came before Grover’s.

Show the answer

Turing describes a universal machine that can run any algorithm.
Shannon founds information theory: how far a message can be compressed, and how to send it reliably over a noisy channel.
Moore observes that the number of transistors on a chip doubles at a steady rate.
Feynman argues that simulating quantum systems looks hard for classical computers, and suggests computers built on quantum mechanics.
Bennett and Brassard propose a key-distribution protocol whose security rests on quantum mechanics.
Deutsch defines a universal quantum computer and asks whether it could beat classical ones.
Bennett and Wiesner show that one qubit, plus a shared entangled pair, can carry two classical bits (superdense coding).
Shor finds efficient quantum algorithms for factoring and discrete logarithms.
Grover finds a quantum algorithm that searches $N$ unsorted items with about $\sqrt N$ queries.

Turing machine (1936) → Shannon’s information theory (1948) → Moore’s law (1965) → Feynman on quantum simulation (1982) → BB84 key distribution (1984) → Deutsch’s universal quantum computer (1985) → superdense coding (1992) → Shor’s algorithm (1994) → Grover’s search (1996).

The thread that matters most

The strong Church–Turing thesis says any reasonable model of computation can be simulated efficiently by a Turing machine. Randomized algorithms such as the Solovay–Strassen primality test (mid-1970s) forced a revision: efficient now meant efficient with a probabilistic Turing machine. Deutsch (1985) asked whether physics itself could ground a stronger thesis, and defined the universal quantum computer. Shor’s algorithm is evidence, not proof, that quantum computers violate even the revised thesis.

6 / 11 · Learn

Information as a resource

Quantum information theory treats information like a physical quantity with exchange rates. Its basic resources are classical bits, qubits, and shared entanglement (a Bell pair split between two people). Its basic processes are storing, sending and transforming them, and, for qubits, not copying them. The central question is how the resources trade.

You have met one exchange rate already. Teleportation (Lesson 8): 1 Bell pair + 2 classical bits sent → 1 qubit state transferred.

Check yourself

Alice and Bob share one Bell pair. Alice holds a qubit in an unknown state $\ket\psi$ and wants Bob to end up with it. What must travel from Alice to Bob?

AOne classical bit: whether $\ket\psi$ is closer to $\ket0$ or to $\ket1$ .
BThe qubit $\ket\psi$ itself: a quantum state can’t be sent any other way.
CTwo classical bits, her measurement results; Bob then applies the matching correction.
DNothing: Alice’s measurement changes Bob’s half instantly, so he already has $\ket\psi$ .

Show the answer

Answer: C. Two classical bits, her measurement results; Bob then applies the matching correction.

Teleportation: 1 Bell pair + 2 classical bits → 1 qubit. The bits travel no faster than light, and Bob can do nothing useful until they arrive.

Why not the others

A. One bit can’t pick out one of four outcomes. Alice’s measurement has four equally likely results, each needing a different correction, so she must send two bits.
B. Sending the qubit is one option, but teleportation’s point is that it isn’t needed. The Bell pair, used up in the process, plus two classical bits, which can travel over an ordinary phone line, do the job.
D. Alice’s measurement does change the joint state, but on its own Bob’s qubit is completely random, whatever $\ket\psi$ is (Lesson 8). Until the two bits arrive he can’t tell which of four corrections to apply, so no information has reached him.

Superdense coding runs the trade the other way. Alice and Bob share $\ket{\beta_{00}}$ , Alice holding the top qubit. To send two bits $x, y$ , Alice applies $Z^xX^y$ to her qubit alone: $I$ , $X$ , $Z$ or $ZX$ . That turns the pair into $\ket{\beta_{xy}}$ , one of the four Bell states from Lesson 7. She sends Bob her qubit. Holding both, Bob runs the Bell circuit backwards (CNOT, then $H$ on the top qubit), which gives $\ket{xy}$ , and measures in the 0/1 basis.

Superdense coding: 1 Bell pair + 1 qubit sent → 2 classical bits transferred.

Check yourself

Alice and Bob share $\ket{\beta_{00}}$ , Alice holding the top qubit. Using superdense coding, Alice wants to send the bits $x = 0$ , $y = 1$ . Which gate does she apply to her qubit?

A $ZX$
B $I$ (she leaves it alone)
C $Z$
D $X$

Hints

Alice applies $Z^xX^y$ . Substitute $x = 0$ and $y = 1$ .
Any gate to the power 0 is $I$ .

Show the answer

Answer: D. $X$

$Z^0X^1 = X$ . On Alice’s qubit it turns $\ket{\beta_{00}} = (\ket{00}+\ket{11})/\sqrt2$ into $(\ket{10}+\ket{01})/\sqrt2 = \ket{\beta_{01}}$ , and Bob’s reversed Bell circuit turns that into $\ket{01}$ : the bits 0, 1. One qubit carried two bits, and the shared pair was used up.

Why not the others

A. $ZX$ makes $\ket{\beta_{11}}$ , so Bob would read 11. With $x = 0$ the $Z$ is left out.
B. With $I$ the pair stays $\ket{\beta_{00}}$ , and Bob reads 00. To send $y = 1$ the gate must include $X$ .
C. $Z$ turns the pair into $\ket{\beta_{10}}$ , so Bob would read 10: the two bits swapped. In $Z^xX^y$ , the $X$ carries $y$ and the $Z$ carries $x$ .

Classical information has its own exchange rate, found by Shannon in 1948. A source that emits symbols with probabilities $p_1, \dots, p_k$ can be compressed to about $H$ bits per symbol on average, over long messages, and no further, where

H = -\sum_i p_i \log_2 p_i = \sum_i p_i \log_2 \frac{1}{p_i}.

A fair coin has $H = 1$ . A biased source has less, because frequent symbols can get short codewords. Schumacher’s compression theorem is the quantum version, with qubits in place of bits.

Check yourself

A source emits the symbols A, B, C, D with probabilities $\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8}$ . What is its entropy, in bits per symbol?

$H = \;?$

Hints

For each symbol, how many halvings of 1 give its probability? That number is $\log_2(1/p)$ .
Entropy is the probability-weighted average of $\log_2(1/p)$ : $H = \sum_i p_i \log_2(1/p_i)$ .
Compute $\tfrac{1}{2}\cdot 1 + \tfrac{1}{4}\cdot 2 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3$ .

Show the answer

Answer: $H = \frac{7}{4}$

$H = \sum_i p_i \log_2(1/p_i) = \tfrac{1}{2}\cdot 1 + \tfrac{1}{4}\cdot 2 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 = \tfrac{7}{4}$ bits per symbol.

For each symbol, $\log_2(1/p)$ is 1, 2, 3, 3 bits. Weight each by its probability and add: $H = \tfrac{1}{2}\cdot 1 + \tfrac{1}{4}\cdot 2 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 = \tfrac{7}{4}$ . A code that gives each symbol a codeword of exactly that many bits (shortest for the most frequent) averages $\tfrac{7}{4}$ bits per symbol, and Shannon’s theorem says no code can do better on average.

Common slips

$2$ : That is $\log_2 4$ , the entropy if all 4 symbols were equally likely. Unequal probabilities give less: frequent symbols can get shorter codewords.
$-\frac{7}{4}$ : Entropy is never negative. $\log_2 p$ is negative when $p < 1$ , and the minus sign in $H = -\sum_i p_i \log_2 p_i$ makes the total positive.
$\frac{9}{4}$ : That averages $\log_2(1/p)$ over the symbols without weighting them. Each symbol counts in proportion to how often it occurs: $H = \sum_i p_i \log_2(1/p_i)$ .
$9$ : That adds $\log_2(1/p)$ for every symbol without weighting by probability. Weight each term: $H = \sum_i p_i \log_2(1/p_i)$ .

A code that achieves it

Use the codewords A → 0, B → 10, C → 110, D → 111. No codeword is the start of another, so a stream of them can be decoded without separators. The average length is $\tfrac12\cdot1 + \tfrac14\cdot2 + \tfrac18\cdot3 + \tfrac18\cdot3 = 1.75$ bits per symbol, exactly the entropy. No code can do better on average.

7 / 11 · Explore

Telling |0⟩ from |+⟩

Predict, then see

A cloning machine (pretend one exists, although Lesson 7 showed that none can) has turned one unknown qubit into 10 copies. The qubit was either $\ket0$ or $\ket+$ . You measure all ten copies in the 0/1 basis, and every result is 0. What can you conclude?

ANothing: each $\ket+$ copy is a coin flip, so either state could easily give this.
BIt was $\ket0$ , for certain.
CAlmost certainly $\ket0$ , but $\ket+$ is still possible.

Why does a single 1 settle the question, while a run of 0s only makes $\ket0$ likely? A sentence or two is enough.

Show what happens

What happens: C. Almost certainly $\ket0$ , but $\ket+$ is still possible.

A single 1 settles it: $\ket0$ never gives 1 in this basis, so you had $\ket+$ . A run of 0s only makes $\ket0$ likely, because each $\ket+$ copy also gives 0 with probability ½, independently of the others. So the rule “answer $\ket0$ only if every result is 0” never errs on $\ket0$ , and errs on $\ket+$ only when every copy comes up 0. More copies make that rarer, but no finite number makes it impossible.

Why not the others

A. Each $\ket+$ copy is a fair coin, but ten 0s in a row from fair coins is rare. Meanwhile $\ket0$ gives this result every time, so the evidence strongly favours $\ket0$ .
B. Ten 0s are exactly what $\ket0$ gives, but $\ket+$ can give them too: each copy shows 0 with probability ½. That run is rare, not impossible.

Check yourself

Put a number on it. With the rule “answer $\ket0$ only if all ten results are 0”, what is the probability that you answer wrongly when the qubit was $\ket+$ ? Give an exact fraction.

$P(\text{error} \mid +) = \;?$

Hints

For one copy of $\ket+$ , what is the probability of the outcome 0?
The ten copies are independent, so the probability that all ten give 0 is a product.
Compute $(\tfrac12)^{10}$ .

Show the answer

Answer: $P(\text{error} \mid +) = 0.001$

Each copy of $\ket+$ gives 0 with probability $\abs{\braket{0}{+}}^2 = \tfrac12$ , independently, so all ten do with probability $(\tfrac12)^{10} = \tfrac{1}{1024} \approx 0.001$ . On $\ket0$ the rule never errs.

Common slips

$\frac{1}{32}$ : That multiplies the amplitude $1/\sqrt2$ ten times. The chance that one copy gives 0 is the squared magnitude, $\abs{\braket{0}{+}}^2 = \tfrac12$ , so ten copies give $(\tfrac12)^{10}$ .
$\frac{1}{2}$ : That is the chance for one copy. All ten copies must give 0, and independent probabilities multiply: $(\tfrac12)^{10}$ .
$\frac{1}{20}$ : That divides $\tfrac12$ by 10. For ten independent copies the probabilities multiply: $\tfrac12 \times \tfrac12 \times \dots$ , ten times.
$0$ : That is the overall error rate if $\ket0$ and $\ket+$ are equally likely, $\tfrac12 \times \tfrac{1}{1024}$ . The question asks for the error given that the qubit was $\ket+$ .
$0.999$ : That is the chance that at least one copy gives 1, which is when the rule gets $\ket+$ right. The error is the opposite event: all ten results are 0.

Check yourself

Now run it the other way. Suppose a device could look at one copy and say, without error, whether it is $\ket0$ or $\ket+$ . What could you build with it?

ANothing new: knowing which state you have doesn’t let you copy it.
BA cloner for these two states: identify the state, then prepare as many fresh copies of it as you like.
CA way to read out the amplitudes $\alpha$ and $\beta$ of any qubit.

Show the answer

Answer: B. A cloner for these two states: identify the state, then prepare as many fresh copies of it as you like.

Identify, then prepare: that is cloning, which the no-cloning theorem of Lesson 7 forbids for non-orthogonal states like these. So no such device can exist. Shortly you will argue both directions in your own words.

Why not the others

A. Once you know the state, copying is easy, because you can prepare it from scratch: $\ket0$ needs no gates and $\ket+ = H\ket0$ . What no-cloning forbids is copying a state you don’t know, and the device would remove exactly that uncertainty.
C. The device only chooses between the two candidates named in advance; it says nothing about other states. Its real consequence is copying: identify, then prepare.

8 / 11 · Practice

Practice

Check yourself

A source emits the symbols A, B, C, D, E, F, G, H with probabilities $\tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}, \tfrac{1}{8}$ . What is its entropy, in bits per symbol?

$H = \;?$

Hints

For each symbol, how many halvings of 1 give its probability? That number is $\log_2(1/p)$ .
Entropy is the probability-weighted average of $\log_2(1/p)$ : $H = \sum_i p_i \log_2(1/p_i)$ .
Compute $\tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3$ .

Show the answer

Answer: $H = 3$

$H = \sum_i p_i \log_2(1/p_i) = \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 = 3$ bits per symbol.

For each symbol, $\log_2(1/p)$ is 3, 3, 3, 3, 3, 3, 3, 3 bits. Weight each by its probability and add: $H = \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 + \tfrac{1}{8}\cdot 3 = 3$ . A code that gives each symbol a codeword of exactly that many bits (shortest for the most frequent) averages $3$ bits per symbol, and Shannon’s theorem says no code can do better on average.

Common slips

$-3$ : Entropy is never negative. $\log_2 p$ is negative when $p < 1$ , and the minus sign in $H = -\sum_i p_i \log_2 p_i$ makes the total positive.
$24$ : That adds $\log_2(1/p)$ for every symbol without weighting by probability. Weight each term: $H = \sum_i p_i \log_2(1/p_i)$ .

Check yourself

A box holds one qubit, either $\ket0$ or $\ket\psi = \tfrac12\ket0 + \tfrac{\sqrt3}{2}\ket1$ . A cloner (pretend one exists) gives you $N = 3$ copies. You measure each copy in the 0/1 basis and answer “ $\ket0$ ” only if every result is 0. If the box held $\ket\psi$ , what is the probability that you answer wrongly? Give an exact fraction.

$P(\text{error} \mid \psi) = \;?$

Hints

What is the chance that one copy of $\ket\psi$ gives 0 in the 0/1 basis?
It is $\abs{\braket{0}{\psi}}^2$ , and the copies are independent, so the error is that probability raised to the power $N$ .
Square the $\ket0$ amplitude, then raise it to the power $N$ .

Show the answer

Answer: $P(\text{error} \mid \psi) = \frac{1}{64}$

Each copy of $\ket\psi$ gives 0 with probability $\abs{\braket{0}{\psi}}^2 = \tfrac{1}{4}$ , independently, so all 3 give 0 with probability $(\tfrac{1}{4})^{3} = \tfrac{1}{64}$ .

The rule can only go wrong when the box held $\ket\psi$ and every copy gave 0 (a $\ket0$ input always gives 0, so it is never misjudged). One copy of $\ket\psi$ gives 0 with probability $\abs{\braket{0}{\psi}}^2 = \abs{\tfrac12}^2 = \tfrac{1}{4}$ . The 3 copies are measured independently, so the probabilities multiply: $(\tfrac{1}{4})^{3} = \tfrac{1}{64} \approx 0.0156$ . In general the error is $\abs{\braket{0}{\psi}}^{2N}$ , which goes to 0 as $N$ grows.

Common slips

$\frac{1}{8}$ : That multiplies the amplitude $\tfrac12$ instead of the probability. The chance that one copy gives 0 is $\abs{\braket{0}{\psi}}^2 = \tfrac{1}{4}$ , so all 3 give 0 with probability $(\tfrac{1}{4})^{3}$ .
$\frac{1}{4}$ : That is the chance for one copy. All 3 copies must give 0, and independent probabilities multiply: $(\tfrac{1}{4})^{3}$ .
$\frac{63}{64}$ : That is the chance that at least one copy gives 1, which is when the rule gets $\ket\psi$ right. The error is the opposite event: all 3 results are 0.
$0.008$ : That is the overall error rate if the box is equally likely to hold either state, $\tfrac12 \times \tfrac{1}{64}$ . The question asks for the error given that the box held $\ket\psi$ .

Check yourself

Match each task to the family it belongs to.

Match each of these…

Factoring a large number
Deciding whether $f$ is constant or balanced
Finding a marked item in an unsorted list
Predicting the dynamics of a molecule

…with one of these

Quantum error correction
Quantum search
Quantum simulation
Fourier-transform family

Hints

Two tasks belong to the same family.
Deutsch–Jozsa’s $H^{\otimes n}$ is the Fourier transform over $n$ ⁠-bit strings.
Error correction protects any algorithm; it is not itself one of the three families.

Show the answer

Factoring a large number	Fourier-transform family
Deciding whether $f$ is constant or balanced	Fourier-transform family
Finding a marked item in an unsorted list	Quantum search
Predicting the dynamics of a molecule	Quantum simulation

Factoring (Shor) and Deutsch–Jozsa are both Fourier-family algorithms: $H^{\otimes n}$ is the Fourier transform over $n$ ⁠-bit strings. Search is Grover’s, and molecular dynamics is quantum simulation. Error correction protects all of them.

9 / 11 · Explain

Identifying and cloning, in your own words

Explain it

Why would a device that perfectly identifies which of two non-orthogonal states it was given let you clone them? And why would a cloner let you tell them apart?

Show a model answer

Given a perfect identifier, identify the state, then prepare as many fresh copies of it as you like: that is cloning. Conversely, given a cloner, make $N$ copies and measure each in a basis that contains one of the two states, say $\ket\psi$ , and answer “ $\ket\psi$ ” only if every copy gives the outcome $\psi$ . A $\ket\psi$ input always does. A $\ket\varphi$ input fools you with probability $\abs{\braket{\psi}{\varphi}}^{2N}$ , which goes to 0 as $N$ grows. Since the no-cloning theorem rules out a cloner for non-orthogonal states, perfect identification is impossible too.

A good answer covers

Identifier → cloner: identify the state, then prepare fresh copies of it.
Cloner → identifier: make many copies and use the statistics of measurements on them.
The error falls as the number of copies grows (for example $\abs{\braket{\psi}{\varphi}}^{2N}$ , or $(\tfrac12)^N$ for $\ket0$ versus $\ket+$ ).
Links the argument to no-cloning: since cloning is impossible, so is perfect identification.

10 / 11 · Mastery check

Mastery check

Check yourself

A list of $N = 10^{12}$ unsorted entries contains one marked entry. The only way to learn about an entry is to ask a black box “is entry $x$ the marked one?” A classical computer needs about 500,000,000,000 questions on average. Roughly how many does the best quantum algorithm need?

AAbout 1
BAbout 40
CAbout 1,000,000
DAbout 500,000,000,000, the same as classically

Show the answer

Answer: C. About 1,000,000

Grover’s algorithm needs about $\sqrt N \approx 1{,}000{,}000$ queries (more precisely about $\tfrac{\pi}{4}\sqrt N \approx 785{,}398$ ), a quadratic gain over the classical 500,000,000,000. It has been proved that no quantum algorithm can do much better.

Why not the others

A. A popular picture is that the computer checks all 1,000,000,000,000 entries in one go. A query on a superposition does involve every entry, but measuring the result in the 0/1 basis returns one random entry, no better than one classical guess. The best quantum search needs about $\sqrt N \approx 1{,}000{,}000$ queries.
B. That would be an exponential speedup: $\log_2 N \approx 40$ queries. Unstructured search has no such speedup: it has been proved that about $\sqrt N \approx 1{,}000{,}000$ queries are needed.
D. There is a quantum speedup here, though only a quadratic one: Grover’s algorithm needs about $\sqrt N \approx 1{,}000{,}000$ queries instead of about 500,000,000,000.

Check yourself

Someone gives you a single qubit and promises it is either $\ket+$ or $\ket-$ . Can any measurement tell you which one, with certainty?

AYes: measure it in the 0/1 basis.
BYes: measure it in the ± basis.
CNo, but more copies can make the error as small as you like.
DNo, and no number of copies would help either.

Show the answer

Answer: B. Yes: measure it in the ± basis.

$\ket+$ and $\ket-$ are orthogonal, so measuring in the ± basis gives a different outcome for each, every time.

Why not the others

A. In the 0/1 basis, $\ket+$ and $\ket-$ each give both outcomes with probability $\tfrac12$ , so one result tells you nothing. They are orthogonal, though: in the ± basis they give different outcomes every time.
C. These two are orthogonal, $\braket{+}{-} = 0$ , so the ± basis separates them: each gives its own outcome every time. One copy settles it.
D. For these two, one copy is already enough: they are orthogonal, so the ± basis separates them with certainty.

Check yourself

A box holds one qubit, either $\ket0$ or $\ket\psi = \ket+$ . A cloner (pretend one exists) gives you $N = 3$ copies. You measure each copy in the 0/1 basis and answer “ $\ket0$ ” only if every result is 0. If the box held $\ket\psi$ , what is the probability that you answer wrongly? Give an exact fraction.

$P(\text{error} \mid \psi) = \;?$

Show the answer

Answer: $P(\text{error} \mid \psi) = \frac{1}{8}$

Each copy of $\ket\psi$ gives 0 with probability $\abs{\braket{0}{\psi}}^2 = \tfrac{1}{2}$ , independently, so all 3 give 0 with probability $(\tfrac{1}{2})^{3} = \tfrac{1}{8}$ .

The rule can only go wrong when the box held $\ket\psi$ and every copy gave 0 (a $\ket0$ input always gives 0, so it is never misjudged). One copy of $\ket\psi$ gives 0 with probability $\abs{\braket{0}{\psi}}^2 = \abs{\tfrac{1}{\sqrt2}}^2 = \tfrac{1}{2}$ . The 3 copies are measured independently, so the probabilities multiply: $(\tfrac{1}{2})^{3} = \tfrac{1}{8} \approx 0.125$ . In general the error is $\abs{\braket{0}{\psi}}^{2N}$ , which goes to 0 as $N$ grows.

Common slips

$\frac{\sqrt{2}}{4}$ : That multiplies the amplitude $\tfrac{1}{\sqrt2}$ instead of the probability. The chance that one copy gives 0 is $\abs{\braket{0}{\psi}}^2 = \tfrac{1}{2}$ , so all 3 give 0 with probability $(\tfrac{1}{2})^{3}$ .
$\frac{1}{2}$ : That is the chance for one copy. All 3 copies must give 0, and independent probabilities multiply: $(\tfrac{1}{2})^{3}$ .
$\frac{7}{8}$ : That is the chance that at least one copy gives 1, which is when the rule gets $\ket\psi$ right. The error is the opposite event: all 3 results are 0.
$\frac{1}{16}$ : That is the overall error rate if the box is equally likely to hold either state, $\tfrac12 \times \tfrac{1}{8}$ . The question asks for the error given that the box held $\ket\psi$ .

Check yourself

Alice and Bob share 3 Bell pairs. Using superdense coding, Alice sends Bob her 3 halves. How many classical bits can Bob learn from them?

Show the answer

Answer: $6$

Superdense coding: 1 Bell pair + 1 qubit sent gives 2 classical bits, so 3 qubits give 6 bits.

For each pair, Alice applies one of $I$ , $X$ , $Z$ or $ZX$ to her half, which turns the pair into one of the four Bell states, and sends that qubit. Bob, now holding both qubits, runs the Bell circuit backwards (CNOT, then $H$ on the top qubit) and measures in the 0/1 basis: 2 bits per pair. For 3 pairs: 6 bits.

Common slips

$3$ : Without shared entanglement, 3 qubits can deliver at most 3 classical bits (the Holevo bound). The shared pairs are what double it: superdense coding gets 2 bits per qubit sent.
$12$ : The rate is 2 bits per qubit sent, and each of those qubits uses up one Bell pair. The pairs are not a separate channel: 6 bits in total.

Check yourself

Which of these statements has been proved?

ABQP is strictly larger than P: some problem is easy for quantum computers but hard for classical ones.
B $\text{BQP} \subseteq \text{PSPACE}$ : whatever a quantum computer does efficiently, a classical computer can do with polynomial memory.
CFactoring is NP-complete.
DQuantum computers can solve NP-complete problems in polynomial time.

Show the answer

Answer: B. $\text{BQP} \subseteq \text{PSPACE}$ : whatever a quantum computer does efficiently, a classical computer can do with polynomial memory.

What is proved: $\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}$ , and factoring is in BQP (Shor). Whether BQP is strictly larger than P, and whether quantum computers can solve NP-complete problems efficiently, are open.

Why not the others

A. Open. Proving it would also prove $\text{P} \neq \text{PSPACE}$ , a famous unsolved problem. Shor’s algorithm is strong evidence, not proof, because no one has proved that factoring is classically hard.
C. Not known, and widely believed false. Factoring is in NP, but no one has shown that every NP problem reduces to it.
D. Open, and no known quantum algorithm does it. The problems Shor solved, factoring and discrete logarithms, are not known to be NP-complete.

11 / 11 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

Name the three families of quantum algorithms, an example of each, and the kind of speedup it gives.
Show the key points
- Fourier transform: Shor (superpolynomial over the best classical algorithm known); Deutsch–Jozsa is the simplest member
- Search: Grover, about $\sqrt N$ queries instead of about $N$ (quadratic)
- Simulation: exponential savings for many physical systems
- Deutsch–Jozsa’s exponential gap holds only against exact classical algorithms
Why can’t one copy tell $\ket0$ from $\ket+$ with certainty, and what do $N$ copies buy you?
Show the key points
- The states are not orthogonal: $\abs{\braket{0}{+}}^2 = \tfrac12$
- With $N$ copies and the all-zeros rule, the error given $\ket+$ is $(\tfrac12)^N$ , e.g. $1/1024$ for 10 copies
- A perfect identifier would allow cloning (identify, then prepare), so no-cloning forbids it
What do teleportation and superdense coding trade, and what is proved about BQP?
Show the key points
- Teleportation: 1 Bell pair + 2 bits → 1 qubit; superdense coding: 1 Bell pair + 1 qubit → 2 bits
- Nothing travels faster than light: the classical bits are needed
- $\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}$ is proved; whether BQP is larger than P is open

Key ideas

Three families: Fourier transform (Shor, superpolynomial), search (Grover, quadratic), simulation (exponential for many systems). Deutsch–Jozsa’s exponential gap is only against exact algorithms.
A quantum computer’s amplitudes can’t be read out: the QFT needs about $n^2$ gates against the FFT’s $n\,2^n$ steps, but only one outcome comes out per run.
$\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}$ is proved. Whether quantum computers are strictly more powerful is open.
Information is a resource with exchange rates: 1 Bell pair + 2 bits → 1 qubit (teleportation), 1 Bell pair + 1 qubit → 2 bits (superdense coding). A source needs about $H$ bits per symbol.
Non-orthogonal states can’t be told apart with certainty; $N$ copies push the error down geometrically, and perfect identification would mean cloning.

Go further

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

But what is quantum computing? (Grover’s algorithm)3Blue1Brown · Video
Animates how Grover’s search turns amplitude toward the answer, and why it needs about √N steps rather than N.
Fundamentals of quantum algorithmsJohn Watrous, IBM Quantum · Course
Free lessons on phase estimation, Shor’s factoring algorithm and Grover’s search, which this lesson can only name.
Finally, a problem that only quantum computers will ever be able to solveKevin Hartnett, Quanta Magazine · Article
Explains a 2018 black-box result giving strong evidence that quantum computers can do what no classical computer can.
Discriminating two qubitsRyan O’Donnell, Carnegie Mellon · Video
An 18-minute lecture on the best single measurement for telling two known states apart, and the error it must accept.

Before you start

Three families of algorithms

Counting steps: FFT versus QFT

From n=10n = 10n=10 to n=20n = 20n=20

One more: n=16n = 16n=16

What is proved, and what is open

Milestones in order

Information as a resource

Telling |0⟩ from |+⟩

Practice

Identifying and cloning, in your own words

Mastery check

Recap

Key ideas

Go further

From $n = 10$ to $n = 20$

One more: $n = 16$