The 2000 Volen Center Scientific Retreat
Edward Farhi, Ph.D.
Professor, Center for Theoretical Physics
Massachusetts Institute of Technology
Cambridge, Massachusetts
April 25, 2000

What You Could Do with a Quantum Computer If You Had One

There has been a lot of talk recently about quantum computers and here I am going to give a brief introduction to this trendy topic. At the outset I must say that nobody has yet built a quantum computer and it may be a long time before anybody builds one. The interest in this subject is in the fact that if you had a quantum computer it could do things that a conventional computer could not. A quantum computer could solve certain problems much faster than a conventional computer. This is not because the chips in a quantum computer run extremely fast. It is because a quantum computer uses a different logic than an ordinary computer and for certain problems using quantum logic this allows for tremendous algorithmic speedup.

This means that a quantum computer could execute many fewer operations to solve certain problems than a conventional computer would have to execute. This decrease in the required number of steps necessary to solve problems is what makes the study of quantum computation exciting.

We can idealize a conventional computer as a device that acts on strings of bits. Each bit takes the value 0 or 1. A conventional computer takes an input string of bits and produces an output string that is the answer to a problem. The computer acts by executing a program. The program results in a sequence of instructions that tell the computer how to change the bits. Each step of the running program changes a few bits. The harder the problem the more steps are required to go from the input to the output.

Although you may think that conventional computers are really very fast, there are problems that require so many steps that a conventional computer running since the Big Bang would not have had enough time to solve the problem.

The basic building block of a quantum computer is called a qubit. We can idealize a qubit as a spin-one-half particle such as the electron. You can think of a spin-one-half particle as spinning about an axis much like the earth spins. This is where, however, the analogy to a macroscopic spinning object ends.

The spinning electron carries angular momentum. If you pick any direction and measure the component of the angular momentum along that direction you get only one of two possible values +1/2 or -1/2 (in some units.) There is no classical spinning object that has the property that the component of its angular momentum along any direction must take one of two fixed values. This is called quantization of angular momentum and is a purely quantum effect. Now the qubit in a quantum computer plays the role of the bit in an ordinary computer. Spin +1/2 along some ' direction can be associated with bit value 0 and spin -1/2 can be associated with bit value 1. So far a qubit sounds like an ordinary bit. The difference is that an ordinary bit can have the value 0 or 1 but the qubit can be a quantum superposition of the two values +1/2 and -1/2. These quantum superpositions have no classical analogues. A quantum computer consists of a string of qubits. A quantum algorithm is a set of instructions for manipulating these qubits a few at a time. The rules for how the qubits can be controlled are governed by quantum mechanical law (which is perfectly well understood) and these rules are completely different from the rules that govern the behavior of bits in an ordinary computer. Quantum algorithms take advantage of quantum superposition and the basic wave like nature of quantum systems.

In a few key cases it has been shown that the number of qubit steps required to solve a problem is far fewer than the number of steps required in an ordinary computer acting with ordinary bits. The most striking example is the ability of a quantum computer to factor a large number with very few steps. Consider a large number, say one with 200 digits, and the goal is to write this number as a product of prime factors. It turns out that the fastest existing computers cannot factor a number this big in less than a century. The best known algorithm requires too many steps. If this problem is given to a quantum computer running carefully written quantum code, however, the factors could be found with very few steps. This dramatic speedup is important because it demonstrates that a quantum computer could do something a conventional computer could not do in a reasonable amount of time.

Also, factoring is not just an esoteric math problem. Almost all existing encryption systems are based on the inability of computers to quickly factor large numbers. If you had a quantum computer you could break all existing codes used by the military and financial institutions! For this reason the government is very interested in knowing if a functioning quantum computer could ever be built. On the theoretical side it is important to know if there are other problems that can be solved quickly on a quantum computer. We know of examples of problems where quantum speedup is not available and accordingly there is no advantage to using a quantum computer. We need to better understand the class of problems that are amenable to quantum speedup.

On the experimental side, so far only a few-qubit quantum computers have been built. By few I mean three or four. Experimentalists are trying hard to see if they could eventually build a three or four thousand qubit machine, which is what you would need to solve a difficult problem. Building a quantum computer is actually very technically challenging and probably a new idea is needed before a big one is ever built. But I am hoping that one is built because I am sure it will have applications beyond what has already been discovered.