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.
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 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 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 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 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.
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∥-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∥-protocols. We apply our technique to obtain an efficient Q∥-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 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