A quantum computer is not a faster everything
A quantum algorithm is a program that uses interference to make a right answer likely. It speeds up a few kinds of problem a lot, some a little, and most everyday jobs not at all.
It matters because the headlines say more than the facts. In this lesson you run one amplification step on four items, then you sort problems into those that gain and those that do not.
By the end of this lesson
Note
I can say what quantum algorithms speed up and what they do not.
Key words
| Word | What it means | Example |
|---|---|---|
| Algorithm | a set of steps that solves a problem | |
| Amplification | steering amplitude toward a marked answer | |
| Speed-up | needing fewer steps than the best ordinary method | |
| Marked item | the answer you are searching for | |
| Noise | small errors that spoil a real qubit's state | |
| Factoring | finding the primes that multiply to a number | 15 = 3 x 5 |
The cells students fill in are left blank in this preview.
Amplification steers the chances toward one item
Take four items, numbered 00, 01, 10 and 11, and mark one of them, say 11. Start with every amplitude equal, 0.5, so every chance is 0.25.
Step one: flip the sign of the marked amplitude. No chance changes. Step two: reflect every amplitude about the average, which means new = 2 x average - old. The marked one grows and the others shrink.
Worked example: one step on four items
| Stage | Amplitudes of 00, 01, 10, 11 | Chance of 11 |
|---|---|---|
| Start, all equal | 0.5, 0.5, 0.5, 0.5 | 0.25 |
| Flip the sign of 11 | 0.5, 0.5, 0.5, -0.5 | 0.25 |
| The average of these four | (0.5 + 0.5 + 0.5 - 0.5) / 4 = 0.25 | not used |
| Reflect: 2 x 0.25 - old | 0, 0, 0, 1 | 1 |
The cells students fill in are left blank in this preview.
Run the amplification script
docker exec jupyter python3 steps/amplify.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Amplified search needs fewer steps
With four items one step is enough. For more items, you repeat the two steps. The number of repeats grows like the square root of the number of items.
An ordinary search through unsorted items checks about half of them on average. So for a million items, an ordinary search needs about 500,000 checks and amplification needs under 800 steps. This is a speed-up, but a modest one.
Worked example: how the steps grow
| Items | Ordinary checks, on average | Amplification steps |
|---|---|---|
| 4 | about 2 | 1 |
| 100 | about 50 | 7 |
| 10,000 | about 5,000 | 78 |
| 1,000,000 | about 500,000 | 785 |
The cells students fill in are left blank in this preview.
Factoring and simulation gain the most
Factoring a very large number can be much faster on a big enough quantum computer. The method uses interference to find a repeating pattern. Some public-key encryption rests on factoring being hard, so this matters.
Simulating molecules is another gain, since a molecule is itself quantum. But a machine of the size needed does not exist yet.
Worked example: who gains from a quantum computer
| Problem | Quantum help | Why |
|---|---|---|
| Searching unsorted items | Modest: square root of the steps | Amplification |
| Factoring a very large number | Large, in theory | Interference finds a repeating pattern |
| Simulating a molecule | Large, in theory | The molecule is itself quantum |
| Sorting a list | No large gain known | Nothing to amplify |
| Showing a web page | None | The work is not about search or patterns |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think a quantum computer tries every answer at once and so does everything faster. A measurement gives one answer. Gain comes only when gates and interference make the right answer likely. For most jobs nobody knows how to do that.
Real qubits are noisy, a simulator is not
A real qubit loses its state to its surroundings. Small errors, called noise, build up with every gate. Fixing them needs error correction, which uses many physical qubits for one useful qubit.
The lab has no noise and is exact. It also stores every amplitude, so each qubit doubles the memory. This is a simulator for learning the rules. It cannot show a speed-up and says nothing about how fast a real machine would be.
How many amplitudes for 30 and 50 qubits
docker exec jupyter python3 -c "print(2 ** 30, 2 ** 50)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.