QLunch: Manaswi Paraashar

Speaker: Manaswi Paraashar, Aarhus University

Title: Quantum query-to-communication simulation and the role of symmetry

Abstract: Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {0,1}^n \to {0,1} and G \in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function (f \circ G) equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is known as the BCW Simulation Theorem. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f \circ G) \leq 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We exhibited a total function for which the (log n) overhead in the BCW simulation is required. We also 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).

This talk is based on two joint works with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil Mande, and Ronald de Wolf.