Quantum Cut Sparsifiers
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 Õ(n /ε2) 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 ∼ 2n. 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.
Related
- Charging of a quantum battery by a two-photon quantum pulse
- Quantum computing and quantum optics with recoiled free electrons
- Resource-efficient quantum-walker quantum random access memory
- Bosonic quantum error correction with microwave cavities for quantum repeaters
- Reflections on quantum Reflectometry: Quantum and tunneling capacitances as well as sisyphus and hermes resistances
BibTeX
@misc{basu2026quantum,
title = {{Quantum Cut Sparsifiers}},
author = {Arpon Basu and Joshua Brakensiek and Pravesh K. Kothari and Aaron Putterman},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.09728},
eprint = {2606.09728},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.09728},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Quantum Cut Sparsifiers
AU - Arpon Basu
AU - Joshua Brakensiek
AU - Pravesh K. Kothari
AU - Aaron Putterman
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2606.09728
UR - https://arxiv.org/abs/2606.09728
AB - 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 Õ(n /ε^2) 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^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.
ER -