# How can one check whether a given quantum state is a graph state?

We can build a quantum state from a graph, which is a mathematical concept. But, vice versa, how can one check whether or not a given quantum state is a graph state?

• You might want to have a look at stabilizer testing which can probably be adapted for graph states ... See e.g. Sec. 1.3 in [Gross et al. CMP 2021], arxiv.org/abs/1712.08628 Apr 12 '21 at 8:03

Remember that a graph state is simply the $$|+\rangle$$ state on every qubit together with a bunch of controlled phases enacted between them. So, assuming you have a list of the probability amplitudes of your state, you first check that, if there are $$n$$ qubits, every amplitude is $$\pm1/\sqrt{2^n}$$.
Once you have done this, you need to determine the pattern of controlled phases. This is easy. Find the amplitude of a term $$x$$ which is all 0s except for two 1s. The sign of that amplitude tells you whether $$(-1)$$ or not $$(+1)$$ a controlled phase gate was applied between that particular pair of qubits. So, go through every possible pair of qubits, determine the controlled-phase gates. Then you just have to verify whether all the other $$\pm$$ signs on the amplitudes are compatible with that assignment.
If you want to find the answer experimentally, a possible (not necessarily optimal) way to do so is the following. Note that a graph state is stabilized by the generators $$g_v=X_v \prod_{w\in N(v)} Z_w,$$ where $$v$$ is a vertex of the graph and $$N(v)$$ is its neighborhood. You can find the neighborhood of a vertex by measuring $$X$$ on qubit $$v$$ and $$Z$$ on all others. The outcomes of the neighborhood will be perfectly correlated with the $$X$$-outcome, because $$\langle \psi | g_v |\psi \rangle = 1$$. This can be repeated for each qubit. Probably this could be done more efficiently, but at least this should be better than full tomography.