Quantum Cut Sparsifiers

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 widetilde{O}\(n /varepsilon²\) many terms while preserving the energy of every state up to a factor of 1 pm varepsilon. Our result can be interpreted as giving an importance sampling scheme for the edges of an arbitrary graph G such that the Kikuchi graph at level ell of the sampled graph is a spectral approximation to the Kikuchi graph of G. Importantly, the same sampling scheme works simultaneously for all ell. 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 sim 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é, 2020], itself building on an 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.