Imagine two offices, located halfway around the world from each other, 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 the 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 that includes Harry Buhrman, CWI/University of Amsterdam, 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.
(Reference: H. Buhrman; R. Cleve; J. Watrous; R. de Wolf, Physical Review Letters, 15 Oct. 2001; full text at this URL)
(Editor's Note: This story is based on 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.)
[Contact: Harry Buhrman]
15-Oct-2001
