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

arXiv1804.06857MaRDI QIDQ6300533FDOQ6300533

Authors: Michael Jarret 

Publication date: 18 April 2018

Abstract: 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}$, $2hgeqgammageqsqrt{h}^2+d_{max}^2-d_{m}ax$; (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 $2hgeqgamma$ 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. If efficiently computable, the constant opens up a very clear path towards adaptive quantum adiabatic algorithms, those that adjust the adiabatic path based on spectral structure. I sketch a bashful adiabatic algorithm that aborts the adiabatic process early, uses the resulting state to approximate the weighted Cheeger constant, and restarts the process using the updated information. Should this approach work, it would provide more rigorous foundations for adiabatic quantum computing without extit{a priori} knowledge of the spectral gap.

This page was built for publication: Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300533)