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: https://drops.dagstuhl.de/opus/volltexte/2020/12584/
Go to the corresponding LIPIcs Volume Portal


Chakraborty, Sourav ; Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Paraashar, Manaswi

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead

pdf-format:
LIPIcs-CCC-2020-32.pdf (0.5 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI