QuICS Seminar
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f : {-1, 1}^n to {-1, 1}, the two-party bounded-error quantum communication complexity of 2-bit distributed versions of f is O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast to the classical randomized analogue of this statement, where the log n factor is absent. A natural question is if this O(log n) factor can be avoided. Aaronson and Ambainis (FOCS'03) showed that this factor is avoidable when f = OR.
Perhaps somewhat surprisingly, we show that the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F such that Q^{cc}(F') = Omega(Q(F) log n), where F' is a distributed version of F.
To the best of our knowledge, it was not even known prior to this work whether there existed a total function F such that the bounded-error quantum communication complexity of any distributed version F' satisfies Q^{cc}(F) = omega(Q(F)).
Based on joint work with Sourav Chakraborty (ISI, Kolkata), Arkadev Chattopadhyay (TIFR, Mumbai) and Manaswi Paraashar (ISI, Kolkata).