首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
  • 本地全文:下载
  • 作者:Sourav Chakraborty ; Arkadev Chattopadhyay ; Nikhil Mande
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-15
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f : − 1 1 n − 1 1 and : − 1 1 2 − 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. H{\o}yer and de Wolf (STACS'02) showed that for the Set-Disjointness function, 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 NO R n ) is O ( Q ( NO R 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 n − 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 )) .

  • 关键词:Quantum communication complexity ; quantum query complexity ; simulation theoerems
国家哲学社会科学文献中心版权所有