This article is part of our Information about information project, run in collaboration with FQXi. Click here to read other articles on quantum computing.

Quantum computing often grabs the headlines. The word "quantum" itself is intriguing enough, and combined with the promise of computational power that surpasses anything we have seen so far it becomes irresistible. But what exactly is quantum computing?

Zeroes, ones, and both

To get to grips with quantum computing, first remember that an ordinary computer works on 0s and 1s. Whatever task you want it to perform, whether it's calculating a sum or booking a holiday, the underlying process is always the same: an instance of the task is translated into a string of 0s and 1s (the input), which is then processed by an algorithm. A new string of 0s and 1s pops out at the end (the output), which encodes the result. However clever an algorithm might appear, all it ever does is manipulate strings of bits — where each bit is either a 0 or a 1. On the machine level, this either/or dichotomy is represented using electrical circuits which can either be closed, in which case a current flows, or open, in which case there isn't a current.

The idea of superposition led the physicist Erwin Schrödinger to speculate that a cat in a box could be both dead and alive as long as you don't look at it. (This cat is definitely alive.)

Quantum computing is based on the fact that, in the microscopic world, things don't have to be as clear-cut as we'd expect from our macroscopic experience. Tiny particles, such as electrons or photons, can simultaneously take on states that we would normally deem mutually exclusive. They can be in several places at once, for example, and in the case of photons simultaneously exhibit two kinds of polarisation. We never see this superposition of different states in ordinary life because it somehow disappears once a system is observed: when you measure the location of an electron or the polarisation of a photon, all but one of the possible alternatives are eliminated and you will see just one. Nobody knows how that happens, but it does. (You can find out more in Schrödinger's equation — what is it?)

Superposition frees us of from binary constraints. A quantum computer works with particles that can be in superposition. Rather than representing bits — such particles would represent qubits, which can take on the value 0, or 1, or both simultaneously. "If you do something to [such a quantum system], it's as though you are doing it simultaneously to 0 and to 1," explains Richard Jozsa, a pioneer of quantum computing at the University of Cambridge.

Spooky action

You might object that something like superposition could perhaps be achieved using only ordinary classical physics — perhaps by processing two ordinary bits at the same time or something like that — in which case quantum computing wouldn't be that much more amazing than classical computing. But there is more to quantum physics than just superposition. If you look at a system of more than one qubit, then the individual components aren't generally independent of each other. Instead, they can be entangled. When you measure one of the qubits in an entangled system of two qubits, for example, then the outcome — whether you see a 0 or a 1 — immediately tells you what you will see when you measure the other qubit. Particles can be entangled even if they are separated in space, a fact that caused Einstein to call entanglement "spooky action at a distance".

Albert Einstein called entanglement "spooky action at a distance".

Entanglement means that describing a system of several qubits using ordinary classical information, such as bits or numbers, isn't simply about stringing together the descriptions of the individual qubits. Instead, you need to describe all the correlations between the different qubits. As you increase the number of qubits, the number of those correlations grows exponentially: for n qubits there are 2ⁿ correlations. This number quickly explodes: to describe a system of 300 qubits you'd already need more numbers than there are atoms in the visible Universe. The idea is that, since you can't hope to write down the information contained in system of just a few hundred qubits using classical bits, perhaps a computer running on qubits, rather than classical bits, can perform tasks a classical computer can never hope to achieve. This is the real reason why physicists think quantum computing holds such promise.

There's a hitch however. While a quantum algorithm can take entangled qubits in superposition as input, the output will also usually be a quantum state — and such a state will generally change as soon as you try to observe it. "Nature pulls a trick here," says Jozsa. "She updates a quantum state, but then she doesn't allow you to get all the information." The art of quantum computing is to find ways of gaining as much information as possible from the unobservable.

An example

An example of a quantum algorithm is one Jozsa developed together with another pioneer of quantum computing, David Deutsch. The task it performs is slightly curious, but we will think of it as follows. Imagine a line of people waiting at the gates of heaven to see whether they'll be let in. Guarding those gates is Saint Peter who, in deference to his love for computer science, has labelled all the people with numbers written in binary. There happen to be exactly 2³ = 8 people, which means that each person gets their own unique string of three 0s and 1s (see the table on the right or this article for more about binary numbers). Peter records his decisions by allocating a 1 to a particular bit-string if he is going to let the corresponding person in, and a 0 if he's not. (Technically this allocation is called a Boolean function, a rule which assigns to each bit-string a 0 or a 1. Boolean functions are a staple of computer science, which is why our example isn't as far-fetched as it may seem at first.)

You don't know what Peter is going to decide to do with each individual, but you do know that he's set in his ways: he'll either let everybody in (every bit-string gets allocated a 1), or he will let exactly half the people in (half of bit-strings get allocated a 0 and the other half a 1). Your task is, not to find out what happens to each individual, but whether Peter is in a generous mood and lets everybody in, or whether he is in a grumpy mood, deciding to let only half of the people in. How many values of Peter's Boolean function do you need to look up to find out which of the two alternatives it is?

If you work like a classical computer, then in the worst-case scenario you'll have to look the function up five times. That's because even if you see a 1 allocated to the first 4 bit-strings you check, you still can't be sure that all the bit-strings come with a 1: there is still the possibility that it's only half of them, so you do need that 5th look-up. If you have a quantum computer, however, you can get it to look up the function value for all the eight people simultaneously, so you only need one look-up. "For the cost of running the program once with this funny superposition input, you have somehow computed all the [values at once]," explains Jozsa. This advantage of quantum over classical computation becomes even more apparent when there are more people: for a line consisting of 2ⁿ individuals, a classical computer would need to look up the function 2^n-1+1 times, a number that grows very quickly with n. A quantum computer would always only need to look once.

Will quantum computing take us higher?

But then there is nature's trick: your eight simultaneously-looked-up values will be encoded in a quantum state you can't actually read, since any measurement of it will disturb it. Luckily, though, you're not trying to find out what'll happen to each individual. You only want to know whether Peter is feeling generous our grumpy. "That's only one yes-no question," says Jozsa. "It's a small amount of information about a lot of values."

Jozsa and Deutsch showed that it's possible to perform an extra operation on your quantum state, one which teases the simple piece of information you are after into just the right places for you to be able to read it off (see this article for a little more detail). It's a bit like a house of cards that will collapse as soon as you look at it. You might never be able to see it in its full glory, but if it was constructed in just the right way, you may at least be able to ascertain some information on what it looked like from the collapsed heap. And that's one reason why quantum computers are more powerful than classical ones. To find even simple patterns or structures within systems of many components a classical computer often has no choice but to first evaluate all, or at least many, of the components individually. A quantum computer, on the other hand, can evaluate all of them simultaneously. And although you may not be able to read off all those individual values, you can often extract just enough information to glean a pattern in them.

Jozsa and Deutsch came up with this algorithm in 1992 and it was the first that could be proven to work exponentially faster than any classical algorithm designed to perform the same task. If you're imagining Jozsa and Deutsch as quantum engineers tinkering away in a lab, however, you couldn't be further from the truth. Both of them are theorists. They use the mathematical formalism that describes quantum mechanics and theoretical computer science to work out what a combination of the two can achieve. It's a purely mathematical endeavour — we're still some way away from actually building fully functional quantum computers that can perform useful tasks. You can find out more in the following articles:

• Quantum computing: Some (not so) gruesome details (for a little more detail on the Deutsch-Jozsa algorithm)
• What can quantum computers do?
• Do quantum computers exist?

About this article

Richard Jozsa

Marianne Freiberger is Editor of Plus. She would like to thank Richard Jozsa, Leigh Trapnell Professor of Quantum Physics at the University of Cambridge, for his extremely helpful, very patient and generally invaluable explanations.