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

Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries

François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman

Published Dec 11, 2024• 0 citations
arXivHTMLPDF

Abstract

In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.

DOI
10.48550/arxiv.2412.08091

Related papers

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

Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries

François Le Gall, Oran Nadler, Harumichi Nishimura +1 more

In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.

Leibniz international proceedings in informatics•Jan 1, 2025•1 citation

Quantum Communication Cannot Simulate a Public Coin

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e. whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper.

arXiv:quant-ph/0411051•Nov 8, 2004•34 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

New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques

Rahul Jain, Hartmut Klauck

Consider the following simultaneous message passing (SMP) model for computing a relation f sube X times Y times Z. In this model Alice, on input x isin X and Bob, on input y isin Y, send one message each to a third party Referee who then outputs a z isin Z such that (x, y, z) isin f. We first show optimal direct sum results for all relations / in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of /, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•21 citations

Communication Complexity of Private Simultaneous Quantum Messages Protocols

Akinori Kawachi, Harumichi Nishimura

The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum message from the private input $x_i$ and the shared random string (entangled states), and then sends it to the referee $R$. Receiving the messages, $R$ computes $F(x_1,\ldots,x_k)$. Then, $R$ learns nothing except for $F(x_1,\ldots,x_k)$ as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound $(3-o(1))n$ of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of $2n$-bit input, which is larger than the trivial upper bound $2n$ of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

arXiv:2105.07120•Leibniz international proceedings in informatics•Jan 1, 2021•15 citations
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.
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.
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.
We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e. whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper.
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.
Consider the following simultaneous message passing (SMP) model for computing a relation f sube X times Y times Z. In this model Alice, on input x isin X and Bob, on input y isin Y, send one message each to a third party Referee who then outputs a z isin Z such that (x, y, z) isin f. We first show optimal direct sum results for all relations / in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of /, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.
The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, kkk parties P1,…,PkP_1,\ldots,P_kP1​,…,Pk​ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xkx_1,\ldots, x_kx1​,…,xk​. Every PiP_iPi​ generates a quantum message from the private input xix_ixi​ and the shared random string (entangled states), and then sends it to the referee RRR. Receiving the messages, RRR computes F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​). Then, RRR learns nothing except for F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n(3-o(1))n(3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n2n2n-bit input, which is larger than the trivial upper bound 2n2n2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.