# Graph state and maximally entangled state

How can I show that a multi-qudit graph state $$|G\rangle$$ is the maximally entangled state? What kind of measure of entanglement can be used to quantify the amount of entanglement in a given graph state?

• Careful: connected axioms Nov 23 '18 at 3:17
• How do you define maximally entangled in the multi-qudit context? Nov 23 '18 at 6:58
• The entanglement entropy is maximal for all their partitions. Nov 23 '18 at 8:49

Consider a graph $$G$$, and we create the corresponding graph state $$|G\rangle$$ by placing a qubit on every vertex in the $$|+\rangle$$ state, and applying a controlled-phase gate along every edge.
Now, take a bipartition of $$G$$. On either side of the bipartition, we can apply unitaries (we're just not allowed to do anything across the partition). Hence, we can apply controlled-phases along any edges that remain within a bipartition. We are reduced to a graph state that is the same as the original, but only has edges across the bipartition, and it has the same amount of entanglement with respect to that bipartition.
Next, throw away all vertices that don't have an edge, as they're irrelevant. Let's have the sizes of the two bipartitions being $$n\leq m$$. Then we can write the graph state as $$\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle\otimes(Z_{N(x)}|+\rangle^{\otimes m}),$$ where $$N(x)$$ describes the neighbourhood of the spins of the first bipartition specified by $$x$$. More explicitly, a $$Z$$ is applied to any qubit in the second bipartition if it is the neighbour to an odd number of vertices $$i$$ in the first bipartition for which $$x_i=1$$.
Under the assumption that $$N(x)$$ is distinct for all $$x\in\{0,1\}^n$$, this is a Schmidt decomposition, meaning that there are $$2^n$$ Schmidt coefficients, each of value $$1/2^n$$, from which you can calculate anything such as the entanglement entropy, $$n$$. However, if any qubits were discarded in the discard step, this entanglement entropy will not be maximal.
Moreover, the assumption of the distinctness of $$N(x)$$ is not necessarily true. Think, for example, of the square graph (of 4 vertices), and a bipartition of grouping qubits on the diagonals. Here, $$N(00)=N(11)$$. However, this can be avoided by using the local equivalence of graph states to minimise the number of edges across the bipartition. I don't have a rigorous proof for this off the top of my head, bur probably a good way to approach it is to show that if $$N(x)=N(y)$$, then $$N(x\oplus z)=N(y\oplus z)$$. This means that you would break down the state into the form $$\frac{1}{\sqrt{2^n}}\sum_{z\in\{0,1\}^n}(|z\rangle+|z\oplus x\oplus y\rangle)\otimes\left(Z_{N(z)}|+\rangle^{\otimes m}\right),$$ where we restrict the sum over $$z$$ to avoid double counting. This leads to a halving of the number of Schmidt coefficients, each of which has doubled in value. The entanglement entropy is $$n-1$$. Of course, it could be reduced by any integer amount depending on the structure. The most extreme case, of course, is the fully connected graph (which is locally equivalent to a GHZ state). Any bipartition only has 1 ebit of entanglement across the bipartition, even though it initially looks like there are many edges crossing it.