Abstract
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{1,1}ⁿ → {1,1} and •:{1,1}² → {1,1} the twoparty boundederror quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the boundederror quantum query complexity of f. Note that the boundederror randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the boundederror 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 boundederror quantum communication complexity of SetDisjointness 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 SetDisjointness 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 2bit function •, such that Q^{cc}(F ∘ •) = ω(Q(F)).
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2020:12584,
author = {Sourav Chakraborty and Arkadev Chattopadhyay and Nikhil S. Mande and Manaswi Paraashar},
title = {{Quantum QueryToCommunication Simulation Needs a Logarithmic Overhead}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {32:132:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12584},
URN = {urn:nbn:de:0030drops125842},
doi = {10.4230/LIPIcs.CCC.2020.32},
annote = {Keywords: Quantum query complexity, quantum communication complexity, approximate degree, approximate spectral norm}
}
Keywords: 

Quantum query complexity, quantum communication complexity, approximate degree, approximate spectral norm 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 