update.560 (fwd)

[Jim Choate]

---------- Forwarded message ----------
Date: Tue, 9 Oct 2001 09:31:32 -0400 (EDT)
From: AIP listserver <physnews at aip.org>
To: physnews-mailing at aip.org
Subject: update.560

PHYSICS NEWS UPDATE                         
The American Institute of Physics Bulletin of Physics News
Number 560  October 9, 2001   by Phillip F. Schewe, Ben Stein, and
James Riordon

THE 2001 NOBEL PRIZE IN PHYSICS goes to Eric Cornell of
[SSZ: text deleted]

QUANTUM FINGERPRINTING.  Imagine two offices, located
halfway around the world, and their headquarters wants to make
sure that they each have the identical copy of a database.  Imagine
further that the databases are huge--10^20 bits each.  They could
transmit the database to the headquarters, and the headquarters
could compare them.  But transmitting 10^20 bits--equal to about
11 billion gigabytes would take an enormous amount of time.
There is a method in which they only need to send 10^10 bits--a
little over a gigabyte--and the headquarters still gets enough
information to determine that they have the exact same database. 
This method is called "classical fingerprinting."  The idea is that
each office independently, without communicating to each other,
generates a distinctive number, called a fingerprint, by performing
a calculation involving the entire database and locally generated
random numbers, called keys.  The result of the calculation-a
fingerprint of 10^10 bits--is then sent to the headquarters.  Now, a
Dutch-Canadian team (Harry Buhrman, CWI/University of
Amsterdam, 011-31-20-5924076, buhrman at cwi.nl) has suggested
a "quantum fingerprinting" scheme which would involve an
exponentially smaller transmission of information to do the same
job.  For the 10^20 bit database, each office would only have to
transmit a fingerprint of about 70 "quantum bits" (qubits), which
could be, for example, specially prepared photons.  Such photons
could contain the result of a computation between the database and
many different random keys simultaneously, rather than a single
random key.  The researchers say that one could demonstrate this
new fingerprinting technique with quantum computers not much
more complex than the ones that exist today.  Buhrman estimates
that quantum fingerprinting becomes more efficient than classical
fingerprinting in a quantum computer with 5 to 10 qubits.  (H.
Buhrman; R. Cleve; J. Watrous; R. de Wolf, Physical Review
Letters, 15 Oct. 2001; full text at www.aip.org/physnews/select)