1. Introduction
Scientists have pondered the eventuality of the quantum computer since
1980 when quantum theory was applied to the classical Turing machine.
Not only can quantum computers run one billion times faster than typical
silicon-based computers, but also theoretically, they can run and
consume no energy. That being true, quantum computers could obsolete
the silicon chip much as the transistor did the vacuum tube.
Consequently, silicon chip and computer manufacturers, the U.S.
government, and Japan are directing huge sums of money for quantum
computer research. This paper provides an overview of the quantum
computing world, and how the dawn of the quantum computer will affect
the computing industry. We discuss how quantum computers originated,
the inevitability of their use, and how they differ from classical computers.
We use the principles of superposition, entanglement, and quantum
teleportation as examples, and provide an overview of the NMR-type
quantum computer (produced as a prototype at MIT in 1989) at the end
of our discussion. This paper is intended for the general reader, and
explains basic quantum computer features, and the paradoxical effects
quantum theory produces in a practical world. This author has not built
nor operated a quantum computer, and so he relies heavily on scientific
literature. The single book published on the topic is Explorations in
Quantum Computing , by Colin Williams and Scott Clearwater.
2. Inevitability of Quantum Computers
As technology rushes forward, several factors work together to push us
toward the quantum computing world, and push aside classical
silicon-based chips. These factors are:
Scaling in size
Energy consumption
Economics of building leading-edge computers
New quantum computer applications that cannot be executed by
classical computers
At today?s rate of chip miniaturization, energy efficiency, and economics,
the classical computer of the year 2020 (if it could happen at all), would
contain a CPU running at 40 GHz (or 40,000 MHz), with 160 Gb (160,000
MB) RAM, and would run on 40 watts of power.
2.1 Scaling
Our computing world is surrounded by breath-taking innovations; many
of them involve more powerful and smaller chips. Chip capacity doubles
every 18 months according to Moore?s Law, but chip size remains
constant. Additionally, the number of transistors on a single chip is rising
exponentially. Keyes (Williams & Clearwater, 1998) extrapolates that
if
miniaturization continues at today?s rate, a single atom will represent
a
bit by the year 2020. This trend inevitably leads us into the micoworld
of
quantum effects, where classical rules no longer apply.
2.2 Energy
Chip speed is rising exponentially. Faster, more densely packed, and
closer transistors cause thermodynamic problems. Advances in energy
efficiency are required to keep the chips from melting during use.
Fortunately, energy efficiencies are increasing, and the thermodynamic
problems are being resolved. These energy advances are also pushing
the physics of chips into the quantum realm.
Quantum computers are reversible, and thus have no net energy
consumption. Quantum reversibility implies that quantum computers
drive themselves forward in infinitesimal (reversible) steps, much the
same way that molecules of perfume diffuse from a perfume bottle.
Quantum computer programs are not run, but are said to evolve, as they
process a program?s inputs to outputs. Incidentally, reversibility also
means that the inputs of a quantum computer can be implied from the
outputs; the program can be run backward to get the inputs.
The argument for energy inevitability is a carrot-and-stick argument: the
energy inefficiencies drive us away from classical computers and the
appeal for energy-free (or at least, reduced energy consumption)
computing drives us toward quantum computers.
2.3 Economics
In addition to the energy factors at the computing micro level,
large-scale economic factors push us to a more energy-efficient means
of computing: five percent of our country?s entire power production is
consumed by computing machinery (Malone95). With fossil fuels
continuing to dwindle, fission power in disfavor with the public, and fusion
power still many decades away, the drain computers impose on our
power supply could become significant . (Williams & Clearwater, p12)
Additionally, the cost to build a semiconductor plant doubles every three
years. Extrapolate that trend to the year 2020, and a semiconductor
plant will cost $1 trillion to build five percent of the U.S. GNP. Based
on
Motorola?s sales figures, a similar company would need $10 trillion in
annual sales to support construction at that level.
Japan, in its bid for software and hardware global dominance has
allocated large funds for quantum computer research. A
Hewlett-Packard V.P., reported that the Japanese is performing 70
percent of all quantum computer research (ACM Conference 1997). The
country has included quantum computers as an integrated step of their
global acquisition strategy.
2.4 New Applications
2.4.1 Encryption Technology
The speed of quantum computing jeopardizes encryption
schemes that rely on impracticably long times to decrypt by
brute force methods. Encryption schemes that take millions
of years to guess and check are now vulnerable to quantum
computers that could reach a solution within a year. Many
governments, including the U.S., use such encryption
schemes for national security. The government is very
interested in any technology that puts that at risk. As a
result, the Office of Naval Research, the CIA, and DARPA,
are sinking large sums of money into quantum computer
research. DARPA is funding $5 million for a Quantum
Information and Computing Institute, and the CIA is funding
an unknown amount for factoring of large integers, a
fundamental part of encryption technology.
2.4.2 Ultra-secure and Super-dense
Communications
It is possible to transmit information without a
signal path by using a newly-discovered
quantum principle called quantum teleportation.
With this method of transmission, one cannot
possibly intercept the path and extract
information. Ultra-secure communication is
also possible by super-dense information
coding, a new technology in its own right.
Quantum bits can be used to communicate
more information per bit than the same number
of classical bits.
2.4.3 Improved Error Correction and Error
Detection
Through similar processes that support
ultra-secure and super-dense
communications, existing bit streams can be
made more robust and secure improving error
correction and detection. Recovering
information from a noisy transmission path will
be lucrative and useful.
2.4.4 Molecular Simulations
In 1982, Richard Feynman demonstrated that
classical computers couldn?t simulate quantum
effects without exponential slowing; a quantum
computer can simulate physical processes of
quantum effects in real time. Molecular
simulations of chemical interactions will allow
chemists and pharmacists to learn more about
how their products interact. Further, they will be
able to determine how their products interact
with biological processes; how a drug may
interact with a person?s metabolism or disease.
Pharmaceutical research offers a big market to
such applications.
2.4.5 True Randomness
Classical computers cannot generate true
random numbers. Classical computers?
random number generators are
pseudo-random generators there is always a
cycle or a trend, however subtle.
Pseudo-random generators cannot simulate
natural random processes accurately for some
applications, and cannot reproduce certain
random effects. Quantum computers can
generate true randomness, thus give more
veracity to programs that need true
randomness in their processing. Randomness
plays a significant part of applications with a
heavy reliance on statistical approaches, for
simulations, for code making, randomized
algorithms for problem solving, and for stock
market predictions, to name a few.
With the global forces of computer competition,
encryption technology for national security, new
applications, and the thermodynamics of
computer systems changing as they are, the
scientific community is rushing to produce the
first viable quantum computer. The world is
moving toward a place that no classical
computer has gone before, nor can go.
3. History
Quantum theory arose with Max Planck?s discovery of the energy
quantum (Nobel Prize, 1918), and Einstein?s discovery of the photon
(Nobel Prize, 1921). We might trace the invention of the modern
computer to 1956, when Bardeen?s and Brattain?s won the Nobel Prize
for inventing the transistor. The idea of a quantum computer originated
in
1980 when P. Benioff thought about the now classic Turing machine
(developed in 1935 by Alan Turing) in terms of quantum states. Whereas
the conventional Turing machine computes by punching holes in a linear
strip of paper, the Benioff?s Quantum Turing Machine (QTM) has strips
of paper with multiple paths, each one with a probability of traversal.
The
QTM has exponentially many paths, not all equally probable, but all
possible.
Two years later, Richard Feynman showed that because of these diverse
paths, a classical computer would slow exponentially while attempting to
traverse an exponentially growing number of paths. That is, a classical
computer could not simulate quantum processes. Berthiaume &
Brassard proved in 1994 that QTMs are theoretically faster than Turing
machines, part due to the parallelism of quantum computing; Shor
demonstrated this in 1994 by factoring large integers in polynomial time.
Shor?s algorithm was the first significant problem solved by a quantum
approach to excel classical computers.
In 1996, Grover showed a quantum algorithm to search unsorted
databases in the square root of the time it would take a classical
computer to find an entry. It is said that to search for a name in the
entire
text of the Library of Congress would take a classical computer about
100 years. A quantum computer, however, could find that name in under
a half-second. Grover?s algorithm and the law of super-positioning
makes this possible. (Super-positioning is discussed later in this paper.)
(Science News Online, 6/14/97) ("What is a Quantum Phone Book??,
Lucent Technologies)
The Turing machine, designed around a machine traversing a strip of
paper, is hard to use as a focus to manipulate new ideas in programming
and electronics. In 1993, Yao showed that the same effect could be
accomplished with quantum circuits. Quantum circuits are equivalent to
digital logic circuits, but use quantum principles. Classical circuits
use
Boolean logic, either state 0 or 1 for inputs and outputs. Quantum circuits
use these states simultaneously-the inputs of a quantum circuit are both
0 and 1.
These algorithms were constructed and proved in theory, but in June
1998, Gershenfeld and Chuang built the first quantum computer at MIT. It
was based on the principles of Nuclear Magnetic Resonance (NMR).
Other types of quantum computers may be built, but NMR it is
characteristic in that it uses molecules in a liquid CPU of chloroform
for
logic gates. The prototype is discussed later in this paper.(Gershenfeld
and Chuang, Scientific American)
In December 1998, Anton Zeilinger was able to teleport a beam
of light
about three feet across his laboratory. He did this using a principle called
quantum entanglement, both of which are explained later in this paper.
(?Science, Magic, and Quantum Computers?, Green) (?The Innsbruck
Experiment?, Scientific American December 22, 1997) (Hall, Scientific
American)
4. What is Different About Quantum Computers?
While many differences exist between quantum and classical computers,
this paper addresses only two:
Superpositioning to support the explanation of quantum circuits
Entanglement to support the explanation of quantum teleportation
4.1 Superpositioning
Superpositioning implies that two things can overlap without
interfering with one-another. In classical computers, electrons
cannot occupy the same space at the same time, but as waves
they can.
4.1.1 Superposition in waves
Figure 1 illustrates two superimposed waves A and B.
If we add these waves together numerically, S = A + B, the
result is a wave that looks like neither of its components.
However, we could retrieve either wave by subtracting out
the other, as shown. (The wave form S, is shown as dotted
to indicate that it is only the apparent wave form; the actual
wave form is the combination of two different waves. In the
quantum world, the combined waveform is a set of amplitude
probabilities.)
4.1.2 Superposition in link list pointers
For a programming-specific example, let?s look at a data
structure called a linked list. Each data node in the list
contains a reference, or pointer, to the next data node. The
program traverses the list by jumping to the next data node
indicated by the pointer. In a doubly linked list, the data node
contains two pointers, one for traversing to the top of the list,
and another for traversing to the bottom of the list.
Another way of implementing a doubly linked list is to use a
single pointer space containing the exclusive-or (XOR) or
the two adjacent pointers. Figure 2 shows a link list node
with pointer S that is the XOR of reference A (before) and
reference B( after). To traverse the link list upward, the
program XORs the current pointer (S) with the one it just left
(B), and the result is the pointer of the next node (A). The
same process works when traversing down the list. The
superpositioning of node pointers is analogous to the water
wave superposition example we just used, and is how the
quantum states are maintained simultaneously in a quantum
bit.
4.2 State Vectors
A state vector is the superpositioning of all the probabilities that a
quantum bit may find itself in. These probabilities are not all equal.
One may think of this as a vector of the probabilities drawn in a
two-dimensional coordinate system of the Complex plane. That is,
coordinates of the form x+iy, where x is a coordinate on the Real
number line, and y is a coordinate on the Imaginary number line.
Classical bits are either vectors of 0 or 1, and have no Imaginary
component. Quantum bits, called ?qubits?, have both components.
If the probabilities are equal, the vector can be represented as 45
degrees from vertical; if the probability of 1 is twice that of 0, the
vector can be represented as 30 degrees from vertical. This
vector represents the superposition of the probability of 1 and the
probability of 0 simultaneously. In this way, the state vectors of
classical bits are ?collapsed? qubit state vectors.
It is important to note that any physical quantity expressed by an
imaginary number cannot be measured directly, and any physical
quantity expressed by a complex number can be measured only
on its real number component. Thus, qubits cannot be measured
directly. Any measurement of a qubit breaks superposition and
collapses its state vector to a classical bit, just as subtracting a
component wave or XOR?ing a pointer, produces a different result.
In performing computation with qubits, it is important not to
measure the qubits until the final answer is computed; otherwise,
the information can be lost or changed.
5. Quantum Circuits
5.1 The Square-Root-NOT Gate
Williams and Clearwater provide an excellent example
of a quantum circuit that cannot be explained in
classical physics terms. It also illustrates the principle
of quantum circuits and superpositioning. They have
termed the gate the Square-Root-NOT gate, in
contrast to the classical NOT gate.
The classical NOT gate takes either a 0 or 1 input and
converts it to a 1 or 0 output respectively. It is a
reversible gate in that the input may be deduced from
the input. The quantum circuit symbol for the NOT gate
is shown in Figure 3 (top).
Now imagine another logic circuit that is also
reversible, but contains two gates in series such that
the input of either a 0 or 1 is converted to a 1 or 0
output respectively. Because the two-gate circuit is
reversible like the NOT gate, and inverts the input
exactly like the NOT gate, each gate is called a
Square-Root-NOT gate (see Figure 3, bottom). There
is no way classical gates can perform this logic. It can
be done as a quantum circuit.
A quantum circuit has two important differences. First,
the input is a qubit, and contains the superposition of
both 1 and 0, and the output is also the superposition
of both 1 and 0, but with the probabilities reversed.
Second, the output of the first gate, halfway through the
circuit, is in an unknown state; it has a calculable state
vector, but one that cannot be measured directly.
5.2 The Universal Gate XOR
A universal gate can be used to produce all circuits.
Both classical and quantum computers have a
universal gate: the XOR gate. Any circuit can be made
with only this gate. Of course, the circuit might be
awkward, but it will work. Let it suffice for now that
quantum circuits can be built, at least on paper, with
similar tools available for classical circuits, and one
may construct a logic circuit to do what one wants. The
XOR gate has a naturally occurring counterpart that
comes into play when building quantum computers,
which will be discussed in the section on the NMR
prototype.
6. Entanglement and Quantum Teleportation
6.1 EPR Paradox and Hidden Variables
The quantum property of entanglement has an
interesting history. Einstein, who claimed that ?God
does not play dice with the universe? used the
property of entanglement in 1935 in an attempt to
prove that quantum theory was incomplete.
Albert Einstein, Boris Podolski, and Nathan Rosen
knew the state vectors of certain quantum systems
were correlated, or entangled with each other. By
changing the state vector of one system, we
instantaneously change the corresponding state
vector of the other system. This happens
independently of the medium through which the
communicating signal travels. Since nothing can travel
faster than the speed of light, how can one system
(arbitrarily far apart) affect the other? Einstein called
this a ?spooky action at a distance.? It required a
philosophy of reality contrary to science as they
(Einstein and his counterparts) knew it. Einstein
preferred the idea that some unknown or hidden
variables contributed to the effect, and since they
weren?t known, then quantum theory was incomplete.
In 1964, John Bell proved that no hidden variables
existed (Bell?s Theorem). This implied that spooky
action at a distance was a fact. In 1982, Alan Aspect
performed an experiment in which he showed that
Bells? Theorem had experimental validity. Either some
faster-than-light speed communication occurred, or
some other mechanism was at work. This basic
concept has made all the difference between classical
ideas of reality and quantum ideas of reality.
Throughout previous history, all physical phenomenon
depended on some force, and a particle to carry that
force. Therefore, the speed of light restriction applied.
For example, an electron carries electrostatic forces, a
graviton, etc carry gravitational forces. However, with
entanglement, quantum systems are correlated in a
way that does not involve a force, and the speed of
light restriction does not apply. The mechanism by
which one system affects the other is yet unknown.
6.2 Collapse of the State Vector
When two quantum systems are created while
conserving some property, their state vectors are
correlated, or entangled. For example, when two
photons are created, and their spin conserved, as it
must, one photon has a spin of 1 and a spin of -1. By
measuring one of the photon?s state vectors, the state
vector collapses into a knowable state.
Instantaneously and automatically, the state vector of
the other photon collapses into the other knowable
state. When one photon?s spin is found to be 1, the
other photon?s spin of -1 immediately becomes known
too. There are no forces involved and no explanation
of the mechanism.
6.3 Quantum Teleportation
The principle of entanglement enables quantum teleportation. This does
not involve moving an entity from one physical location to another (like
many popular science fiction stories). This kind of teleportation
involves
destruction of the original and recreation of an identical duplicate at
another location.
6.3.1 Brassard?s Theoretical Circuit
In 1996, Gilles Brassard conceived of a
quantum circuit that could create and entangle
two pairs of qubits, where one is entangled with
two others. Figure 4 shows Brassard?s
quantum circuit. In general:
Alice?s circuit entangles three bits (M,
A, and B), and transmits M to Bob.
Using knowledge from M, Bob?s circuit
produces a replica of bit B.
The instantaneous result on B, by
measuring M, is effectively a
teleportation of qubit B.
For purposes of discussion, the gates marked
L, R, S, and T, are referred to as:
L = left-rotation
R = right-rotation
S = forward-phase shift gates
T = backward-phase shift gates
The XOR gate is shown as a circumscribed
cross. These gates can cause entanglement
when qubits are put through them.
The conceptual circuit works like this:
1.Two classical bits, M and A, are entered
into the circuit at line 1 (bottom input)
and line 2 (middle input) where A is
rotated left, and its output is XOR?d with
M.
The output lines 1 and 2 will have
identical, entangled qubit states.
The output of line 1 (qubit M, called the
?messenger?) is sent to Bob in a
standard, classical way.
2.Another bit B with any state (or unknown
state) is entered into the circuit at line 3
(top input) which is XOR?d from the
middle line and right rotated.
The output line 3 produces qubit B, now
entangled with both M and A.
Alice can now measure the qubits from
output lines 2 and 3, which will collapse
the state vectors to produce two
classical bits. The measurement also
affects the state of qubit M. Alice sends
the results of the states she measured
to Bob, again in a classical way.
3.Bob creates two classical bits B? and
A?, with the same state (not the same
bits) as told to him by Alice, and inputs
these bits into his circuit?s input lines 2
and 3.
Qubit M, received from Alice (partially
affected by Alice?s measurements, and
the classical bits B? and A?) will go
through Bob?s circuit and disentangle
M.
Output line 1 will produce a qubit with the
identical state vector as the original bit
B. By being disentangled, the input M will
in effect ?become? the original B.
The original qubit B was not magically
transferred through space. It was
recreated from a different bit M; only the
state vector information was transferred
through space, when Alice told Bob the
states of the qubits A and B that she
measured.
6.3.2 Zeilinger?s Experimental Circuit
Figure 5 shows Zelinger's diagram of how he
set up his teleportation device at the
University of Austria at Innsbruck. This
diagram shows the physical counterpart to
Brassard?s theoretical circuit described
above.
1.At the sending station of the quantum
teleporter, Alice encodes a messenger
photon (M) with a specific state: 45
degrees of polarization. This travels
toward a beam splitter.
2.Meanwhile, two additional entangled
photons (A and B) are created. The
polarization of each photon is in a fuzzy,
undetermined state, yet the two photons
have a precisely defined
interrelationship. Specifically, they must
have complementary polarization. For
example, if photon A is later measured to
have horizontal (0 degrees) polarization,
then the other photon must collapse into
the complementary state of vertical (90
degrees) polarization.
3.Entangled photon A arrives at the beam
splitter at the same time as the message
photon M. The beam splitter causes
each photon to either continue toward
detector 1 or change course and travel
to detector 2.
4.In 25 percent of all cases, when two
photons go in different directions, Alice
does not know which photon went to
which detector. This inability for Alice to
distinguish between the two photons
induces quantum weirdness. By the very
fact that the two photons are now
indistinguishable, the M photon loses its
original identity and becomes entangled
with A.
5.The polarization value for each photon is
now indeterminate, but since they travel
toward different detectors, Alice knows
that the two photons must have
complementary polarizations.
Since message photon M must have
complementary polarizations to photon
A, then the other entangled photon (B)
must now attain the same polarization
value as M. Therefore, teleportation is
successful. Indeed, Bob sees that the
polarization value of photon B is 45
degrees: the initial value of the message
photon.
7. The NMR Chloroform Prototype
Although quantum computers were predicted some years ago, the
engineering obstacles were considered prohibitive. Additionally,
quantum computers were not expected to be produced, even in
prototype, until the year 2025. Despite predictions, Gershenfeld and
Chuang at MIT built the first prototype in the summer of 1998 .
(Gershenfeld and Chuang, Scientific American) Although there are many
quantum computer designs, Gershenfeld and Chuang chose one based
on nuclear magnetic resonance (NMR) principles.
7.1 Basic design
In a NMR-type quantum computer, the atoms are used as
qubits. Also, Gershenfeld and Chuang chose a liquid CPU
containing two ounces of chloroform. The carbon-hydrogen
atoms of chloroform each act as XOR gates, or in the jargon
of quantum computers, controlled-NOT gates. The atoms
are programmed through a sequence of radio pulses, and
the answer is read through standard NMR detection
techniques. The CPU is a two-bit ?circuit? with about 1023
molecules. Each atom has a two-spin state, a chemical
spin and an atomic spin. The two spin types used together
provide 2-bits, and when used in conjunction with the other
atom of the molecule, the molecule provides an effective
XOR gate.
Each atom acts like a bar magnetic when in an external
magnetic field, the atoms aligning parallel (spin 1) or
antiparallel (spin 0) to the field. Using a radio pulse, the
atoms can be made to flip between states. This is the
atom?s so-called chemical spin.
An atom?s atomic spin causes it to precess in the
magnetic field. Depending on its chemical spin alignment, it
will rotate clockwise or counter-clockwise, much like a
gyroscope.
7.2 Controlled-NOT Gate
The Controlled-NOT gate is a better description of the XOR
gate because it is a two-bit gate where one input controls
the inversion property of the other input. Call one input line
the Control, and the other input line the NOT input. The
NOT function works only if the Control line is set. Any input
to the NOT line is ignored if the Control is not set. The truth
table below is for the Controlled-NOT gate. Recall that the
XOR gate, or the Controlled-NOT gate,. is a universal gate,
and therefore any circuit can be made from just this one
kind of gate.
LINE
1
(Control)
LINE 2
(NOT)
OUTPUT
0
0
0
0
1
0
1
0
0
1
1
1
Figure 6 diagrams of how a controlled-NOT gate works at
the atomic level. The nature of the molecule works for the
quantum computer because the chemical spin has slightly
more energy in one alignment than the other. The hydrogen
atom works like the control input, and the carbon acts like
the NOT input. If the carbon is parallel aligned (spin 1) with
the magnetic field, then a properly tuned radio signal can
cause it to flip to be aligned antiparallel (spin 0) if the
hydrogen is in the aligned position (state 1). If the hydrogen
atom is in state spin 0, then the carbon will not flip states
even with the radio pulse. (Similarly, the carbon atom can be
flipped from state 0 to state 1 when hydrogen is in state 1.)
Two radio pulses are required to affect a carbon state
transition, one for precessing and one for alignment. In this
way, the quantum computer sends a programmed series of
radio pulses at the molecules to set and reset the various
bits of the ?molecular registers?. In contrast to the
classical computer, which sends bits through gates to
perform computation, the quantum computer sends the
gates at the qubits to perform computation.
By throwing a programmed set of radio pulses at the
molecules, and the numerous quantum gates within,
Gershenfeld and Chuang implemented Grover?s search
algorithm to select a marked item in an unsorted list of
items. Their quantum computer performed the equivalent of
opening a two-number combination padlock and in few
number of average tries than a classical computer would
need.
8. Conclusion
This paper is meant to be an overview of the marvelous ideas of
quantum computing, its concepts, and how quantum theory allows
technological jumps in the computer industry that will revolutionize the
practical computing world. Quantum computes are coming, and they will
require a new way of looking at computing. Applications that can not be
done now are easily possible with quantum computers. The spin-off
concepts, like quantum teleportation, open vistas only imagined before.
Computer science is still immature for its barely 80 years, and this
radical divergence from the traditional development path is one indicator
that. Who knows what the next 870 years will bring?