IEICE TRANSACTIONS on Information
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
Summary :
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
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.1 pp.1-8
- Publication Date
- 2013/01/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.1
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Marcos VILLAGRA, Masaki NAKANISHI, Shigeru YAMASHITA, Yasuhiko NAKASHIMA, "Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 1, pp. 1-8, January 2013, doi: 10.1587/transinf.E96.D.1.
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
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1/_p
Copy
@ARTICLE{e96-d_1_1,
author={Marcos VILLAGRA, Masaki NAKANISHI, Shigeru YAMASHITA, Yasuhiko NAKASHIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication},
year={2013},
volume={E96-D},
number={1},
pages={1-8},
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
keywords={},
doi={10.1587/transinf.E96.D.1},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
T2 - IEICE TRANSACTIONS on Information
SP - 1
EP - 8
AU - Marcos VILLAGRA
AU - Masaki NAKANISHI
AU - Shigeru YAMASHITA
AU - Yasuhiko NAKASHIMA
PY - 2013
DO - 10.1587/transinf.E96.D.1
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2013
AB - 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
ER -
English
