An especially useful class of quantum states is graph states which, as the name suggests, are associated with a graph , where the vertices represent qubits initialised into the
state, state, and edges represent the application of controlled-phase gates between respective vertices. A graph state can therefore be expressed as,
Since gates are diagonal and therefore commute with one another, the order in which they are applied is irrelevant, meaning there is great flexibility in the preparation of graph states and room for parallelisation in the application of the required CZ gates.
An alternative mathematical way of describing a graph state relies on the stabiliser formalism. For every vertex a stabiliser is defined as
where are all the vertices in the neighborhood of vertex . The graph state is uniquely defined as the eigenstate of all the stabilizers with eigenvalue .
When the topology of the graph is a 2D lattice, the state is also said to be a cluster state.