2026-07-23T03:46:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12584 2024-03-06T10:50:30Z ddc:004 open_access

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead Chakraborty, Sourav Chattopadhyay, Arkadev Mande, Nikhil S. Paraashar, Manaswi Quantum query complexity quantum communication complexity approximate degree approximate spectral norm 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)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sourav Chakraborty and Arkadev Chattopadhyay and Nikhil S. Mande and Manaswi Paraashar 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.32 urn:nbn:de:0030-drops-125842 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.32 eng https://creativecommons.org/licenses/by/3.0/legalcode