Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Multiple-Valued Logic (ISMVL)

Classical vs Quantum Fingerprinting

Barry C. Sanders

Published May 24, 2005• 0 citations
Publisher

Abstract

When communication is expensive, the important task of testing two binary strings for equality can be achieved by generating relatively short fingerprints of each string and comparing those fingerprints. Quantum fingerprinting, in which the fingerprint is encoded onto qubits (the quantum version of the bit), is significantly less expensive: exponentially better in the case of no shared randomness and potentially perfect for the case of shared entanglement. Single-qubit quantum fingerprinting is feasible, and we have demonstrated its advantages theoretically and experimentally

DOI
10.1109/ismvl.2005.13

Related papers

Quantum Fingerprinting

Harry Buhrman, Richard Cleve, John Watrous +1 more

Classical fingerprinting associates with each string a shorter string (its fingerprint), such that any two distinct strings can be distinguished with small error by comparing their fingerprints alone. The fingerprints cannot be made exponentially smaller than the original strings unless the parties preparing the fingerprints have access to correlated random sources. We show that fingerprints consisting of quantum information can be made exponentially smaller than the original strings without any correlations or entanglement between the parties. This implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity.

arXiv:quant-ph/0102001•Physical Review Letters•Sep 26, 2001•1,188 citations

Single-Qubit Optical Quantum Fingerprinting

Rolf T. Horn, С. А. Бабичев, Karl-Peter Marzlin +2 more

We analyze and demonstrate the feasibility and superiority of linear optical single-qubit fingerprinting over its classical counterpart. For one-qubit fingerprinting of two-bit messages, we prepare "tetrahedral" qubit states experimentally and show that they meet the requirements for quantum fingerprinting to exceed the classical capability. We prove that shared entanglement permits 100% reliable quantum fingerprinting, which will outperform classical fingerprinting even with arbitrary amounts of shared randomness.

arXiv:quant-ph/0410232•Physical Review Letters•Oct 4, 2005•55 citations

Single-qubit optical quantum fingerprinting

Rolf T. Horn, Karl-Peter Marzlin, Barry C. Sanders

We show that single qubit quantum fingerprinting without shared randomness is feasible with linear optics and is demonstrably superior to its classical counterpart. Furthermore a shared source of entanglement, provided for example by a parametric down converter, permits 100% reliable quantum fingerprinting, which outperforms classical fingerprinting even with arbitrary amounts of shared randomness.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Oct 19, 2004•10 citations

Quantum fingerprinting without a shared phase reference

Michał Lipka, Marcin Jarzyna, Michał Jachura +1 more

One of the standard communication complexity problems is deciding whether bit strings held by two separate parties Alice (A) and Bob (B) are equal or different. In the simultaneous message passing model, A and B send certain information to a Referee, who makes the decision. The overall goal is to minimize the amount of communication involved while not exceeding desired error probability. This is achieved by sending only fingerprints of the original n-bit strings. In the best classical protocols, these scale as O(√n) if A and B have no access to shared randomness [1]. The recently proposed [2] and demonstrated quantum fingerprinting [3], exploiting phase-modulated weak coherent pulses, provides O(log2n) scaling in the number of used qubits, but needs phase stability between A and B. Here we introduce and analyse a quantum fingerprinting protocol based on two-photon interference which does require a shared phase reference and works in scenarios when the global phase of transmitted signals becomes completely random. Interestingly, the performance of this protocol, quantified in terms of the Chernoff information [4], is enhanced through the use of non-classical single-photon states, even in the regime of high transmission loss.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 1, 2017•0 citations

Realization of Communication Protocols with a Quantitative Quantum Communication Advantage

Juan Miguel Arrazola, Dave Touchette, Benjamin Lovitz +2 more

Quantum Fingerprinting offers a exponential advantage over classical protocols in comparing two remote files by a referee in the simultaneous message passing protocol without shared randomness. We show how to realize this advantage using simple optical communication techniques.

Frontiers in Optics•Jan 1, 2016•0 citations

Practical Quantum Communication

Juan Miguel Arrazola

Current communication networks are based on classical physics and classical information-processing. However, for nearly a century, we have known that at its most fundamental level, the universe is governed by the laws of quantum mechanics. With quantum communication, new possibilities arise in our capabilities to transmit and process information which, in many cases, lead to advantages compared to what is classically possible. The entire scope of tasks for which quantum communication can offer improvements has not yet been fully explored, but several quantum protocols are known that can either perform tasks which are impossible with classical resources or can outperform classical protocols. These quantum protocols are well understood from a theoretical point of view, but many of them have never been demonstrated in practice. Thus, in the context of quantum communication, there is a significant gap between theory and experiment that must be removed in order to harness the advantages provided by quantum mechanics in a practical setting. \n \nIn this thesis, we develop a series of tools for developing and testing practical quantum communication protocols. Our main technique is a theoretical reformulation of existing quantum communication protocols that converts them into a form in which they can be demonstrated with existing experimental techniques. More precisely, they can be implemented using only coherent states of light and linear optics circuits while still retaining the crucial properties of the original abstract protocols. We use this result to construct practical protocols for the Hidden Matching problem and quantum fingerprinting. \n \n \nIn the case of quantum fingerprinting, we make a thorough analysis of the role played by experimental errors and show that our practical protocol can still be implemented in the presence of these imperfections. In fact, we report a proof of concept experimental demonstration of a quantum fingerprinting system that is capable of transmitting less information than the best known classical protocol for this problem. Our implementation is based on a modified version of a commercial quantum key distribution system using off-the-shelf optical components over telecom wavelengths, and is practical for messages as large as 100 Mbits, even in the presence of experimental imperfections. \n \nSimilarly, in the context of cryptography, we propose a multiparty quantum signature protocol that can be implemented from any point-to-point quantum key distribution network, proving its security against forging, repudiation and non-transferability. Crucially, since quantum key distribution is already a practical technology, so is this protocol. However, unlike other tasks in quantum communication, there has not been significant theoretical work on establishing a security model for quantum signature schemes. Consequently, we also constructed a security framework for these schemes and proved several properties that these protocols must satisfy in order to achieve their security goals. \n \nFinally, in addition to proposing new practical protocols, we provide a reliable data analysis technique to verify an important property of many quantum communication protocols: the presence of entanglement. Our technique is based on entanglement witnesses and it does not require the specification of a prior distribution nor the assumption of independent measurements. The technique is suitable to be used with nonlinear entanglement witnesses, which we show can be constructed from any linear witness and evaluated from the same experimental data. We also develop numerical tools necessary to employ this approach in practice, rendering the procedure ready to be applied to current experiments. We demonstrate this by analyzing the data of a photonic experiment generating two-photon states whose entanglement is verified with the use of an accessible nonlinear witness.

•Oct 30, 2015•0 citations
When communication is expensive, the important task of testing two binary strings for equality can be achieved by generating relatively short fingerprints of each string and comparing those fingerprints. Quantum fingerprinting, in which the fingerprint is encoded onto qubits (the quantum version of the bit), is significantly less expensive: exponentially better in the case of no shared randomness and potentially perfect for the case of shared entanglement. Single-qubit quantum fingerprinting is feasible, and we have demonstrated its advantages theoretically and experimentally
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that any two distinct strings can be distinguished with small error by comparing their fingerprints alone. The fingerprints cannot be made exponentially smaller than the original strings unless the parties preparing the fingerprints have access to correlated random sources. We show that fingerprints consisting of quantum information can be made exponentially smaller than the original strings without any correlations or entanglement between the parties. This implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity.
We analyze and demonstrate the feasibility and superiority of linear optical single-qubit fingerprinting over its classical counterpart. For one-qubit fingerprinting of two-bit messages, we prepare "tetrahedral" qubit states experimentally and show that they meet the requirements for quantum fingerprinting to exceed the classical capability. We prove that shared entanglement permits 100% reliable quantum fingerprinting, which will outperform classical fingerprinting even with arbitrary amounts of shared randomness.
One of the standard communication complexity problems is deciding whether bit strings held by two separate parties Alice (A) and Bob (B) are equal or different. In the simultaneous message passing model, A and B send certain information to a Referee, who makes the decision. The overall goal is to minimize the amount of communication involved while not exceeding desired error probability. This is achieved by sending only fingerprints of the original n-bit strings. In the best classical protocols, these scale as O(√n) if A and B have no access to shared randomness [1]. The recently proposed [2] and demonstrated quantum fingerprinting [3], exploiting phase-modulated weak coherent pulses, provides O(log2n) scaling in the number of used qubits, but needs phase stability between A and B. Here we introduce and analyse a quantum fingerprinting protocol based on two-photon interference which does require a shared phase reference and works in scenarios when the global phase of transmitted signals becomes completely random. Interestingly, the performance of this protocol, quantified in terms of the Chernoff information [4], is enhanced through the use of non-classical single-photon states, even in the regime of high transmission loss.
Current communication networks are based on classical physics and classical information-processing. However, for nearly a century, we have known that at its most fundamental level, the universe is governed by the laws of quantum mechanics. With quantum communication, new possibilities arise in our capabilities to transmit and process information which, in many cases, lead to advantages compared to what is classically possible. The entire scope of tasks for which quantum communication can offer improvements has not yet been fully explored, but several quantum protocols are known that can either perform tasks which are impossible with classical resources or can outperform classical protocols. These quantum protocols are well understood from a theoretical point of view, but many of them have never been demonstrated in practice. Thus, in the context of quantum communication, there is a significant gap between theory and experiment that must be removed in order to harness the advantages provided by quantum mechanics in a practical setting. \n \nIn this thesis, we develop a series of tools for developing and testing practical quantum communication protocols. Our main technique is a theoretical reformulation of existing quantum communication protocols that converts them into a form in which they can be demonstrated with existing experimental techniques. More precisely, they can be implemented using only coherent states of light and linear optics circuits while still retaining the crucial properties of the original abstract protocols. We use this result to construct practical protocols for the Hidden Matching problem and quantum fingerprinting. \n \n \nIn the case of quantum fingerprinting, we make a thorough analysis of the role played by experimental errors and show that our practical protocol can still be implemented in the presence of these imperfections. In fact, we report a proof of concept experimental demonstration of a quantum fingerprinting system that is capable of transmitting less information than the best known classical protocol for this problem. Our implementation is based on a modified version of a commercial quantum key distribution system using off-the-shelf optical components over telecom wavelengths, and is practical for messages as large as 100 Mbits, even in the presence of experimental imperfections. \n \nSimilarly, in the context of cryptography, we propose a multiparty quantum signature protocol that can be implemented from any point-to-point quantum key distribution network, proving its security against forging, repudiation and non-transferability. Crucially, since quantum key distribution is already a practical technology, so is this protocol. However, unlike other tasks in quantum communication, there has not been significant theoretical work on establishing a security model for quantum signature schemes. Consequently, we also constructed a security framework for these schemes and proved several properties that these protocols must satisfy in order to achieve their security goals. \n \nFinally, in addition to proposing new practical protocols, we provide a reliable data analysis technique to verify an important property of many quantum communication protocols: the presence of entanglement. Our technique is based on entanglement witnesses and it does not require the specification of a prior distribution nor the assumption of independent measurements. The technique is suitable to be used with nonlinear entanglement witnesses, which we show can be constructed from any linear witness and evaluated from the same experimental data. We also develop numerical tools necessary to employ this approach in practice, rendering the procedure ready to be applied to current experiments. We demonstrate this by analyzing the data of a photonic experiment generating two-photon states whose entanglement is verified with the use of an accessible nonlinear witness.