Quantum Cut Sparsifiers

arXiv:2606.09728 · quant-ph, cs.DS · Submitted 2026-06-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Quantum Cut Sparsifiers".

Kai: The gist In an n-qubit system,

Mira: First, who's behind it and why it matters.

Paper summary: Kai: So, we're looking at this paper called Quantum Cut Sparsifiers. It deals with how to take a complex quantum system description, a Hamiltonian, and make it much smaller without losing the essential physics. The main claim is that for any n-qubit QC Hamiltonian, you can sparsify it down to Oe(n/ε2) terms while keeping the energy of every state within a factor of one plus or minus epsilon <ref:2606.09728#pg1,any n-qubit QC Hamiltonian>.

Mira: That sounds like a big deal because typically, when you simplify things in quantum mechanics, you risk losing critical information about how the system behaves. This paper is specifically focusing on Quantum Cut Hamiltonians, which are these two-local Hamiltonians involving Pauli matrices and edges in some graph G <ref:2606.09728#pg2>.

Lev: So what's the actual result? Does this mean we can actually build smaller quantum circuits that still represent the same physics?

Kai: Exactly, Lev. The main result establishes that a sparsifier Ge exists with Ee <= Oe(n/ε2), and if the graph G is unweighted, you can compute this in near-linear time <ref:2606.09728#pg2>. That's a very efficient way to achieve this size reduction.

Mira: What makes it interesting is that this sampling scheme works for all levels of the Kikuchi graph at once, which the paper connects to the Laplacian of these graphs <ref:2606.09728#pg7>. That's a strong statement about its applicability across different scales.

Kai: And they’re not just talking about abstract graphs; they are showing this works for any graph by using expander decomposition to extend the idea from expanders to all graphs <ref:2606.09728#pg10>. That’s a huge generalization in terms of what systems we can apply this to.

Lev: If we think about running this on real quantum hardware, how does that polynomial bound translate? We're talking about the size of the matrix or the number of terms you have to store.

Kai: The paper addresses that algorithmically with Theorem seven point six, which gives an Oe(m) time algorithm to compute a re-weighted subgraph G' such that the energy is preserved up to a factor of one plus or minus epsilon and E' <= O(n log29(n)/ε2), with probability one minus one/n six <ref:2606.09728#pg24>.

Mira: That is a much better time complexity than what they got from the natural approach of leverage score sampling, which they noted yields a polynomially worse bound because the underlying matrices have dimension ∼ two n <ref:2606.09728#pg2>. So they found a way to beat that initial polynomial hurdle.

Kai: They did. And for weighted graphs, they use a weight-bucketing approach and an edge-moving lemma to get even better complexity, leading to Theorem eight point one zero with E' <= O(n log11(n)/ε2) for weighted cases <ref:2606.09728#pg33>.

Lev: So, if I were trying to implement this on a superconducting processor, would I need an extremely large number of qubits just to handle the decomposition or the sampling process?

Kai: Not necessarily for the core sparsification part. The method relies on decomposing the action of these matrices into invariant subspaces <ref:2606.09728#pg2>, and then using operator-valued inequalities to extend it to all expander graphs <ref:2606.09728#pg6>.

Mira: The underlying theory is quite deep, moving from harmonic analysis on hypercube slices to spectral bounds for expanders <ref:2606.09728#pg15>, which is how they establish the spectral lower bound for QC operators associated with expander graphs. It’s a lot of machinery underpinning that final result.

Lev: For error correction researchers like us, I’m thinking about what this means for fault tolerance. If we can represent these Hamiltonians compactly, it might make simulating larger quantum systems more feasible before we hit the limits of current hardware coherence times.

Kai: It gives us a better handle on the structure of these Hamiltonians <ref:2606.09728#pg5>. The authors also noted that this work provides some insight into relating the non-redundancy of systems of local Hamiltonians to their ultimate sparsifiability <ref:2606.09728#pg5>.

Mira: So, looking at the overall picture of Quantum Cut Sparsifiers, it seems they’ve put together a combination of harmonic decomposition, that operator inequality from Alon and Kozma, and expander decomposition to get this efficient computation for all QC Hamiltonians <ref:2606.09728#pg2>.

Lev: It’s impressive that they managed to prove this holds simultaneously for all level k Kikuchi graphs, which is what Theorem one point five is about <ref:2606.09728#pg7>. That’s a lot of structural rigidity being preserved in the approximation.

Kai: The real implication here is that we can actually find near-optimal sparsifiers for these quantum systems, and the authors show this works with near-linear size quantum cut sparsifiers <ref:2606.09728#pg2>.

Mira: It’s important to remember that the paper states its limitation: they are working on QC Hamiltonians specifically, and while they extend it to all graphs, that extension relies on expander decomposition <ref:2606.09728#pg10>.

Lev: So what's the bigger picture for someone just listening to the show? It means that when you deal with a complex quantum problem described by these local interactions, you have a way to represent it much more compactly using fewer terms without sacrificing accuracy.

Kai: That’s it. The Quantum Cut Sparsifiers paper gives us concrete tools for making these quantum descriptions smaller and faster to handle.

Mira: It shows that even though the underlying structure is complex, there are efficient ways to find a good, small approximation of that structure <ref:2606.09728#pg5>.

Lev: It points toward methods for improving error correction simulations by reducing the complexity of the model itself.

Kai: We’ll stick with this paper as a key piece in understanding how to efficiently manage and compress these types of quantum Hamiltonians moving forward.

Conclusion: Kai: So we're wrapping up on Quantum Cut Sparsifiers and looking at who wrote this stuff, Mira, what do we actually get out of all that work?

Mira: Well, the authors are building on ideas about how these quantum systems behave in a way that connects graph theory with actual quantum states. They take something called a Quantum Cut Hamiltonian and they figure out how to make it much smaller while keeping the physics accurate.

Lev: So, for someone who's thinking about running this on real hardware, what does that compression actually mean in terms of qubit count? Is it just theoretical savings or can we actually build something smaller?

Kai: It means they found a way to represent these Hamiltonians with fewer terms, specifically at a size related to n over epsilon squared. That's the main number they're pointing to for how compact this representation is.

Mira: And the big deal is that this method works for all levels of Kikuchi graphs, which means it’s not just a fluke on one specific structure; it applies across a whole family of related systems.

Lev: That sounds robust, but what about the complexity of finding that sparser version? The paper mentions some algorithms, and I wonder if that’s practical for the kind of noise we actually deal with in experiments.

Kai: They did address that with an algorithm that runs in time related to n log something over epsilon squared. It’s not instantaneous, but it's better than what they found before, which was a polynomial scaling problem because the dimension gets huge.

Mira: So the authors managed to combine these different mathematical tools—harmonic decomposition and those operator inequalities—to achieve this size reduction for all of them simultaneously.

Lev: It’s interesting that they used expander decomposition to get from just expanders to any general graph, which is a big generalization for what kinds of problems we can tackle.

Kai: Exactly, so it shows that these local quantum interactions aren't just restricted to special structures; the sparsification technique has this broad applicability across different graph types.

Mira: It really confirms that you don't need an incredibly complex structure to have a manageable representation of these systems for simulation purposes.

Lev: So, moving forward, I think we need to look at how this structural insight helps us understand the fundamental limits of simulating these quantum states.

Princeton University · UC Berkeley · Harvard University

quant-ph, cs.DS

Submitted: 2026-06-08

Updated: 2026-10-07

Comments: 42 pages, full version of SODA 2027 paper

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 87/100

The gist: The gist In an n-qubit system, any n-qubit QC Hamiltonian can be sparsified to Oe(n/ε2) many terms while preserving the energy of every state up to a factor of 1 ± ε.

Key concepts

Quantum Cut (QC) Hamiltonian
These are specific types of quantum Hamiltonians used in n-qubit systems. They are defined as 2-local, meaning each term involves Pauli matrices and an edge from a graph. The paper focuses on finding ways to simplify these complex Hamiltonians while keeping their energy properties accurate.
Kikuchi Graphs
These graphs provide a combinatorial interpretation for QC Hamiltonians. They are constructed based on sets $S$ and $T$ of equal size, where the symmetric difference between them equals an edge. The QC Hamiltonian is identified as the Laplacian of these Kikuchi graphs, allowing for graph-theoretic analysis.
Sparsification Techniques
The proof combines several advanced mathematical tools. It uses operator-valued inequalities to extend sparsification from expander graphs to general graphs, and expander decomposition to cover all possible graph structures. This combination allows for the construction of efficient sparsifiers.
$\epsilon$-QC Sparsifier
This is a simplified version of the original QC Hamiltonian that has been approximated by a smaller set of terms. The paper aims to create an $\epsilon$-QC sparsifier, meaning the energy calculated from this smaller set is very close to the true energy, within a factor of $1 \pm \epsilon$.

Terminology

Summary

The gist In an n-qubit system, any n-qubit QC Hamiltonian can be sparsified to Oe(n/ε2) many terms while preserving the energy of every state up to a factor of 1 ± ε.

Quantum Cut Sparsifiers

The paper focuses on the sparsifiability of Quantum Cut (QC) Hamiltonians, defined as a 2-local Hamiltonian where each term involves Pauli matrices and an edge in a graph G <ref:2606.09728#pg2>. The goal is to construct an epsilon-Quantum Cut (ε-QC) sparsifier Ge = (V, E, e we) such that for all states ψ⟩ ∈ C 2[n], the energy is preserved up to a factor of 1 ± ε, i.e., (1 − ε)LG ≼ LGe ≼ (1 + ε)LG <ref:2606.09728#pg5>. The main result establishes that such a sparsifier exists with Ee ⩽ Oe(n/ε2), and if G is unweighted, it can be computed in near-linear time <ref:2606.09728#pg2>.

Key Concepts and Tools

The paper introduces the combinatorial interpretation of QC Hamiltonians through Kikuchi graphs, which are defined based on sets S, T ∈ 2[n] being connected if S = T and S ⊕ T = e for an edge e <ref:2606.09728#pg6>. The QC Hamiltonian LG is identified as the Laplacian of the Kikuchi graph KG, and the level k Kikuchi graph KG,k is a restriction of this graph to subsets [n]k <ref:2606.09728#pg7>. The theorem is restated in terms of these graphs as Theorem 1.5 (Kikuchi sparsifiers), stating that there exists a weighted graph H = ([n], E, e we) such that supp(we) ⩽ Oe(ε-2n), and (1 − ε)LKG,k ≼ LKH,k ≼ (1 + ε)LKG,k for all 0 ≤ k ≤ n <ref:2606.09728#pg7>.

Techniques for Sparsification

The proof strategy relies on combining several advanced techniques. The authors note that the natural approach of leverage score sampling yields a polynomially worse bound because the underlying matrices have dimension ∼ 2 n <ref:2606.09728#pg2>. Instead, they decompose the action of these matrices into invariant subspaces <ref:2606.09728#pg2>. They then use an operator-valued inequality of Alon and Kozma [AK20], which builds on an octopus inequality of Caputo, Liggett, and Richthammer [CLR10], to extend the sparsification technique to all expander graphs <ref:2606.09728#pg6>. Finally, they invoke expander decomposition to extend the sparsifier to all graphs <ref:2606.09728#pg8>.

Extension to General Graphs

The generalization from expanders to all graphs is achieved by using expander decomposition, which allows for the decomposition of any graph into pieces that are mild expanders <ref:2606.09728#pg10>. The argument for expanders relies on establishing a new lower bound for the spectrum QC operators associated with expander graphs in terms of (appropriately scaled) the QC operator associated with a complete graph by invoking the Alon-Kozma inequality [AK20] <ref:2606.09728#pg15>. This spectral lower bound suffices for bounding the sum of leverage scores on the i-th eigenspace by ∼ n/i, which is then used to apply matrix concentration inequalities <ref:2606.09728#pg15>.

Algorithmic and Weighted Extensions

The paper addresses algorithmic aspects through Theorem 7.6, which provides an Oe(m) time algorithm that computes a re-weighted subgraph G' such that (1 − ε) · LG ≼ LG' ≼ (1 + ε) · LG and E' ⩽ O(n log29(n)/ε2), with probability 1 − 1/n6 <ref:2606.09728#pg24>. For weighted graphs, the authors use a weight-bucketing approach and an edge-moving lemma to handle edges between components of G <ref:2606.09728#pg9>. This leads to Theorem 8.10, which provides a re-weighted subgraph G' such that (1 − ε) · LG ≼ LG' ≼ (1 + ε) · LG and E' ⩽ O(n log11(n)/ε2), with probability 1 − 1/n6 <ref:2606.09728#pg33>.

Conclusion

The paper concludes by showing how to combine a harmonic decomposition of hypercube slices, a powerful operator inequality of Alon and Kozma, and an expander decomposition framework to efficiently compute near-optimal sparsifiers of all Quantum Cut Hamiltonians <ref:2606.09728#pg2>. This work resolves the question about the smallest possible ε-QC sparsifier for QC Hamiltonians, showing that near-linear size quantum cut sparsifiers indeed exist <ref:2606.09728#pg2>. The methods also provide partial insight into relating the non-redundancy of systems of local Hamiltonians to their ultimate sparsifiability <ref:2606.09728#pg5>.

References

[AF02] David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/ aldous/RWG/book.html <ref:2606.09728#pg9>.

[AGKM23] Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, and Peter Manohar. A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 <ref:2606.09728#pg2>.

[AK20] Gil Alon and Gady Kozma. Comparing with octopi. Ann. Inst. Henri Poincaré Probab. Stat., 56(4):2672–2685, 2020 <ref:2606.09728#pg7>.

[ALM+25] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum maxcut via partially entangled matchings. arXiv preprint arXiv:2504.15276, 2025 <ref:2606.09728#pg2>.

[APS25] Anuj Apte, Ojas Parekh, and James Sud. Conjectured bounds for 2-local hamiltonians via token graphs. ArXiv, abs/2506.03441, 2025 <ref:2606.09728#pg5>.

[AZ19] Dorit Aharonov and Leo Zhou. Hamiltonian sparsification and gap-simulation. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, January 10-12, 2019 <ref:2606.09728#pg3>.

[BBG+20] Aaron Bernstein et al. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432, 2020 <ref:2606.09728#pg7>.

[BBKL26] Ainesh Bakshi et al. Sharp bounds on the eigenvalues of kikuchi graphs and applications to quantum max cut, 2026 <ref:2606.09728#pg2>.

[BBP26] Arpon Basu, Joshua Brakensiek, and Aaron Putterman. Many hamiltonians are sparsifiable, 2026 <ref:2606.09728#pg2>.

[BCK20] Christian Bessiere et al. Chain Length and CSPs Learnable with Few Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1420–1427, April 2020 <ref:2606.09728#pg6>.

[BG25] Joshua Brakensiek and Venkatesan Guruswami. Redundancy is all you need. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1614–1625, New York, NY, USA, 2025 <ref:2606.09728#pg8>.

[BH13] Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum ground states. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 871–880, 2013 <ref:2606.09728#pg2>.

[BHKL25] Arpon Basu et al. Improved lower bounds for all odd query locally decodable codes. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1262–1285, 2025 <ref:2606.09728#pg5>.

[BK96] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n 2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 47–55, New York, NY, USA, 1996 <ref:2606.09728#pg2>.

Improvements for AI systems

  1. A near-linear size quantum cut sparsifier can be computed for unweighted graphs in time O(m log10(m)) with high probability, ensuring that (1 - ε) · LG ≼ LGe ≼ (1 + ε) · LG holds with probability ⩾ 1 − 1/n6.

  2. The system can approximate the maximum energy of a Quantum Cut Hamiltonian by constructing a sparsifier Ge with E' ≤ O(n log29(n)/ε2), which is significantly better than the trivial O(n 2) bound derived from naive importance sampling.

  3. The AI system can compute an (1 ± ε)-Kikuchi sparsifier for any given graph G by decomposing it into expander components and applying Lemma 6.1, achieving a total edge count bounded by X i∈[k] O(n log9(n)/ε2).

  4. The system can handle weighted graphs by employing an edge-moving lemma to aggregate edges between connected components of the original graph G, allowing the sparsifier size to remain near-linear even with high weight variations.

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 /epsilon 2) many terms while preserving the energy of every state up to a factor of 1 plus or minus epsilon. 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 of the sampled graph is a spectral approximation to the Kikuchi graph of G. Importantly, the 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 about 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 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.

Sources

Related papers