# Relationship between the eigenvalues of a Laplacian matrix and the eigenvalues of the Hamiltonian of a graph for Max-Cut

Is there a relationship between the eigenvalues of a Laplacian matrix of a graph and the eigenvalues of the Hamiltonian for Max-Cut?

It is shown here, that Max-Cut can be written as a maximization problem involving the graph Laplacian:

$$\underset{x \in \mathbb{R}^n}{\max} x^T L x, \quad x_i \in \{-1,1\},\quad i=1,...,n\tag{1}\,.$$

The Laplacian matrix is defined as: $$L=D-A$$, where $$D$$ is the degree matrix and $$A$$ is the adjacency matrix of the graph.

The formulation is equivalent to maximizing- $$C(x)=\frac{1}{2} \sum\limits_{i,j} \omega_{ij} \cdot x_i(1-x_j), \quad x \in \{-1,1\}^n\tag{2}\,.$$

From this, the Hamiltonian can be constructed, with the assignment: $$x_i \rightarrow (1-Z_i)/2$$, where $$Z_i$$ is the Pauli-Z operator. The Hamiltonian becomes (see this):

$$H=\sum\limits_{i with some constant offset: $$cst = \sum\limits_{i

There are several results known for the eigenspectrum of the Laplacian of a graph, such as Cheeger's inequality. Is there some relation to the eigenvalues of the Hamiltonian? Is there anything that can be followed for the spectral gap of the Hamiltonian?