#### 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 *U**C* − *p**h**a**s**e* = ∣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

- Any
**connected**graph state ∣*G*⟩ is a**fully entangled**and violates some Bell inequality.*m*-particle state - 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 2*m*number of continuous parameters). - Two graph states are locally unitarily interconvertible under the transformation ⊗
*i*= 1*m**U**i*, and this is equivalent to convertibility under stochastic local operations and classical communication (SLOCC).

### Related papers

- 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 .

Category:Quantum States Category:Mathematical Structure Category:Models of Quantum Computation