Quantum Cut Sparsifiers
2026-06-08 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors build on previous work about making complicated quantum systems simpler by reducing the number of interactions without losing important information. They focus on Quantum Cut Hamiltonians and show that these can be approximated with far fewer terms while keeping the energy levels almost the same. Their method cleverly uses a special sampling technique that works well for all parts of the system simultaneously, improving on older methods that were less efficient for large quantum systems. They apply advanced mathematical tools related to graph theory and matrix inequalities to achieve this reduction for a wide range of graphs.
Hamiltonian sparsificationQuantum Cut Hamiltonianimportance samplingKikuchi graphspectral approximationexpander graphsoperator-valued inequalitymatrix concentration inequalities
Authors
Arpon Basu, Joshua Brakensiek, Pravesh K. Kothari, Aaron Putterman
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 $\widetilde{O}(n /\varepsilon^2)$ 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 \emph{Kikuchi} graph at level $\ell$ of the sampled graph is a spectral approximation to the Kikuchi graph of $G$. Importantly, the \emph{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^n$. 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 \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.