Abstract
In this paper, we continue a line of research initiated by Basu, Brakensiek, and Putterman [2026] studying the sparsifiability of Hamiltonians. We focus particularly on the sparsifiability of the widely-studied Quantum Cut (QC) Hamiltonians. Our main result is that in an n-qubit system, any n-qubit QC Hamiltonian can be sparsified to O(n /ε²) many terms while preserving the energy of every state up to a factor of 1 ± ε. Our result can be interpreted as giving an importance sampling scheme for the edges of an arbitrary graph G such that the \emph{Kikuchi} graph at level ℓ of the sampled graph is a spectral approximation to the Kikuchi graph of G. Importantly, the \emph{same} sampling scheme works simultaneously for all ℓ. The natural approach of leverage score sampling, analyzed via matrix concentration inequalities, yields a polynomially worse bound in our setting because the underlying matrices have dimension ∼ 2ⁿ. Instead, our approach relies on decomposing the action of these matrices into invariant subspaces. Then, by using an operator-valued inequality of Alon and Kozma [Ann. Henri Poincar\'e, 2020], itself building on an \emph{octopus inequality} of Caputo, Liggett, and Richthammer [J. AMS, 2010], we extend our sparsification technique to all expander graphs. We then invoke expander decomposition to extend our sparsifier to all graphs.