License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.32
URN: urn:nbn:de:0030-drops-125842
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12584/
Chakraborty, Sourav ;
Chattopadhyay, Arkadev ;
Mande, Nikhil S. ;
Paraashar, Manaswi
Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead
Abstract
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the bounded-error quantum query complexity of f. Note that the bounded-error randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the bounded-error 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 bounded-error quantum communication complexity of Set-Disjointness 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 Set-Disjointness 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 2-bit 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 Query-To-Communication Simulation Needs a Logarithmic Overhead}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-156-6},
ISSN = {1868-8969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12584},
URN = {urn:nbn:de:0030-drops-125842},
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 |
