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

Question

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?

Answer 1

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.

Answer 2

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.