{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2606.09728",
  "author_total": 4,
  "authors": [
    {
      "name": "Arpon Basu"
    },
    {
      "name": "Joshua Brakensiek"
    },
    {
      "name": "Pravesh K. Kothari"
    },
    {
      "name": "Aaron Putterman"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6d6m9r5a2b5hx.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2606.09728",
  "fulltext_url": null,
  "id": "6d6m9r5a2b5hx",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2606.09728",
  "language": null,
  "licence": "CC-BY-SA-4.0",
  "licence_label": "CC BY-SA 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-sa/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7163988256",
  "pdf_url": "https://arxiv.org/pdf/2606.09728",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-07",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6d6m9r5a2b5hx.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:53Z",
      "native_id": "2606.09728",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2606.09728"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Quantum Cut Sparsifiers",
  "title_text": "Quantum Cut Sparsifiers",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:53Z",
  "url": "https://research.draconitic.com/paper/6d6m9r5a2b5hx",
  "venue": "arXiv",
  "versions": []
}