A completely new kind of computer is rising on the technology horizon, and it has just reached a significant milestone.  A quantum computer, a device first suggested decades ago by Richard Feynman and others, has been constructed by Isaac Chuang and his coworkers at IBM’s Almaden Research Center in California.  The prototype quantum computer uses entangled nuclear spins for storage and has a capacity of seven “qubits”, a term that will be discussed below.  Using a quantum-computing algorithm developed by AT&T's Peter Schor in 1995, this quantum computer has factored the number 15 into its prime- factors, 3 and 5.  Admittedly, factoring 15 perhaps doesn’t sound like much of an accomplishment, but it represents the most complex computation that has ever been performed with a quantum computer.  It requires some explanation to appreciate what has been accomplished so far and where it will lead.

A conventional computer has a memory in which bits of information are stored in definite binary states of 1or 0, and a processor that operates on this stored information.  For example, the memory may contain two numbers stored in binary representation and a program specifying the locations of these numbers and calling for them to be multiplied together and the result stored.  With the execution of the program by the processor, the numbers are fetched, multiplied, and their product in binary representation stored in the memory.

A quantum computer differs from this computing scheme is one important way: the definite-state memory 0-or-1 bits in the conventional computer are replaced by indefinite qubits (short for quantum bits).  The qubits are possible states in a quantum system and may be indefinite.  For example, all fluorine-19 nuclei have a nuclear spin of ½ unit of angular momentum.  This spin may point either “up” i.e., parallel the flux lines of an external magnetic field, or “down”, i.e. opposite the direction of the lines of flux.  It is a peculiarity of the rules of quantum mechanics that no other spin directions, (e.g., “sideways”) are allowed for ½ unit spins.  The spin of a fluorine-19 nucleus might be in an up state, a down state, or a mixture of the two, depending on the conditions of preparation.  If the spin direction is used, as in the IBM quantum computer, to represents a binary qubit, then that qubit may be 1, 0, or a mixture of both.

The up and down spin states have slightly different energies, so a slight addition or subtraction of energy using megahertz radio waves can force the nuclear spins into one orientation or the other.  However, it is also possible to prepare the spin orientation of the nucleus in an indefinite state that is 50% up and 50% down.  There are also techniques for measuring (or reading out) the spin state acting as a qubit.  If the qubit in an indefinite 50-50 state is read out, the quantum rules require it to randomly “collapse” into either a 1 or a 0 state, with an equal chance of each outcome.

Of course, a quantum computer needs more than just qubits for its operation.  The qubits must be well enough insulated from the random scrambling effects of random environmental noise (called decoherence) that the coherent state of the quantum system is preserved for at least for long enough to set up a calculation, perform it, and read out the results.  It must have the ability to initialize any qubit in a specified state, and to measure the state of a specific qubit.  It must have “universal quantum gates”, logical elements capable of arranging any desired logical relationship between the states of qubits.   It must also have a processor capable of interlinking quantum gates to establish rules and boundary conditions for their inter-relationships.  In a quantum computation the arrangement of quantum gates connects the qubits in a logical pattern, according to a program or algorithm, and after an interval the qubits assigned to the result are read out.  If this is done properly, the quantum computer can be made to perform calculations in a way that is qualitatively different from calculations performed on a conventional computer.

The powerful capability of a quantum computer is its use in computational problems that require searches over a large number of possibilities in order to find those that satisfy certain criteria.  An example is a search over all prime numbers to find a pair that produces a specified number, when that number is very large.

A conventional computer must explore all the combinations of alternatives, one set at a time, in such a search.  This may be computationally “hard” if the number of alternatives is very large.  A quantum computer with enough qubits to hold the problem, on the other hand, can search the alternatives in parallel, all at the same time, and reach the problem’s solution in a much faster time.

The new quantum computer constructed by IBM uses the nuclear spins of seven atoms that are part of a molecule with the iron-based chemical composition H₅C₁₁O₂F₅Fe.  Two of the eleven carbon atoms in the molecule are carbon isotope 13 and all of the fluorine atoms are fluorine isotope 19.  All of the other non-hydrogen atoms in the molecule have even isotope numbers and no nuclear spins.  For the quantum computation, a sample of about 10¹⁸ of these molecules is placed in a magnetic field and manipulated using the techniques of nuclear magnetic resonance (NMR), so that the spins function as qubits.  NMR is an excellent technology for implementing quantum computing because nuclear spins are well isolated from environmental noise.  Therefore, the decoherence time, i.e., the time after which quantum coherence is lost due to random interactions with the environment, is very long.  The NMR fields of the quantum computer are manipulated so that Schor’s prime factor algorithm is performed and the number 15 is factored into the primes 3 and 5.

To factor a larger number, a system with more than 7 qubits would be required.  Things would get interesting when about 24 qubits were available for such computations.  With 36 qubits or so, a quantum computer should quickly perform computations that would require a time equal to the age of the universe on a conventional computer.  Unfortunately, such a qubit scale-up is difficult, because the IBM device is near a hard technology limit of NMR quantum computing.  For its operation, all the qubits must be in the same molecule, and molecules with more than 7 or so spins that can be used as qubits do not seem to be feasible.

Fortunately, there are alternative technologies for quantum computing that promise to be more scaleable than the NPR technique.  In particular, the technologies of electron spin orientation in quantum dots, nuclear spin orientation of single atom impurities in semiconductors, and manipulation of magnetic flux quanta in superconductors all show promise of providing a basis for scalable quantum computers.  There is intensive work on quantum computing in these area, but difficult decoherence problems must be overcome before they become competitive with NMR.

What actually goes on in a quantum computer to produce their amazing capabilities?  The British mathematician David Deutsch, who has contributed to the development of the theory of quantum computing, likes to invoke the Everett-Wheeler interpretation of quantum mechanics (see my column "Other Universes II" in the November-1984 Analog) to describe this Quantum computing process.  Deutsch asserts that the quantum wave function describing the qubits splits among many parallel universes, so that the quantum computer calculations proceed in many parallel universes at the same time.  Finally, the answer is found in one of these universes and is transmitted to all the others, which effectively recollapse into one universe.  This is certainly a colorful way of describing quantum computing, but it is very non-economical, in the sense that the assertion is in danger of having its throat cut by Occam’s Razor.

As the originator of the transactional interpretation of quantum mechanics (see "The Quantum Handshake" in the November-1986 Analog), I prefer to visualize the process in a different way.  The programming of the quantum computer that sets up the problem has created a set of conditions such that the quantum mechanical wave function can only form a final transaction and collapse by solving the problem (e.g., finding the prime factors of an input number).  The advanced and retarded waves, describing all the possible qubit states of the system, race through the computer, seeking the ultimate multi-node quantum handshake that solves the problem.  This process happens very fast, because the propagation time of advanced waves is negative.  The net result is that the solution transaction forms, the wave function collapses into the solution state, and the result is read out.  This, I think, provides a simple, economical, and insightful view of what goes on in a quantum computer.

How might a quantum computer be put to use?  Consider the widely used information protection scheme called RSA public-key encryption, which is embodied in the widely distributed PGP encryption software.  Suppose, for example, that Alice wants to use the RSA procedure to send a private message to Bob.  Bob has previously posted his public encryption key (a long string of 1s and 0s) in some public database.  Alice retrieves Bob’s public key from the Internet, and she uses it on her conventional computer running a widely distributed public-key encryption program (e.g. the PGP program) to encrypt her private message to Bob.

Once this is done, the message cannot be decoded, except by Bob, even by someone who has both Bob’s public key and Alice’s encryption program.  Now Bob receives Alice’s encrypted message by E-mail and decrypts it using his second private key and the same program.  The privacy of the message is ensured because only Bob has the private key, and he has never revealed it to anyone else, not even Alice..

The RSA encryption algorithm depends critically on the fact that it is easy to multiply two large prime numbers together and obtain their product, but it is computationally “hard” to factor the resulting product back into the original primes, if they are not known.  The main part of the public encryption key used by Bob is, in fact, a large number that is the product of two primes, and his private decryption key is one of the prime factors of that public key.

With a conventional computer, it might require many years of computer time to factor the large number in Bob’s public key.  However, with a quantum computer the large number, at least in principal, can be factored very rapidly and the message broken.  Thus, the RSA encryption procedure is based on the assumption of the difficulty of prime factoring, and quantum computers threaten to invalidate that assumption.

It is not surprising that the National Security Agency, the code-breaking and electronic surveillance arm of the U. S. federal government, has for many years opposed the wide distribution of strong encryption schemes such as the RSA algorithm.  It has also arranged for federal laws that block the distribution in certain forms of strong encryption outside the USA and Canada.  It is perhaps more surprising that the NSA is currently one of the principal funding sources for research into quantum computing.  Big Brother would like to read your E-mail, even when it is RSA encrypted.

Beyond code breaking, there are other uses for quantum computers.  They should make possible super-fast searches of large databases, for example.  Moreover, in physics there are many problems involving the simulation of quantum systems that can only be poorly approximated by calculations on conventional computers.  With a computer that had a good "quantum coprocessor", such physical systems could be simulated much more directly, in ways that are not presently feasible.  In my own area of physics research, ultra-relativistic heavy ion physics, we badly need this capability.  We limp along without it, making approximations that are only pale shadows of the quantum reality.  I would like a good quantum computer on my desk, right now!

AV Columns On-line: Electronic reprints of over 100 "The Alternate View" columns by John G. Cramer, previously published in Analog, are available on-line at: http://www.npl.washington.edu/av.

References

IBM Quantum Computer:

"IBM's Test-Tube Quantum Computer Makes History", http://www.research.ibm.com/resources/news/20011219_quantum.shtml

Cryptography:

The PGP Encryption Software, http://web.mit.edu/network/pgp-form.html

The Transactional Interpretation of Quantum Mechanics

John G. Cramer, Reviews of Modern Physics 58, #3 (1986);

John G. Cramer, International Journal of Theoretical Physics 27, 227 (1988); and

http://www.npl.washington.edu/tiqm

Exit to  issue index .