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:2502.13427

Does there exist a quantum fingerprinting protocol without coherent measurements?

Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, Qisheng Wang

Published Feb 19, 2025• 0 citations
arXivHTMLPDF

Abstract

Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with $O(\log n)$ qubits communication for the equality problem. In the protocol, Alice and Bob create some quantum fingerprints of their inputs, and the referee conducts the SWAP tests for the quantum fingerprints. Since $Ω(\sqrt{n})$ bits communication is required with the classical SMP scheme for the equality problem first shown by Newman and Szegedy (STOC 1996), there exists an exponential quantum advantage in the amount of communication. In this paper, we consider a setting in which the referee can do only incoherent measurements rather than coherent measurements including the SWAP tests. We first show that, in the case of one-way LOCC measurements, $Ω(\sqrt{n})$ qubits communication is required. To prove the result, we derive a new method to replace quantum messages by classical messages and consider a reduction to the optimal lower bound in the hybrid SMP model where one message is quantum and the other is classical, which was first shown by Klauck and Podder (MFCS 2014). Our method uses the result of Oszmaniec, Guerini, Wittek, and Acín (PRL 2017), who showed that general POVM measurements can be simulated by randomized projective measurements with small ancilla qubits, and Newman's theorem. We further investigate the setting of quantum SMP protocols with two-way LOCC measurements, and derive a lower bound against some restricted two-way LOCC measurements. To prove it, we revisit the technique to replace quantum messages by classical deterministic messages introduced by Aaronson (ToC 2005) and generalized by Gavinsky, Regev, and de Wolf (CJTCS 2008), and show that, using the deterministic message, the referee can simulate the two-way LOCC measurements.

DOI
10.48550/arxiv.2502.13427

Related papers

One-qubit fingerprinting schemes

Niel de Beaudrap

Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.

arXiv:quant-ph/0309036•Physical Review A•Feb 18, 2004•30 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•5 citations

Simultaneous Communication Protocols with Quantum and Classical Messages

Dmitry Gavinsky, Oded Regev, Ronald de Wolf

We study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical.We show that in an SMP protocol that computes some function with the first party sending q qubits and the second sending c classical bits, the quantum message can be replaced by a randomized message of O(qc) classical bits, as well as by a deterministic message of O(qc log q) classical bits.Our proofs rely heavily on earlier results due to Scott Aaronson [1,2].In particular, our results imply that quantum-classical protocols need to send Ω( n/ log n) bits/qubits to compute Equality on n-bit strings, and hence are not significantly better than classical-classical protocols (and are much worse than quantum-quantum protocols such as quantum fingerprinting).This essentially answers a recent question of Wim van Dam [7].Our results also imply, more generally, that there are no superpolynomial separations between quantumclassical and classical-classical SMP protocols for functional problems.This contrasts with the situation for relational problems, where exponential gaps between quantum-classical and classical-classical SMP protocols are known.We show that this surprising situation cannot arise in purely classical models: there, an exponential separation for a relational problem can be converted into an exponential separation for a functional problem.

arXiv:0807.2758•Chicago Journal of Theoretical Computer Science•Jan 1, 2008•14 citations

Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication

Daiki Suruga

Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function $f$ and fixed error $0\le\varepsilon<1$, we prove that the optimal worst-case communication per instance for $f^n$ converges to \[ D^\parallel(f)=\log|\mathrm{Row}(f)|+\log|\mathrm{Col}(f)|, \] where $\mathrm{Row}(f)$ and $\mathrm{Col}(f)$ are the sets of distinct rows and columns of the table $(f(x,y))_{x,y}$. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all $n$ outputs correctly to decay as $2^{-Ω(n)}$, even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is $(1-\varepsilon)D^\parallel(f)$. Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with $D^\parallel(f)$ replaced by $\log|\mathrm{Row}(f)|$. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.

quant-pharXiv:2609.14658•Sep 15, 2026•0 citations

Strengths and Weaknesses of Quantum Fingerprinting

Gavinsky, Dmytro, Julia Kempe, Ronald de Wolf

We study the power of quantum fingerprints in the simultaneous message passing (SMP) setting of communication complexity. Yao recently showed how to simulate, with exponential overhead, classical shared-randomness SMP protocols by means of quantum SMP protocols without shared randomness ($Q^\parallel$-protocols). Our first result is to extend Yao's simulation to the strongest possible model: every many-round quantum protocol with unlimited shared entanglement can be simulated, with exponential overhead, by $Q^\parallel$-protocols. We apply our technique to obtain an efficient $Q^\parallel$-protocol for a function which cannot be efficiently solved through more restricted simulations. Second, we tightly characterize the power of the quantum fingerprinting technique by making a connection to arrangements of homogeneous halfspaces with maximal margin. These arrangements have been well studied in computational learning theory, and we use some strong results obtained in this area to exhibit weaknesses of quantum fingerprinting. In particular, this implies that for almost all functions, quantum fingerprinting protocols are exponentially worse than classical deterministic SMP protocols.

arXiv:quant-ph/0603173•Mar 20, 2006•18 citations

On the Limits of Quantum Multiparty Simultaneous Communication

Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

cs.CCCross-listedarXiv:2609.10289•Sep 10, 2026•0 citations
Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with O(log⁡n)O(\log n)O(logn) qubits communication for the equality problem. In the protocol, Alice and Bob create some quantum fingerprints of their inputs, and the referee conducts the SWAP tests for the quantum fingerprints. Since Ω(n)Ω(\sqrt{n})Ω(n​) bits communication is required with the classical SMP scheme for the equality problem first shown by Newman and Szegedy (STOC 1996), there exists an exponential quantum advantage in the amount of communication. In this paper, we consider a setting in which the referee can do only incoherent measurements rather than coherent measurements including the SWAP tests. We first show that, in the case of one-way LOCC measurements, Ω(n)Ω(\sqrt{n})Ω(n​) qubits communication is required. To prove the result, we derive a new method to replace quantum messages by classical messages and consider a reduction to the optimal lower bound in the hybrid SMP model where one message is quantum and the other is classical, which was first shown by Klauck and Podder (MFCS 2014). Our method uses the result of Oszmaniec, Guerini, Wittek, and Acín (PRL 2017), who showed that general POVM measurements can be simulated by randomized projective measurements with small ancilla qubits, and Newman's theorem. We further investigate the setting of quantum SMP protocols with two-way LOCC measurements, and derive a lower bound against some restricted two-way LOCC measurements. To prove it, we revisit the technique to replace quantum messages by classical deterministic messages introduced by Aaronson (ToC 2005) and generalized by Gavinsky, Regev, and de Wolf (CJTCS 2008), and show that, using the deterministic message, the referee can simulate the two-way LOCC measurements.
Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.
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.
We study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical.We show that in an SMP protocol that computes some function with the first party sending q qubits and the second sending c classical bits, the quantum message can be replaced by a randomized message of O(qc) classical bits, as well as by a deterministic message of O(qc log q) classical bits.Our proofs rely heavily on earlier results due to Scott Aaronson [1,2].In particular, our results imply that quantum-classical protocols need to send Ω( n/ log n) bits/qubits to compute Equality on n-bit strings, and hence are not significantly better than classical-classical protocols (and are much worse than quantum-quantum protocols such as quantum fingerprinting).This essentially answers a recent question of Wim van Dam [7].Our results also imply, more generally, that there are no superpolynomial separations between quantumclassical and classical-classical SMP protocols for functional problems.This contrasts with the situation for relational problems, where exponential gaps between quantum-classical and classical-classical SMP protocols are known.We show that this surprising situation cannot arise in purely classical models: there, an exponential separation for a relational problem can be converted into an exponential separation for a functional problem.
Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function fff and fixed error 0≤ε<10\le\varepsilon<10≤ε<1, we prove that the optimal worst-case communication per instance for fnf^nfn converges to D∥(f)=log⁡∣Row(f)∣+log⁡∣Col(f)∣, D^\parallel(f)=\log|\mathrm{Row}(f)|+\log|\mathrm{Col}(f)|, D∥(f)=log∣Row(f)∣+log∣Col(f)∣, where Row(f)\mathrm{Row}(f)Row(f) and Col(f)\mathrm{Col}(f)Col(f) are the sets of distinct rows and columns of the table (f(x,y))x,y(f(x,y))_{x,y}(f(x,y))x,y​. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all nnn outputs correctly to decay as 2−Ω(n)2^{-Ω(n)}2−Ω(n), even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is (1−ε)D∥(f)(1-\varepsilon)D^\parallel(f)(1−ε)D∥(f). Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with D∥(f)D^\parallel(f)D∥(f) replaced by log⁡∣Row(f)∣\log|\mathrm{Row}(f)|log∣Row(f)∣. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.
We study the power of quantum fingerprints in the simultaneous message passing (SMP) setting of communication complexity. Yao recently showed how to simulate, with exponential overhead, classical shared-randomness SMP protocols by means of quantum SMP protocols without shared randomness (Q∥Q^\parallelQ∥-protocols). Our first result is to extend Yao's simulation to the strongest possible model: every many-round quantum protocol with unlimited shared entanglement can be simulated, with exponential overhead, by Q∥Q^\parallelQ∥-protocols. We apply our technique to obtain an efficient Q∥Q^\parallelQ∥-protocol for a function which cannot be efficiently solved through more restricted simulations. Second, we tightly characterize the power of the quantum fingerprinting technique by making a connection to arrangements of homogeneous halfspaces with maximal margin. These arrangements have been well studied in computational learning theory, and we use some strong results obtained in this area to exhibit weaknesses of quantum fingerprinting. In particular, this implies that for almost all functions, quantum fingerprinting protocols are exponentially worse than classical deterministic SMP protocols.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of kkk players receives an unrestricted string xj∈{0,1}nx_j\in\{0,1\}^nxj​∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0nx_1\oplus\cdots\oplus x_k=0^nx1​⊕⋯⊕xk​=0n. For k≥8k\ge8k≥8 and worst-case error at most 1/31/31/3, we prove quantum lower bounds of Ω(min⁡{n,k2})Ω(\min\{n,k^2\})Ω(min{n,k2}) on total communication and Ω(min⁡{n/k,k})Ω(\min\{n/k,k\})Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/41/41/4. For n=k2n=k^2n=k2 and worst-case error at most 1/31/31/3, we prove that quantum protocols require maximum message length Ω(n)Ω(\sqrt n)Ω(n​) qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a kkk-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k)Ω(n^{1-1/k})Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8)\varepsilon\in(0,1/8)ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1))Ω(n^{(k-1)/(k+1)})Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(log⁡n)O(\log n)O(logn), giving exponential separations in both regimes. The implicit constants are independent of kkk, and both quantum lower bounds become linear when k≥clog⁡nk\ge c\log nk≥clogn for any fixed c>0c>0c>0.