Quantum Computing and Qubits
The idea of a quantum computer is not new. (1) The spark came from Richard Feynmann in 1982 (2) where he thought about the simulation of a quantum-mechanical object by other quantum systems. This discussion led David Deutsch to describe a quantum computer in 1985. (3)
Then began a hunt for algorithms that could take advantage of the unusual properties of a quantum computer. For a long while only contrived examples could be found and there was little challenge to the dominance of classical computers. Peter Shor came up with the killer application for quantum computers in 1994 - factorization (4), that is figuring out the unique set of prime numbers that have to be multiplied together to produce a given number. This may not sound like something of practical interest, but many encryption algorithms have their security based on the difficulty of factorizing large numbers. Today there are many examples of algorithms that are advantageously done on quantum computers including methods to search large data bases (5), finding optimal solutions (the traveling salesman problem is an example), sophisticated signal processing (SETI-like searches) and ironically methods for secure communications. Factorization and secure communications are the reasons that the NSA is a major funder of quantum computing research. New quantum computing algorithms are being found regularly.
While quantum computing shows great promise the realization of a practical quantum computer is proving to be difficult. The key is the basic building block of such a computer: the quantum bit or qubit. Qubits must have the following properties to be a part of a practical quantum computer:
Individually Addressable: Each qubit has to be dealt with singly without disturbing the other qubits.
Initializable: Each qubit has be set to some specific state before the algorithm is run.
Readable: The state of each qubit has to be read out at the end of the algorithm to figure out the result.
Long Coherence Time: The qubit has to sit in whatever state it is in long enough for the algorithm to run to completion.
A few qubit systems running simple algorithms have been realized. Options for qubits include:
Trapped Ions: Individual ionized atoms can be trapped and have different quantum energy levels. These tend to be difficult to read and have short coherence time. It is very difficult to trap many ions and maintain a useful coherence time.
Nuclear Spin: The spin of the nucleus of certain atoms can be controlled and read with magnetic fields. They are difficult to address individually and have short coherence time. You may ask what spin is, but that needs another column.
Trapped Electrons: Looking like the best bet. Electrons, or impurities, can be trapped in nanostructures called quantum dots. The spin or energy quantum state of the electron can be controlled and read with simple electronics. Coherence time remains a problem.
Photon Polarization: Not practical for computing as it is difficult to alter them without destroying them and impossible to store them for any useful time. They are ideal for quantum communication.
All of these have been demonstrated as qubits and a few have actually been used to perform the simplest of quantum algorithms to demonstrate quantum computing. There are many websites that keep track of this fast developing field.(6)
As of today it remains to be seen if a useful quantum computer can actually be built. A break through is needed to demonstrate a qubit technology satisfying all the criteria, something with long coherence time which can be easily set and read is the stumbling block, at low cost. Then millions of them could be coupled together to build a machine that could actually perform a calculation more efficiently than classical computers. The ever growing power and capabilities of classical computers means that the bar for a useful quantum computer keeps getting higher.
NSA Calling: The NSA gives the characters a call. Apparently one of their quantum computer projects achieved success yesterday. The machine then politely asked everyone to leave the building as it wanted to be alone. When that request was not honored the machine got violent. The survivors cut the power and net access and an NSA emergency team went in late last night. As of this morning none have returned and contact has been lost. Are the characters willing to check it out for a fat fee? What besides an angry quantum computer are the characters going to find in a secret NSA lab?
An Unexpected Gift: A laptop arrives in the mail. On booting up it has instructions on how to use its quantum algorithms to break into the FBI database where the characters discover that the FBI knows all about their semi-legal activities. The FBI is apparently deciding on whether tomorrow or the next day is the right time to shut the characters down. Who built the lap top? Why was it sent to the characters? What else can be done with it?
Death Threat in the Lab: An old friend shows up at the door in the middle of the night. He is terribly afraid as he has received mysterious death threats about his upcoming presentation about a promising improvement to qubits. He has been advised not to pursue this line of research any further if he knows what is good for him and his family. The researcher is baffled since even he admits that his improved qubit is still a long way from producing any sort of practical quantum computer and only a small number of people have any idea what he is planning to present. Who is so concerned about a basic research project? How did they find out about it? Maybe there is something else going on?
1 - There are many books on the subject of quantum computers. The Quest for the Quantum Computer by Julian Brown and David Deutsch, one of the pioneers, is a recent good one.
2 - R. Feynman, Int. J. Theor. Phys. 21, 467 (1982).
3 - D. Deutsch, Proc. R. Soc. London A 400, 97 (1985).
4 - P.W. Shor, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, CA), p. 124 (1994).
5 - Called Grover's algorithm.
6 - Oxford's Qubit.org and links from this site is a good starting point. Any web search on quantum computing will pull up a flood of information. .