log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Nikhil Mande - Georgetown University
Wednesday, April 1, 2020, 11:00 am-12:15 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

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).  

This talk is organized by Andrea F. Svejda