I cannot understand the proof of Lemma 5 from the paper "Resources Required for Preparing Graph States". Here it is:

enter image description here

(In this paper, $|G:S\rangle$ denotes $Z_S$ applied to the graph state $|G\rangle$, and the $/$ symbol denotes contraction of an edge.)

I have two questions

1) Why is the operator $Z_{v^{\prime\prime}}^k$ inside the big brackets necessary? Since $v^{\prime\prime}$ is not present in the graph $G/vv^\prime/v^\prime v^{\prime\prime}$, does this operator not just cancel out with the one inside the term $(|0\rangle +Z_{v^{\prime\prime}}^k|1\rangle)_{v^{\prime\prime}}$ ?

2) What is special about having $v^\prime$ and $v^{\prime\prime}$ here? If we had no $v^{\prime\prime}$ vertex, and the vertex $v^\prime$ attached directly to $R$ (see figure 1), would this same argument not work?


2 Answers 2


1) This equation is at best confusing, and at worst perhaps even straight-up wrong. Firstly, they use a different edge contraction notation as in the equations description and secondly, as you observe, they appear to have a Z operator acting upon qubit $v^{\prime\prime}$ which is no longer a vertex of the edge-contracted state.

Perhaps the Z-operators on various qubits do cancel out as desired when applied to the correct qubits, but this is clearly a confusing and non-obvious way of representing the state. Looking at it, I suspect that they have simply mixed up $v$ and $v^{\prime\prime}$, since the operator $Z^k_{v}Z^l_{N_G(v^{\prime\prime})\setminus \{v^\prime\}}$ looks correct to me.

Assuming this is the case, the reason we can write the state like this can be seen by considering a simpler case. First, we observer that the two-vertex line graph $L_2$ can be written as:

$$ \def\ket#1{\lvert #1 \rangle}\def\bra#1{\langle #1 \rvert} \ket{L_2} = \frac{1}{\sqrt{2}}(\ket{++} + \ket{--}) $$

whereas the state associated with the three-qubit line $L_3$ can be written as

$$ \begin{aligned} \ket{L_3} &= \frac{1}{2}(\ket{+++} + \ket{+--} + \ket{--+} + \ket{-+-}) \\ &= \frac{1}{2}\big[(\ket{++} + \ket{--})_{1,3}\ket{+}_2 + (\ket{+-} + \ket{-+})_{1,3}\ket{-}_2\big] \\ &= \frac{1}{\sqrt{2}}\sum_{i=0,1}Z_3^i\ket{L_2}_{1,3}(\ket{0} + Z_2^i\ket{1}) \end{aligned} $$

where $L_2 = L_3 \;/\; (1, 2)$. This equation is telling us that if we measure the middle qubit in the $X$-basis, we essentially perform an edge contraction on one of it's connected edges. It is easy to see that applying this twice yields their desired result.

So yeah, my money is that it's just a typo.

2) You are correct in asserting that the edge contraction trick would work with only two nodes (up to the $Z$ operators applied to the remaining state). The reason they do this is because the lemma's real purpose is for their proof of theorem 3, in which they seek to produce a graph $\tilde{G}$ of maximum vertex degree 3. This requires adding the extra internal vertex $v^\prime$ with degree two, since if one were not to do this, the subsequent expansions would not serve to reduce the overall degree.

The best way to see this is to take the example given in Figure 1 and try the subsequent expansions of $v$ and $v^{\prime\prime}$ in the case where $v^\prime$ does and doesn't exist. In the latter case, the expansion of the right node serves to increase the degree of the original node, whereas in the former case the middle node goes from degree 2 to 3. If you repeat this enough times, you will soon see that the centre node is necessary to reduce the overall degree.


I can't really follow the description in the paper you've linked, but it looks similar to the 'identity removal' procedure described in one of my papers here (see Definition 2.27). We describe the one-way model of quantum computing and graph states using the ZX-calculus, which I think is a more clear way of thinking about these things.


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.