What is a quantum computer?

Let me first explain how a "classical" computer works. The main components of a classical computer are the CPU (central processing unit), memory (in a modern computer, the RAM and hard drive), and the software. Of course, you usually have user input and output devices (e.g. keyboard, monitor), but they are just for communication with the computer and not central to the computing process itself. The software contains lines of "code" which are written instructions for the CPU to execute. For example, one instruction might be for the CPU to add the numbers 5 and 6. Another instruction could be to save the number 15 in memory. How is the memory implemented? Well, the information is saved in bits. Each bit can be in the state 0 or 1. Physically, a bit is usually implemented by placing a certain electrical charge on a capacitor (two small metal plates very close to each other). The voltage on the capacitor will then depend on how much charge is on it. If the voltage is between say 0 and 0.5 volts then we identify that state as 0 and if the voltage is greater than 0.5 volts, then that state is 1. We can change the state of the bit by moving charge on and off the capacitor.

In the last ten years, scientists have become interested in studying quantum computers. There are several reasons. First, we know that there are limits to how much classical computer power we can pack into a given volume. The rise of the computing age has been spurred by the fact that semiconductor companies can squeeze more and more circuits into smaller and smaller chips with each passing year. Computers that used to fill rooms (40 - 50 years ago) now fit into 5 pound packages. However, we know from fundamental physics principles that this trend cannot continue. After all, you can't make a circuit out of one atom! So one motivation is that to continue increasing our computing power, we will have to look into alternative approaches from silicon-based classical computers. One of these is quantum computation.

Second, it appears that quantum computers can calculate some things "faster" than classical computers. What do I mean by faster? An algorithm is a set of instructions that when executed perform a useful task (like putting a bunch of words in alphabetical order or multiplying two numbers). Computer scientists measure the speed of the algorithm by comparing how many instructions have to be executed (i.e. the number of steps) and the size of the input data. For example, if the algorithm is to multiply two numbers, the size of the input data would be the total number of digits in the two numbers. In 1994, Peter Shor discovered that if you have a N-digit number that is the product of two prime factors, a quantum computer can find the factors in approximately N squared steps. In comparison, the best known algorithm for classical computers needs exp(N^(1/3)) steps. So the quantum algorithm is exponentially faster than the classical algorithm. It happens that modern encryption of data depends on the fact that it takes a classical computer exponentially increasing time to find the two prime factors. If a quantum computer could be built, it could conceivably break all the encryption codes at banks, the CIA, etc.!

Now that I've explained why quantum computers are interesting, I will try to explain how they work. A quantum computer has all the same elements as a classical computer: CPU, memory, software. The distinction is in the implementation of these elements. Recall that a classical computer saves information in bits, which can be in the state 0 or 1. A quantum computer, however, stores information in quantum bits ("qubits") that can be in both 0 and 1 at the same time. To be more precise, the most general state of a qubit is
|psi> = |state 0> + |state 1> * exp(i*phi).
Here exp(i*phi) is a complex number whose absolute value is one and phi is a continuous number between 0 and 2*pi. Notice that I've put the words "state 0" inside "|>". This notation emphasizes that these states are no longer classical objects (like voltages on capacitors), but they are quantum states. This is a difficult concept to explain without a course in quantum mechanics, so I will merely try to give you a flavor of the idea. If we tried to put a classical bit in both states 0 and 1 at the same time, it wouldn't work. For instance, if we added 0.3 volts (the capacitor in state 0) to 0.7 volte (the capacitor in state 1), we would get 1 volt which the CPU would read at state 1. However, for a qubit, we can perform an operation on the quantum state |psi> and this operation would be performed independently on state 0 and state 1 at the same time. It's as if we are performing a computation on one classical bit that is in state 0 and on a separate classical bit that is in state 1. So we already have double the computing power! If we have N qubits, then we can perform computations on 2^N different states at the same time.

The bad news is that we can only read the result from one of these 2^N states. This is a consequence of a fundamental postulate in quantum mechanics. Therefore, we have to design very clever quantum algorithms that somehow focus all the information into one state, the state that we read out. So far besides the prime factoring algorithm, scientists have only found a handful of useful quantum algorithms which are faster than their classical counterparts.

How do we actually build these quantum computers? The key is to find a way to implement the qubit. There are many ideas so far, but the simplest is to use an ion (an electrically charged atom). If you remember your high school chemistry, you may recall pictures of an electron orbiting a nucleus. That electron can occupy different quantum states, which can be used to implement a qubit. Then you can shine a laser on the ion to move the electron from one state to another (analagous to the CPU). The problem is that if you put an electron in an excited state (as opposed to its ground state which is the most energetically favorable), then the electron will be "unhappy" and want to return to its ground state. The technical term for this behavior is "decoherence." We lose quantum information because our quantum bits interact with the environment, which causes them to relax to their most energetically favorable state. The decoherence problem has limited quantum computers to 10 qubits or less so far.

Thus quantum computers are an interesting piece of science but not yet a practical technology.