Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande +1

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$ and $\bullet :\{-1,1{\}}^2\to \{-1,1\}$ the two-party bounded-erro…