We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (bounded error) model.
We present a two-player communication task that can be solved by a protocol of polylogarithmic cost in the simultaneous message passing model with classical communication and shared entanglement, but requires exponentially more communication in the classical interactive model. Our second result is a two-player nonlocality game with input length n and output of polylogarithmic length, that can be won with probability 1-o(1) by players sharing polylogarithmic amount of entanglement. On the other hand, the game is lost with probability Ω(1) by players without entanglement, even if they are allowed to exchange up to k bits in interactive communication for certain k∈Ω(n1/4). These two results give almost the strongest possible (and the strongest known) indication of nonlocal properties of two-party entanglement.
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(logn) qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.
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 xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) 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=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(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 Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(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(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.
We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Boolean functions f:{0,1}n×{0,1}m→{0,1} we have DA→B(f)≤O(QA→B,∗(f)⋅m). This bound was previously known for total functions, while for partial functions this improves on results by Aaronson, in which either a log-factor on the right hand is present, or the left hand side is RA→B(f), and in which also no entanglement is allowed. In our second contribution we investigate the power of quantum proofs over classical proofs. We give the first example of a scenario, where quantum proofs lead to exponential savings in computing a Boolean function. The previously only known separation between the power of quantum and classical proofs is in a setting where the input is also quantum. We exhibit a partial Boolean function f, such that there is a one-way quantum communication protocol receiving a quantum proof (i.e., a protocol of type QMA) that has cost O(logn) for f, whereas every one-way quantum protocol for f receiving a classical proof (protocol of type QCMA) requires communication Ω(n/logn).