Constant communication complexity protocols for multiparty accumulative boolean functions

Abstract

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)={⨁}_{i=1}^n{t}_B(x_i^1{x}_i^2...x_i^m)$, where $X_j=(x_1^j,x_2^j,...,x_n^j),1\le j\le m$ and $t_B(x_i^1{x}_i^2...x_i^m)=1$ for input $m$-tuples $x_i^1{x}_i^2...x_i^m\in B\subseteq A\subseteq \{0,1{\}}^n$, and 0, if $x_i^1{x}_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\le j\le m$ are given to the $m\ge 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\ge 3$ parties under appropriate uniform parity promise restrictions on input $m$-tuples $x_i^1{x}_i^2...x_i^m,1\le i\le 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\ge 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.

15 pages, 2 tables

References in corpus (4)

• Substituting Quantum Entanglement for Communication
• Quantum Entanglement and Communication Complexity
• Multiparty Quantum Communication Complexity
• Quantum Entanglement and the Communication Complexity of the Inner Product Function