NEWSFOCUS
Building a quantum computer, however,
is easier said than done. Researchers must
keep the qubits isolated enough to maintain
their delicate quantum waves, yet make them
interact enough to perform a calculation.
That’s a monumental challenge. Quantum
computing has been a hot topic since the
1990s, but physicists are still struggling to
manipulate a handful of qubits. The best
anyone has done with Shor’s algorithm has
been to factor 21.
One company, D-Wave of Burnaby,
Canada, sells a more limited type of
supposedly quantum computer that cannot
run Shor’s algorithm. But for the most
part, quantum computing remains a basic
research subject, says Addison Snell, an
industry analyst with Intersect360 Research
in Mountain View, California. “If I were a big
company like IBM, I’d have a couple of guys
in the back room working on this,” he says.
Countermeasures
Even if a quantum computer remains a remote
threat, some researchers are already work-
ing to counter it. That’s because it’s not just
future communications that might be jeopar-
dized, but also messages we’re sending today,
which could be cracked after a quantum com-
puter becomes a reality. “How do you know
that somebody hasn’t recorded all those com-
munications?” says Georgia Tech’s Fortnow.
“The Internet doesn’t forget so fast.”
The easiest safeguard would be to improve
cryptography. A quantum computer couldn’t
defeat every type of encryption. In symmetric
or private key systems, Alice and Bob share
a secret key and a public algorithm that, for
example, makes two different chunks of coded
message look like random bits when Eve
compares them. In that case, Eve can’t hack
a transmission by looking for correlations
in the stream of bits. Such schemes seem
capable of withstanding a quantum attack and
already encrypt most of the data transmitted
in secure Internet transactions.
New public key algorithms might also
fend off a quantum computer. For example,
Chris Peikert, a cryptographer at Georgia
Tech, and colleagues are working on so-called
lattice methods. A lattice is a repeating array
of dots like the atoms in a crystal. In three
dimensions, each distinct crystal lattice can
be characterized by three arrows or “basis
vectors” that can be added to and subtracted
from one another repeatedly to reconstruct
the structure. Describing a lattice in 1000
dimensions requires 1000 basis vectors.
Given only the basis vectors for a
1000-dimensional lattice, which two points in
the lattice are closest together? That is, what
is the shortest vector that can be made from
the basis vectors? That problem appears to be
hard, even for a quantum computer, Peikert
says. So he’s developing schemes in which the
basis vectors serve as the public key to encode
a message, and the shortest vector serves
as the private key to decode it. “In terms of
having something that is real that can be
measured and optimized, we are either there
or very close to there,” Peikert says.
Perhaps the best defense against a
quantum computer is another quantum
strategy: quantum key distribution. In that
technology, Alice passes Bob a secret key
encoded in individual photons. The photons
can be polarized—say, horizontally for 0 and
vertically for 1. Thanks to quantum theory,
Eve can’t measure the photons without
altering them and revealing herself.
A handful of companies already
sell quantum key distribution systems.
For example, ID Quantique in Geneva,
Switzerland, has roughly 100 systems in use;
its clients include the Canton of Geneva, which
protects election results with the technology.
Current systems cost about $100,000 for two
stations linked by an optical fiber. And they’re
not yet ideal: A message sent across a network
must be decoded at each station along the way,
where it might be intercepted.
To overcome that weakness, researchers
hope to use the photons not simply to send
the key, but to create a mysterious quantum
connection called entanglement between
qubits in 0-and-1 states at either end of a link.
Alice and Bob could then generate a secret
key by measuring their qubits: Alice would
measure hers, causing its state to “collapse”
into either 0 or 1. She’d know that Bob’s had
collapsed into the same state. Entanglement
could be passed from node to node, so that
Alice and Bob could share the key without
danger of spying at the nodes between them.
That vision requires a device called a
quantum repeater at each node. Such a thing
does not yet exist, but it should be easier
to make than a quantum computer, says
Gregoire Ribordy, co-founder and CEO of
ID Quantique: “Which is good, because it
means we will be able to do [fully] quantum
communications before encryption is broken.”
More immediate dangers
Even without a quantum computer, public
key systems are under pressure because of
improvements in algorithms and increases in
computing power. When RSA was invented
in 1977, mathematician and writer Martin
Gardner challenged readers to crack a message encoded with a 426-bit key. Ronald
Rivest, a computer scientist at MIT and one of
the inventors of RSA, estimated that it would
take 40 quadrillion years to do so. Seventeen years later, 600 volunteers decoded the
message in 8 months. To fend off such challenges, Internet companies such as Google
and Microsoft are now phasing out 1024-bit
RSA keys in favor of tougher 2048-bit ones.
But going further and switching to new
algorithms would be hugely expensive.
Widespread quantum key distribution would
require rewiring networks with optical fibers.
Without a dramatic threat, the technologies
may not be worth the hassle. “The old
joke is that one of the uses for quantum
computing is to create a market for quantum
key distribution,” says Scott Aaronson, a
theoretical computer scientist at MIT.
The economic calculus could also cut
the other way, however. If quantum-proof
algorithms and quantum key distribution
take off, then they might blunt the desire of
governments and private companies to build
a quantum computer. “It could happen,”
Ribordy says. “It’s a good argument.”
Aaronson argues that a quantum computer
will have other uses and that the real reason to
build one is to prove it can be done. “That’s a
harder case to make to many business people,
but I think that’s the honest case,” he says. It
also doesn’t sound like a goal that NSA would
spend $80 million to reach. –ADRIAN CHO
Trumped? As a code cracker, a quantum computer might be foiled by simpler quantum key distribution.
Weakness
Could crack current algorithms for public
key encryption
Passes key for private key algorithms under
eavesdroppers' noses
Can't break private key encryption, could be
shut out by quantum key distribution
Requires rewiring networks with optical fiber,
fully quantum network not yet possible
Has been a decade away for nearly 20 years
and may stay that way
Hard and expensive, but easier and cheaper
than building a quantum computer
Primarily a theoretical construct Entering market Status
Strength
Prospects
Universal Quantum Computer vs. Quantum Key Distribution
