文章基本信息

标题：Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
本地全文：下载
作者：Marcos Villagra ; Masaki Nakanishi ; Shigeru Yamashita 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input with positive probability, and rejects an incorrect input with probability 1. In this work we relate strong quantum nondeterministic multiparty communication complexity to the rank of the communication tensor in the Number-On-Forehead and Number-In-Hand models. In particular, by extending the definition proposed by de Wolf to {\it nondeterministic tensor-rank} (nrank), we show that for any boolean function f with communication tensor Tf, \begin{enumerate} \item in the Number-On-Forehead model, the cost is upper-bounded by the logarithm of nrank(Tf); \item in the Number-In-Hand model, the cost is lower-bounded by the logarithm of nrank(Tf). \end{enumerate} This naturally generalizes previous results in the field and relates for the first time the concept of (high-order) tensor rank to quantum communication. Furthermore, we show that strong quantum nondeterminism can be exponentially stronger than classical multiparty nondeterministic communication. We do so by applying our results to the matrix multiplication problem
关键词：exponential separation, matrix multiplication, Multiparty communication, quantum nondeterminism, tensor rank