Graph states are a class of many-body quantum state. The graph state formalism provides and over-arching description of a variety of different quantum states, encapsulating almost all of the central states in quantum information theory (the most notable exception being the W, or Dicke, state), such as the Bell states, GHZ states, CSS error correcting codes and cluster states. This is not mere coincidence - the mathematical structure of these states is particularly simple (often reducing to just properties of the underlying graph) and therefore permits superior analysis compared to the vast majority of states. They therefore also provide a rich testing ground for exploring and developing key ideas.

Consider a graph $G$, which is composed of $N$ vertices, $V$, and a set of edges $E$. Each vertex is associated with a qubit. There are two alternative (equivalent) ways to define a graph state on the graph $G$. For the first option, we take each qubit to be prepared in the state $\ket{+}=(\ket{0}+\ket{1})/\sqrt{2}$, and apply controlled-phase gates between each pair of qubits that constitute an edge.

For the second option, we define a set of operators $K_n$, one for each vertex, as follows: $$ K_n=X_n\prod_{(n,m)\in E}Z_m. $$ $X_n$ and $Z_m$ are the Pauli $X$ and $Z$ operators acting on qubits $n$ and $m$ respectively. We will also use the notation $X_x$ for $x\in\{0,1\}^N$ to denote a product of $X$ operators on the sites where the bit string $x$ has value 1. The operators $K_n$ mutually commute, $[K_n,K_m]=0$. The graph state for this graph is the $+1$ eigenstate of all $N$ of the operators $K_n$, and we will denote it by $\ket{\psi^G}$. The other eigenstates are $\ket{\psi_x}=Z_x\ket{\psi^G}$, which have eigenvalues $(-1)^{x_n}$ with stabilizers $K_n$.

In general, if we want to talk about noise, we must discuss mixed states. We will restrict to the class of graph-diagonal states, meaning density matrices which are diagonal in the graph state basis $\ket{\psi_x}$. It is useful to note that any state can be made graph-diagonal while preserving the diagonal elements in the graph state basis, just by the random application of local unitaries at each site (an entanglement non-increasing operation). A general graph-diagonal state can be written as $$ \rho=\frac{1}{2^N}\sum_{x\in\{0,1\}^N}s_xK_x $$ where $s_{00\ldots 0}=1$, and positivity imposes that $$ \sum_{x\in\{0,1\}^N}s_x(-1)^{x\cdot y}\geq 0\qquad\forall y\in\{0,1\}^N. $$ For now, we are interested in the further resitrction in which we define $$ H=-\sum_{n=1}^NK_n $$ and $$ \rho=\frac{e^{-\beta H}}{\text{Tr}(e^{-\beta H})}. $$ This is known as the thermal state of a graph, $G$, where $\beta$ is the inverse temperature. An alternative description of this state is, starting from $\ket{\psi^G}$, one applies at random on each site, an operation $Z$ with probability $p=(1-\tanh(2\beta))/2$.

• What is the maximum temperature at which a given graph is entangled? How is this affected by the graph structure?
• How can this entanglement be detected?
• What is the maximum temperature at which entanglement can usefully be distilled?

Even though, in general, we do not yet have the tools to talk about multipartite entanglement properly, the structure of graph states allows us to make a lot of progress with these problems, and hopefully gives hints as to how to tackle more general problems. A key to the separability and distillability properties of thermal graph states is the partial transpose criterion. This is because the partial transpose is particularly easy to take on a graph-diagonal state. Recall that under the transpose, the Pauli operators transform as follows: $$ X\mapsto X\qquad Z\mapsto Z\qquad Y\mapsto -Y $$ So, if we take the partial transpose of our state $\rho$, some of the weights $s_x$ just change sign. Moreover, since it is just the weights that change, and not the terms themselves, the eigenvectors remain the same. This lets us evaluate the eigenvalues under the partial transpose. The sign of the smallest determines whether the state is positive or negative under the partial transpore with respect to a particular bipartition.

It is well known that:

• for a multipartite state to be distillable when multiple copies are available, but each party acts locally, the state must be negative under the partial transpose with respect to every possible bipartition (i.e. if there is to be entanglement present across a paticular bipartition in the final state, there must be some distillable entanglement across that bipartition in the initial state).
• for a multipartite state to be fully separable (i.e. completely dis-entangled), it must be positive under the partial transpose with respect to every possible bipartition.

While these are necessary conditions, they are not generally sufficient conditions. However, we can prove that for a massive class of thermal graph states, the distillability condition is also sufficient. For the separability condition, we can prove that all trees whose thermal states have positive partial transpose under all bipartitions are fully separable. We conjecture that:

• A $k$-colourable thermal graph state is fully separable if it is separable under the $k$-colouring partition.
• Positive partial transpose of a bipartition of a bipartite graph implies its separability with respect to that partition.
• What is the computational complexity of determining the critical temperature for a given family of graphs? (This seems to have some interesting connections to zeros of the partition function of the same graph, but for complex parameters.)

These statements remain unproven. We have also managed to develop entanglement witnesses that saturate the partial transpose threshold i.e. for thermal tree states we know that the entanglement witnesses are optimal. Indeed, for GHZ states (which correspond to star graphs), we know this over approximately half of the possible parameter space.

There are many other features of entanglement that are worth investigating with the graph state formalism. For instance, we recently investigated the intriguing phenomenon of the ability for two parties, Alice and Bob, to share a separable quantum state, for Alice to send a separable qubit to Bob, and for them to suddenly share entanglement! This can be understood in the following way:
Consider a chain of 3 sites to be a graph. Number the sites 1,2,3 in order. The optimal bipartition for the persistence of entanglement is 2-(1,3) i.e. the two-colouring partition. Hence, there exist temperatures at which 2-(1,3) is entangled, but 1-(2,3) and (1,2)-3 are separable. So, if the protocol starts with Alice holding qubits 1 and 2, and Bob holding 3, the state is separable between Alice and Bob. Alice then sends qubit 1 to Bob. In transit, 1 is separable from the rest of the system. On arrival, however, Alice and Bob share some entanglement. It turns out this this possibility is a remarkably common phenomenon.

1. A. Kay, Arboreal Bound Entanglement, J. Phys. A: Math. Theor. 43, 495301 (2010) arXiv
2. A. Kay, Optimal Detection of Entanglement in GHZ States, Phys. Rev. A 83, 020303(R) (2011) arXiv
3. A. Kay and J. K. Pachos, Multipartite purification protocols: upper and optimal bounds , Phys. Rev. A 75, 062307 (2007) arXiv
4. A. Kay, J. K. Pachos, W. Dur and H. J. Briegel, Optimal purification of thermal graph states , New J. Phys. 8 (2006) 147 arXiv
5. T. S. Cubitt, F. Verstraete, W. Dur and J. I. Cirac, Separable States Can Be Used To Distribute Entanglement, Phys. Rev. Lett. 91, 037902 (2003) arXiv
6. A. Kay, Using Separable Bell-Diagonal States to Distribute Entanglement , Phys. Rev. Lett. 109, 080503 (2012) arXiv