# Graph states

=== Definition ===

The general form of graph states was introduced as a generalization of cluster states, which have been shown to be a resource for one-way quantum computation. The importance of graph states stems from the fact that universality of quantum computer based on these states is one of the fundamental applications of entanglement in quantum computation theory.

Definition: A graph state is a pure m-qubit state  ∣G corresponding to a graph G(V, E). The graph is described by the set V of vertices with cardinality  ∣V∣ = m, representing the qubits of  ∣G, and the set E of edges, i.e. pairs of vertices, representing pairs of qubits of  ∣G.

#### Construction

In order to construct  ∣G one takes  ∣ + ⟩ ⊗ m, with $\; |+\rangle=(|0\rangle + |1\rangle)/ \sqrt{2}$, as the initial state. Then, according to a given graph G(V, E), one applies a controlled phase gate UC − phase = ∣0⟩⟨0∣ ⊗ 1 + ∣1⟩⟨1∣ ⊗ σ3 to any pair of qubits corresponding to vertices connected by an edge from E.

Note that, since all such controlled phase operations commute even if performed according to the edges with a common vertex, the order in which the operations are applied is arbitrary.

#### Properties

1. Any connected graph state  ∣G is a fully entangled m-particle state and violates some Bell inequality.
2. From the construction it follows that the set of graph states is described by a polynomial number m(m − 1)/2 of discrete parameters (while in general the set of all states in the m-qubit Hilbert space is described by an exponential  2m number of continuous parameters).
3. Two graph states are locally unitarily interconvertible under the transformation   ⊗ i = 1mUi, and this is equivalent to convertibility under stochastic local operations and classical communication (SLOCC).
• R. Horodecki, P. Horodecki, M. Horodecki, K. Horodecki, Quantum entanglement, e-print .
• R. Raussendorf, D. Browne, H.-J. Briegel, Phys. Rev. A 68, 022312 (2003).
• H.-J. Briegel, R. Raussendorf, Phys. Rev. Lett 86, 910 (2001).
• R. Raussendorf, H.-J. Briegel, Phys. Rev. Lett 86, 5188 (2001).
• Hein et al., Proceedings of the International of Physics School Enrico Fermi on Quantum Computers, Algorithms and Chaos (2005) e-print .