# Graph state

In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they are a convenient way of representing certain types of entangled states.

Graph states are useful in quantum error-correcting codes, entanglement measurement and purification and for characterization of computational resources in measurement based quantum computing models.

## Formal definition

Given a graph G = (VE), with the set of vertices V and the set of edges E, the corresponding graph state is defined as

${\left| G \right\rangle} =\prod _{(a,b)\in E}U^{\{ a,b\} } {\left| + \right\rangle} ^{\otimes V}$

where the operator $U^{\{ a,b\} }$ is the controlled-Z interaction between the two vertices (qubits) a, b

$U^{\{ a,b\} } =\left[\begin{array}{cccc} {1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {-1} \end{array}\right]$

And

${\left| + \right\rangle} =\frac{{\left| 0 \right\rangle} +{\left| 1 \right\rangle} }{\sqrt{2} }$

### Alternative definition

An alternative and equivalent definition is the following.

Define an operator $K_{G}^{(a)}$ for each vertex a of G:

$K_{G}^{(a)} =\sigma _{x}^{(a)} \prod _{b\in N(a)}\sigma _{z}^{(b)}$

where N(a) is the neighborhood of a (that is, the set of all b such that $(a,b)\in E$) and $\sigma _{x,y,z}$ are the pauli matrices. The graph state ${\left| G \right\rangle}$ is then defined as the simultaneous eigenstate of the $N=\left|V\right|$ operators $\left\{K_{G}^{(a)} \right\}_{a\in V}$ with eigenvalue 1:

$K_{G}^{(a)} {\left| G \right\rangle} ={\left| G \right\rangle}$