Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices

Understand

Cheeger inequalities bound the spectral gap $\gamma$ of a space by isoperimetric properties of that space and vice versa.

• In this paper, I derive Cheeger-type inequalities for nonpositive matrices (aka stoquastic Hamiltonians), real matrices, and Hermitian matrices.
• For matrices written $H = L+W$, where $L$ is either a combinatorial or normalized graph Laplacian, I show that: (1) when $W$ is diagonal and $L$ has maximum degree $d_{\max}$, $2h \geq \gamma \geq \sqrt{h^2 + d_{\max}^2}-d_\max$; (2) when $W$ is real, we can often route negative-weighted edges along positive-weighted edges such that the Cheeger constant of the resulting graph obeys an inequality similar to that above; and (3) when $W$ is Hermitian, the weighted Cheeger constant obeys $2h \geq \gamma$ here $h$ is the weighted Cheeger constant of $H$.
• This constant reduces bounds on $\gamma$ to information contained in the underlying graph and the Hamiltonian's ground-state.