首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity
  • 本地全文:下载
  • 作者:Xiaoming Sun ; Marcos Villagra
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    There are three different types of nondeterminism in quantum communication: i) \nqp-communication, ii) \qma-communication, and iii) \qcma-communication. In this \redout{paper} we show that multiparty \nqp-communication can be exponentially stronger than \qcma-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists a total function that is hard for \qcma-communication and easy for \nqp-communication. The proof of it involves an application of the pattern tensor method and a new lower bound for polynomial threshold degree. Another important consequence of this result is that nondeterministic rank can be exponentially lower than the discrepancy bound.

  • 关键词:nondeterministic communication complexity; norm-bound; pattern-tensor; tensor-rank; threshold degree
国家哲学社会科学文献中心版权所有