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:quant-ph/0505088

A Note on Shared Randomness and Shared Entanglement in Communication

Dmitry Gavinsky

Published May 12, 2005• 4 citations
arXivHTMLPDF

Abstract

We consider several models of 1-round classical and quantum communication, some of these models have not been defined before. We "almost separate" the models of simultaneous quantum message passing with shared entanglement and the model of simultaneous quantum message passing with shared randomness. We define a relation which can be efficiently exactly solved in the first model but cannot be solved efficiently, either exactly or in 0-error setup in the second model. In fact, our relation is exactly solvable even in a more restricted model of simultaneous classical message passing with shared entanglement. As our second contribution we strengthen a result by Yao that a "very short" protocol from the model of simultaneous classical message passing with shared randomness can be simulated in the model of simultaneous quantum message passing: for a boolean function f, QII(f) \in exp(O(RIIp(f))) log n. We show a similar result for protocols from a (stronger) model of 1-way classical message passing with shared randomness: QII(f) \in exp(O(RIp(f))) log n. We demonstrate a problem whose efficient solution in the model of simultaneous quantum message passing follows from our result but not from Yao's.

DOI
10.48550/arxiv.quant-ph/0505088

Related papers

Shared Randomness and Quantum Communication in the Multi-Party Model

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the second strongest mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.

•Oct 4, 2012•4 citations

Shared Randomness and Quantum Communication in the Multi-Party Model

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call "XOR-shared randomness." Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the "second strongest" mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.

arXiv:1210.1535•Oct 4, 2012•4 citations

Shared randomness and entanglement in communication complexity

Dmitry Gavinsky

We study the role of shared randomness and shared entanglement in the context of communication complexity, both classical and quantum.In the first part of this thesis we present two exponential separations in the simultaneous message passing model of communication complexity.First, we describe a relation that can be computed with O(log ri) classical bits of communication in the presence of shared randomness, but needs (n'/3) communication if the parties do not share randomness, even if communication is quantum.Second, we describe a

•Jan 1, 2006•0 citations

Shared Randomness and Quantum Communication in the Multi-party Model

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared randomness. Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k ≥ 3 is any constant. We demonstrate a promise function GPkthat can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send nΩ(1)qubits to compute it. Moreover, the quantum complexity of GPk remains nΩ(1)even if the “second strongest” mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: · In the two-party case, only a relational communication problem with similar properties is known. · In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2O(c)log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•5 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

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
We consider several models of 1-round classical and quantum communication, some of these models have not been defined before. We "almost separate" the models of simultaneous quantum message passing with shared entanglement and the model of simultaneous quantum message passing with shared randomness. We define a relation which can be efficiently exactly solved in the first model but cannot be solved efficiently, either exactly or in 0-error setup in the second model. In fact, our relation is exactly solvable even in a more restricted model of simultaneous classical message passing with shared entanglement. As our second contribution we strengthen a result by Yao that a "very short" protocol from the model of simultaneous classical message passing with shared randomness can be simulated in the model of simultaneous quantum message passing: for a boolean function f, QII(f) \in exp(O(RIIp(f))) log n. We show a similar result for protocols from a (stronger) model of 1-way classical message passing with shared randomness: QII(f) \in exp(O(RIp(f))) log n. We demonstrate a problem whose efficient solution in the model of simultaneous quantum message passing follows from our result but not from Yao's.
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the second strongest mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call "XOR-shared randomness." Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the "second strongest" mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.
We study the role of shared randomness and shared entanglement in the context of communication complexity, both classical and quantum.In the first part of this thesis we present two exponential separations in the simultaneous message passing model of communication complexity.First, we describe a relation that can be computed with O(log ri) classical bits of communication in the presence of shared randomness, but needs (n'/3) communication if the parties do not share randomness, even if communication is quantum.Second, we describe a
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared randomness. Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k ≥ 3 is any constant. We demonstrate a promise function GPkthat can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send nΩ(1)qubits to compute it. Moreover, the quantum complexity of GPk remains nΩ(1)even if the “second strongest” mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: · In the two-party case, only a relational communication problem with similar properties is known. · In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2O(c)log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.
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.
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.