Search

Using graphs and hypergraphs to systematically model collections of arbitrary subsets of parties representing {\it ensembles (or collections)} of shared multipartite CAT states, we study transformations between such {\it ensembles} under {\it local operations and classical communication (LOCC)}. We show using partial entropic criteria, that any two such distinct ensembles represented by {\it $r$-uniform hypergraphs} with the same number of hyperedges (CAT states), are LOCC incomparable for even integers $r\geq 2$, generalizing results in \cite{mscthesis,sin:pal:kum:sri}. We show that the cardinality of the largest set of mutually LOCC incomparable ensembles represented by $r$-uniform hypergraphs for even $r\geq 2$, is exponential in the number of parties. We also demonstrate LOCC incomparability between two ensembles represented by 3-uniform hypergraphs where partial entropic criteria do not help in establishing incomparability. Further we characterize LOCC comparability of EPR graphs in a model where LOCC is restricted to teleportation and edge destruction. We show that this model is equivalent to one in which LOCC transformations are carried out through a sequence of operations where each operation adds at most one new EPR pair., Comment: 13 pages, 4 figures, presented in AQIS 2007

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., Comment: 15 pages, 2 tables

We develop graph theoretic methods for analysing maximally entangled pure states distributed between a number of different parties. We introduce a technique called {\it bicolored merging}, based on the monotonicity feature of entanglement measures, for determining combinatorial conditions that must be satisfied for any two distinct multiparticle states to be comparable under local operations and classical communication (LOCC). We present several results based on the possibility or impossibility of comparability of pure multipartite states. We show that there are exponentially many such entangled multipartite states among $n$ agents. Further, we discuss a new graph theoretic metric on a class of multi-partite states, and its implications., Comment: To appear in the Journal of Mathematical Physics, 33 pages, 16 figures

In this paper we show that sufficient multi-partite quantum entanglement helps in fair and unbiased election of a leader in a distributed network of processors with only linear classical communication complexity. We show that a total of $O(\log n)$ distinct multi-partite maximally entanglement sets (ebits) are capable of supporting such a protocol in the presence of nodes that may lie and thus be biased. Here, $n$ is the number of nodes in the network. We also demonstrate the difficulty of performing unbiased and fair election of a leader with linear classical communication complexity in the absence of quantum entanglement even if all nodes have perfect random bit generators. We show that the presence of a sufficient number $O(n/\log n)$ of biased agents leads to a non-zero limiting probability of biased election of the leader, whereas, the presence of a smaller number $O(\log n)$ of biased agents matters little. We define two new related complexity classes motivated by the our leader election problem and discuss a few open questions., Comment: 10 pages, no figures, LaTeX

We develop protocols for preparing a GHZ state and, in general,a pure multi-partite maximally entangled state in a distributed network with apriori quantum entanglement between agents using classical communication and local operations. We investigate and characterize the minimal combinatorics of the sharing of EPR pairs required amongst agents in a network for the creation of multi-partite entanglement. We also characterize the minimal combinatorics of agents in the creation of pure maximal multi-partite entanglement amongst the set $N$ of $n$ agents in a network using apriori multi-partite entanglement states amongst subsets of $N$. We propose protocols for establishing multi-partite entanglement in the above cases., Comment: Substantially extended, title changed, 18 pages, 4 figures