Simultaneous Communication Protocols with Quantum and Classical Messages

Dmitry Gavinsky^{∗}  Oded Regev^{†}  Ronald de Wolf^{‡}

December 29, 2008

Abstract

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 Ω(\sqrt{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.

1 Introduction

We consider the simultaneous message passing (SMP) model of communication complexity. Here Alice receives input x and Bob receives input y. They each send one message to a third party, called the “referee.” Given the two messages, the referee outputs a value which should equal the function value f(x, y) with probability at least, say, 2/3.

We are interested in comparing classical and quantum SMP protocols. Consider for instance the Equality function: x, y ∈ {0, 1}^{n}, and f(x, y) = 1 iff x = y. If Alice and Bob do not share randomness, then this function exhibits an exponential quantum-classical gap: there is an SMP protocol for f where Alice and Bob each send O(log n) quantum bits to the referee [6], using a technique called “quantum fingerprinting.” On the other hand, if the messages are classical, then Θ(\sqrt{n})-bit messages are necessary and sufficient [3, 12, 4], as we will explain in Section 3.

∗NEC Laboratories America, Inc. 4 Independence Way, Suite 200. Princeton, U.S.A.

†School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel. Supported by the Binational Science Foundation, by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, and by a European Research Council (ERC) Starting Grant.

‡CWI, Kruislaan 413, 1098SJ Amsterdam, The Netherlands. Partially supported by Veni and Vidi grants from the Netherlands Organization for Scientific Research (NWO), and by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848.

Here we consider a question recently asked by Wim van Dam [7]: what happens if one of the messages (say Alice’s) is quantum, while the other is restricted to be classical? We call such protocols quantum-classical SMP protocols. For instance, one may ask whether some variant of quantum fingerprinting still works if one of the two messages is classical.

Our main results here say that the quantum message can be “simulated” by a classical message that is only moderately larger. More specifically, we show that the following hold for protocols computing a Boolean function:

• In Theorem 4 we show that a private-coin (resp. public-coin) quantum-classical protocol where Alice sends q qubits and Bob sends c bits, gives a private-coin (resp. public-coin) classical-classical protocol where Alice sends a randomized O(qc)-bit message and Bob sends a randomized c-bit message.

• In Corollary 6 we show that a private-coin quantum-classical protocol where Alice sends q qubits and Bob sends c bits, gives a private-coin classical-classical protocol where Alice sends a deterministic O(qc log q)-bit message and Bob sends a randomized c-bit message.

Our proofs rely heavily on earlier results in the one-way communication model by Aaronson [1, 2].

The latter result implies that quantum-classical private-coin protocols for Equality need to send Ω(\sqrt{n/ log n}) bits and/or qubits. This is not significantly better than the Θ(\sqrt{n}) bits that are necessary and sufficient for classical protocols.

The results above are rather unusual in communication complexity, where typically introducing quantum elements gives exponentially more power for at least some problems. The exponential improvements given by the quantum-quantum fingerprinting protocol is a prime example of this. This is also the case with one-way communication complexity, where we know Boolean functions whose quantum complexity is exponentially smaller than their classical complexity [8]. As another example, Gavinsky et al. [8] exhibit a function with an exponential gap between classical-classical SMP protocols with shared entanglement and those with only shared randomness. Yet another example is obtained when considering relations instead of functions in our model [5]. We elaborate on this in Section 7.

2 Preliminaries

We assume familiarity with quantum computing [13] and with the basic notions of classical and quantum communication complexity [10, 14]. Informally, the setting of communication complexity is as follows. Alice receives some input x ∈ X, Bob receives some input y ∈ Y, and together they want to compute some function f(x, y), with error probability at most 1/3 for all (x, y) in some domain D ⊆ X × Y. If D = X × Y then the problem is called total, otherwise it is called partial. A Boolean function f has range {0, 1}. The communication matrix M_{f} corresponding to f is the |X| × |Y | matrix whose (x, y)-entry equals f(x, y) if (x, y) ∈ D, and equals ‘*’ otherwise.

In the simultaneous message passing (SMP) model, Alice and Bob each send a message to a third party (called the referee), who then computes the output. In the one-way model Alice sends one message to Bob (no referee here), while in the two-way model they can interact arbitrarily.

The cost of a communication protocol is its total communication on the worst-case input. The (bounded-error) communication complexity of f (in one of the above models) is the minimal cost among all protocols that compute f with probability of error at most 1/3 for each input.

Classical protocols may be deterministic or randomized. When dealing with randomness, we have to distinguish between private coins and public coins.^{1} The former are visible only to individual parties, while the latter are shared among all parties and may help them coordinate their actions. In one-way and two-way models, the difference between public-coin and private-coin communication complexity is at most an additive O(log n) bits [11], but in the SMP model it can make a big difference. In particular, while the private-coin SMP complexity of Equality is Θ(\sqrt{n}) bits, its public-coin complexity is constant: the protocol picks a shared random n-bit string r, Alice and Bob send the inner product of their input with r (mod 2) to the referee, who checks whether the two received bits are equal.

The following theorem can be derived from the proof of [2, Theorem 1.4]. Here by a measurement operator E we mean a positive semidefinite matrix with eigenvalues in [0, 1]. The acceptance probability of the two-outcome measurement with operators E and I − E on density matrix ρ is p = Tr(Eρ).

Theorem 1 (Aaronson). For all δ > 0 the following holds. Suppose Alice has the classical description of an arbitrary q-qubit density matrix ρ and Bob has a measurement operator E ∈ {E_{b}}_{b∈{0,1}^{c}}. Then Alice can send Bob a randomized O(qc)-bit message that enables him to output a value p′ that approximates p = Tr(Eρ) in the following sense: with probability at least 1 − δ we have |p − p′| ≤ δ (the constant in the O(·) depends on δ, and no public coin is used).

3 Warmup: replacing a randomized message by deterministic

Our goal in this paper is to replace a quantum message by a randomized or deterministic one that is not much bigger. Let us first consider a known case: replacing a randomized message by a deterministic one. Babai and Kimmel [4] showed the following. If there is a bounded-error privatecoin SMP protocol for a Boolean function f, where Alice sends c_{A} bits and Bob sends c_{B} bits, then there exists another bounded-error private-coin SMP protocol for f where Alice deterministically sends O(c_{A}c_{B}) bits, and Bob (who is still randomized) sends c_{B} bits.

As an application of this result, note that in any bounded-error protocol for Equality where Alice is deterministic, she needs to send a different message for each of the 2^{n} inputs x: if she sends the same message for x and for x′, then the referee will have the same acceptance probability on inputs (x, x) and (x′, x) and hence on at least one of those pairs he will err with probability at least 1/2. This implies that in any bounded-error private-coin SMP protocol for Equality, n ≤ O(c_{A}c_{B}), and hence we obtain the bound c_{A} + c_{B} ≥ Ω(\sqrt{n}) mentioned in the introduction.

As a warm-up for the results in the next sections, we sketch a simple proof of the Babai-Kimmel result here. Consider any Boolean function f, partial or total, and a bounded-error privatecoin SMP protocol for f. Let r(a, b) ∈ [0, 1] denote the referee’s acceptance probability if he receives message a ∈ {0, 1}^{c_{A}} from Alice and b ∈ {0, 1}^{c_{B}} from Bob. We use A_{x} for the random variable which is Alice’s message (its distribution depends on her input x), and similarly B_{y} for Bob’s message. Note that for every input x, y where f is defined, the acceptance probability 𝔼_{a∼A_{x},b∼B_{y}}[r(a, b)] approximates the function value: |f(x, y) − 𝔼_{a∼A_{x},b∼B_{y}}[r(a, b)]| ≤ 1/3.

1We will not consider models with shared entanglement here.

We now modify the protocol as follows. Let Alice send her (probabilistic) message s · c_{B} times, for some integer s to be determined later, at a total communication cost of sc_{A}c_{B} bits. For a fixed message b from Bob, the referee computes p̃_{b}, defined as the average of r(a_{i}, b) over all messages a_{i} received from Alice. Choosing s a sufficiently large constant, the Chernoff bound implies that p̃_{b} is within 1/10 of its expectation p_{b} = 𝔼_{a∼A_{x}}[r(a, b)], except with probability ≪ 2^{−c_{B}}:

Pr[|p̃_{b} − p_{b}| > 1/10] ≪ 2^{−c_{B}}.

Hence by a union bound, there exists a deterministic message from Alice that would cause the approximations p̃_{b} to be 1/10-close to p_{b} simultaneously for all b ∈ {0, 1}^{c_{B}}. The desired protocol is clear now: Alice, given her input x, sends the sc_{A}c_{B}-bit deterministic message described above. The referee uses this information to compute a value p̃_{b} such that |p̃_{b} − p_{b}| ≤ 1/10 where b is the message he received from Bob, and accepts with probability p̃_{b}. Clearly, for each input pair x, y the acceptance probability of this protocol differs from that of the original protocol by at most 1/10, and hence correctness is maintained. We have reproved:

Theorem 2 (Babai & Kimmel). Let f be a (possibly partial) Boolean function. If there is a bounded-error private-coin SMP protocol for f where Alice sends c_{A} bits and Bob sends c_{B} bits, then there is a bounded-error private-coin SMP protocol for f where Alice deterministically sends O(c_{A}c_{B}) bits, and Bob (who is still randomized) sends c_{B} bits.

Actually, Babai and Kimmel showed something slightly stronger, namely that both Alice’s and Bob’s randomized message can simultaneously be replaced by deterministic messages of length O(c_{A}c_{B}).

Theorem 3 (Babai & Kimmel). Let f be a (possibly partial) Boolean function. If there is a bounded-error private-coin SMP protocol for f where Alice sends c_{A} bits and Bob sends c_{B} bits, then there is a deterministic SMP protocol for f where Alice and Bob send O(c_{A}c_{B}) bits.

This theorem is essentially tight for the Equality problem, where the deterministic communication complexity is 2n. Consider the following bounded-error private-coin protocol, adapted from [3]. Alice and Bob fix, beforehand, a good error-correcting code C : {0, 1}^{n} → {0, 1}^{m} with m = O(n). For m = c_{A}c_{B}, they can view the codewords as c_{A} × c_{B} Boolean matrices. Alice sends a random column of C(x) together with its index, sending c_{A} + log c_{B} bits in total. Bob sends a random row of C(y) with its index, sending c_{B} + log c_{A} bits. The referee checks whether the row and column agree in the one point where they intersect. If x = y then the two bits are the same, otherwise they differ with constant probability. Repeating a constant number of times, we obtain a bounded-error private-coin SMP protocol where Alice sends O(c_{A} + log c_{B}) bits and Bob sends O(c_{B} + log c_{A}) bits.

Note that Theorem 2 fails spectacularly for public-coin SMP protocols: the bounded-error public-coin SMP complexity of Equality is constant, while a deterministic player needs to send n bits, no matter what the other player sends.

4 Replacing a quantum message by a randomized one

We now prove that in quantum-classical SMP protocols, the “quantum leg” of the protocol can be replaced by a randomized message.

Theorem 4. Let f be a (possibly partial) Boolean function. If there is a private-coin (resp. publiccoin) bounded-error quantum-classical SMP protocol for f where Alice sends q_{A} qubits and Bob sends c_{B} classical bits, then there is a private-coin (resp. public-coin) bounded-error SMP protocol for f where Alice sends O(q_{A}c_{B}) classical bits and Bob sends c_{B} classical bits.

Proof: We prove the theorem for private-coin protocols. The proof for public-coin protocols is essentially the same, just fix the shared randomness at the start of the argument and average over it at the end. In general the three-party protocol has the following form: Alice sends the referee a q_{A}-qubit density matrix ρ_{x}, while Bob sends a classical message b ∈ {0, 1}^{c_{B}}, whose distribution depends on his input y. The referee then measures ρ_{x} with a measurement operator E_{b}, and outputs 1 if the measurement accepts (which happens with probability p_{b} = Tr(E_{b}ρ_{x})).

The SMP protocol promised by the theorem is as follows: Bob sends a c_{B}-bit message b, exactly as in the original quantum-classical protocol. Using Theorem 1, Alice sends to the referee a randomized message of O(q_{A}c_{B}) bits to enable him to obtain with probability at least 1 − δ an approximation p̃_{b} to p_{b} = Tr(E_{b}ρ_{x}) to within ±δ, where δ = 1/10. Finally, the referee outputs 1 with probability p̃_{b}, and 0 otherwise. The overall error probability is at most 2δ worse than in the original protocol.

Note the difference between the above two proofs. The proof of Theorem 2 obtains approximations p_{b} for all b ∈ {0, 1}^{c_{B}} simultaneously, which enables the referee to learn f(x, y) for each y. On the other hand, the proof of Theorem 4 only obtains an approximation p_{b} for the specific b that the referee received from Bob, which enables the referee to predict f(x, y) for the specific input y that Bob holds.

5 Replacing a quantum message by a deterministic one

By combining Theorem 4 with the Babai-Kimmel theorem (Theorem 2), we see that in every quantum-classical private-coin SMP protocol with q_{A} qubits and c_{B} bits, we can replace Alice’s message by a deterministic message of O(q_{A}c_{B}^{2}) bits. However, we can obtain something that is usually stronger, namely a deterministic message of O(q_{A}c_{B} log q_{A}) bits. The crucial tool is the following result, which is an extension of a result of Aaronson [1, Theorem 3.4]:

Theorem 5. For all δ > 0 the following holds. Suppose Alice has the classical description of an arbitrary q-qubit density matrix ρ, and Bob has 2^{c} measurements operators {E_{b}}_{b∈{0,1}^{c}}. There is a deterministic message of O(qc log q) bits from Alice that enables Bob to output values p′_{b} satisfying that |p_{b} − p′_{b}| ≤ δ simultaneously for all b ∈ {0, 1}^{c} where p_{b} = Tr(E_{b}ρ).

It is interesting to compare this with Theorem 1. While Theorem 1 allows us to approximate one p_{b} to within ±δ (with some small probability of error) using an O(qc)-bit message, Theorem 5 allows us to approximate all p_{b} to within ±δ (without probability of error) at the expense of increasing the message length by a factor log q. Theorem 5 generalizes Aaronson’s [1, Theorem 3.4], which proves the special case where Tr(E_{b}ρ) is close to 0 or 1 for all b. Our proof is a modification of his. We conjecture that the log q factor is not needed.

Proof: Suppose Alice sends r = O(log q) many copies of her state, for sufficiently large constant in the O(·) which may depend on δ. Let ρ′ = ρ^{⊗r} be the state she sends, and K = rq = O(q log q) its total number of qubits. Define the observable^{2}

F_{b} = \frac{1}{r} ∑_{j=1}^{r} E_{b}^{(j)},

where E_{b}^{(j)} applies E_{b} to the jth copy. This measures the fraction of successes if you separately measure each of the r copies of ρ with E_{b}. Since r = O(log q), a Chernoff bound implies that the outcome p′_{b} of this measurement applied to ρ′ will probably be close to its expectation p_{b} = Tr(E_{b}ρ):

Pr[|p′_{b} − p_{b}| > δ/4] ≤ 1/poly(q).  (1)

Alice’s classical message. Consider all b = 1, …, 2^{c} in order. We will sequentially build a sequence of K-qubit density matrices ρ_{b}, one for each E_{b}. Alice’s classical message will enable Bob to reconstruct this entire sequence. Call b good if |Tr(F_{b}ρ_{b}) − p_{b}| ≤ δ; call b bad otherwise. Note that if Bob has a classical description of a good ρ_{b}, then he can approximate p_{b} to within ±δ (since he knows what F_{b} is). We start with the completely mixed state: ρ_{1} = I/2^{K} and define the subsequent ρ_{b} one by one, as follows. If b is good, then define ρ_{b+1} to be equal to ρ_{b}. If b is bad, Alice appends the pair (b, p̃_{b}) to her message, where p̃_{b} is the log(1/δ) + O(1) most significant bits of p_{b}, so |p̃_{b} − p_{b}| ≪ δ. In this case, let M_{b} be the projector on the subspace spanned by the eigenvectors of F_{b} with eigenvalues in the interval [p̃_{b} − δ/2, p̃_{b} + δ/2], and let ρ_{b+1} be the renormalized projection of ρ_{b} on this subspace.^{3} Continuing all the way to b = 2^{c}, we obtain a message (b_{1}, p̃_{b_{1}}), …, (b_{T} , p̃_{b_{T}}) for some T. We need to show two things: (1) this message enables Bob to approximate all p_{b} to within ±δ, and (2) T = O(K), which implies that the message length is O(qc log q) bits. We will show these two things in turn.

(1) Why this works. Note that Bob knows which b ∈ [2^{c}] are bad, since those b are exactly the ones in Alice’s message. Bob can in fact compute the whole sequence ρ_{1}, …, ρ_{2^{c}} given the message: ρ_{1} = I/2^{K}; if b is good then ρ_{b+1} = ρ_{b}; if b is bad then (b, p̃_{b}) is part of Alice’s message and ρ_{b+1} can be computed from this information. Suppose Bob wants to approximate p_{b} = Tr(E_{b}ρ). If b is good then by definition |Tr(F_{b}ρ_{b}) − p_{b}| ≤ δ and Bob can calculate Tr(F_{b}ρ_{b}). If b is bad, then the pair (b, p̃_{b}) is part of Alice’s message, so Bob knows p_{b} with sufficient precision. Hence Bob can approximate all p_{b} up to ±δ, for all b simultaneously.

(2) Why the message is not too long. Here we show T = O(K). Define η = 1 − δ/4 and t = ⌈(K + 1)/ log(1/η) + 1⌉ = O(K). Suppose, by way of contradiction, that T ≥ t. We consider the sequence b_{1}, …, b_{t} of the first t bad b’s. Let

p = Tr (M_{b_{t}} ⋯ M_{b_{1}} \frac{I}{2^{K}} M_{b_{1}} ⋯ M_{b_{t}})

be the probability that all t measurements succeed if we start with the completely mixed state and sequentially measure M_{b_{1}}, …, M_{b_{t}}. We will derive contradicting upper and lower bounds on p.

First, the upper bound on p. If we sequentially measure M_{b_{1}}, …, M_{b_{t}}, starting from the completely mixed state, and if all t measurements succeed, then we exactly have the sequence of density matrices ρ_{b_{1}} = I/2^{K}, …, ρ_{b_{t}}, ρ_{b_{t}+1}. We claim that if ρ_{b} is bad, then Tr(M_{b}ρ_{b}) ≤ η, and hence the probability that all t measurements succeed is p ≤ η^{t}. The claim follows easily from a Markov argument: Let X denote the random variable representing the outcome of measuring ρ_{b} with the observable F_{b}. Notice that X takes values in [0, 1]. Assume Tr(M_{b}ρ_{b}) = Pr[|X − p̃_{b}| ≤ δ/2] > η. Then Tr(F_{b}ρ_{b}) = 𝔼[X] must necessarily be in the range

2An observable F is a Hermitian matrix that describes a measurement, as follows. By diagonalization we can write F = ∑_{i} λ_{i}P_{i}, where P_{i} is the projector on the eigenspace corresponding to eigenvalue λ_{i}. These eigenspaces are all orthogonal to each other and ∑_{i} P_{i} = I. The corresponding measurement on a density matrix ρ gives outcome λ_{i} with probability Tr(P_{i}ρ). Hence the expectation of the measurement is ∑_{i} λ_{i}Tr(P_{i}ρ) = Tr(F ρ).

3The fact that this projection is nonzero (and hence can be renormalized to have trace 1) follows from the argument in the “Second, the lower bound on p” paragraph below.

[η(p̃_{b} − δ/2), η(p̃_{b} + δ/2) + 1 − η] ⊆ [p̃_{b} − 3δ/4, p̃_{b} + 3δ/4] ⊆ [p_{b} − δ, p_{b} + δ],

and hence ρ_{b} is good.

Second, the lower bound on p. Note that M_{b} succeeds on ρ′ iff the outcome p′_{b} of the observable F_{b} is at most δ/2 away from the number p̃_{b}, which is the truncated version of p_{b} = Tr(E_{b}ρ) (recall |p̃_{b} − p_{b}| ≪ δ). Hence by Eq. (1), we have

Tr(M_{b}ρ′) = Pr[|p′_{b} − p̃_{b}| ≤ δ/2] ≥ Pr[|p′_{b} − p_{b}| ≤ δ/4] ≥ 1 − 1/poly(q).

This allows us to measure ρ′ with M_{b} while disturbing the state by only an insignificant amount.^{4} If we measure each of M_{b}, for the first t bad b’s in sequence, starting in ρ′, then with probability at least 1/2 all measurements will succeed. However, the completely mixed state can be written as \frac{I}{2^{K}} = \frac{1}{2^{K}} ρ′ + (1 − \frac{1}{2^{K}})ρ′′ where ρ′′ is orthogonal to ρ′. Hence if we start from I/2^{K}, then the probability of all measurements succeeding is p ≥ 1/2^{K+1}.

Combining the bounds of the last two paragraphs together with our value of t gives a contradiction.

Corollary 6. Let f be a (possibly partial) Boolean function. If there is a bounded-error quantumclassical private-coin SMP protocol for f where Alice sends q_{A} qubits and Bob sends c_{B} bits, then there is a bounded-error private-coin SMP protocol for f where Alice deterministically sends O(q_{A}c_{B} log q_{A}) bits, and Bob (who is still randomized) sends c_{B} bits.

Proof: As in the proof of Theorem 4, we assume without loss of generality that the protocol has the following form: Alice sends the referee a q_{A}-qubit density matrix ρ_{x}, while Bob sends a classical message b ∈ {0, 1}^{c_{B}}, whose distribution depends on his input y. The referee then measures ρ_{x} with a measurement operator E_{b}, and outputs 1 if the measurement accepts (which happens with probability p_{b} = Tr(E_{b}ρ_{x})).

The desired SMP protocol is as follows: Bob sends a c_{B}-bit message b, exactly as in the original quantum-classical protocol. Using Theorem 5, Alice sends to the referee a deterministic message of O(q_{A}c_{B} log q_{A}) bits to enable him to obtain (with certainty) an approximation p̃_{b} to p_{b} = Tr(E_{b}ρ_{x}) to within ±δ, where δ = 1/10. Finally, the referee outputs 1 with probability p̃_{b}, and 0 otherwise. The overall error probability is at most δ worse than in the original protocol.

As argued in Section 3, in a bounded-error protocol for Equality where Alice is deterministic, she needs to send at least n bits. Hence we obtain the following lower bound on quantum-classical private-coin SMP protocols for Equality, which is tight up to the \sqrt{log n}-factor.

Corollary 7. Every quantum-classical private-coin SMP protocol for Equality has communication complexity Ω(\sqrt{n/ log n}).

4This is a well-known and very intuitive property in quantum computing; we refrain from spelling out the quantitative details so as not to crowd out the intuition with even more technicalities (see for instance the “almost as good as new lemma” [1, Lemma 2.2]).

6 Tightness

The example of the Equality function shows that Theorems 5 and Corollary 6 are essentially tight.

We do not know whether Theorem 4 is close to optimal, but at least it shows that the gap between quantum-classical and classical-classical SMP protocols is at most polynomial. The following communication problem, adapted from [5, 9, 8], presents an interesting quantum-classical public-coin protocol that uses about n^{1/3} qubits. We do not know an equally efficient classicalclassical public coin protocol for this problem; the best one we know sends about \sqrt{n} bits. This suggests that quantum-classical SMP protocols can at least have some polynomial advantage over classical-classical protocols.

The problem is as follows. Let n be an even integer. Alice receives x ∈ {0, 1}^{n}, while Bob receives a perfect matching M (i.e., a partition of [n] = {1, …, n} into n/2 disjoint pairs, called “edges”), and a string w ∈ {0, 1}^{n/2} whose bits are indexed by the edges in M. We can view the edges of M as rows (of weight 2) in an n/2 × n matrix M over GF (2). Then the matrix-vector product Mx is the n/2-bit string obtained by taking, for each edge (i, j) of M in order, the XOR x_{i} ⊕ x_{j}. The promise is that the Hamming distance between w and Mx is either at most n/6 or at least n/3, and the function value is 1 in the first case and 0 in the second.

One can show easily that the deterministic complexity of the problem is Ω(n), as follows. By the probabilistic method, there exists a set S ⊆ {0, 1}^{n} of size |S| = 2^{Ω(n)} such that all distinct x, x′ ∈ S are at distance around n/2. But then for each distinct x, x′ ∈ S we can find a matching M where the n/2-bit strings Mx and Mx′ have distance close to n/2 (pick as many edges as possible that have one endpoint in a bitlocation where x and x′ agree, and one endpoint where they disagree). Putting w = Mx, we have f(x, M, w) = 1 but f(x′, M, w) = 0. Hence in a deterministic protocol, Alice will need to send a different message for each of the x ∈ S. Therefore the deterministic SMP (and even one-way) communication complexity of this function is Ω(n).

On the other hand, here is a bounded-error public-coin SMP protocol where Alice sends q_{A} ≈ n^{1/3} qubits and Bob sends c_{B} ≈ n^{1/3} bits. Alice and Bob use the public coin to select a random subset S ⊆ [n] of about n^{2/3} elements from [n]. Now with high probability, M ∩(S ×S) will contain Θ(n^{1/3}) edges. Alice sends the referee n^{1/3} copies of the uniform superposition \frac{1}{\sqrt{|S|}} ∑_{i∈S}(−1)^{x_{i}}|i⟩.

Bob sends over Θ(n^{1/3}) edges in M ∩ (S × S), together with the corresponding bits of w. The referee constructs two-dimensional measurement operators from the edges he received from Bob, and measures each of the quantum states with them. With probability close to 1, one of those measurements will succeed and give him a bit of the string Mx. Since the location of that bit in Mx is random, comparing that bit with the corresponding bit of w (which is part of Bob’s message), gives the referee the function value with probability at least 2/3.^{5}

7 Functional separations versus relational separations

As mentioned before, Theorem 4 implies that the gap between quantum-classical and classicalclassical SMP protocols is at most polynomial for any Boolean function. In contrast, Bar-Yossef et al. [5] exhibited a relational problem for which quantum-classical SMP protocols are exponentially better than classical-classical SMP protocols with a public coin. In a relational problem, for each input pair (x, y) there is a set of valid outputs z. In the case of [5], Alice receives an arbitrary string x ∈ {0, 1}^{n} and Bob receives a perfect matching M on [n] from a set of Θ(n) possible perfect matchings. Their goal is to output any z of the form (i, j, x_{i} ⊕ x_{j}) where (i, j) ∈ M.

5The best classical protocol that we know works similarly. It selects a set S of about \sqrt{n} elements, and Alice sends the corresponding bits of x to the referee at the expense of about \sqrt{n} bits of communication.

Bar-Yossef et al. exhibit a quantum-classical SMP protocol that solves this problem with success probability 1, with a log n-qubit message from Alice to the referee and a log n-bit message from Bob. Their protocol works as follows: Alice sends the referee a uniform superposition

\frac{1}{\sqrt{n}} ∑_{i=1}^{n}(−1)^{x_{i}}|i⟩.

Bob sends the referee the index of his matching M in the set of Θ(n) possible matchings, which takes log n + O(1) classical bits. Viewing M as a measurement consisting of n/2 orthogonal twodimensional projectors (one for each edge (i, j) ∈ M), the referee measures the quantum state he received from Alice. This gives him the state

\frac{1}{\sqrt{2}} ((−1)^{x_{i}}|i⟩ + (−1)^{x_{j}}|j⟩) = \frac{(−1)^{x_{i}}}{\sqrt{2}} (|i⟩ + (−1)^{x_{i}⊕x_{j}}|j⟩)

for a uniformly random edge (i, j) ∈ M. From this the referee can obtain the bit x_{i} ⊕ x_{j} with certainty, and output (i, j, x_{i} ⊕ x_{j}) accordingly. No public coin is needed. In contrast, Bar-Yossef et al. proved a Θ(\sqrt{n}) bound for classical-classical public-coin protocols for this relational problem.

To summarize, we see that when comparing the quantum-classical SMP model to the classicalclassical SMP model, one can obtain an exponential separation for a relation but not for a Boolean function. In the remainder of this section we show that such a situation cannot occur for purely classical models. More precisely, we show that for models obeying the Yao principle [15] (defined next), any separation for a relation implies a similar separation for a function (and sometimes even for a Boolean function). Notice that the converse implications clearly holds, i.e., a separation for a functional problem is also a separation for a relational problem, since functions are a special case of relations.

Consider any computational model that has a class of deterministic algorithms (or protocols), each of a certain cost. A randomized algorithm in such a model is a probability distribution over deterministic algorithms. The Yao principle states the equality of two different complexities: (1) the ε-error complexity (the minimal cost of randomized algorithms whose error probability is at most ε on every input) and (2) the ε-error distributional complexity under the hardest input distribution μ (the minimal cost of deterministic protocols that have error probability at most ε under μ). Because of the minimax theorem from game theory, allowing shared randomness in one’s communication model is a sufficient condition for the Yao principle to hold.

Now assume any two computational models, both obeying the Yao principle. Call these models “a” and “b”, respectively. Let R_{a,ε} and R_{b,ε} denote the ε-error complexities in these two models. Assume we have a separation between these two models, showing that R_{a,2ε}(P) is greater than R_{b,ε}(P) for some relational problem P. We will next show how to construct a function f for which there is a separation between R_{a,ε}(f) and R_{b,ε}(f) that is at least as large.

Let μ be a worst-case input distribution for the distributional R_{a,2ε}-complexity of relation P. That is, any deterministic protocol in the “a” model solving P with distributional error at most 2ε under μ, must use at least R_{a,2ε}(P) bits of communication. Next, by the Yao principle, there is a deterministic protocol in the “b” model solving P with error at most ε under distribution μ, using at most R_{b,ε}(P) bits of communication. Being deterministic, this protocol necessarily computes some function with error probability 0, call it f. Hence we see that for this function, R_{b,ε}(P) ≥ R_{b,0}(f). Moreover, note that the probability under μ that f(x, y) is not a valid answer for P, is at most ε.

To complete the argument, we now show that R_{a,ε}(f) ≥ R_{a,2ε}(P). Consider an optimal ε-error protocol for f in the “a” model with complexity R_{a,ε}(f). By the Yao principle, there exists a deterministic protocol for f in the “a” model with distributional error at most ε under μ, and the same complexity. By the union bound, the same protocol computes P with distributional error at most 2ε under μ. The desired inequality R_{a,ε}(f) ≥ R_{a,2ε}(P) now follows from the choice of μ. In sum, we have found a function f with R_{a,ε}(f) ≥ R_{a,2ε}(P) > R_{b,ε}(P) ≥ R_{b,0}(f) ≥ R_{b,ε}(f).

The separation we obtained above is for a functional problem, but not necessarily a Boolean one. We now observe that if the R_{a}/R_{b}-separation we start with is sufficiently strong, and the number of output bits of P is not too large, then one can obtain a Boolean function with a strong R_{a}/R_{b}-separation. Assume f has a k-bit output, and assume that g : {0, 1}^{k} → {0, 1}^{10k} is an error-correcting code with constant rate and constant relative distance (which is known to exist). Let f_{1}, …, f_{10k} be the Boolean functions representing the bits of g(f(·)). Having ε-error protocols for each of these Boolean functions, each of complexity c, implies an ε-error protocol for f of complexity O(ck). Hence for at least one j we have R_{a,ε}(f_{j}) = Ω(R_{a,ε}(f)/k). Accordingly, if the original relational R_{a}/R_{b}-separation was by more than a factor k, then we now have a R_{a}/R_{b}- separation for a Boolean function.

Acknowledgments

We thank Wim van Dam for asking the question that prompted this research, Ben Toner for useful discussions, and the anonymous CJTCS referees for some comments that improved the presentation of the results.

References

[1] S. Aaronson. Limitations of quantum advice and one-way communication. Theory of Computing, 1:1–28, 2005. Earlier version in Complexity’04. quant-ph/0402095.

[2] S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society of London, A463(2088), 2007. quant-ph/0608142.

[3] A. Ambainis. Communication complexity in a 3-computer model. Algorithmica, 16(3):298–301, 1996.

[4] L. Babai and P. G. Kimmel. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In Proceedings of the 12th IEEE Conference on Computational Complexity, pages 239–246, 1997.

[5] Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of 36th ACM STOC, pages 128–137, 2004.

[6] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16), September 26, 2001. quant-ph/0102001.

[7] W. van Dam. Personal communication, May 2007.

[8] D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential separations for oneway quantum communication complexity, with applications to cryptography. In Proceedings of 39th ACM STOC, pages 516–525, 2007. quant-ph/0611209.

[9] D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. In Proceedings of 38th ACM STOC, pages 594–603, 2006. quant-ph/0511013.

[10] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.

[11] I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67–71, 1991.

[12] I. Newman and M. Szegedy. Public vs. private coin flips in one round communication games. In Proceedings of 28th ACM STOC, pages 561–570, 1996.

[13] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[14] R. de Wolf. Quantum communication and complexity. Theoretical Computer Science, 287(1):337–353, 2002.

[15] A. C-C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of 18th IEEE FOCS, pages 222–227, 1977.