A Quantum Computer Will Solve Everything — How Much of That Is True?

Trying every path at once

The commonest explanation of a quantum computer runs like this: an ordinary computer tries one path at a time, a quantum computer tries every path at once. The maze analogy, the satnav analogy — they are all this.

An obvious objection follows. Isn't that what a graphics card does? Instead of placing dots one by one it sprays thousands of nozzles at once. Thousands of workers working together. So is a quantum computer just a computer with more workers?

No. And because the analogy leaves out the difference, any explanation that starts from it never quite fits together. The difference is three sentences. What it holds doubles each time; what it reads is only one; so the wrong answers are erased before the reading.

What it holds doubles each time

Ten coins laid heads or tails can be arranged in 1,024 ways. For an ordinary computer to look at all 1,024, it must compute 1,024 times. A graphics card does it in one go with 1,024 nozzles. Either way, something numbering 1,024 is needed.

A qubit is different. A qubit is a coin that has not yet settled heads or tails. Because it has not settled, it holds both. Lay ten such coins and, still unsettled, they hold all 1,024 possibilities at once. Add one more: 2,048. It doubles.

What it reads is only one

But here is the catch. It holds 1,024, yes — but you cannot read all 1,024. The moment the lid comes off, each of the ten coins settles heads or tails, and only one of the 1,024 is visible. Which one is a matter of chance.

So holding and then simply looking is a lottery: a one-in-1,024 chance of the right answer. Useless. Every path was tried at once, and what arrived cannot be read. This is where the analogy breaks.

So the wrong answers are erased first

The real trick of a quantum computer is not holding but erasing. To understand it, a pair of noise-cancelling headphones is enough.

Those headphones listen to the outside noise through a microphone, make a sound that is its exact opposite, and put it in your ear. The two sounds meet and cancel. Sound can be cancelled because it is a wave: a crest meeting a trough disappears.

The 1,024 possibilities inside the qubits are each a wave too, so they can cancel one another (interference). A quantum computation is the arranging of steps so that the waves of the 1,023 wrong answers meet in opposition and vanish, while the wave of the right answer piles up. The wrong answers are made to noise-cancel themselves.

Then the lid comes off. The ten coins settle, and those ten digits are very likely the answer. Not certainly — so it is run a few times to check.

So only erasable problems get solved

This is the most important sentence in the piece. A quantum computer does not speed up just any calculation. The problem must be one where the steps can be arranged so that the wrong answers cancel. Only a handful of problems have such steps known: splitting a large number into primes, imitating how molecules move, finding one item in an unsorted list. And the first of those is the basis of today's internet encryption.

It is because this sentence was missing that quantum computing seemed so hard. With the picture of a universal calculator in your head, no explanation of qubits could ever fit.

A little further in

So what is real and what is inflated?

Back to the opening claims, one line at a time.

This is why the satnav analogy is especially bad. Route-finding is not on the list of erasable problems. The favourite example of what a quantum computer does well is something it does not do at all.

Where the idea of computing with waves came from

That a qubit is a wave is not a metaphor. In 1924 de Broglie proposed that every particle is also a wave, and Schrödinger wrote down how such waves move. A quantum computer is that equation turned into a machine a century later.

The first to say build it was Feynman, in 1982: nature runs on quantum rules, so to imitate nature a computer must be quantum too. Nobody then knew how. The steps came in 1994; a few working qubits, in the 2000s.

Why is it frozen?

Photographs of quantum computers show a gold chandelier. That is not the computer; it is the refrigerator. The computer is a chip the size of a fingernail at the very bottom, and everything else cools it to near absolute zero.

It is frozen because the slightest disturbance to the waves stops the cancelling from working. Heat or vibration from outside jumbles them. The cold is not for the calculation; it is to protect the waves — to cut the chip off from the world.

Reaching near 269 below is the same technology as the superconducting magnets of a fusion machine. KSTAR's magnets, a quantum chip and a hospital MRI all live at the same temperature. One temperature, superconductivity, holds up three different technologies. That gets its own piece in this series.

What you would study to do this

In Korea the Korea Research Institute of Standards and Science in Daejeon is building one, superconducting. The paths inside split like this.

1. Someone who arranges the steps so the wrong answers cancel — mathematics and computer science. Each new set of steps is a paper and a headline.
2. Someone who catches and corrects jumbled qubits — the field called error correction, and the biggest wall right now.
3. Someone who makes the chip — semiconductor fabrication and cryogenic materials.
4. Someone who handles lasers and vacuum — optics. In the trapped-atom design, this is the person who switches the computer on.
5. Someone who tends the refrigerator — cryogenic plant. The same job as the one in the fusion piece.
6. Someone who replaces the ciphers — security practice. The only seat where the work already exists though the machine does not.

The sixth line is the unexpected seat. No quantum computer yet can break a cipher. But ciphertext sent today can be stored and broken later, so the ciphers must change now — and banks, governments and carriers are already hiring for it. A rare case of the job arriving before the machine.

So when?

A machine big enough to break ciphers is still far off. Today's have a few hundred qubits, and they jumble so readily that the count of usable ones is far smaller. Breaking a cipher is thought to need thousands that hold steady.

So what quantum computers do at present is not solve problems but learn to hold still. They are in the making. The day one is finished, this piece leaves the series and becomes history.

The question that remainsIf only erasable problems can be solved, how many of the problems we most want solved can be arranged that way?