文章基本信息
- 标题：Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead
- 本地全文：下载
- 作者：Sourav Chakraborty ; Arkadev Chattopadhyay ; Nikhil S. Mande 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：169
- 页码：32:1-32:15
- DOI：10.4230/LIPIcs.CCC.2020.32
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 Ω(â^Sn). The BCW simulation yields an upper bound of O(â^Sn 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 ⢠= âS., 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 â^~ âS.) = Î~(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)).
- 关键词：Quantum query complexity; quantum communication complexity; approximate degree; approximate spectral norm
