Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

Details Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

2012-02-29

arxiv.org/abs/1202.6444v1

Computer Science

Computational Complexity

15 pages, extended abstract to appear in Proceedings of the 9th annual conference on Theory and Applications of Models of Comp

Scientific paper

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$, 1) in the Number-On-Forehead model, the cost is upper-bounded by the logarithm of $nrank(f)$; 2) in the Number-In-Hand model, the cost is lower-bounded by the logarithm of $nrank(f)$. 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.

Affiliated with

Also associated with

No associations

Rating

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523499