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

arXiv:1810.12808 · Physical Review A

Quantum sketching protocols for Hamming distance and beyond

João Fernando Doriguello, Ashley Montanaro

Published Jun 24, 2019• 7 citations
arXivHTMLPDF

Abstract

Comparing data is ubiquitous in communication, and quantum protocols like quantum fingerprinting provide an exponential advantage in the complexity of equality testing. In this work, a quantum protocol for approximately computing another comparison measure, the Hamming distance, up to low relative error, is developed.
DOI
10.1103/physreva.99.062331

Related papers

Classical vs Quantum Fingerprinting

Barry C. Sanders

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

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 24, 2005•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

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

Experimental demonstration of quantum advantage in communication complexity for Euclidean distance problem

Verena Yacoub, Niraj Kumar, Iordanis Kerenidis +1 more

When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of $10^8$, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.

quant-pharXiv:2605.31516•Jun 1, 2026•0 citations

On the power of quantum fingerprinting

Andrew Chi-Chih Yao

In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R<??par line>,pub(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•44 citations

On the power of quantum fingerprinting

Andrew Chi-Chih Yao

In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R<??par line>,pub(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•3 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.
When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of 10810^8108, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.
In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R<??par line>,pub(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.
In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R<??par line>,pub(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.