Graph state

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

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

where and the operator is the controlled-Z interaction between the two vertices (qubits) a, b

Alternative definition[edit]

An alternative and equivalent definition is the following.

Define an operator for each vertex v of G:

where are the Pauli matrices and N(v) is the set of vertices adjacent to v. The operators commute. The graph state is defined as the simultaneous -eigenvalue eigenstate of the operators :


  • If is a three-vertex path, then the stabilizers are

The corresponding quantum state is

  • If is a triangle on three vertices, then the stabilizers are

The corresponding quantum state is

Observe that and are locally equivalent to each other, i.e., can be mapped to each other by applying one-qubit unitaries. Indeed, switching and on the first and last qubits, while switching and on the middle qubit, maps the stabilizer group of one into that of the other.

More generally, two graph states are locally equivalent if and only if the corresponding graphs are related by a sequence of so-called ``local complementation" steps, as shown by Van den Nest et al. (2005).

See also[edit]


  • M. Hein; J. Eisert; H. J. Briegel (2004). "Multiparty entanglement in graph states". Physical Review A. 69: 062311. arXiv:quant-ph/0307130. Bibcode:2004PhRvA..69f2311H. doi:10.1103/PhysRevA.69.062311.
  • S. Anders; H. J. Briegel (2006). "Fast simulation of stabilizer circuits using a graph-state representation". Physical Review A. 73: 022334. arXiv:quant-ph/0504117. Bibcode:2006PhRvA..73b2334A. doi:10.1103/PhysRevA.73.022334.
  • M. Van den Nest; J. Dehaene; B. De Moor (2005). "Local unitary versus local Clifford equivalence of stabilizer states". Physical Review A. 71: 062323. arXiv:quant-ph/0411115. Bibcode:2005PhRvA..71f2323V. doi:10.1103/PhysRevA.71.062323.
  • Graph states on