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²⁰ bits each. They could transmit the database to the headquarters, and the headquarters could compare them. But transmitting 10²⁰ 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¹⁰ 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¹⁰ bits--is then sent to the headquarters.

Now, a Dutch-Canadian team (Harry Buhrman, CWI/University of Amsterdam, 011-31-20-5924076, buhrman@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²⁰ 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.)