Quantum's Next Leap

[R. A. Hettinga]

Anyone want to take bets on how long it will be -- like *every* business
claimed to be a dot-com in Clinton's bubble ;-) -- before *everyone* in the
cryptography business will claim to be a quantum crypto company?

Don't laugh. Weirder stuff has happened, right?

Cheers,
RAH
--------

<http://www.informationweek.com/shared/printableArticle.jhtml?articleID=20000170>

InformationWeek

Quantum's Next Leap

Quantum computing may still be far from reality, but the idea is getting a
very real financial boost from the government


By Aaron  Ricadela,   InformationWeek
 May 10, 2004
 URL:
http://www.informationweek.com/story/showArticle.jhtml?articleID=20000170



 At a late-January meeting in a Marriott off the Washington beltway in
Falls Church, Va., the Defense Department's main technology-research arm
floated a proposal as nearly 100 scientists listened. They'd come from
Boeing, IBM, Lockheed Martin, and other companies; from the Army, the Navy,
and NASA; and from leading universities to hear a proposal for accelerating
efforts to build a computer that theoretically could exist inside a coffee
cup.

 Within the next several months, the Defense Advanced Research Projects
Agency, which will spend more than $2.8 billion this year on research and
development for the Pentagon, is expected to launch a multimillion-dollar
program to kick-start U.S. research in quantum computing, an esoteric area
of inquiry under way at government labs, universities, and companies such
as AT&T, Hewlett-Packard, IBM, and Microsoft. These supercomputers--built
according to the strange laws of quantum physics, often operating at
temperatures nearing absolute zero, and occupying spaces that can resemble
a vial of liquid more than an electronic box--theoretically could perform
within seconds calculations that take today's machines hours and solve in
hours problems that might require centuries if run on state-of-the-art
silicon.

 If the research pans out, and there's no guarantee it will, quantum
computers could revolutionize a computer industry whose main engine of
economic growth--the doubling of computing power each year and a half
predicted by Moore's Law--is in danger of losing steam.

 The implications of quantum computers, which store and process information
by exploiting the laws of quantum physics governing subatomic
particles--"spooky action at a distance," Einstein observed--could turn
upside down entire fields of research, including cryptography, engineering,
weather prediction, space flight, and mathematics. Existing public key
cryptographic systems would be useless. Timekeeping more precise than with
atomic clocks could pinpoint satellites and spacecraft with stunning
accuracy. Quantum computers could also yield exponential improvements in
the speed of database searches and perform calculations virtually
insolvable today. "Pratt & Whitney could use a 10-times performance
improvement tomorrow if it were available at a reasonable cost," says Pete
Bradley, an associate fellow for high-intensity computing at the United
Technologies Corp. division that makes aircraft engines, in an E-mail
message.

 It won't be ready tomorrow. In fact, it could take 20 years or more to
build a functional quantum computer. But consider the potential. The
fundamental idea of quantum computing is that a particle--a quantum bit, or
qubit--can represent both a 1 and 0 at the same time, so the number of
calculations scales exponentially with each quantum-computing bit, compared
with linearly in an electronic computer, where each bit must be either a 1
or 0. So a quantum computer using 14 calculating atoms, which is twice as
large as what's been assembled today, could perform more simultaneous
calculations (16,384) than the fastest supercomputer in the United States,
at Los Alamos National Laboratory in New Mexico. (Los Alamos Lab itself
spends about $11 million a year on quantum-computing research.) Scientists
are a long way from those results, but the Defense Department program could
pick up the pace of innovation with more funding. The U.S. government
already backs quantum-computing research to the tune of $80 million to $90
million per year.

 Darpa's proposed program, called Focused Quantum Systems, or Foqus, aims
to build a quantum computer capable of factoring a 128-bit number--a common
method of online encryption--in 30 seconds, with 99.99% accuracy. "Darpa
has decided to put a huge chunk of money out for researchers to build a
quantum computer," says Nabil Amer, the manager and strategist of the
physics of information for IBM Research. "This will be a highly coordinated
effort with the serious goal of bringing us to a go/no-go point: Will we be
able to build this computer or not? Darpa all of a sudden got an epiphany."

 IBM, MIT's Lincoln Laboratory, and other companies and universities are
expected to participate in Foqus, with the goal of defining how to design a
quantum computer, get information in and out of it, and correct inevitable
errors. Darpa also is interested in the flip side of code-cracking: using
quantum mechanics to create a new type of cryptography that couldn't be
cracked with even the fastest factoring algorithms.  A couple decades from
now, quantum computers could lock down electronic signals coming from
Boeing's airliners and fighter jets, says Gary Fitzmire, VP of engineering
and IT in Boeing's Phantom Works advanced R&D unit. Fitzmire and his team
have been logging their own frequent-flier miles in pursuit of knowledge:
One technologist went to Darpa's Falls Church meeting; Fitzmire, who's
based in St. Louis, attended a Darpa conference in Southern California in
March and recently paid a visit to Cambridge University's physics
department to bone up on plans. "When we want to send data wirelessly from
an F-18 or AWACs [radar-surveillance plane], we think there's some promise
inside quantum computing to boost our information assurance," Fitzmire
says. "We don't want these signals jammed or eavesdropped on."

 Darpa describes Foqus only as a possibility. A bid for scientists to
participate will likely come "sometime in the near future," a spokeswoman
says. The agency is interested in quantum computing for its potential to
help understand ultrasecure communications and superaccurate calibration,
she says.

 The potential rewards are so great, Microsoft has hired prize-winning
mathematician Michael Freedman to explore the theoretical possibilities of
building and programming a quantum computer. "What's going to be on your
desktop in 30 years?" asks Jennifer Chayes, manager of Microsoft Research's
theory group, which studies mathematics, physics, and theoretical computer
science and employs Freedman. "Or painted on the wall, in your bracelet, or
in your phone? Let's hope it's much more powerful than today. If the new
paradigm is going to be quantum computing, we want to make sure Microsoft
is there. We want to say something about how these things are built."

NIST's Williams warns companies not to miss the boat on quantum computing.
Photo by David Deal
What isn't clear is whether quantum computers of useful size actually can
be built in our universe. It's even unclear whether the theoretical
constructs--the physics of quantum mechanics and our concept of the
algorithms that could be run on them--are correct. "Everything at the
moment is very rudimentary, but they're the key steps to building something
more complicated," says Carl Williams, chief of the atomic physics division
at the National Institute of Standards and Technology, which sets U.S.
measurement and timekeeping standards. "Which is going to be the technology
that wins in building this new type of computer? I think that's unknown."

 The notion of constructing a computer that behaved according to the laws
of quantum physics arose in the early 1980s, when the late Richard Feynman,
a Nobel Prize winner at the California Institute of Technology, postulated
that the only way to simulate a quantum mechanical system--one in which
particles can spin clockwise and counterclockwise at the same time--was
with a computer that itself behaved that way. A big breakthrough came in
1994 when Peter Shor, a researcher at AT&T's Bell Labs in New Jersey,
showed in an algorithm how a quantum computer theoretically could quickly
find the factors of large numbers. Since the codes that protect military
and financial secrets are based on the inability to do that, government
money began flowing into quantum-computing research.

 According to people familiar with Foqus, the Darpa program is expected to
be more ambitious than past programs in the amount of funding and freedom
given to researchers. Those include a 3-year-old, $100 million Darpa
program called Quist and another government program at Advanced Research
Development Activity, a research arm for U.S. intelligence organizations,
that IBM's Amer describes as "methodical and conservative." The National
Science Foundation also funds quantum-computing research by individual
scientists.

 Engineers no doubt will continue wringing performance gains out of silicon
chips. But the computing industry knows it can't keep shrinking the size of
the electronics on those chips forever. As components approach the
nanoscale, power leakage and heat start to hold back performance.

 Quantum computers aren't the only potential successors to silicon-based
ones. Hewlett-Packard is researching a branch of nanotechnology it calls
molecular electronics to exploit quantum effects in nanoscale materials to
build more-efficient computers. Researchers at the University of Southern
California first used reactions of DNA molecules in a test tube a decade
ago to carry out steps to solve a computational problem. Two weeks ago,
Israeli scientists said they had programmed a DNA computer to detect signs
of cancer.  There's also no agreement about the best way to build a quantum
computer. Experiments by Isaac Chuang and Neil Gershenfeld at MIT and David
Wineland at NIST use atoms or charged ions in an electromagnetic trap,
while IBM is testing superconducting materials that can generate quantum
bits. "We're trying to beat our brains to come up with something different
than what others are doing," Amer says. Two weeks ago, IBM and Stanford
University launched joint research in a related area called spintronics,
which aims to design electronics by controlling how electrons spin, instead
of how they transmit electrical charges. They plan to research applications
for building quantum computers, among other areas.

 Another question hanging over the field is whether experiments are
progressing quickly enough. Researchers estimate it would take a quantum
computer of 100,000 calculating atoms to perform work that's beyond the
reach of today's most-powerful computers, such as breaking the 128-bit
codes used to encrypt E-mail and other Internet data in a reasonable amount
of time. "We're barely getting one or two" calculating atoms, says Stan
Williams, director of quantum-science research and a senior fellow at HP.
Scientists need to focus on goals less complicated than breaking codes that
secure online data, Williams says. "You'd need a quantum computer so large
that it would be like trying to build a supercomputer before a transistor
radio," says Williams, who's responsible for making sure HP's nanotech and
quantum research has a payoff. "You need to take baby steps and bootstrap
an industry out of quantum computing," he says. "Where's the low-hanging
fruit that will start to get some revenue to pay for more R&D?"

 One possibility is a new HP project exploring how small numbers of quantum
bits could be sent through fiber-optic cable to offices and homes in wired
cities. If they can, HP researchers theorize, the quantum properties of
photons could be exploited to model more-efficient outcomes for markets
that behave according to game theory, such as financial markets and
auctions. "We're trying to find what people would call a killer app,"
Williams says. "Rather than beat our heads against the wall and bloodying
ourselves trying to factor a large number, we're trying to find something
people would pay money for with just a few qubits and the basic research on
the technology for delivering them."

 THE UPSHOT
 Quantum computing, though still largely theoretical, could get a boost
from the Defense Department, which is considering pumping funding into a
focused program to prove whether it's viable

 If it works, quantum computing could provide such enormous computing power
that it would make today's encryption and other information-security
systems obsolete

 Researchers at companies such as Boeing, Hewlett-Packard, IBM, and
Microsoft are doing their own research, as well as cooperating with Defense
Department efforts

 Even if successful, quantum computing is likely a decade--or, more likely,
two--away


The price may be unknown--"a nickel a qubit," Williams jokes--but the goal
is serious. Companies expect even futuristic researchers to keep an eye on
cash flow. "You're almost responsible in a laboratory like HP's for having
a business model," Williams says. "We're going off in a different
trajectory than other people."

 Other technology companies, including Intel, aren't jumping into the
high-risk field. Intel's business could be directly threatened by a
breakdown in the advances predicted by Moore's Law. But quantum-computing
technologies "are far away from anything Intel as a mass-market supplier of
complex math functions would be interested in," says Pat Gelsinger, Intel's
chief technology officer. The company is funding some university research,
but no Intel staffers are researching it directly. "I don't think it
matters before 2020," Gelsinger says.

 Some in the high-performance-computing user community are skeptical as
well. One technologist on Wall Street says a shift as big as the one from
electronic to quantum computing--no matter how technically feasible--would
require massive amounts of work to fit into the private sector. Every line
of companies' software code would have to be ported or rewritten, for
example.

 It's a dilemma for every emerging technology: When is the right time to
give it money and attention? Quantum computing is harder to justify than
most, since practical uses seem so far off--and far out. Yet it's those
hard-to-imagine uses that also make it so critical to understand. NIST's
Williams acknowledges that most companies don't yet see what value comes
from tracking quantum computing, quantum information, and quantum
cryptography. "At the same time, they may say, 'This is scary,'" he says.
"When the boat sails, if they're not on, they may cease to exist."


-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com