Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians

We give a classical $1\mathrm{/}(qk+1)$-approximation for the maximum eigenvalue of a $k$-sparse fermionic Hamiltonian with strictly $q$-local terms, as well as a $1\mathrm{/}(4k+1)$-approximation when the Hamiltonian has both $2$-local and $4$-local terms. More generally we obtain a $1\mathrm{/}O(q{k}^2)$-approximation for $k$-sparse fermionic Hamiltonians with terms of locality at most $q$. Our techniques also yield analogous approximations for $k$-sparse, $q$-local qubit Hamiltonians with small hidden constants and improved dependence on $q$.