Lesson 4 of 4

Qubits and search.

About 40 minutes · 9 practice questions

Read the full article: Quantum computing

A qubit as an arrow on a sphere: a gate that makes a superposition, a measurement that gives 0 or 1 by chance, phase that makes interference, and Grover's search, which finds one item in an unsorted store in far fewer steps than an ordinary search.

Step 1 of 9 · A qubit

Step 1 of 9

A qubit

An ordinary bit is 0 or 1. A qubit is a quantum bit, and its state is drawn here as an arrow on a sphere: up is $|0\rangle$ ⁠, down is $|1\rangle$ ⁠, and every other direction is a superposition, a blend of both. The qubit itself is a tiny circuit on the chip under the sphere, a superconductor that works only when it is extremely cold, close to absolute zero.

Gates are a quantum computer’s operations, like AND and NOT among logic gates, and each gate turns the arrow. The X (NOT) gate turns it half a turn, from $|0\rangle$ ⁠ to $|1\rangle$ ⁠, just like NOT. The H gate tips it onto the equator. Measure and search is locked at Qubit now. Predict what the measurements will give.

To the question

Step 2 of 9

Phase

Now the measurements are running: each one flies from the arrow into one of the tubes, 0 or 1, and the ring marks the chance. Gate is at H, then Z. The Z gate turns the arrow half a turn about the upright axis, to the far side of the equator. The arrow’s direction around that axis is called phase.

Try: switch between H and H, then Z and compare the tubes.

Back to the experiment

To the question

Step 3 of 9

Interference

H and Z on their own do not look useful: one gives a random result, and the other changes something a measurement cannot see. The power comes when gates are combined. Gate is locked at H now. Predict what a second H will do.

To the question

Step 4 of 9

Search

Grover’s search finds one marked item among $N$ ⁠ unsorted items. With $n$ ⁠ qubits there are $N = 2^n$ ⁠ items, and at the start an H gate on every qubit gives them all the same chance: a measurement is a blind guess. Each round flips the sign of the answer and then reflects every bar about the average, and the answer’s bar grows. On the sphere, the arrow moves by the same angle each round, from “every wrong answer” at the top pole towards the answer at the bottom pole.

The start is very close to “every wrong answer”, and the angle each round adds is small, in proportion to $\dfrac{1}{\sqrt{N}}$ ⁠. So it takes about $\dfrac{\pi}{4}\sqrt{N}$ ⁠ rounds to reach the answer. The Search size and Search rounds are locked now.

To the question

Step 5 of 9

Too many rounds

16 items and 3 rounds: the answer’s bar is tall, and the arrow is nearly at the bottom pole. Search rounds is locked. Predict what will happen if you keep turning.

To the question

Step 6 of 9

A million items

An ordinary search of an unsorted store checks item after item, and on average needs $\dfrac{N + 1}{2}$ ⁠ looks. Grover’s search needs about $\dfrac{\pi}{4}\sqrt{N}$ ⁠ rounds. When the store is small the difference is small, but it grows with $N$ ⁠: the looks grow like $N$ ⁠, and the rounds only like $\sqrt{N}$ ⁠.

Try: change the Search size and the Search rounds, and find for each size the number of rounds with the highest chance.

Back to the experiment

To the question

Step 7 of 9

A flip

Not every gate makes randomness. Start with the gate an ordinary computer has too.

To the question

Step 8 of 9

How many items

Under Measure and search at Search each item is one combination of noughts and ones.

To the question

Step 9 of 9

The ordinary way

To know how much the quantum search saves, you need to know what an ordinary search costs.

To the question

Interactive scene

Loading the interactive version…

Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.

To the experiment

Practice · Predict, then look

After the H gate the arrow lies on the equator, halfway between $|0\rangle$ ⁠ and $|1\rangle$ ⁠. A qubit like this is prepared again and again and each one is measured. What will each measurement give?

To the experiment

Practice · Choose

Choose H, then Z. The Z gate turns the arrow round the equator to the far side. What is the chance a measurement gives 1 now?

To the experiment

Practice · Predict, then look

One H gate gives half-and-half measurements. What will the chance of 1 be after H, then H?

To the experiment

Practice · Calculate

The Search size is 6 qubits: $2^6 = 64$ ⁠ items, one of which is the answer. How many Search rounds bring the chance of finding it closest to 100%?

To the experiment

Practice · Predict, then look

16 items and 3 rounds: the chance of finding the answer is about 96%. What will happen to the chance if you run 6 rounds?

To the experiment

Practice · Choose

In an unsorted store of a million items, an ordinary search checks item after item, and on average needs about half a million looks. About how many rounds does Grover’s search need?

To the experiment

Practice · Calculate

Gate: X (NOT). The qubit started at $|0\rangle$ ⁠, and the gate flipped it. What is the chance a measurement gives $0$ ⁠?

To the experiment

Practice · Calculate

The Search size is locked at 5 qubits. How many items can they search?

To the experiment

Practice · Calculate

The Search size is locked at 6 qubits, $64$ ⁠ items, one of which is the answer. An ordinary search checks item after item, in random order. How many looks does it need on average before it finds the answer, $\dfrac{N + 1}{2}$ ⁠?