Physics – Quantum Physics
Scientific paper
2005-10-07
Physics
Quantum Physics
15 pages, 2 tables
Scientific paper
Generalizing a boolean function from Cleve and Buhrman \cite{cb:sqec}, we consider the class of {\it accumulative boolean functions} of the form $f_B(X_1,X_2,..., X_m)=\bigoplus_{i=1}^n t_B(x_i^1x_i^2... x_i^m)$, where $X_j=(x^j_1,x^j_2,..., x^j_n), 1\leq j\leq m$ and $t_B(x_i^1x_i^2... x_i^m)=1$ for input $m$-tuples $x_i^1x_i^2...x_i^m\in B\subseteq A\subseteq \{0,1\}^n$, and 0, if $x_i^1x_i^2...x_i^m\in A\setminus B$. Here the set $A$ is the input {\it promise} set for function $f_B$. The input vectors $X_j, 1\leq j\leq m$ are given to the $m\geq 3$ parties respectively, who communicate cbits in a distributed environment so that one of them (say Alice) comes up with the value of the function. We algebraically characterize entanglement assisted LOCC protocols requiring only $m-1$ cbits of communication for such multipartite boolean functions $f_B$, for certain sets $B\subseteq \{0,1\}^n$, for $m\geq 3$ parties under appropriate uniform parity promise restrictions on input $m$-tuples $x_i^1x_i^2...x_i^m, 1\leq i\leq n$. We also show that these functions can be computed using $2m-3$ cbits in a purely classical deterministic setup. In contrast, for certain $m$-party accumulative boolean functions ($m\geq 2$), we characterize promise sets of mixed parity for input $m$-tuples so that $m-1$ cbits of communication suffice in computing the functions in the absence of any a priori quantum entanglement. We compactly represent all these protocols and the corresponding input promise restrictions using uniform group theoretic and hamming distance characterizations.
Das Sima
Kumar Somesh
Pal Sudebkumar Prasant
No associations
LandOfFree
Constant communication complexity protocols for multiparty accumulative boolean functions 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 Constant communication complexity protocols for multiparty accumulative boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant communication complexity protocols for multiparty accumulative boolean functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-561329