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 Conference on Computational Complexity (CCC)

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

Rahul Jain, Hartmut Klauck

Published Jul 1, 2009• 21 citations
Publisher

Abstract

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.

DOI
10.1109/ccc.2009.28

Related papers

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

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

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

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

Quantum Versus Classical Simultaneity in Communication Complexity

Dmitry Gavinsky

This paper addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication “layouts”: two-way interactive communication, one-way communication and simultaneous message passing (SMP). I demonstrate a functional (problem c̅E̅q̅T̅, whose communication complexity is O (log n)2) in the quantum version of the SMP and Ω̃ (√n) in the classical (randomized) version of SMP. Second, this paper contributes to understanding the power of the weakest commonly studied regime of quantum communication-SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model “as weak as possible”). Our function c̅E̅q̅T̅ has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.

arXiv:1705.07211•IEEE Transactions on Information Theory•May 22, 2019•10 citations

New bounds on private simultaneous quantum message passing

Uma Girish, Alex May, Natalie Parham +1 more

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then each send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $ε$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones.

quant-pharXiv:2606.12557•Jun 12, 2026•3 citations
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.
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 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.
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.
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.
This paper addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication “layouts”: two-way interactive communication, one-way communication and simultaneous message passing (SMP). I demonstrate a functional (problem c̅E̅q̅T̅, whose communication complexity is O (log n)2) in the quantum version of the SMP and Ω̃ (√n) in the classical (randomized) version of SMP. Second, this paper contributes to understanding the power of the weakest commonly studied regime of quantum communication-SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model “as weak as possible”). Our function c̅E̅q̅T̅ has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.
In the private simultaneous message (PSM) setting, kkk players obtain inputs xi∈{0,1}nx_i\in\{0,1\}^nxi​∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk)f(x_1,...,x_k)f(x1​,...,xk​) but no other information about (x1,...,xk)(x_1,...,x_k)(x1​,...,xk​). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for kkk-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2)f(x_1,x_2)f(x1​,x2​) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting sss be the size of a quantum circuit computing fff, dfd_fdf​ be the circuit depth, kkk the number of players, nnn the number of bits received by each player, and εεε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅log⁡O(df)(s/ε)\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)PSMk∗​(f)≤(kn+s)⋅logO(df​)(s/ε). 2) The square of the Fourier 1 norm of fff, ∥f^∥12\Vert \hat{f}\Vert_1^2∥f^​∥12​, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12)\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)PSM(f)≤O(∥f^​∥12​). In proving the first upper bound, we generalize existing TTT-depth based techniques for NLQC from 222 to k≥2k\geq 2k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.