If you are a fan of police procedure series such as CSI, Law and Order, and others you are probably very aware of the importance of our fingerprints. They can lead the detectives straight to the culprit and, once he is caught, they can secure his (or her) arrest and conviction. The reason why fingerprints are so powerful is that each of us have a different set. Even though our fingerprints are a very small part of us they are enough to identify us.
Fig. 1: Fingerprint
Fingerprinting in computer systems work in a similar way. Computer information is usually a sequence of zeros and ones but they can add up to very long strings of data. Given two strings can you differentiate between the two without having to read the entire string? That’s where fingerprinting comes in. Fingerprinting algorithms map arbitrarily large data items (computer files, for example) to a much smaller string. This string is called the Fingerprint of the item and it can be used to identify if two files are equal or not. For example, this is how web browse check if a remote file has been modified.
That’s all very nice, but a question does arise: how small can this Fingerprint be? What is the minimum amount of information that needs to be provided so that you can differentiate between two strings? You don’t want a fingerprint to be as large as the original file but you also want it to be a reliable tool. How small the fingerprint can be?
Let’s consider a setting where two people, Alice and Bob, each receive a string of information. None of them know anything about what the other received. Then, Alice and Bob separately prepare a Fingerprint for the file they received and they send it to a third party, the Referee. By looking at the Fingerprint the Referee must determine whether Alice and Bob received the same data or not. This setting is known as a simultaneous message-passing model and is frequently used in computer sciences.
Alice and Bob can communicate with the Referee in two different ways: using classical or quantum communication. Classical communication uses bits, sequences of ones and zeros, that are transported from one place to another (that’s the one your browser uses). In quantum communication quantum states, called q-bits, are transferred from one place to another, and that makes a big difference. It has been shown that the best classical communication protocols require a Fingerprint that scales with the square root of the size of the original file. Therefore, for a file with 106 bytes, you’ll need about 103 bytes in the fingerprint. However, if quantum communication is used the size of the Fingerprint can be greatly diminished.
Fig. 2: Experimental setting used for the quantum fingerprinting protocol.
The theory behind quantum fingerprint has been around since 2011, but there hadn’t been an experimental realization that proved that quantum communication could, in fact, involve a smaller Fingerprint than it’s classical analogue. Now, in 2016, a group of scientists from China have experimentally demonstrated a quantum fingerprinting protocol that beats the classical limit. They showed that quantum fingerprinting can transmit less information than what would be required for classical fingerprinting. In some cases, this reduction was up to 84%.
The protocol used by the scientists still needs some adjustments and improvements before it can be used in real world applications. For example, even though it uses less energy overall it takes more time to run. But it is an impressive finding that shows how amazing quantum mechanics can be. Plus, it can very likely lead to very interesting developments in communication theory.
By Kellen Manoela Siqueira
The full paper can be found in the June, 2016 edition of Physical Review Letters.