Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR12-004 | 12th October 2012 06:10

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

RSS-Feed




Revision #3
Authors: Masaki Nakanishi, Yasuhiko Nakashima, Marcos Villagra, Shigeru Yamashita
Accepted on: 12th October 2012 06:10
Downloads: 793
Keywords: 


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 {\it 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 that $NQP\nsubseteq BQP$ for Number-On-Forehead communication.



Changes to previous version:

fixed some lesser typos and improved the separations.


Revision #2 to TR12-004 | 13th June 2012 10:28

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication


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 {\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)$. Furthermore, we show that when the number of players is $o(\log\log n^{1/4})$ we have that $NQP\nsubseteq BQP$ for Number-On-Forehead communication.



Changes to previous version:

Corrected a mistake in the proof of the separation theorem. This changed the result to a separation of NQP from BQP for NOF communication.


Revision #1 to TR12-004 | 29th February 2012 05:57

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication


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 {\it nondeterministic tensor-rank} ($nrank$), we show that for any boolean function $f$ with communication tensor $T_f$,
\begin{enumerate}
\item in the Number-On-Forehead model, the cost is upper-bounded by the logarithm of $nrank(T_f)$;
\item in the Number-In-Hand model, the cost is lower-bounded by the logarithm of $nrank(T_f)$.
\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.



Changes to previous version:

Changed format, and fixed several typos. Also added more details for some proofs, and some missing references.


Paper:

TR12-004 | 10th January 2012 14:11

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication


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 {\it nondeterministic tensor-rank} ($nrank$), we show that for any boolean function $f$ with communication tensor $T_f$,
\begin{enumerate}
\item in the Number-On-Forehead model, the cost is upper-bounded by the logarithm of $nrank(T_f)$;
\item in the Number-In-Hand model, the cost is lower-bounded by the logarithm of $nrank(T_f)$.
\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.



ISSN 1433-8092 | Imprint