Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
Yes.
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.
