Revolutionary
Computing Technologies - Quantum Computing
from: Center
for Integrated Space Microsystems Programs
Objectives of the CISM Quantum
Computing Initiative
The objectives behind the CISM
quantum computing initiative are to develop novel quantum algorithms,
and designs for quantum devices, that tackle computational problems of
practical significance to NASA. Specific objectives for FY'99 include
the following:
To understand whether
quantum computers can speed up the solution of
NP-complete problems beyond what we showed in FY'98.
To understand whether
quantum computers can enhance signal processing and
data compression.
To invent a
methodology, and computer software, for automating the
discovery of novel quantum algorithms.
To identify a spectrum
of potential applications of quantum computers, at
varying degrees of difficulty, that impact NASA
mission objectives.
To perfect the design
of one such application (a two-port optical quantum
gyroscope) that promises an eight order of magnitude
improvement in the sensitivity to rotations.
To file patents on any
exploitable technologies that derive from our work.
To publish academic
papers in respected journals.
Background
In
FY'98 CISM began funding research into quantum computing under its
Revolutionary Computing Program. The first year has been very
successful with several new quantum algorithms being discovered, new
collaborations forged and connections made to NASA's primary mission
objectives.
Quantum computing is a new field
that combines ideas from quantum physics and computer science to
investigate the design and capabilities of hypothetical computing
devices that harness delicate quantum effects in the service of
computation [Wil98a]. Computation with quantum systems offers a
revolutionary approach to computing in general: By clever utilization
of the properties of superposition, interference, entanglement, non-clonability
and non-determinism, exhibited by all quantum systems, a new form of
"quantum parallelism" appears achievable, wherein an
exponential number of computational paths can be explored "at
once" in a single device. The challenge is to frame computational
questions in such as way as to extract a useful, typically
probabilistic, answer.
It is important to realize that it
is not just that quantum computers operate faster or at smaller scales
than classical computers, but that they operate using different laws
of physics from those followed by all existing classical computers. We
are in the early stages of understanding the impact this shift in
foundations, but it does seem like several remarkable computational
possibilities present themselves that could have a direct impact of
NASA's primary mission objectives. These include the use of quantum
computers to make ultra-precise gyroscopes, to greatly improve the
precision of atomic clocks, and to perform certain search, signal
processing and data communication tasks much faster than is possible
classically.
Our interest in quantum computing
stems primarily from the need to solve hard, supposedly
"intractable", computational problems on a routine basis.
Detailed mission planning, deep space network communications
scheduling, and spacecraft design optimization are just a few examples
of the kinds of NP-complete problems that we face. So far, there is no
known classical computing technique that can solve such problems using
polynomially bounded resources in the worst case. Today we employ a
small army of computer scientists to work on developing the very best
classical algorithms for performing these computations. As we move out
into the next century, NASA envisions a huge increase in the number of
concurrent space missions. In such a climate the computational demands
we will face will become significant factors impeding progress.
Moreover, as our spacecraft become more remote from Earth, the speed
of light limited communication delays force us to place more autonomy
on-board. To function autonomously, such as to re-plan a series of
observations, and data analyses in real-time during a fly-by of an
astronomical body, we need to bring massive computational power to
bear under extreme constraints on allowed mass, time and power. Like
the ARO, NSA and DARPA (the other U.S. government agencies funding
quantum computing) we would like to know if quantum computers could
provide any help.
Moreover, historically, JPL has been
one of the key innovators of computer technology in the United States.
To give just a few examples, JPL has designed and built massively
parallel computers, hypercubes, and neural network hardware and we
currently invest in superconducting electronics based computers,
quantum dots, nanotechnology, and reconfigurable, fault-tolerant,
hardware. These research activities rarely make the headlines as the
space missions do, but computer technology research plays a critical
supporting role for our primary mission objectives.
FY 98 Achievements
In FY'98 we organized the First NASA
International Conference on Quantum Computing & Quantum
Communications. Articulated and defended JPL's quantum computing
program at NASA Autonomy & Information Technology Program Plan
Review. Gave presentations to Dr. Stone (JPL Director), NASA, NSA, NRO,
and BMDO. Published a book, "Explorations in Quantum
Computing", TELOS/Springer-Verlag, the first book on quantum
computing. Gave talks at Oxford University, British Computer Society,
and TRW. Initiated new quantum computing efforts at JPL including
quantum gyroscopes, Earth-to-space quantum key distribution and
"base 3" quantum computing.
In FY'98 we made significant first
steps in support of our technical objectives. In particular, we
discovered a new quantum algorithm that can solve the hardest
instances of NP-complete problems in a time that scales 
where 0 < x < 1 and N is the number of possible solutions
[Cer98]. In comparison, the previous best known quantum algorithm for
this problem was Grover's algorithm [Gro96], which has a complexity
of . In FY'99 we plan to extend these results in the hope of
getting even better speedups.
Later in the year, we discovered a
new quantum algorithm for performing the quantum wavelet transform
[Fij98]. In classical computing the wavelet transform is as useful as
the Fourier transform, especially in signal and image processing.
However, to date, all quantum algorithms have relied upon the quantum
Fourier transform. We anticipate that our quantum wavelet transform
will enable new classes of quantum algorithms to be developed,
especially in the areas of signal processing and data compression.
We recognize, however, that there is
more potential from quantum technology than just computation.
Moreover, certain non-computational devices appear to be more feasible
to implement within the near future. In an effort to elucidate new
ideas, and to push the envelope on existing ones, in 1998 we organized
the "First NASA International Conference on Quantum Computing and
Quantum Communications", held in Palm Springs, California. We
imposed an a priori structure of the meeting that was designed to
solicit feedback on how quantum computing might impact NASA mission
objectives in computation and communications. I am delighted to say
that NASA really obtained great value for money from this conference.
In particular, four key ideas emerged that caught our attention:
quantum gyroscopes [Dow98], improved precision of atomic clocks, the
first steps in quantum algorithms for tackling NP-complete
(structured) problems [Gro98] and the potential for Earth-to-space
quantum key distribution (QKD) [But98]. The proceedings are about to
be published as Volume 1509, of Springer-Verlag's Lecture Notes in
Computer Science. Non-JPL references are listed here. The JPL ones are
reported in the Publications Chapter.
[But98] "Practical Free-space
Quantum Key Distribution over 1 km", W. T. Buttler, R. J. Hughes,
P. G. Kwiat, S. K. Lamoreaux, G. G. Luther, G. L. Morgan, J. E.
Nordholt, C. G. Peterson, C. M. Simmons, http://xxx.lanl.gov/archive/quant-ph/9805071
(1998)
[Gro98] "Quantum Search on
Structured Problems", L. K. Grover, to appear in Proceedings of
the First NASA International Conference on Quantum Computing &
Quantum Communications, Palm Springs, CA, Vol. 1509, Springer-Verlag
Lecture Notes in Computer Science (1998) also available at http://www.lanl.gov/archive/quant-ph/9802035
[Gro96] "A Fast Quantum
Mechanical Algorithm for Database Search", Lov Grover, Proc. 28th
Ann., Symp. on Theory of Computation, (STOC96) pp212-219 (1996)
Future Plans
In FY'99 we plan to push out both
the quantum algorithms and quantum devices fronts. Specifically, we
plan to find applications of the quantum wavelet transform that we
invented in FY'98, and along the way to develop a new classical
approach to the Fast Fourier transform. We might also develop quantum
circuits for other transforms that crop up in classical computer
science, such as the Discrete Cosine Transform used in image
compression.
We plan to continue our work in
quantum recurrent networks (QRNs) and collaborate with Lute Maleki's
horology group to build a simple prototype QRN that can be trained to
generate truly random samples from arbitrary stochastic processes.
Such a capability is of use in solving certain problems via Monte
Carlo techniques and is guaranteed to avoid the problem of spurious
correlations that arise in pseudo-random number generators.
In FY'98 we made advances in the
study of quantum search algorithms. We plan to extend these results in
FY'99. In particular, we are exploring the advantages of using
intermediate measurements made during the course of coherent quantum
computations, the use of self-organization during search (to hone in
on a solution). We also plan to investigate the quantum analogs of
classical randomized algorithms (which are the best approach to
NP-complete problems known classically).
A primary goal in FY'99 will be to
see if we can extend the range of problems that can be sped up using
quantum computing. In particular, we are investigating the use of
quantum computers for computing high dimensional integrals.
In FY'98 we developed a prototype
quantum circuit design program. We would like to integrate this with
other approaches to circuit design based on algebraic factorization,
induction and numerical optimization. The point here would be to
develop a toolkit that supports our own quantum algorithm discovery
efforts and which is useful in developing the circuits needed to drive
the quantum gyroscope.
The quantum gyroscope is an idea
invented by Jon Dowling, a new hire in our group [Dow98]. If two
particles, entangled in a special way, are fed into a two-port Mach-Zehnder
interferometer, the phase sensitivity scales as the Heisenberg limited
DELTA phi = O(1/N) where N is the number of particles incident per
unit time. In a one-port device the phase sensitivity scales, at best,
as DELTA phi = O(1/Sqrt[N]). Calculations suggest that the two-input
port optical quantum gyroscope ought to be about 10^8 (one hundred
million) times more sensitive to rotations than a one-input port
optical gyroscope. Such an increase in sensitivity will be vital in
future missions that must navigate dense asteroid fields or debris
thrown off from comets. Moreover, quantum gyroscopes might also enable
new classes of Earth-observing missions based on detecting minute
gravitational deviations and may help in pointing the arms of massive
space-borne interferometers that are planned to obtain high resolution
images of planets orbiting stars in other solar systems. Quantum
gyroscopes will also facilitate new tests of general relativity. Thus,
for NASA, the confluence of quantum computing techniques and optical
gyroscopy has the potential to be "mission-enabling", i.e.,
to allow entirely new types of mission to be conducted.
In FY'99 we plan to move out on the
quantum gyroscope idea. We will build a software simulator of the
gyroscope and use this to optimize the entangled state fed into the
device to achieve maximum sensitivity to rotations. We will also use
the simulator explore the effect of decoherence and errors on the
gyroscope's performance.
Rationale/Benefits
Hypothetical quantum computers can
perform certain computational tasks exponentially faster than any
classical computer. Thus, if successful, our program will result in
highly efficient algorithms for several NASA-related application
domains such as scheduling, planning, pattern recognition, and data
compression.
While our focus remains to solution
of computational problems, we recognize opportunities along the road
to achieving that goal. The quantum gyroscope requires fairly modest
computational needs - basically only a quantum circuit that is capable
of preparing a special entangled state of two qubits. This would
provide a valuable intermediate goal on the road to more general
quantum computing.
Task Leader: Colin
Williams
Team Members: Jonathan Dowling, Amir
Fijany, Michail Zak, Alex Gray
Collaborators: James Franson,
Applied Physics Laboratory, Johns Hopkins University
Nicolas Cerf, Free University of Brussels
Dan Abrams, M.I.T.
Bob Gingrich, Caltech
Giovanni della Rossa, Quantumatics Inc.
Lute Maleki, JPL atomic clock group
Nan Yu, JPL atomic clock group
Related Links:
Revolutionary
Computing Technologies
