Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the bounded-error quantum query complexity of f. Note that the bounded-error randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the bounded-error randomized query complexity of f. Thus, the BCW simulation has an extra O(log n) factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. Razborov (IZV MATH'03) showed that the bounded-error quantum communication complexity of Set-Disjointness is Ω(√n). The BCW simulation yields an upper bound of O(√n log n). Høyer and de Wolf (STACS'02) showed that this can be reduced to c^(log^* n) for some constant c, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is NOR_n ∘ ∧) is O(Q(NOR_n)). Perhaps somewhat surprisingly, we show that when • = ⊕, then the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F:{-1,1}ⁿ → {-1,1} such that Q^{cc}(F ∘ ⊕) = Θ(Q(F) log n). To the best of our knowledge, it was not even known prior to this work whether there existed a total function F and 2-bit function •, such that Q^{cc}(F ∘ •) = ω(Q(F)).
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the bounded-error quantum query complexity of f. Note that the bounded-error randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the bounded-error randomized query complexity of f. Thus, the BCW simulation has an extra O(log n) factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. Razborov (IZV MATH'03) showed that the bounded-error quantum communication complexity of Set-Disjointness is Ω(√n). The BCW simulation yields an upper bound of O(√n log n). Høyer and de Wolf (STACS'02) showed that this can be reduced to c^(log^* n) for some constant c, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is NOR_n ∘ ∧) is O(Q(NOR_n)). Perhaps somewhat surprisingly, we show that when • = ⊕, then the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F:{-1,1}ⁿ → {-1,1} such that Q^{cc}(F ∘ ⊕) = Θ(Q(F) log n). To the best of our knowledge, it was not even known prior to this work whether there existed a total function F and 2-bit function •, such that Q^{cc}(F ∘ •) = ω(Q(F)).
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}ⁿ → {-1,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that 𝖱^{cc}(f∘G) ≤ 2𝖱(f), where 𝖱^{cc} and 𝖱 denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. This established the somewhat surprising fact that quantum reductions are in some cases inherently more expensive than classical reductions. We improve upon their result in several ways. - We show that the log n overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). Our upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. This also provides a different, and arguably simpler, proof of Aaronson and Ambainis’s O(√n) communication upper bound for Set-Disjointness. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) is at most 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We note here that prior to our work, the possibility of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been ruled out. More specifically, we show the following. - We show that the log n overhead is *not* required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model.
We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/,...,X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/.../spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/ : 2/sup [n]/ /spl rarr/ {0,1}, such that F(X/sub 1/,...,X/sub t/) = f/sub F/(X/sub 1/ /spl cap/.../spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i : f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).
In this paper, we focus on the quantum communication complexity of functions of the form f∘G=f(G(X1,Y1),…,G(Xn,Yn)) where $f: \Bset^n \to \Bset$ is a symmetric function, $G: \Bset^j \times \Bset^k \to \Bset$ is any function and Alice (resp. Bob) is given (Xi)i∈[n] (resp. (Yi)i∈[n]). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of f∘G is $O(Q(f)\QCCEX(G))$ when the parties are allowed to use shared entanglement, where Q(f) is the query complexity of f and $\QCCEX(G)$ is the exact communication complexity of G. }{In this paper, we first show that the same statement holds \emph{without both shared entanglement and shared randomness}, which generalizes their result. Based on the improved result, we next show tight upper bounds on f∘AND2 for any symmetric function f (where $\textrm{AND}_2 : \Bset \times \Bset \to \Bset$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f:X x Y-->{0,1} be a Boolean function, fool^1(f) its maximal fooling set size among 1-inputs, Q_1^*(f) its one-sided error quantum communication complexity with prior entanglement, and NQ(f) its nondeterministic quantum communication complexity (without prior entanglement; this model is trivial with shared randomness or entanglement). Our main results are the following, where logs are to base 2: * If the maximal fooling set is "upper triangular" (which is for instance the case for the equality, disjointness, and greater-than functions), then we have Q_1^*(f)>=(1/2)log fool^1(f) - 1/2, which is essentially optimal by superdense coding. No super-constant lower bound for equality seems to follow from earlier techniques. * For all f we have Q_1^*(f)>=(1/4)log fool^1(f) - 1/2, which is optimal up to a factor of 2. * NQ(f)>=log \fool^1(f)/2 + 1. We do not know if the factor 1/2 is needed in this result, but it cannot be replaced by 1: we give an example where NQ(f)~0.613 log fool^1(f).