2
$\begingroup$

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<j}\omega_{ij}Z_iZ_j\,,\tag{3}$$ with some constant offset: $$cst = \sum\limits_{i<j}\omega_{ij}/2\,.\tag{4}$$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.