Computing without computing

Toby Howard

This article first appeared in Personal Computer World magazine, August 1998.

THE IDEA OF USING the fundamental particles of matter to build a "quantum computer" is a hot research topic. Quantum computers are strange: they exploit the counter-intuitive behaviour of the sub-atomic world to perform billions of computations simultaneously. Now they're set to get stranger still, with the prospect of a quantum computer which computes without doing any computing at all.

The new machine is the brainchild of Professor Richard Jozsa of the University of Plymouth, who has found a way to apply an idea called "interaction-free measurement" to computer design.

With apologies to any professional physicists reading, here's how it works. Figure 1 shows a simple experimental set-up:

There's a source of light (photons), two "beam splitters", which split a beam of light into two new beams, two mirrors, and two photon detectors. According to the laws of quantum mechanics, when a photon enters splitter 1, it splits into two "ghost photons", which simultaneously travel along both the red and the blue paths. At splitter 2, the ghosts are re-combined into a real photon which hits the blue detector. It never hits the red detector. This "splitting" sounds bizarre, but experiments have shown that this is just what photons seem to do.

Now imagine that an object is placed so as to block the red path, as shown in Figure 2.

This changes everything. Because there is now only one clear path from splitter 1 to a detector, quantum mechanics now states that the photon behaves like an indivisible particle. This time, when the photon hits splitter 1, it will randomly take the red path or the blue path.

If it takes the red path, it will be blocked by the object, and so will never reach a detector. If it takes the blue path, however, when it reaches splitter 2 it again randomly chooses which way to go next. There's an equal chance of it going to the red or the blue detector.

Suppose we don't know whether an object is blocking one of the paths -- what can we deduce by examining the behaviour of the detectors? If we ever see a photon at the blue detector, we can't say for sure whether there was an object blocking one of the paths or not. On the other hand, if we ever see a photon at the red detector, we know there must be an object in the system.

Now for the really kooky bit. If a photon ever gets to the red detector, it must have followed the blue route, therefore avoiding the object. But we know that finding a photon at the red detector means there must be an object present. So, although this photon has not encountered the object, it is telling us that the object is there! This is "interaction-free measurement". Professor Jozsa's breakthrough is to prove that this same situation can apply to the workings of a quantum computer.

A conventional computer manipulates binary digits, or bits, and at any instant a bit can either be a 0 or a 1 -- no other value is possible. Quantum computers, however, use fundamental particles to create "qubits" (kew-bits). A qubit, which as well as taking the values 0 or 1, can also exist in a "superposition", when it is a 0 and a 1 simultaneously. This means, for example, that a set of 16 qubits can simultaneously represent all the numbers between 0 and 32767 (2¹⁵ - 1). The incredible power of the quantum computer comes from the ability to perform calculations on all these numbers simultaneously.

Jozsa takes this further. His idea is to place not just the qubits, but the entire computer, including its program, in a superposition of states. He has shown that just as a photon can detect the presence of an object without interfering with it, so a quantum computer could find the results of a program without actually having to run the program. All you have to do is wait long enough for the results as if the program had been run. Note that you can't get away with not actually writing the program! The program must still exist in the quantum computer, and it must be a correct algorithm for solving the problem.

There are still formidable technical challenges in building quantum computers, and no-one yet knows whether they'll ever be overcome. But the researchers are optimistic, with prototype quantum logic elements already working under lab conditions.

A few decades into the next millennium, we'll probably become blase about the quantum computers on our desk. While the machines of the 20th century buzzed and got hot, the new machines will run quiet and cold. They'll be computing on a massive scale, but at the same time, doing absolutely nothing.

Toby Howard teaches at the University of Manchester.