|
��������� REPORT DOCUMENTATION PAGE
|
����������� Form Approved
�������� OMB No. 0704-0188
|
|
Public reporting burden for this collection of information
is estimated to average 1 hour per response, including the time for reviewing
instruction, searching existing data sources, gathering and maintaining the
data needed, and completing and reviewing the collection of information. Send
comments regarding this burden estimate or any other aspect of this
collection of information, including suggestions for reducing this burden, to
Washington headquarters Services, Directorate for Information Operations and
Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302, and to the Office of Management and Budget, Paperwork Reduction Project
(0704-0188) Washington DC 20503.
|
|
1.� AGENCY USE ONLY (Leave blank)
|
2.�� REPORT DATE�
September 1999
|
3.� REPORT TYPE AND DATES COVERED
Master�s Thesis
|
|
4.� TITLE AND SUBTITLE�
QUANTUM COMPUTERS AND THEIR IMPACT ON DoD IN THE 21ST
CENTURY
|
5.� FUNDING NUMBERS
|
|
6.�� AUTHOR(S)
Mades, John E.
|
|
|
7.� PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)
Naval Postgraduate School
Monterey, CA� 93943-5000
|
8.�
PERFORMING� ORGANIZATION� REPORT NUMBER
���
|
|
9.� SPONSORING / MONITORING AGENCY NAME(S) AND ADDRESS(ES)
|
10. SPONSORING / MONITORING
�����
AGENCY REPORT NUMBER
|
|
11.� SUPPLEMENTARY NOTES�
The views expressed in this
thesis are those of the author and do not reflect the official policy or
position of the Department of Defense or the U.S. Government.
|
|
12a.� DISTRIBUTION / AVAILABILITY STATEMENT�
Approved for public release;
distribution unlimited.
|
12b.
DISTRIBUTION CODE
|
|
13. �ABSTRACT (maximum 200 words)
Computer processor speeds
double every eighteen months according to Moore�s law.� This growth will
reach a limit by the year 2020.� Quantum computation is one proposed
alternative to bypass this limitation.� This thesis explores the topic of
quantum computation.� Specifically, we address what is a quantum computer,
its various proposed implementations, its technological feasibility, and its
military applications.� Recent experiments have provided a proof of concept
for quantum computation and some researchers believe that a working model
could be developed within a reasonable time period.� This success has caused
a marked increase in the interest in quantum computers and their proposed
potential.� We attempt to separate fact from fiction to see what possible
benefits the Department of Defense could obtain from it.
|
|
14. �SUBJECT
TERMS�
Quantum Computers, Quantum Parallelism, Teleportation,
Quantum Communication, Quantum Cryptography
|
15.� NUMBER OF PAGES
�57
|
|
|
16.�
PRICE CODE
|
|
17.� SECURITY CLASSIFICATION OF REPORT
Unclassified
|
18.�
SECURITY CLASSIFICATION OF THIS PAGE
Unclassified
|
19.� SECURITY CLASSIFI- CATION OF ABSTRACT
Unclassified
|
20.� LIMITATION OF ABSTRACT
UL
|
|
|
|
|
|
|
|
NSN 7540-01-280-5500����������������������������������������������������������������������������������������������������������
Standard Form 298
(Rev. 2-89)�
�������������������������������������������������������������������������������������������������������������������������
Prescribed by ANSI Std. 239-18
Approved for public release; distribution is unlimited
QUANTUM COMPUTERS AND THEIR IMPACT ON DoD IN THE 21ST
CENTRUY
John E. Mades
Captain, United States Marine Corps
B.S.,University of Houston, 1990
Submitted in partial fulfillment of the
requirements for the degree of
MASTER OF SCIENCE IN COMPUTER SCIENCE
from the
NAVAL POSTGRADUATE SCHOOL
�June 1999
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
Wolfgang Baer, Co-Advisor
Since its inception, the Electronic Warfare Integrated Reprogramming
Database (EWIRDB) has emerged as the primary Department of Defense (DoD)
approved source of electronic warfare (EW) data.� Its utilization in the
areas of battle planning and EW research enables our military forces to
effectively exploit the electromagnetic spectrum and ultimately shape the
outcome of battle.� The usefulness of the EWIRDB, however, is hampered by
its cumbersome and non-intuitive representation of data.
The primary goal of this thesis is the development of a
semantically-improved conceptual design of EWIRDB data based on the
object-oriented data model (OODM).� The secondary goal of the thesis is the
specification of a logical design, based on the new conceptual design, to
provide the structure for a subsequent implementation of EWIRDB data on the
Multimodel and Multilingual Database System (M2DBS) in the
Laboratory for Database Systems Research at the Naval Postgraduate School.
The work contained herein confirms the utility of the OODM in
representing EWIRDB data, shows the new OODM-based conceptual design to be
superior to that which currently exists, and specifies a logical design for
an M2DBS implementation of sample EWIRDB data.
sor
|
|
|
|
|
 |
|
|
|
Dan Boger, Chairman
Department of Computer Science
|
|
QUANTUM COMPUTERS AND THEIR IMPACT ON THE DEPARTMENT
OF DEFENSE IN THE 21ST CENTURY
John E. Mades - Captain, United States Marine Corps
B.S., University of Houston, 1990
Computer processor speeds double every eighteen months
according to Moore�s law.� This growth will reach a limit by the year 2020.�
Quantum computation is one proposed alternative to bypass this limitation.�
This thesis explores the topic of quantum computation.� Specifically, we
address what is a quantum computer, its various proposed implementations, its
technological feasibility, and its military applications.� Recent experiments
have provided a proof of concept for quantum computation and some researchers
believe that a working model could be developed within a reasonable time
period.� This success has caused a marked increase in the interest in quantum
computers and their proposed potential.� We attempt to separate fact from
fiction to see what possible benefits the Department of Defense could obtain
from it.
Master of Science in
Computer Science-September 1999
Advisor: Neil C. Rowe,
Department of Computer Science
Co-Advisor: Wolfgang Baer,
Department of Computer Science
����������������������������������������������������������������������������������������������������������� ����������
Unclassified/A
Table of Contents
I.������ INTRODUCTION................................................................................................................................... 1
II.���� BACKGROUND..................................................................................................................................... 5
A.���� FEYNMAN�S APPROACH............................................................................................................... 7
B.���� DEUTSCH�S CONTRIBUTION......................................................................................................... 9
C.���� BELL�S THEOREM........................................................................................................................... 11
III.������� WHAT IS A QUANTUM COMPUTER?...................................................................................... 13
A.� PROPERTIES OF QUANTUM COMPUTATION........................................................................... 13
1.����� SUPERPOSITION......................................................................................................................... 14
2.����� ENTANGLEMENT....................................................................................................................... 14
3.����� LOGICAL/PHYSICAL
REVERSIBILITY.................................................................................... 15
4.����� COHERENCY................................................................................................................................. 17
5.����� TIME-INDEPENDENCE............................................................................................................... 17
6.����� OUTPUT INTERROGATION...................................................................................................... 18
B.���� A GENERAL QUANTUM COMPUTER MODEL........................................................................ 18
IV.������� REALIZATIONS.............................................................................................................................. 21
A.���� QUANTUM GATE MODEL............................................................................................................ 21
B.� EXAMPLES OF QUANTUM GATES............................................................................................... 23
C.���� QUANTUM WIRES......................................................................................................................... 27
D.���� I/O PROBLEM................................................................................................................................... 28
E.����� CHUANG�S PROOF OF CONCEPT................................................................................................ 29
F.����� SUMMARY OF IMPLEMENTATION APPROACHES.............................................................. 31
V.���� A QUANTUM COMPUTER SIMULATOR...................................................................................... 37
VI.������� CAPABILITIES OF QUANTUM COMPUTERS........................................................................ 41
A.���� QUANTUM ALGORITHMS........................................................................................................... 41
B.���� NP-HARD/COMPLETE PROBLEMS............................................................................................. 42
C.���� QUATUM TELEPORTATION AND COMMUNICATION....................................................... 43
D.���� TECHNOLOGICAL FEASIBILITY................................................................................................. 43
VII.������ POSSIBLE MILITARY APPLICATIONS.................................................................................. 45
A.���� INTELLIGENCE................................................................................................................................. 46
1.����� CRYPTOGRAPHY........................................................................................................................ 46
2.����� PHOTO ANALYSIS..................................................................................................................... 46
3.����� DATA FUSION............................................................................................................................. 46
4.����� SCAN OF
ELECTROMAGNETIC SPECTRUM....................................................................... 47
5.����� SECURE DISTRIBUTION OF
DATA........................................................................................ 47
B.���� ARTIFICIAL INTELLIGENCE......................................................................................................... 48
C.���� ACQUISITIONS................................................................................................................................ 48
VIII.���� CONCLUSION................................................................................................................................. 51
LIST OF FIGURES
Figure 1......................................................................................................................................................... 13
Figure 2......................................................................................................................................................... 19
Figure 3......................................................................................................................................................... 21
Figure 4......................................................................................................................................................... 22
Figure 5......................................................................................................................................................... 23
Figure 6......................................................................................................................................................... 24
Figure 7......................................................................................................................................................... 26
Figure 8......................................................................................................................................................... 38
LIST OF TABLES
Table 1.......................................................................................................................................................... 16
Table 2.......................................................................................................................................................... 31
Table 3.......................................................................................................................................................... 43
Table 4.......................................................................................................................................................... 49
Moore�s law provides a rough estimation for the
extrapolation of computer processor speeds over time.� Moore�s law states that
�Computer processor speeds double every eighteen months�.� But there is a
limit: Reference 1 asserts that with the current technology the physical limit
for processor speeds will be reached in the year 2020.� The current technology
relies on placing more transistors in a smaller area on the microprocessor
surface in order to increase computing speed (clock speed).� Concomitantly
there is a heat dissipation problem due to the increased number of transistors
per unit area.� Therefore by extrapolating the energy dissipation trend the
current technology should reach the thermal noise limit for the atomic level
around the year 2020 [Ref. 1].� At this point we will have entered the quantum
realm.� Additionally, there is an economic concern in that the cost of
constructing �clean� rooms to produce semiconductors doubles every three years
[Ref. 1, p. 11].� At this rate, the cost of producing a new semiconductor plant
in 2020 will reach the trillion-dollar level.� Clearly this would be
prohibitive to business.� What do we do then? Quantum computation is one of the
areas being explored to answer this question.
How does this pertain to us in the
Department of Defense? The military mirrors society in many aspects, one of
which is the ubiquitous use of computers.� We in the military currently use computers for everything
from administration to target guidance.� The Joint Vision 2010 [Ref. 21] points
out �This era will be one of accelerating technological change.� Critical
advances will have enormous impact on all military forces.� Successful
adaptation of new and improved technologies may provide great increases in
specific capabilities.� Conversely, failure to understand and adapt could lead
today�s militaries into premature obsolescence and greatly increase the risks
that such forces will be incapable of effective operations against forces with
high technology.�� Therefore we must examine new areas of technology that could
represent a significant benefit to our warfighting capability.� Quantum
information systems is an area of new technology that could provide that
benefit and the potential payoff is enormous.� The arena of information systems
is one of the pillars of our warfighting ability and one of our greatest
vulnerabilities.� We depend upon the unfettered access to the electromagnetic
spectrum, whether through electromagnetic waves or wires.� However, DoD
computer systems endure hundreds of� �cyber� attacks every day.� To continue
our quest for the �high ground� we need to explore new technologies as they are
being discovered.
Applications for DoD cryptographers
could include quantum cryptography, new ways to break and make codes, which
with the explosion of the Internet could help better secure the safety of DoD
computer systems.� Additionally, quantum computers can offer a solution to
these needs.� Through �quantum parallelism� the Schor algorithm for quantum
computation may be able to assist in breaking some of today�s unbreakable codes
or developing stronger ones.� �Quantum parallelism� may allow us to build
neural nets that can learn more quickly and may allow us to solve some of the
more interesting computation problems known as NP-hard/complete. �
��������� Imagine a radio intercept system that collect over
the entire electromagnetic spectrum, simultaneously decrypting and providing
real-time scanning for key words or phrases could be possible.� Imagine a
computer system that allows artificially intelligent systems to process
exponentially faster because it can reason millions of ways in parallel.
Cryptographic key exchanges could be 100% secure with the ability to detect
eavesdroppers.� The possibility of these conjectures was relegated to science
fiction until recently due to limitations in computer speed and system
�knowledge�.
Isaac Chuang�s recent experiment
using Nuclear Magnetic Resonance (NMR) techniques to apply Grover�s Algorithm
has generated increased interest in the realization of quantum computers.� In
the fall of 1997 when our group began preliminary research into quantum
computers, a search of the Internet found maybe 20 sites pertaining to quantum
computation.� One year later there are over 1,800 sites.� This shows the
remarkable interest in the potential for quantum computing.� Additionally, as
noted in Ref. 2, quantum mechanics provides a better explanation of physical
reality than classical mechanics and can therefore provide more information
about the �complexity� or �knowledge� of the system [Ref. 8, p. 97].
However, this interest should be
tempered with a sense of caution.� The results of quantum mechanics are well
documented experimentally, but academic understanding will not automatically
yield an engineering success.� There are several impediments to the
construction of a quantum computer: decoherence, size, economic factors etc.�
Therefore we must proceed toward the goal of constructing a quantum computer
with those impediments in mind.
This paper will explore quantum
computing by explaining what a quantum computer is, why we should choose to
build one, how we could implement one, and its limitations and advantages for
military needs.
In quantum mechanics, a system can be
interpreted as existing in a superposition of states simultaneously, such as a
bit of information being both a 1 and a 0 at the same time.� This superposition
of states is the key to the possible exponential increase offered by computing
at the quantum level.� Each of these states can separately perform calculations
for the solution of a problem.� However a theoretical impediment to quantum
computing is the lack of a machine model.� The Turing model of computation,
developed by Alan Turing, appears inadequate to describe the computational
processes occurring.� In the Turing model, questions of how to implement the
reading of the data tape and writing to the data tape are ignored, essential
questions that cannot be ignored under quantum computing.� Therefore, a new
model must be developed to describe and formalize the process.� This new model
should be based on applied mathematics or physics in order to more accurately
give insight into the quantum computational process.� No longer can we think of
data as just 1�s and 0�s, but as the probabilities of a 1 or 0, representing
superposition of states.� Additionally, the quantum computer can no longer be
thought of as a tape head and an infinitely long tape.� In accordance with
quantum mechanics we must think of the tape as a system described by the state
function Y(t) that evolves
over time to perform the calculation.
Classical computer systems perform
computation by sending an electric signal through a circuit in conjunction with
a timing signal.� This signal is independent in that it does not require
interaction with any other signal in order to perform its calculation.�
Calculations performed in this manner take place through space (the
microprocessor) and time (the length of time required to traverse the
circuit).� A quantum computer system performs its calculations by controlling
the memory evolution over time.� Quantum computations must be prepared in an
initial state, which would correspond with to �input�.� This input is then
transitioned to other quantum states by one of several methods (see table 2 in
section III for a list of methods).� Input to a general quantum computation is
now more than just the concatenation of its bits, because each input bit can
be� �entangled� with its neighbor and each bit is in a superposition of states.�
Entanglement is �a property of correlated pairs of quantum systems�[Ref. 1,
p.180].� Two elements can be entangled if they are emitted by the same source
at the same time as in the case of photons in an Einstein-Podolsky-Rosen (EPR)
experiment.� A good model of entanglement is a linear system of four blocks
attached to each other by springs while the springs are in tension.� A block in
this system cannot be moved without influencing its neighbors.� In this way
calculations are dependent not only upon the evolution of the system in time,
but the interaction of the input bits as they evolve over time.
Classical computer systems have an
understood and well-defined computational model known as the Turing model.�
This model was developed independently by four men, Alan Turing, Alonso Church,
Kurt G�del, and Emil Post, and is a mathematical model for the computing
process.� The Turing machine consists of an infinite �tape� in two directions
with a �head� that is capable of reading and writing to the �tape�.� The tape
is� prepared such that data and a �program� (set of instructions) are resident
on the �tape�.� The �program� or set of instructions is run on the machine
using a finite-state machine model that allows it to read and write to the
�tape� and then halt.� The tape is pulled past the tape head to allow it to
read and write to the tape.� This model provided the insights necessary for the
construction of the modern �universal computer� like the personal computer that
sits on your desk at work, a machine just as capable of doing your word
processing as it is at playing a video game.�
The Turing model is discrete and
works well when we are working with a classical interpretation of physical
reality.� However, questions regarding how and when one reads and writes to the
�tape� cannot be ignored with a quantum computer since if we �look� at the tape
before the computation is finished we have altered the answer, according to
quantum mechanical theory (Heisenberg uncertainty principle).� Therefore, when
we implement a quantum computer we can try to simulate it with a classical
system or choose a physical system that can change over time in order to
provide us with the desired calculation. The first case is impossible and the
reasons are explained in reference 2.� However, with the second we must be
careful in our selection of the physical system because not every physical
system will provide a meaningful calculation or be �universal�.� An
uninteresting physical system for calculation is a brick.� If the brick is
elevated off the ground and then dropped we could consider that a calculation
of its trajectory; however, it is not scalable to our current technology
standards and is not expandable to do other calculations.
We discuss now two seminal papers
that form the foundation of study in this field, references 2 and 8.�
Feynman�s paper [Ref. 2] is concerned
about simulating physics with computers and trying to create a simulator for
quantum mechanics.� Therefore, he does not address the �universal quantum
computer�.� Feynman describes the general attributes that are necessary for a
computer to simulate physics correctly as ��that there is to be an exact
simulation, that the computer will do exactly the same as nature.�� The
stipulation of an exact simulation is understood to be a fidelity measure of
the system: We should expect the same results from the computer as from
nature.� Additionally, he points out that �The rule of simulation that I would
like to have is that the number of computer elements required to simulate a
large physical system is only to be proportional to the space-time volume of
the physical system.�� He would consider simulation a failure if in order to
simulate physics he would have to build a computer that would be excessively
large.� Also the number of elements should not increase exponentially with the
given problem and should not take the lifetime of the universe to solve.
Feynman then makes the point that
computers imitate time rather than simulate it, with discrete state
transitions.� If a computer is to simulate quantum-mechanical processes, it
must simulate probability.� Discrete systems can accomplish this through
various means, one of which is modeling it with Markov chains.� A Markov chain
is a way of modeling a stochastic process by assuming that the system can be in
one of a finite number of states; the probability of being in a state is
dependent only on the state that immediately preceded it in time and not any of
the other states that it had to pass through to get to the current state.� A
Markov process would not produce the kind of fidelity that Feynman is referring
to because the information in it is less than the information representible in
a quantum one.� Feynman uses the example of a system with R particles, where
probabilities must be assigned for each particle�s position x such that each
particle has one of a finite set of positions x1 , x2 ,
�, xR� at time t.� Then a k digit number can be assigned as the
probability for the given particle at that position at that time.� One problem
with this model is that one must ignore the probability that some occurrences
might happen, for example: �If the probability of something happening is 10-700
, we say it isn�t going to happen� [Ref. 2, p. 472].� The second problem is you
would need a separate k-digit number for R particles in every configuration of
the system and for all N points in space.� The ability to store and simulate
this much information is beyond the capability of classical computers
currently; therefore, he concludes that a direct simulation is not feasible.�
However, the task may be handled by a system which imitates nature.� The two
choices that he presents are a probabilistic classical computer or a natural
system that can simulate the computation.� The answer he provides for utilizing
a probabilistic classical computer is a definitive no because classical systems
cannot replicate the true randomness found in nature.� Therefore we should
simply observe an imitative system and record the answer.� Feynman does not
offer a specific system or design for a universal quantum simulator; rather he
states that �we should try to find out what kinds of quantum mechanical systems
are mutually intersimulatable, and try to find a specific class, or a character
of that class which will simulate everything�.�� Although Feynman�s tone is
somewhat doubting, he later wrote a follow-up paper [Ref. 9] to revise his
initial thoughts here and expound on the ideas brought out in David Deutsch�s
paper.
In 1985, from a different perspective
than Feynman, Deutsch approached quantum computing through the Turing or
Church-Turing hypothesis [Ref. 8]: �The assumption that the intuitive notion of
�computable function� can be identified with the class of partial recursive
functions�� [Ref. 10, p. 166].� Deutsch paraphrases this as: ��Every �function
which would naturally be regarded a computable� can be computed by the
universal Turing machine� [Ref. 8, p. 99].� He refers to this as the weak form
of the Church-Turing hypothesis, because the language does not reflect concepts
that are easily definable for physical systems.� So he restates the hypothesis
as the Church-Turing principle: �Every finitely realizable physical
system can be perfectly simulated by a universal model computing machine
operating by finite means� where �a computing machine M is capable of perfectly simulating a
physical system J,
under a given labeling of their inputs and outputs, if there exists a program p(J) for M
that renders M computationally
equivalent to J under that
labeling.� In other words, p(J) converts M into a �black box� functionally
indistinguishable from J.�
[Ref. 8, p. 99].� Computational equivalence is important to computer science
because that is where we derive the �universal computer�, a machine that can
compute any function that a Turing machine can compute.� Deutsch says that both
a Turing machine and a quantum computer operate by finite means: �(i) only a
finite subsystem (though not always the same one) is in motion during any one
step, and (ii) the motion depends only on the state of a finite subsystem, and
(iii) the rule that specifies the motion can be given finitely in the
mathematical sense (for example as an integer).� [Ref. 8, p. 100].� He shows
that there is no difference between a machine that alters the input state
(classical computer method) in order to calculate/compute and one that alters
its constitution to become a different machine computing a different function
(quantum computer method). Thus Deutsch establishes a case for computational
equivalence between a Turing machine and a universal quantum computer.
Deutsch argues that it is not
physical laws which inhibit us from �computing� certain functions, but the
algorithms designed for the classical systems.� Therefore, if we were to
develop a universal quantum computer and the algorithms that utilize it then we
might expand our pool of �computable� functions.� A �universal quantum
computer� could simulate �ideal closed (zero temperature) systems, including �
quantum computers and quantum simulators, with arbitrarily high but not perfect
accuracy.� [Ref. 8, p.102].� So Deutsch claims that perfect accuracy is not
required because he is investigating the quantum simulator not quantum
computer.� Deutsch provided the impetus to expand this area of research to its
present state with this comment.
C. �BELL�S THEOREM
Quantum computers are only one area of research in quantum information
systems.� Other areas include quantum communication and quantum cryptography,
which use Bell�s inequality.
When quantum theory was developed,
several prominent scientists disagreed with a part of the theory known as quantum
nonlocality.� The problem is this:� �Classical physics holds that any
relationship existing between two or more particles must be mediated by a local
force-attraction, repulsion, or at least some signal.� Quantum mechanics
predicts that two particles can be correlated instantaneously in the absence
of any such force or signal�� [Ref. 11, p. 65].� Einstein together with Podolsky
and Rosen (EPR) argued that a thought experiment developed by David Bohm to
test the validity of quantum nonlocality proved it impossible.� The thought
experiment is formulated as two particles shot off from a common source toward
opposite sides of a room.� According to quantum mechanics the spins of the two
protons, when measured, should be instantly correlated-- that is, when the spin
of particle A is found to be �up�, the spin of particle B should be found to be
�down�, at exactly the same moment.�� If the measurement of proton A can
produce an instantaneous effect on a distant proton B, then it should be
possible to detect an intruder �wiretapping� a communication channel built from
a stream of protons A.� Spin is essentially a measurement of the angular
momentum of a particle and is inherent in sub-atomic particles.� Einstein saw
this as a paradox because in order for B to �know� what A�s spin was (under
classical physics) a signal would have to travel between A and B
instantaneously.� This is not allowed under relativity (nothing can travel
faster than the speed of light). Bell showed that there is no paradox because
this cannot be explained by classical physics, only by the laws of quantum
mechanics. Intuitively, we can say that the two spins are �entangled� to begin
with and thus no information need be transmitted later between A and B.
��
�
To understand what a quantum
computer is, we will start with a common reference point: a personal computer.
�Intuitively, a computing machine is any physical system whose dynamical
evolution takes it from one set of �input� states to one of a set of �output�
states.� The states are labelled in some canonical way, the machine is prepared
in a state with a given input label and then, following some motion, the output
state is measured.� [Ref. 8, p. 97].� We can illustrate this idea in the figure
below.
Figure 1
There exists a computational equivalency between this
model and a quantum computer. In both cases the computation is considered to be
generated by the time evolution of a computer memory from an initial to a final
state.� In a quantum computer it is not the state of the memory but the
probability of measuring a state that is propagated in time.� However, this is
only the beginning.� To design a quantum computer we must add mechanisms to
implement superposition, entanglement, logical/physical reversibility,
coherency, time-independence and output interrogation.
����������� In a classical computer one bit of information is
stored as either a certain 1 or a certain 0.� In quantum systems, on the other
hand, one �qubit� of information will reside in a superposition of states as a
1 or 0 or both, before measurement.� If we measure the system we collapse the
wave function (Y(t))
and the most likely answer to that point in time will be the result of our
measurement.� Before measurement, a qubit register n qubits long represents 2n
states of information.� This is a substantial increase over a classical system,
and can be especially powerful if the qubits are correlated or �entangled�.�
Superposition is a necessary but not sufficient condition in and of itself to
derive the benefits of quantum computation.� We can perform a calculation with
data that has been placed in a known superposed state.� However, this is
performance of a classical calculation with a quantum system, because once the
calculation is complete and we measure the result we only get the single value of
that qubit at that time rather than the average of all the values that that
qubit had been.
����������� An additional requirement for quantum computation
is correlation or �entanglement� of the qubits.� �Entanglement allows one to
encode data into non-trivial multi-particle superpositions of some preselected
basis states� [Ref. 23, p.1].� Stated another way, entanglement provides the
additional condition necessary for quantum computation because it is the
interaction of the qubits through time and superposition that provides
the �quantum parallelism�.� Quantum parallelism allows us to perform
calculations on the 2n states simultaneously.� When we measure a
superposed and entangled quantum system we get one set of the values that the
qubit(s) had been after the calculation. Obtaining more than two entangled
particles is very difficult, however.
����������� The condition of logical reversibility refers to
an observer�s ability to infer the input from a given output.� A stipulation of
maintaining a quantum system is that it be physically reversible, which
requires that the wave function not be collapsed due to the physical process
(qubits passing through a quantum gate).� Physical reversibility is required
because the fundamental behavior of nature is time-reversible.� Time order is
impaired by measurement, which also increases entropy and looses information.�
If a quantum calculation is to proceed without the loss of information, the
calculation must be carried out in a physically reversible system.� Physical
reversibility also says that when a quantum element (qubit) undergoes a
physical interaction, that interaction cannot change the time-independence or
coherence (a concept explained shortly) of the quantum element.� The only
exception to the condition of reversibility in a quantum computation is the
final step (when we read out our answer).� A way of ensuring this is make
quantum gates and quantum circuits logically reversible.� The table below
illustrates a logically reversible controlled XOR exclusive-or.
Table 1
|
|
Input # 2
|
Output #1 (Answer)
|
(control bit)
|
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
|
1
|
1
|
0
|
1
|
As we can see from the table if the inputs are the same then
the �answer� is 0, if the inputs are different then the �answer� is 1.� Thus we
can infer input 1 from output 1 and output 2 through another XOR operation:
(output 1 XOR output 2 = input 1). Output 2 is the control bit for the
operation and is the same as the input 2; therefore we have retrieved the input
from the output and the operation is logically reversible.� The Toffoli gate is
an example of a quantum gate that performs a similar type of calculation;
however it has three inputs and three outputs.�
The extent to which a system must be reversible
has not been fully explored.� It is possible that quantum error correction can
compensate for irreversibility.� Classical error correction uses extra bits
incorporated into a signal to determine bitwise parity deviations from the
original signal.� Similarly, quantum error correction could use extra qubits to
determine errors in a set of qubits.� Notwithstanding, it is doubtful whether
quantum error correction can compensate for both losses due to coherency and
losses that would naturally occur due to qubit interactions with quantum gates.
����������� Coherency losses are the major problem for a practical
quantum computer.� Coherency is the absence of a coupling between a quantum
system and its environment.� �Decoherence is more insidious.� Rather than a
gross bit flip, decoherence is a coupling between two initially isolated
quantum systems (the qubits and its environment) that tends to randomize the
relative phases of the possible states of the memory register.� [Ref. 1,
p.215].� Solving decoherence means to effectively isolate the quantum system
from its environment.� This coupling causes a quantum-mechanical effect to lose
its quantum properties and become a macroscopic event.� Some techniques
currently employed to reduce decoherence include thermal isolation (low
temperatures from cryogenic cooling or other methods), electromagnetic
isolation, and radiation shielding (from cosmic rays and other interference).�
Perfect coherence is not an attainable goal because we can never fully isolate
a given system from all effects; therefore we try to limit those effects during
a given time period in a given space.
����������� Time independence means that the calculating
elements do not change over time.� In a classical system a computational
element can perform different operations at different times because the
calculation steps are transitions between distinct system states.� However,
within a quantum calculation we cannot be so definite.� For example, can a
quantum gate be an XOR gate at time t1 then at time t2
a NOT gate?� We think not.� The reason is that we cannot be sure at what
time the qubit leaves the gate, so we cannot �know� when to change the gate to
something else.� We cannot be sure when the qubit �leaves� the gate because it
is in a quantum-mechanical state and has a probability of being everywhere at
anytime within the system.� If quantum gate arrays are required to be
time-independent, we cannot use switchable circuits to perform quantum
calculations.
����������� Once the quantum calculation has been performed, we are left
with an answer that resides in a superimposed and entangled state.� We could
directly measure this state.� That measurement would yield one of all possible
answers of the calculation and does not utilize the full potential of quantum
computing. Instead, a major benefit of quantum computing is its ability to
extract some overall property of the calculation (average, frequency etc.)[Ref.
24].� To extract this property we must have an output interrogator.� This interrogator
allows us to sample the quantum answer in a time-independent manner.� This
permits us to preserve the quantum nature of the answer and extract the overall
property that we are interested in.� We can then display the result from the
output interrogator in histogram form for us to interpret.��
The following figure represents a
model for a quantum computer which calculates the following function.
Equation 1
where x and y are variables
and a, b, and c are constants.� Classically this would require���������� (2m
�1)(2n �1) calculations.� A quantum computer would require only
one.� Here is how this calculation is done.
Figure 2
A common source emits
entangled particles that are then put into a superposed state.� At the
�entangled state input� position, quantities x and y have been
transformed into qubits and have (2m �1) and (2n �1)
possible values respectively.� We can perform a calculation with these qubits
with some quantum circuit.� Let us say that we calculate� �(x, y, a, b, c).
Then the circuit performs
the calculation on all the superposed states at the same time by transforming
the wave function Y(t) into another wave
function Y�(t)
while preserving logical/physical reversibility, coherency and time
independence.� The completed calculation is shifted to the �entangled answer�
register.� We now interrogate this answer according to what overall property of
the function we are looking for (average, frequency etc.).� In the case above
we need a summation and the output interrogator is constructed for that
purpose.� The output of the interrogator is the overall property of the
function we want to calculate and is displayed in histogram form.� In an ideal
machine only one answer will appear.� In practice the histogram is generated
instead of a single answer because noise and other calculation errors will
broaden the single answer peak.����
Digital computers process information
by routing bits (signals or voltages) through switches or gates.� These gates
can be thought of as rudimentary logical operations.� Typical gates are the
AND, OR, NOT, NAND, NOR and XOR (exclusive-or).�
�
Figure 3
By interconnecting these gates, their operations can be
strung together to form more complex operations such as addition and
multiplication. It is the bit/signal/voltage that is routed through the gate.�
Conversely, in a quantum system the
gate is passed through the data, and it is the interaction between the bits
(qubits) that is important.� Additionally, the number of inputs must be equal
the number of outputs for a quantum gate because otherwise information would be
irreversibly destroyed and the input cannot be inferred from the 
output.� Two proposed
exceptions are the FANOUT and ERASE gates pictured below.
Figure 4
Here both the FANOUT and ERASE have the number of inputs
equal to the number of outputs, but one input for the FANOUT is a constant and
one output for the ERASE is constant.� It is thought that the FANOUT gate
cannot be constructed because it would require the copying of the information
contained in the quantum state which is not possible.� The ERASE gate on the
other hand is possible because destruction of information occurs naturally as a
result of decoherence and other effects.
The following figure illustrates a
Toffoli quantum gate, one of the universal gates proposed for a quantum
computer.
Figure 5
As the qubits pass from left to
right into the gate along �quantum wires� the gate performs an elementary
logical operation on the qubits. Qubits A and C pass through the gate
unchanged, while B is an XOR of qubits A and C.� The gate is configured with
three inputs and three outputs because Toffoli originally reasoned that a
workspace (scratchpad) bit was required when the gate calculation was done.�
Reference 22 provides a strong argument that this workspace bit is not required
and the controlled-XOR discussed in chapter III is sufficient.�
With
these specifications in mind, can any implementations provide us with a quantum
gate?� Here is an example [Ref. 13].
Figure 6
The
figure is of a quantum electrodynamic (QED) cavity.� Sources A and B supply
two-state particles that are qubits.� The qubits are encoded by spin, meaning
that a spin �up� particle is a 1 and a spin �down� is a 0.� A particle is
passed from A through the cavity while it is in resonance established by short
pulses of laser energy (the laser is not part of the diagram).� This transfers
the particle�s state �information� to the cavity (the exact process is
QED-specific).� A particle from B is then passed from R to R-1 through
the cavity; the particle�s state is changed to the exclusive-or of its initial
state.� R, R-1 and Rz(θ) are Ramsey zones.� The
Ramsey zones act as a sensor to let us know when the qubit has left the gate.�
Ramsey zones �sense� atomic oscillations and are named for Norman F. Ramsey.�
This implementation meets the requirements of logical/physical reversibility,
coherence and time independence.� Entanglement would be achieved by correlating
multiple cavities.� Physical reversibility follows because if we take particle
B and run it backwards through the gate we can change its state back to what it
was.� Logical reversibility follows because if we perform the XOR of A and B we
will get what B was originally.� Coherence is satisfied within the area of the
gate if the gate is cooled sufficiently to exclude thermal variations and is
properly shielded from outside sources of radiation (the cavity provides a
degree of isolation).� However, the loss of coherence between gates could be a
problem.� Time independence is met because the gate itself does not change with
time and the system has been sufficiently shielded from external influences.
Several
quantum-mechanical apparati have been proposed as possible implementations as
quantum gates that do not completely meet the requirements for a quantum gate,
as for instance:
Figure 7
Here a flow of two-state
particles, similar to the previous example, are passed through a QED cavity.�
When the stimulating laser is activated, the cavity resonance will flip the
spin of the particle.� The claim is if we know the spin of the particle before
it goes into the cavity and the cavity is in resonance, then the output
particle will have opposite spin to that of the input particle; this simulates
an XOR gate.� This model does comply with the stipulations of logical/physical
reversibility, coherence and time independence.� However, when we turn on the
laser we are choosing which particles we flip the spin on.� Then it cannot be a
quantum process; if we know the spin that means we have somehow measured it.�
Additionally, how would you chain these apparati together to do a meaningful
quantum calculation?� You cannot, because you won�t know when to turn on the
other stimulating lasers to activate the other cavities.� If you did, it would
not be a quantum process.
Not
every developed �quantum device� could be a gate for a quantum computer.� For
example, a new quantum transistor developed at Sandia National Laboratories
utilizes a quantum phenomenon of �tunneling� to achieve much faster transistors
[Ref. 14].� This transistor called a DELTT (Double Electron Tunneling
Transistor) has its switches closed all the time.� The electrons pass to the
other side of the switch by tunneling when their energy is great enough but
still less than the potential energy required to surmount the open switch.�
According to classical mechanics a ball in a gravitational potential (say a
bowl) cannot escape the confines of the bowl unless sufficient energy is
imparted to it to have it roll over the lip of the bowl.� However, in quantum
mechanics there is a finite probability that the ball can �tunnel� through the
side of the bowl and emerge on the other side with far less energy than is
required to roll it out.� Products in the commercial market exploit this
phenomenon, like Charge-Couple Device (CCD) cameras.� Although this circuit element
is a quantum device it could not be utilized as a quantum computer gate because
it does not allow for reversibility: absorption destroys the quantum mechanical
information about the particle.
The last
section has shown how difficult it is to build quantum devices which do not
simply mimic a logic gate but which actually can be used as a building block
for quantum computers.� Once this problem is solved the gates need to be
connected with quantum wires.� What constitutes a quantum wire varies with the
implementation.� However, they need to preserve the three conditions stipulated
for quantum gates.� One proposed implementation of quantum wires is a ballistic
approach, which would shoot qubit particles between gates to achieve interconnection.�
This approach assumes a fairly high degree of shielding from the environment to
prevent decoherence between quantum gates.� Another approach is quantum
teleportation.� Quantum teleportation would �transport� a qubit from one gate
and materialize it in or at the next gate.� Quantum teleportation is explained
later.� As with quantum computation, a major hurdle in connecting quantum gates
is decoherence;� other problems include timing and stray particle
interactions.� Experimental confirmation of quantum wire implementations would
provide a major step toward the realization of a quantum computer.
Another major hurdle that must be
cleared before any quantum computer can be built is the I/O problem:� How do
you entangle more than two qubits at a time for input, how do you read the
answer when the calculation is done, and how do you know when it is done?
Entanglement of more than two
qubits at a time is very hard [Ref. 27].� We must find a source that emits
three or more photons at a time when it transitions from a high energy state to
a low energy state, and currently there are no known natural sources that do
this.� The second part of the I/O problem is:�� If you have classical data that
has been successfully transformed into qubits and you pass these qubits through
a quantum-gate array, then how will you know when the calculation is complete?�
You cannot measure it because you will collapse the wave function and fix it in
a state that may or may not be the answer you are looking for.� A solution has
been proposed which we will look at shortly.� The third part of the I/O problem
was considered in our general quantum computer model in Chapter III.� The
output interrogator must preserve the reversibility, coherence and time
independence so we can extract the overall property in which we are interested,
to harness the full quantum advantage.
Feynman proposed ,as a solution to
the second problem, that a cursor qubit be created to sample the data qubits.�
This cursor bit would travel from qubit-to-qubit to track the calculation.�
This cursor qubit could then be sampled without disturbing the original
calculation, which allows a monitoring of a quantum process by proxy.� However,
there are several problems with this implementation.� How can we entangle more
than three qubits at a time?� We can�t.� Let us suppose that we could entangle
multiple particles simultaneously.� If we measure the cursor qubit then we are
measuring the system that is entangled;� therefore we collapse the wave
function and influence the calculation in a destructive manner.� Let us now
suppose that we isolate the cursor qubit from the system so when we measure it
the wave function will not collapse.� If we isolate the cursor qubit, it has no
�knowledge� of the calculating system and cannot tell us when it is done. This
clearly requires further work.
1998 saw the first experimental proof
of concept for a quantum computer���� [Refs. 16, 17 ].� Prior to this it was
theorized that the quantum coherence problem was too hard to solve and would
prevent development of a quantum computer in the near term.� The approach used
Nuclear Magnetic Resonance (NMR) techniques on a solution of chloroform to
perform a database search known as the Deutsch-Jozsa algorithm.� The Deutsch-Jozsa
algorithm seeks to determine if a function is constant or balanced (having half
the time a value of 0 and half the time a value of 1) in a shorter time than
could be processed sequentially. To solve the problem for a function f having a domain (input) covering N
symbols, we must compute the function f for N symbols to determine if f is constant or balanced.� On a classical sequential machine
this requires N steps.� A parallel classical computer could do those N steps
simultaneously, provided it has N microprocessors.� This is the worst case for
both a deterministic (classical) machine and a classical stochastic machine
[Ref. 24, p. 556].� A quantum computer on the other hand, will be able to
harness quantum parallelism and accomplish this task in 1-2 steps by exploiting
the orthogonal property of the superposed answer.� When the quantum computation
is finished and the answer is interrogated to be a 0, the function can be
inferred to be constant because the answer is orthogonal to the original wave function
(the inner product of two orthogonal vectors is 0).�� If the answer is
interrogated to be a 1, then the function is balanced.�
Although this experiment was not the
most interesting application of quantum computing, it does provide a basis for
future work.� NMR/chloroform computing does not make for a practical
computation machine because a large magnetic source (NMR) would have to be
located close to a digital computer to provide the user interface, and
chloroform is somewhat volatile with its state having to be checked
frequently.� Additionally, large computations would require 10 or more qubits
and NMR computing does not provide the signal strength to distinguish between
so many individual spins with a chloroform solution.
The following table was compiled from
references 1, 3 and 16.� Each implementation provides its own model of quantum
computation.� The likelihood of success represents my judgement based on group
discussions and literature readings (i.e. references, Internet etc.).� Many
implementations are variations on a theme (Optical Lattice, NMR etc.).�
Table 2
|
Implementations
|
Interest������������������������������ (# of
Articles)
|
|
|
|
Nuclear Magnetic Resonance (NMR)
|
20
|
1.
Scalability
2.
Limited number of qubits due to
medium
3.
Volatility of computing solution
4.
Coherence times decrease for
solutions of larger molecules
|
5
|
|
Ion Trap
|
24
|
1.
Scalability
2.
Decoherence due to thermal
coupling
3.
Speed limited to vibrational
mode of ions
4.
Limited number of qubits due to
heating and coherence problems
|
4
|
|
Quantum Cavity (QED)
|
6
|
1.
Spontaneous emission of atoms
from the excited state (one form of decoherence)
2.
Trapping and localization of
atoms within cavities
3.
Maintaining coherence between
multiple cavities
|
7
|
|
Optical
|
2
|
1.
Lack of interaction between
photons (quantum interference)
2.
Limited number of qubits (can
only produce two entangled photons currently)
3.
No nonlinear photon gates
operating at the two-photon level
|
8
|
|
Optical Lattices
|
14
|
1.
Scalability
2.
Spontaneous emission within the
lattice (one form of decoherence)
3.
Inability to affect only one
photon/atom with laser energy
4.
Scattering of laser energy
5.
Thermal insulation
|
8
|
|
Silicon-Based Nuclear Spin
(condensed matter form of NMR)
|
2
|
1.
Nanoscale fabrication
2.
Limitation of probability of
error for each operation
3.
Placing phosphorus atoms in a
array in a semiconductor crystal
4.
Development of defect-free
semiconductor
5.
Decoherence rate of phosphorus
qubits
|
6
|
|
Quantum Dot
|
11
|
1.
Scalability (quantum dot size
not scalable smaller than current technology)
2.
Decoherence times
3.
Coherent optical control of
quantum-dot states
4.
Thermal insulation/isolation
|
6
|
|
Josephson Junction
|
9
|
1.
Nanoscale fabrication
2.
High-precision timing control
3.
Residual two-qubit interactions
4.
Decoherence times
5.
Thermal insulation/isolation
|
4
|
|
SQUID
(another form of Josephson Junction)
|
12
|
1.
Inability to entangle multiple
qubits
2.
No demonstrated logic gates
3.
Thermal insulation/isolation
(operating temperature)
4.
Junction quality (limit number
of impurities)
5.
Suppression of competing modes
6.
Magnetic coupling of flux
qubits� to magnetic impurities
7.
Small junction capacitances
8.
Fabrication technology
|
3
|
|
Neutral Atom
(extension of Optical Lattice)
|
1
|
1.
Low number of neutral atoms in
the lattice (limited number of qubits)
2.
No method for addressing and
reading out of qubits
3.
Must implement quantum error
correction methods
4.
Investigate atomic collision
effects (separations of atoms are small collisions most likely cause
decoherence)
|
3
|
|
Bose Condensate
(in an optical lattice)
|
4
|
1.
Thermal insulation/isolation
(operating temperature)
2.
Not enough experimental evidence
to support model
3.
Single particle theory, multiple
particle experiment
|
2
|
Ion-trap implementation confines identical ions in a laser-cooled
radio-frequency trap such that the ions reside in a one-dimensional lattice in
a harmonic oscillation.� Quantum-gate interactions are induced by stimulating
the ions with a coherent pulse of laser energy to affect the center-of-mass
mode of the collective quantum system.� This one-dimensional lattice models a
quantum register.�
The cavity QED implementation
utilizes the quantized mode of a high-finesse optical or microwave cavity to
change the electronic states of atoms or photons.� The cavity mode is
stimulated into resonance or out of resonance by short pulses of laser energy.�
Optical implementations of quantum
computers are either linear or nonlinear.� The linear optical implementation is
a two-path state system that relies on a photon�s propensity to take one of two
possible paths upon exiting a beam-splitter.� Gates are implemented by linear
optical methods: beam splitters, mirrors, polarizers, wave plates etc.� In a
nonlinear optical implementation, gates are implemented by photonic qubits shifting
the phase of others.�
Implementations utilizing optical
lattices are a condensed-matter variation of the optical method.� Atoms are
trapped in a lattice structure by lasers that perform cooling and trapping.�
Here the atoms are bound together by light instead of a chemical bond like
solids.�
Silicon-based nuclear spin
implementations are semiconductor-based NMR techniques that dope a silicon
wafer with phosphorus.� Metal electrode gates overlying the phosphorus-doped
wafer perform logic-gate operations by affecting the shape of the� dopant wave
function.�
Quantum-dot implementations use the
two spin states of a single electron quantum dot.� Logic gates are implemented
by several means: reducing the gating voltage for the tunneling barrier to
allow electrons to hop from dot to dot, influencing electron spin with another
electron spin, influencing charge orbital degrees of freedom, and control of
quantum-dot states by optical excitation.�
A Josephson junction is a special
switch that is composed of two superconductors sandwiching an insulating
material.� This switch has the property that current will flow without the
application of a voltage potential.� Current flow is produced by electron
tunneling across a small insulating barrier [Ref. 26].� The two charge states
of the superconducting island surrounding the junction would constitute a
qubit.� Logic gate operations are implemented by sequences of voltages across
the junctions to vary the charge state.� SQUID (Superconducting Quantum
Interference Device) is a variation of the Josephson junction implementation
where the presence of a quantized flux acts as the qubit to implement a
two-state system.�
Neutral-atom quantum computers are a
variation of the optical lattice, where neutral atoms form the lattice and
their electric dipoles function as qubits.� Logic gates are implemented by
forcing two neutral atoms to the same potential to generate a dipole-dipole
interaction.�
A Bose-Einstein condensate (BEC)
occurs when bosons (atoms with integer spin) are cooled to near absolute zero
temperature and begin to act as one atom [Ref. 25].� Placing these condensate
atoms in an optical lattice and moving optical-trap potentials so bosons move
in between lattice sites would be an implementation of a BEC quantum computer.���
To analyze the possibilities of
quantum computers we have three choices: Build analytical models, simulate
those models, or measure actual systems.� The last choice is not yet possible
because there are no permanent working models.� Analytical models can only tell
us so much about the behavior.� Therefore we are left with simulation to study
quantum computation.� Any simulation of a quantum computer should incorporate
the elements discussed in chapter III: superposition, entanglement,
logical/physical reversibility, time independence and output interrogation.�
Reference 2 addressed the problem of simulating quantum effects on a discrete
classical computer.� It is hard to simulate quantum effects; we can, however,
reproduce an approximation on a deterministic machine.� Reference 18 provides a
C++ version of a quantum-computer simulator that is programmed to run on a
parallel machine (a machine with more than one microprocessor).� This program
provided the basis for a simulation we wrote.� However, there is no one-to-one
correspondence between reference 18 code and our simulator.
Java� was chosen as the programming
language for the simulator.� Java is more platform-independent than C++ and can
be embedded in HTML Web pages, thus allowing more access to those curious about
quantum computation.� The Java program turned out to be less verbose than the
C++ version in reference 18.� Due to Java�s strong typing, many functions that
would have to be defined as class functions in C++ were simply written as
member functions in Java (this saves the programmer from defining the
functions) or were provided as part of the library accompanying the language.�
A quantum-computer simulator should simulate the workings of a quantum computer
faithfully enough that we can make predictions of how an actual quantum
computer would behave and how we might be able to program it.� A quantum
computer should set up some input qubits into superposed and entangled states.�
These qubits should then pass through a series of quantum logic gates that must
obey the precepts set forth in chapter III.� These logic gates should perform a
kind of calculation on the qubits.� After the calculation is done we should
interrogate the values of the qubits and interpret our answer.� This simulator
implements portions of the model discussed in chapter III, and is displayed
schematically below.�
Figure 8
The simulator program is divided into 6 files/classes: Test1,
UserInterface, Matrix, Complex, Initialize and Evaluation.� Appendix 1 contains
the source code.�
Qubit superposition is realized in a literal way,
by loading a data structure with�� 2n possible values that the user
input could be.� These values are extracted from the data structure randomly,
converted to binary, and the binary representation placed in a one dimensional
array of size n.� In a quantum system all values would take part in the
calculation simultaneously; however because of the sequential nature of
classical microprocessors, multiple random drawings from a data structure are
implemented to simulate the quantum nature of the calculation.� Qubit
entanglement is not implemented.� This process starts with the Test1 driver
program calling UserInterface to collect the user input values.� Test1 then
calls Initialize to implement the superposition.� Also, before calculation can
begin, the simulator must initialize the quantum gate that will be used for
calculation.
A Fredkin gate is used by the simulator to perform
a quantum calculation.� A gate data structure is set up as an N x N matrix
where N is the number of elements in the one-dimensional array.� The matrix
representation for the gate is presented in reference 18 and is implemented with
real and imaginary components which simulate the real and imaginary portions of
the wave function Ψ(t).� Actual gate operation is simulated by the
Evaluation class, which performs a matrix multiplication.� Test1 performs a
looped calculation which corresponds to incrementally stepping through all the
possible values of the qubits. Currently the loop does 100 iterations
maximum.�� Random possible values are withdrawn from the data structure,
converted to binary, and calculated with the gate matrix.�
When the calculation is complete, the answer is a
one-dimensional mixed (real and complex) array that is parsed by Test1.� Test1
acts as the output interrogator, directly interpreting the results from the
answer array.� This is done by setting up a histogram array that is the same size
as the answer array and parsing through the answer array until a nonzero
element is encountered;� whereupon the corresponding element in the histogram
array is incremented by 1.� For instance the output might look like �01010101�
which is 85 in base 10.
The argument could be made that as
the qubit values are withdrawn from the data structure and converted, they
should be placed in an indeterminate state (by giving them a real and complex
component) as they would in nature.� However, this would add complexity to the
matrix multiplication.
����������� Because this simulation was kept as simple as
possible, it does not provide essential services for the user and the fidelity
required to study quantum computation.� No useful calculation is performed by
this simulation; it should be viewed as a proof of concept for implementation
by a platform-independent language (Java).� Entanglement is not implemented
because it is a uniquely quantum effect.� Entanglement might be implemented if
an algorithm could be found to simulate the interaction amongst the qubits.�
Additionally, a GUI (Graphical User Interface), more selection of gates, and an
ability to build a quantum circuits could be implemented.� Hard-coding of the
maximum number of iterations should be replaced by a fidelity selected by the
user (high fidelity = 1,000 iterations, medium fidelity = 500, etc.).
�
Quantum
computers appear to be able to accomplish everything that a classical discrete
computer can [Ref. 19].� Reference 19 shows that a quantum system can be used
to emulate any Turing machine. Therefore, since Turing machines are universal
and can do any conceivable computation, then a quantum system can too.� But a
quantum computer may not always perform as efficiently as a classical discrete
computer.� One reason is that Amdahl�s Law says we can only increase processing
speed by speeding up the slowest portion of a computation, and many sequential
computations would work better on classical computers than on quantum
computers.� A second reason is that quantum systems are not ideal for all
parallel problems since they are advantageous only for problems with low I/O
costs and many solution constraints.
Algorithms specifically designed
for quantum computation are starting to appear.� Two important ones are the
Schor and Grover algorithms.� The Schor algorithm provides a way to find the
prime factorization of a large integer in polynomial time. The success of the
Schor is based upon �modular periodicity, coupled with the power of the Fourier
Transform for exposing periodicity� [Ref. 15, p. 18].� The Schor algorithm
works by finding the periodicity of the input integer, which corresponds to the
prime factor(s) of the input integer.� Grover�s algorithm provides a fast
database search method which seeks to limit the number of accesses to a
database.� Grover�s algorithm seeks to find an element x0
from a database that contains many x by realizing the shortest path
through the complex plane [Ref. 28].� The search uses parallel states of a
quantum system to search through all possible answers at once.� Successful
search paths reinforce one another while unsuccessful ones interfere
randomly.����
Quantum computers may be good for solving NP-Hard/Complete
problems.� Roughly speaking, an NP-Hard/Complete problem is one where an answer
is obtainable,� but the time required to get the answer is prohibitively long.�
The class of these problems that are now efficiently solvable by current
computing methods is rather small.� P represents the class of problems that are
solvable in effort that is a polynomial function of input size.� Complexity
class P problems are run on classical computers everyday and include sorting a
list, searching a database, and most arithmetic operations.� The class of
NP-Hard/Complete problems do not have efficient algorithms to implement them,
and take effort that is an exponential function of the input size.� An example
is the Knapsack problem which involves trying to pack items into a knapsack
such that the sum of the items equals the capacity of the knapsack.� Reference
15 suggests that� quantum computers may be adept at solving such problems by
checking all possible subsets in parallel.� Something similar is done in the
Schor algorithm which takes a large integer and finds all its prime factors by
looking for periodicities.�
However, several limitations need to be overcome
before more general quantum algorithms can be considered. One is the lack of
branching ability in a quantum system;� one-way branching can check for a
certain condition before proceeding with a program/algorithm.� This is not
possible in a quantum algorithm because it violates reversibility.� Other
limitations such as limited entangled states restrict the development of
practical quantum algorithms.
By utilizing the quantum effect of
nonlocality, qubit information can be transported from one quantum gate to
another (�teleported�) without losses due to decoherence or stray particle
interactions.� By utilizing quantum effects such as polarization, spin etc. it
may be possible to encode information so you could always know if someone read
it.� This is quantum cryptography.� Quantum communication uses similar quantum
effects to provide communications across various media.
The following table summarizes the
major area of quantum information systems.
Table 3
|
Quantum Technology
|
Interest
(# of Articles)
|
Problems
|
Prob. Of Success
(1-10) subjective
|
|
Computers
|
242
|
1.
Scalability
2.
Thermal isolation/insulation
3.
Decoherence
4.
Nanoscale fabrication
5.
Single particle theory,
multi-particle experiment
6.
Connection of multiple gates
(quantum wires)
7.
Implementation of �branching�
(if �then)
8.
Multi-particle entanglement
|
8
|
|
Teleportation
|
25
|
1.
Decisionmaker and public acceptance of action at a distance
2.
Decoherence
3.
Limited amount of information
that can be teleported
|
7
|
|
Cryptography
|
82
|
1.
Decoherence
2.
Multi-particle entanglement
sources
3.
Used for key distribution only
(limited amount of information that can be transferred)
|
9
|
|
Communication
|
34
|
1.
Decoherence
2.
Multi-particle entanglement
sources
3.
Distance over which signals can
be sent (30 Km)
4.
Limited bandwidth
|
4
|
When considering military applications for quantum
computing, we should consider computing problems in the military that current
computers cannot solve or take too long to solve.� Additional restrictions
would include non-portability of the platform the quantum computer is mounted
on and a consideration of Amdahl�s Law; Tc = Ts + Tp/N
(Tc = total computation time, Ts = total serial
computation time and Tp/N = total parallel computation time divided
by the number of microprocessors).�
Mobile applications of quantum computing are not
possible in the near or mid-term.� First, the required amount of shielding from
the environment would prohibit deployment of the system to a harsh and
unforgiving environment (i.e. desert, tropical jungle, etc.), which is where
most military deployments take place.� Second, the current and projected size
of the systems will prohibit deployment in relatively small craft (i.e. tank,
aircraft, etc.).� Third, quantum computing is insufficiently reliable
(real-time systems must have redundancy built-in because human life is at
stake), and requires specialized repair staff (and education) and costly repair
parts.�
Given this restriction, military computing
applications that might benefit from quantum computing are:�
����������� -Intelligence
-Cryptography
-Increased
Security
-Breaking
Codes
-Secure
Distribution of Data
-Photo
Analysis
-Data
Fusion
-Scan
of EM Spectrum
-Artificial
Intelligence
����������� -Acquisitions
����������������������� -Modeling
and simulation
����������� -Game Theory
����������������������� -Quantum
Strategies
Reference 5 provides an
experimental implementation of teleportation of secure information.� An
advantage of this method is that the information can be transmitted independent
of the media used.� This is due to a property of quantum mechanics known as
non-locality.� Two entangled photons A and B are created from the same source;
we could destroy photon A and reconstitute its information from B by
transferring it to another photon C.� The amount of information that can be
transferred is limited because it requires the entanglement of multiple
particles, which is hard to do [Ref. 27].
Public-key encryption is
popular and in wide use.� The Schor algorithm on a quantum computer would allow
a user to break the keys generated by a public-key scheme faster.� This has
obvious utility to the intelligence community.
Image processing algorithms
typically look for repeating or periodic patterns in a photograph.� This is
very computationally intensive for a classical discrete system and current
algorithms produce good results with certain pictures but not with others.�
Quantum systems may be more adept at solving this particular problem because
they excel at finding the �periodicity� in functions.� Images could be searched
for known shapes (e.g., tank, aircraft), which are worthy of an analyst�s
scrutiny.
All commanders desire a more
comprehensive picture of the battlefield. Intelligence sections are tasked with
assimilating a vast amount of data into a coherent picture of the battlefield
for the commander.� This assimilation is a process whereby the intelligence
officer reviews the combat information and sorts out what is and is not valid
based on his or her experience.� A quantum system could assist by sorting and
sifting through the raw data looking for predetermined themes and concepts.� A
system utilizing Grover�s algorithm could do this.� This would reduce the
man-hours spent looking through the raw data.
Some intelligence systems
scan for electromagnetic signals and determine bearing to the signal, signal
strength, and what the signal might be from (e.g., commercial TV, radio).�
These systems are limited in how many and what types of signals can be
intercepted.� A quantum system with a high degree of parallelism might be able
to process the data much faster, permitting analysis of multiple signals from
multiple sources or spread-spectrum signals.
Quantum communications (see
Reference 1) could allow the secure exchange of information with one hundred
percent assurance as guaranteed by Bell�s inequality.� If a source were to emit
two entangled photons going in opposite directions and one photon� is directed
down an optical-fiber cable, then if an eavesdropper were to tap into the line,
you would instantly know it.� This is because the eavesdropper would have to
absorb the original photon and could never reproduce the statistical nature of
the original particle.� Any reemitted photons would stand out against the
naturally occurring error and loss rate associated with network
communications.� However, the impediments to this are listed in the last
chapter.� The most troubling impediment is the requirement that the photons be
entangled.� Currently only two entangled photons can be produced from a single
source and this would therefore limit practical application to secure key
exchanges.� Some researchers believe that other ways can be found to produce a
higher bandwidth.
Artificially intelligent quantum systems could be
used by commanders as decision aids.� They could assimilate the vast amounts of
data that need to be considered and produce reasonable courses of action.� A
quantum system could allow a commander to vary parameters more broadly than they
can today to see how different decisions would affect his or her command.� With
an artificially intelligent quantum system, personality traits of opponent
commanders could be programmed into scenarios or general tactics of an opponent
in a wargame.� A quantum system could also be used as a training aid. Quantum
parallelism could make it possible to speed up renditions of virtual
environments and increase their possible realism.�
Quantum systems could provide the
same type of decision aid to program managers and program executive officers
that it could provide to commanders.
Quantum systems provide the
potential to increase the fidelity of models and simulation through quantum
parallelism and the knowledge inherent in them.� With a quantum system we can
encode more information about the problem due to superposition and
entanglement.� This increased information could permit more fidelity and allow
modeling of more complex systems (like explosions) than current classical
computers.
D.� GAME THEORY
Game Theory is being used to study
how groups of people interact [Ref. 7, p. 636].� Since this field is focussed
on probability of outcome, it should mesh well with a quantum computation.� In
reference 6 the authors argue that since game theory is probability-based, it
could exploit a superposition of possible outcomes that would be allowed by
quantum mechanics.� A popular game-theoretic model of the �Prisoner�s Dilemma�
is used to illustrate their point.� Two prisoners are held in separate rooms so
that they cannot communicate.� The table below illustrates the advantages for
each prisoner with the rows designating the benefits for prisoner #1 and the
columns designating the benefits for prisoner #2 where the object is to
maximize the score (based on a scale of 1-10, 10 being the maximum).� For
example, row 2 column 1 (10,0) represents prisoner #1 maximizing his score by
confessing while prisoner #2 does not.
Table 4
|
|
Prisoner 2
Does not Confess
|
Prisoner 2
Confess
|
|
Prisoner 1
Does not Confess
|
5,5
|
0,10
|
|
Prisoner 1
Confess
|
10,0
|
1,1
|
�������
The best strategy when viewed by each
prisoner alone is to �double cross� your partner.� However, if they both do
this it earns both of them a jail sentence and none of the money from the
crime.� So it is better to not double-cross.� From a quantum mechanical
perspective, we can avail ourselves of the superposition of states and remove
the case of the Dilemma [Ref. 6].� This is done by assigning the classical
strategies two base vectors |A> and |B>, performing unitary
transformations on them and realizing an answer in the complex plane.� This
could be viewed as removing the dilemma.� However, this solution is incomplete
because there is no correlation to an actual realizable result. With more study
meaningful methods could be developed to provide insight into and help in
solving decision problems and dilemmas with a quantum approach.�
There is great potential offered in
quantum computation, although a paucity of algorithmic support at this time.�
By investigating it we gain insight into computation in general, and this may
allow us other advances that are not yet realized.� A quantum computer ought to
be built soon.� This will force direct investigation of troubling areas such as
decoherence, scalability etc.� Even a negative result would have significant
scientific meaning.� A few promising implementations could be funded with the
purpose of developing a working prototype within the next ten years.� However,
the diverse funding advocated in reference 15 should be avoided.� We also need
to build a dictionary of common terms; computer scientists and physicists use
terms with different meanings to each group.
Quantum cryptography was rated with
the highest probability of success in Chapter VI because security is of high
concern to business and governments.� This is evidenced by the interest in the
Schor algorithm.� However, several hurdles need to be cleared before any
serious implementation can occur.
Although quantum telportation sounds far-fetched,
it has been experimentally verified.� However, wide implementations of this
technology for communication are not likely because the maximum number of
particles that we can currently entangle is two.� This limits how much
information that can be transmitted at one time. However, it could provide the
answer to the �quantum wires� question: By teleporting qubits between gates,
one could avoid decoherence and stray interactions.� This topic requires
further investigation.
Quantum communication currently faces stiff
competition from current methods. The bandwidths proposed are very small and
would only serve as a means of key exchange.� Therefore problems such as
multi-particle entanglement must be solved to make it practical.
LIST OF
REFERENCES
1.
Williams, C.P., Clearwater, S.H., Explorations
in Quantum Computing, p. 8-9, Springer-Verlag, Inc., 1998.
2.
Feynman, R.P., �Simulating Physics
with Computers�, International Journal of Theoretical Physics, vol. 21,
no. 6/7, 1982.
3.
Brandt, H.E., �Qubit Devices and
the Issue of Quantum Decoherence�, Progress in Quantum Electronics, vol.
22, no. 257-370, 1998.
4.
Marand, C., Townsend, P.D.,
�Quantum Key Distribution over Distances as Long as 30 km�, Optics Letters,
vol. 20, no. 16, 1995.
5.
Furusawa, A., �Unconditional
Quantum Teleportation�,� Science, vol. 282, 1998.
6.
Eisert, J., �Quantum Games and
Quantum Strategies�, http://xxx.lanl.gov/quant-ph/9806088, vol.
2, 1999.
7.
Winston, W.L., Operations
Research: Applications and Algorithms, p. 636-663, PWS-Kent, 1987.
8.
Deutsch, D., �Quantum Theory, the
Church-Turing Principle and the Universal Quantum Computer�, Proceedings of
the Royal Society London, A 400, 97-117, 1985.
9.
Feynman, R.P., �Quantum Mechanical
Computers�, Optics News,� February, 1985.
10. Hopcroft, J.E., Ullman, J.D., �Introduction to
Automata Theory, Languages, and� Computation�, Addison-Wesley, 1979.
11. Marshall, I., Zohar, D., �Who�s Afraid of
Schrodinger�s Cat?�, Bloomsbury, 1997.
12. Jammer, M., �The Philosophy of Quantum Mechanics�,
John Wiley&Sons, 1974.
13. Bennett, C., �Quantum Information and Computation�, Physics
Today , American Institute of Physics, p. 24-30, 1995.
14. Simmons, J., �Quantum Transistor May Lead to Much
Faster Computers�, http://www.sandia.gov/InsideSandia/IS05-98/quantum.html,
1998.
15. Kimble, H., �Quantum Computing�, JASON JSR-95-115,
Mitre Corp., 1996.
16. Chuang, I., �Experimental Realization of a Quantum
Algorithm�, http://squint.stanford.edu/qc/nmrdj/index.html,
1998.
17. Chuang, I., �Experimental Implementation of Fast
Quantum Searching�, http://squint.stanford.edu/qc/nmrqc-grover/index.html,
1998.
18. Marshall, J., �Simulating Quantum Circuits on a
Parallel Machine�, http://www.doc.ic.ac.uk/~jim1/report.html,
1996-97.
19. Benioff, P., �Quantum Mechanical Turing Machines That
Dissipate No Energy�, Physical Review Letters, vol. 48, no. 23,
1581-1585, 1982.
20. Cormen, T., �Introduction to Algorithms�, MIT Press,
1990.
21. Joint Staff, �Joint Vision 2010�, http://www.dtic.mil/doctrine/jv2010/jvpub.htm, 1994.
22. Barenco, A., �Elementary Gates for Quantum
Computation�, http://xxx.lanl.gov/PS_cache/quant-ph/pdf/9503/9503016.pdf,
1995.
23. Cleve, R., �Quantum Algorithms Revisited�, http://xxx.lanl.gov/format/quant-ph/9708016,
1997.
24. Deutsch, D., �Rapid Solution of Problems by Quantum
Computation�, Proceedings of the Royal Society London, A 439, 553-558,
1992.
25. Moerdijk, A., �Bose-Einstein Condensation with Trapped
Atoms�, http://Herman.ni.phys.tue.nl/ardjan/bec.html,
1995.
26. Feynman, R., �The Feynman Lectures on Physics�,
Addison-Wesley, vol. III, 21-(14-18), 1966.
27. Baer, W., �Stanford University Site Visit�,
Inter-department memo, 1999.
28. Jozsa, R., �Searching in Grover�s Algorithm�, http://xxx.lanl.gov/quant-ph/990121,
1999.
INITIAL DISTRIBUTION LIST
1.�������� Defense Technical
Information Center......................................................................... 2
����������� 8725 John J.
Kingman Road, Ste 0944
����������� Fort Belvoir, VA
22060-6218
2.�������� Dudley Knox
Library.................................................................................................. 2
����������� Naval
Postgraduate School
����������� 411 Dyer Road
����������� Monterey,
California 93943-5101
3.�������� Director, Training
and Education.................................................................................. 1
����������� MCCDC, Code C46
����������� 1019 Elliot Road
����������� Quantico, VA
22134-5027
4.�������� Director, Marine
Corps Research Center..................................................................... 2
����������� MCCDC, Code C40RC
����������� 2040 Broadway
Street
����������� Quantico, VA
22134-5107
5.�������� Director, Studies
and Analysis Division........................................................................ 1
����������� MCCDC, Code C45
����������� 3300 Russell Road
����������� Quantico, VA
22134-5130
6.�������� Marine Corps
Representative...................................................................................... 1
����������� Naval
Postgraduate School
����������� Code 037, Bldg.
330, IN-116
����������� 555 Dyer Road
����������� Monterey, CA
93940
7.�������� Marine Corps
Tactical Systems Support Activity.......................................................... 1
����������� Technical
Advisory Branch
����������� Attn: Maj J. C.
Cummiskey
����������� Box 555171
����������� Camp Pendleton,
CA 92055-5080
9.�������� Professor Neil C.
Rowe,
CS/Rp�.���.......�.............................................................2
����������� Naval
Postgraduate School
����������� Monterey, CA
93943
10.������� Dr. Wolfgang Baer,
CS/Ba��...�...................�...........................................................1
����������� Naval
Postgraduate School
����������� Monterey, CA
93943
11.������� Captain John E.
Mades�..��...�...................�...........................................................2
����������� 639 South 22nd
����������� Terre Haute, IN
47803
