| |
|
|
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 H5C11O2F5Fe. 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 1018 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!
John G. Cramer's 2016 nonfiction book (Amazon gives it 5 stars) describing his transactional interpretation of quantum mechanics, The Quantum Handshake - Entanglement, Nonlocality, and Transactions, (Springer, January-2016) is available online as a hardcover or eBook at: http://www.springer.com/gp/book/9783319246406 or https://www.amazon.com/dp/3319246402.
SF Novels by John Cramer: Printed editions of John's hard SF novels Twistor and Einstein's Bridge are available from Amazon at https://www.amazon.com/Twistor-John-Cramer/dp/048680450X and https://www.amazon.com/EINSTEINS-BRIDGE-H-John-Cramer/dp/0380975106. His new novel, Fermi's Question may be coming soon.
Alternate View Columns Online: Electronic reprints of 212 or more "The Alternate View" columns by John G. Cramer published in Analog between 1984 and the present are currently available online 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
