Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
-
- VILLAGRA Marcos
- Graduate School of Information Science, Nara Institute of Science and Technology
-
- NAKANISHI Masaki
- Faculty of Education, Art and Science, Yamagata University
-
- YAMASHITA Shigeru
- Department of Computer Science, Ritsumeikan University
-
- NAKASHIMA Yasuhiko
- Graduate School of Information Science, Nara Institute of Science and Technology
Bibliographic Information
- Other Title
-
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
Search this article
Abstract
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 nondeterministic tensor-rank (nrank), we show that for any boolean function f when there is no prior shared entanglement between the players, 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). Furthermore, we show that when the number of players is o(log log n), we have $NQP\nsubseteq BQP$ for Number-On-Forehead communication.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E96.D (1), 1-8, 2013
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679354987008
-
- NII Article ID
- 10031193989
- 10031167374
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed