Consider a $k-\text{ary}$ tree $T$, for a constant $k$. Consider the corresponding graph state $|\mathsf{G}_T \rangle$ that is defined on $T$.

Is it true that $|\mathsf{G}_T \rangle$ saturates the area law for entanglement entropy, across any bipartition? It is easy to prove that the entanglement entropy for $|\mathsf{G}_T \rangle$, across any bipartition, can be upper bounded by an area law. Does it saturate the bound too?


1 Answer 1



Think about the process of building a graph state: create qubits in the $|+\rangle$ state and apply controlled-phase gates along all the edges.

Now take a bipartition. You can apply any unitary that you want on either side of the partition, so perform controlled-phase gates along all edges not crossing the partition. Let's say the connected qubits on either side of the partition are in sets $S_1$ and $S_2$, where $S_1$ is smaller (or the same size) as $S_2$. You are only left with entangled states across the partition, and they require a number of Bell pairs to build that is equal to $|S_1|$.

To make this explicit, let $x\in\{0,1\}^{|S_1|}$ and let's call $N(x)\in\{0,1\}^{|S_2|}$ the neighbourhood of $x$, by which I strictly mean that bit $i$ of $N(x)$ is the parity of neighbours $j$ of $i$ for which $x_j=1$. Now I can write the graph state (after my unitaries) as $$ \sum_{x\in\{0,1\}^{|S_1|}}|x\rangle\otimes Z_{N(x)}|+\rangle^{\otimes|S_2|}. $$ Now since all the $Z_{N(x)}|+\rangle^{\otimes|S_2|}$ are orthogonal for distinct $x$ (I believe this follows from the fact that you have a tree, and hence no loops), we can see that the way I've written the graph state is a Schmidt decomposition for a maximally entangled state of $|S_1|$ qubits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.