A *graph *is a mathematical object *G = (V , E) *defined using a set *V = {v _{1}, v_{2}, …, v_{N}} *of

*vertices*and a set

*E = {(v*of

_{i}, v_{j}) : v_{i}, v_{j}∈ V}*edges*. The vertices, also sometimes called

*nodes*, are depicted using dots. Each edge consists of a pair of vertices, and the edge is depicted as a line connecting the dots corresponding to the vertices. The graph is called directed if the edge

*(v*is distinct from the edge

_{i}, v_{j})*(v*. The edge

_{j}, v_{i})*(v*is then depicted using a line with an arrow point from

_{i}, v_{j})*v*to

_{i}*v*, and similarly for the edge

_{j}*(v*(the arrow points from node

_{j}, v_{i})*v*to

_{j}*v*). In an undirected graph, the edges

_{i}*(v*and

_{i}, v_{j})*(v*are regarded as equivalent.

_{j}, v_{i})There is also the concept of a

*hypergraph*, in which the edges can consist of more than two vertices. We do not consider hypergraphs in this note.

Graphs have widespread use in science. Graphs can be used to model virtually any system that consists of multiple parts that are related to each other in some way. The nodes of the graph typically represent the various parts of the system, and the edges describe how the different parts of the system are related to each other.

Perhaps not surprisingly, graphs have been used in quantum theory. In this note, I describe some of the ways in which graphs have been used to define quantum states. In particular, I discuss the following three types of quantum states constructed from graphs:

- Graph states: based on the construction in Refs. [1,2].
- The density matrix of a graph in Ref. [7] created by normalizing its Laplacian.
- The density matrix of a graph in Ref. [8] created by normalizing the exponential of the Laplacian.

There is also the construction in Refs. [4,5,6], which we do not discuss here.

## Graph States

*Graph states*, also sometimes called *cluster states*, were defined in [1,2] in the context of measurement-based quantum computing. They have since found use in quantum error-correction as well (see, e.g., [3]). A graph state is a multipartite quantum state defined by a (directed) graph G in which each node v ∈ V represents a qubit and each edge e ∈ E represents an interaction between the two qubits connected by the edge. Specifically, if there are N nodes in the graph, the graph state |G⟩ is defined as follows:

In other words, we form the graph state by first preparing each of the *N *qubits in the |+⟩ state. Then, we apply controlled-Z gates between the qubits whose corresponding vertices are connected by an edge in the graph G. The arrow of the directed edge in the graph points from the control qubit to the target qubit; see the figure below. Recall that the matrix for the controlled-Z gate is

Another equivalent way to define a graph state is as the (unique) simultaneous eigenstate of a set of mutually commuting observables:

where

Recall that σ_{x} and σ_{z} are the Pauli X and Z operators, defined as

The operators *K*^{(a)} represent a Pauli X acting on qubit *a *and a Pauli Z acting on all qubits *b* that are connected to qubit *a *via an edge (the identity acts implicitly on all of the other qubits). This definition of a graph state establishes it explicitly as what is called a *stabilizer state*, which is important in the context of quantum error-correcting codes for fault-tolerant quantum computing.

Yet another way to define a graph state is as follows:

where *A(G)* is the *adjacency matrix *of the graph G, which is an *N×N *matrix defined as

(This definition holds for both undirected and directed graphs. Specifically, if the graph is undirected, then we get a symmetric matrix.)

## States from the Laplacian — First Method

The second method for creating quantum states from graphs is from Ref. [8], which makes use of the Laplacian of a graph.

Let *G* be an undirected graph without any loops (i.e., without edges that start and end at the same node). Above, we defined the adjacency matrix of a graph *G*. Another matrix function of the graph G is the following, denoted by Δ(G):

where *d _{G}(v_{i}) *is the degree of the node

*v*, defined to be the number of edges attached to v

_{i}_{i}. Using this and the adjacency matrix, the

*(combinatorial) Laplacian*of

*G*is defined to be

Because we take *G *to be undirected, its adjacency matrix is symmetric. Since Δ(*G*) is diagonal, we have that the Laplacian *L(G) *is symmetric. Furthermore, *L(G) *is positive semi-definite. To see this, we observe that *L(G) *can be written as

where the matrix *M(G) *is the incidence matrix of *G*, which is a *|E|×|V| *matrix defined as

Since *L(G) *is symmetric and positive semi-definite, the object

is symmetric, positive semi-definite, and has trace one. ρ(*G*) is therefore a density matrix.

## States from the Laplacian — Second Method

The last method we consider comes from Ref. [9], and it is also based on the Laplacian of a graph.

Consider again an undirected graph *G *without any loops. Then, using the Laplacian *L(G) *as above, the object

is a density matrix, where τ > 0 can be thought of as a time parameter.

## References

[1] Hans J. Briegel and Robert Raussendorf. *Persistent Entanglement in Arrays of Interacting Particles. *Phys. Rev. Lett. **86**(5), 910 (2001). arXiv:quant-ph/0004051.

[2] Robert Raussendorf and Hans J. Briegel. *A One-Way Quantum Computer.* Phys. Rev. Lett. **86**(22), 5188 (2001).

[3] Andrew Cross, Graeme Smith, John A. Smolin, and Bei Zeng. *Codeword Stabilized Quantum Codes. *IEEE Trans. Inf. Theory **55**(1), 433 (2009). arXiv:0708.1021.

[4] Mario Krenn, Xuemei Gu, and Anton Zeilinger. *Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings.* Phys. Rev. Lett. **119**, 240403 (2017). arXiv:1705.06646.

[5] Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn. *Quantum experiments and graphs II: Quantum interference, computation, and state generation.* PNAS **116**(10), 4147 (2019). arXiv:1803.10736.

[6] Xuemei Gu, Lijun Chen, Anton Zeilinger, and Mario Krenn. *Quantum experiments and graphs III. High-dimensional and multiparticle entanglement.* Phys. Rev. A **99**, 032338 (2019). arXiv:1812.09558.

[7] Samuel L. Braunstein, Sibashish Ghosh, and Simone Severini. *The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed States.* Annals of Combinatorics **10**, 291 (2006). arXiv:quant-ph/0406165.

[8] Manilo De Domenico and Jacob Biamonte. *Spectral Entropies and Information-Theoretic Tools for Complex Network Comparison. *Phys. Rev. X **6**, 041062 (2016). arXiv:1609.01214.