Pith. sign in

REVIEW 2 major objections 2 minor 1 cited by

Quantum Cut Sparsifiers

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Any n-qubit Quantum Cut Hamiltonian sparsifies to Õ(n/ε²) terms while preserving the energy of every state up to 1 ± ε.

desk verdict The paper gives a linear-size sparsifier for QC Hamiltonians that works simultaneously for every Kikuchi level via subspace decomposition and Alon-Kozma. read the letter →

arxiv 2606.09728 v1 pith:ICL5JJFR submitted 2026-06-08 quant-ph cs.DS

Arpon Basu , Joshua Brakensiek , Pravesh K. Kothari , Aaron Putterman This is my paper · ORCID
classification quant-phcs.DS
keywords quantumcuthamiltonianssparsificationkikuchigraphsoperatorinequalitiesexpanderdecompositionimportancesampling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that any Quantum Cut Hamiltonian on n qubits reduces to roughly n over epsilon squared terms such that the energy of every quantum state remains within a multiplicative 1 ± ε factor of the original. This sparsification comes from an importance sampling of the edges of the underlying graph that makes the Kikuchi graph at every level spectrally close to the original, using the same sample for all levels. The method decomposes the relevant matrices into invariant subspaces to apply an operator-valued inequality that produces the uniform sampling, then invokes expander decomposition to cover arbitrary graphs.

What carries the argument

Invariant subspace decomposition of the matrices, which lets the Alon-Kozma operator-valued inequality produce a uniform edge sampling that simultaneously approximates the Kikuchi graph at every level.

What would settle it

An n-qubit QC Hamiltonian for which every sparsifier with o(n/ε²) terms fails to keep the energy of some state inside the 1 ± ε factor, or for which no single sampling approximates all Kikuchi levels at once.

Watch

Extended reading notes

Core claim

In an n-qubit system, any n-qubit QC Hamiltonian can be sparsified to Õ(n /ε²) many terms while preserving the energy of every state up to a factor of 1 ± ε. This gives 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, with the same sampling working simultaneously for all ℓ.

Load-bearing premise

Decomposing the matrices into invariant subspaces is sufficient for the Alon-Kozma operator-valued inequality to yield a uniform sampling scheme that works simultaneously for every level ℓ of the Kikuchi graph.

Editorial extensions

If this is right

  • The sparsifier for expander graphs extends to arbitrary graphs via expander decomposition.
  • A single sampling scheme approximates the Kikuchi graph at every level ℓ simultaneously.
  • QC Hamiltonian energies can be approximated using far fewer terms than the original while controlling error for all states.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The result may allow more efficient classical algorithms for approximating energies or ground states in QC models by reducing term count.
  • Similar subspace-based sampling could apply to other quantum Hamiltonians where invariant decompositions are available.
  • The bound suggests a quantum analogue of classical cut sparsifiers, with tightness testable on small explicit QC Hamiltonians.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper claims that any n-qubit Quantum Cut (QC) Hamiltonian can be sparsified to ilde{O}(n/\varepsilon^2) terms while preserving the energy of every state up to a (1 \pm \varepsilon) factor. This is realized by an importance-sampling scheme on the edges of an arbitrary graph G such that the induced Kikuchi graph at every level \ell is a spectral approximation to the original, with the identical sampling distribution working simultaneously for all \ell. The proof proceeds by decomposing the relevant operators into invariant subspaces, applying the Alon-Kozma operator-valued inequality (itself based on the Caputo-Liggett-Richthammer octopus inequality), extending the technique to expander graphs, and finally invoking expander decomposition to handle arbitrary graphs.

Significance. If the result holds, it supplies a near-linear-size sparsifier for QC Hamiltonians that overcomes the exponential dimension barrier faced by standard matrix-concentration methods. The explicit use of invariant-subspace decomposition together with the Alon-Kozma inequality to obtain an \ell-uniform sampling scheme is a technically interesting route that may be useful in other high-dimensional quantum sparsification settings. The paper appropriately credits the external inequalities and the prior Basu-Brakensiek-Putterman line of work.

major comments (2)
  1. [Abstract (approach paragraph)] Abstract, paragraph on the approach: the claim that the invariant-subspace decomposition yields a single sampling distribution whose induced Kikuchi graphs are spectral approximations at every level \ell simultaneously is load-bearing for the main theorem, yet the manuscript does not exhibit that the variance proxies or operator-norm bounds inside the Alon-Kozma inequality remain independent of the particular subspaces that arise at each \ell. If these quantities acquire an \ell-dependent factor, the resulting sampling weights would also depend on \ell, contradicting the uniform guarantee.
  2. [Section describing the expander-decomposition step] The extension via expander decomposition (final step of the argument): it is not shown that the decomposition into expanders preserves the QC Hamiltonian structure or that the energy-preservation factor (1 \pm \varepsilon) carries through the decomposition without an additional logarithmic loss that would affect the ilde{O}(n/\varepsilon^2) bound.
minor comments (2)
  1. [Abstract] The abstract refers to 'QC Hamiltonians' without a self-contained definition; a one-sentence reminder of the precise form (sum of cut terms on the underlying graph) would improve readability.
  2. [Introduction / preliminaries] Notation for the Kikuchi graph at level \ell is introduced without an explicit reference to its adjacency operator; adding a short equation or pointer to the standard definition would clarify the spectral-approximation claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of the result's significance and for the careful reading. We address the two major comments below. Both points identify places where the manuscript's exposition can be strengthened with additional lemmas or details; we will incorporate these clarifications in the revision.

read point-by-point responses

  1. Referee: [Abstract (approach paragraph)] Abstract, paragraph on the approach: the claim that the invariant-subspace decomposition yields a single sampling distribution whose induced Kikuchi graphs are spectral approximations at every level ℓ simultaneously is load-bearing for the main theorem, yet the manuscript does not exhibit that the variance proxies or operator-norm bounds inside the Alon-Kozma inequality remain independent of the particular subspaces that arise at each ℓ. If these quantities acquire an ℓ-dependent factor, the resulting sampling weights would also depend on ℓ, contradicting the uniform guarantee.

    Authors: The referee correctly identifies that uniformity across ℓ is central. In Section 3 the invariant subspaces are the common eigenspaces of the family of Kikuchi operators; because the QC Hamiltonian is a sum of two-qubit terms, these subspaces coincide with the weight-ℓ subspaces of the n-qubit space and are therefore independent of the particular graph. The operator-norm bounds supplied to Alon-Kozma are controlled by the maximum degree of G, which is manifestly ℓ-independent. The variance proxies are likewise bounded by the squared ℓ-norm of the edge indicators, again independent of ℓ. We will add an explicit short lemma (new Lemma 3.4) stating these facts and verifying that the sampling distribution produced by the inequality is therefore the same for every ℓ. revision: yes

  2. Referee: [Section describing the expander-decomposition step] The extension via expander decomposition (final step of the argument): it is not shown that the decomposition into expanders preserves the QC Hamiltonian structure or that the energy-preservation factor (1 ± ε) carries through the decomposition without an additional logarithmic loss that would affect the ᵏ(n/ε^{2}) bound.

    Authors: The underlying graph decomposition is performed on the support graph G before any sampling; each expander component inherits the same two-qubit interaction structure, so the resulting Hamiltonians remain QC. The (1 ± ε) guarantee is multiplicative. Because the same sampling distribution is used on every component and the number of components in a standard expander decomposition is O(log n), a union bound over components contributes only an extra log n factor inside the ᵏ notation; the leading n/ε^{2} term is unaffected. The current sketch in Section 4 is too terse on error propagation. We will expand the section with a short paragraph and a reference to the standard decomposition lemma (e.g., Spielman-Teng) to make the preservation and the absence of an extra non-tilde logarithmic loss explicit. revision: yes

Circularity Check

0 steps flagged · score 2.0 of 10

Minor self-citation to prior work by subset of authors; derivation relies on external inequalities

full rationale

The paper continues prior work by three of the four authors but invokes the Alon-Kozma operator-valued inequality (external, 2020), the Caputo-Liggett-Richthammer octopus inequality (external), and expander decomposition as the load-bearing tools for obtaining a single sampling distribution that works uniformly across all Kikuchi levels ℓ. No equation or claim in the provided text reduces the Õ(n/ε²) bound or the simultaneous approximation guarantee to a fitted parameter, a self-defined quantity, or a self-citation chain. The invariant-subspace decomposition is presented as enabling the application of the external inequality rather than as a tautological re-statement of the target result.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The result rests on standard mathematical tools rather than new postulates; no free parameters or invented entities are introduced in the abstract.

assumptions (3)
  • standard math Operator-valued inequality of Alon and Kozma (Ann. Henri Poincaré, 2020)
    Invoked to extend the sparsification from subspaces to expander graphs.
  • standard math Octopus inequality of Caputo, Liggett, and Richthammer (J. AMS, 2010)
    Underlying the Alon-Kozma inequality used in the proof.
  • standard math Expander decomposition theorem for graphs
    Used to lift the expander case to arbitrary graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Cut Sparsifiers." pith.science (2026). https://pith.science/paper/ICL5JJFR

@misc{pith2026260609728,
  author       = {Pith},
  title        = {Pith review of: Quantum Cut Sparsifiers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ICL5JJFR}},
  note         = {Machine review of arXiv:2606.09728}
}
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\'e, 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Sharp Bounds on Ground State Energy of the SYK Model

    quant-ph 2026-07 accept novelty 7.5 of 10

    For super-constant k = o(√n), the expected operator norm of the k-SYK Hamiltonian equals (1−o(1))√(2n)/k, via a twisted-boson operator whose moments match SYK trace moments exactly.

Reference graph

Works this paper leans on

157 extracted references · 90 canonical work pages · cited by 1 Pith paper

  1. [1]

    Physical Review A , volume=

    Good quantum error-correcting codes exist , author=. Physical Review A , volume=. 1996 , publisher=

    1996

  2. [2]

    Proceedings of the Royal Society of London

    Multiple-particle interference and quantum error correction , author=. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , volume=. 1996 , publisher=

    1996

  3. [3]

    Breuckmann and Chinmay Nirkhe , editor =

    Anurag Anshu and Nikolas P. Breuckmann and Chinmay Nirkhe , editor =. Proceedings of the 55th Annual. 2023 , url =. doi:10.1145/3564246.3585114 , timestamp =

    work page doi:10.1145/3564246.3585114 2023

  4. [4]

    2002 , PAGES =

    Lang, Serge , TITLE =. 2002 , PAGES =. doi:10.1007/978-1-4613-0041-0 , URL =

    work page doi:10.1007/978-1-4613-0041-0 2002

  5. [5]

    Hamiltonian Sparsification and Gap-Simulation , booktitle =

    Dorit Aharonov and Leo Zhou , editor =. Hamiltonian Sparsification and Gap-Simulation , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.ITCS.2019.2 , timestamp =

    work page doi:10.4230/lipics.itcs.2019.2 2019

  6. [6]

    doi:10.22331/q-2019-09-30-189 , url =

    The complexity of simulating local measurements on quantum systems , author =. doi:10.22331/q-2019-09-30-189 , url =

    work page doi:10.22331/q-2019-09-30-189 2019

  7. [7]

    Annales Henri Poincar

    Translationally Invariant Universal Quantum Hamiltonians in 1D , author=. Annales Henri Poincar. 2020 , volume=

    2020

  8. [9]

    Quantum Inf

    Itai Arad , title =. Quantum Inf. Comput. , volume =. 2011 , url =. doi:10.26421/QIC11.11-12-10 , timestamp =

    work page doi:10.26421/qic11.11-12-10 2011

Show all 157 references
  1. [10]

    Hastings , title =

    Matthew B. Hastings , title =. 48th International Colloquium on Automata, Languages, and Programming,. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.102 , timestamp =

    2021 doi

  2. [11]

    2013 , url =

    Dorit Aharonov and Itai Arad and Thomas Vidick , title =. 2013 , url =. doi:10.1145/2491533.2491549 , timestamp =

    2013 doi

  3. [12]

    npj Quantum Information , volume=

    Hamiltonian simulation in the low-energy subspace , author=. npj Quantum Information , volume=. 2021 , publisher=

    2021

  4. [13]

    Quantum , volume=

    Hamiltonian simulation for low-energy states with optimal time dependence , author=. Quantum , volume=. 2024 , publisher=

    2024

  5. [14]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Expander decomposition and pruning: Faster, stronger, and simpler , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  6. [15]

    arXiv preprint arXiv:2603.24530 , year=

    Fault-Tolerant Distance Oracles Below the n f Barrier , author=. arXiv preprint arXiv:2603.24530 , year=

  7. [16]

    arXiv preprint arXiv:2004.08432 , year=

    Fully-dynamic graph sparsifiers against an adaptive adversary , author=. arXiv preprint arXiv:2004.08432 , year=

    2004

  8. [17]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Online discrepancy with recourse for vectors and graphs , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  9. [18]

    arXiv preprint arXiv:2102.02991 , year=

    Strongly universal Hamiltonian simulators , author=. arXiv preprint arXiv:2102.02991 , year=

  10. [19]

    Reservoir-sampling algorithms of time complexity o (n (1+ log (

    Li, Kim-Hung , journal=. Reservoir-sampling algorithms of time complexity o (n (1+ log (. 1994 , publisher=

    1994

  11. [20]

    Physical Review A—Atomic, Molecular, and Optical Physics , volume=

    Quantum-Merlin-Arthur--complete problems for stoquastic Hamiltonians and Markov matrices , author=. Physical Review A—Atomic, Molecular, and Optical Physics , volume=. 2010 , publisher=

    2010

  12. [21]

    John Kallaugher and Ojas Parekh , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00054 , timestamp =

    2022 doi

  13. [22]

    Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =

    Jean Bourgain and Alex Gamburd , journal =. Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =

  14. [23]

    Gross , title =

    Jonathan L. Gross , title =. Journal of Combinatorial Theory, Series B , volume =. 1977 , doi =

    1977

  15. [24]

    Silva, Marcel Kenji de Carli and Harvey, Nicholas J. A. and Sato, Cristiane M. , title =. 2016 , url =. doi:10.1145/2746241 , timestamp =

    2016 doi

  16. [25]

    Journal of Combinatorial Theory, Series A , volume =

    Ervin Gergely , title =. Journal of Combinatorial Theory, Series A , volume =. 1974 , doi =

    1974

  17. [26]

    1979 , institution=

    New results on the independence number , author=. 1979 , institution=

    1979

  18. [27]

    1981 , publisher=

    A lower bound on the stability number of a simple graph , author=. 1981 , publisher=

    1981

  19. [28]

    2015 , volume =

    Foundations and Trends® in Machine Learning , title =. 2015 , volume =. doi:10.1561/2200000048 , issn =

    2015 doi

  20. [29]

    1986 , isbn =

    Chew, P , title =. 1986 , isbn =. doi:10.1145/10515.10534 , booktitle =

    1986 doi

  21. [30]

    Approximating s-t minimum cuts in \

    Bencz\'. Approximating s-t minimum cuts in \. 1996 , isbn =. doi:10.1145/237814.237827 , booktitle =

    1996 doi

  22. [31]

    and Teng, Shang-Hua , title =

    Spielman, Daniel A. and Teng, Shang-Hua , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  23. [32]

    and Srivastava, Nikhil , title =

    Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  24. [33]

    and Srivastava, Nikhil , title =

    Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Review , volume =. 2014 , doi =

    2014

  25. [34]

    Code sparsification and its applications , booktitle =

    Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , editor =. Code sparsification and its applications , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.185 , timestamp =

    2024 doi

  26. [35]

    Annals of Mathematics , volume =

    Assaf Naor and Robert Young , title =. Annals of Mathematics , volume =. 2018 , doi =

    2018

  27. [36]

    2025 , isbn =

    Chang, Alan and Naor, Assaf and Ren, Kevin , title =. 2025 , isbn =. doi:10.1145/3717823.3718285 , booktitle =

    2025 doi

  28. [37]

    and Meka, Raghu , title =

    Kane, Daniel M. and Meka, Raghu , title =. 2013 , isbn =. doi:10.1145/2488608.2488610 , booktitle =

    2013 doi

  29. [38]

    2002 , issue_date =

    Feige, Uriel and Schechtman, Gideon , title =. 2002 , issue_date =. doi:10.1002/rsa.10036 , journal =

    2002 doi

  30. [39]

    2021 , month =

    Luca Trevisan , title =. 2021 , month =

    2021

  31. [40]

    2025 , archivePrefix=

    Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs , author=. 2025 , archivePrefix=

    2025

  32. [41]

    Spielman , title =

    Daniel A. Spielman , title =. 2019 , url =

    2019

  33. [42]

    Nilli , abstract =

    A. Nilli , abstract =. On the second eigenvalue of a graph , journal =. 1991 , issn =. doi:https://doi.org/10.1016/0012-365X(91)90112-F , url =

    1991 doi

  34. [43]

    and Spielman, Daniel A

    Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. Ann. of Math. (2) , FJOURNAL =. 2015 , NUMBER =

    2015

  35. [44]

    2015 , isbn =

    Allen-Zhu, Zeyuan and Liao, Zhenyu and Orecchia, Lorenzo , title =. 2015 , isbn =. doi:10.1145/2746539.2746610 , booktitle =

    2015 doi

  36. [45]

    An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =

    Nikhil Srivastava and Luca Trevisan , editor =. An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.85 , timestamp =

    2018 doi

  37. [46]

    Electronic Journal of Combinatorics , volume =

    Alexandr Polyanskii and Rinat Sadykov , title =. Electronic Journal of Combinatorics , volume =. 2024 , doi =

    2024

  38. [47]

    2018 , archivePrefix=

    Hyperbolic polynomials and the Kadison-Singer problem , author =. 2018 , archivePrefix=

    2018

  39. [48]

    , booktitle=

    Cohen, Michael B. , booktitle=. Ramanujan Graphs in Polynomial Time , year=

  40. [49]

    Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =

    Improved bounds in Weaver and Feichtinger conjectures , author =. Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =. 2019 , lastchecked =

    2019

  41. [50]

    Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =

    Zhiqiang Xu and Zili Xu and Ziheng Zhu , keywords =. Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jfa.2023.109978 , url =

    2023 doi

  42. [51]

    , title =

    Cohen, Michael B. , title =. 2016 , howpublished =

    2016

  43. [52]

    2012 , URL =

    Why is the minimum size of a generating set for a finite group at most _2 n ? , AUTHOR =. 2012 , URL =

    2012

  44. [53]

    2024 , archivePrefix=

    Selector form of Weaver's conjecture, Feichtinger's conjecture, and frame sparsification , author=. 2024 , archivePrefix=

    2024

  45. [54]

    2024 , url =

    Surya Teja Gavva and Peng Zhang , title =. 2024 , url =

    2024

  46. [55]

    Proceedings of the London Mathematical Society , volume =

    Alon, Noga and Bucić, Matija and Sauermann, Lisa and Zakharov, Dmitrii and Zamir, Or , title =. Proceedings of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/plms.70044 , url =

    doi

  47. [56]

    How Abelian is a Finite Group? , booktitle =

    L\'aszl\'o Pyber , editor =. How Abelian is a Finite Group? , booktitle =. 1997 , pages =. doi:10.1007/978-3-642-60408-9_27 , isbn =

    1997 doi

  48. [57]

    Information Theory

    Ash, Robert. Information Theory

  49. [58]

    1994 , issn =

    Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q , journal =. 1994 , issn =. doi:https://doi.org/10.1006/jctb.1994.1054 , url =

    1994 doi

  50. [59]

    G. A. Margulis , title =. Problemy Peredachi Informacii , volume =. 1973 , mrnumber =

    1973

  51. [60]

    Lubotzky and R

    A. Lubotzky and R. Phillips and P. Sarnak , title =. Combinatorica , volume =. 1988 , mrnumber =

    1988

  52. [61]

    Combinatorics, Probability and Computing , author=

    Quasirandom Groups , volume=. Combinatorics, Probability and Computing , author=. 2008 , pages=. doi:10.1017/S0963548307008826 , number=

    2008 doi

  53. [62]

    2025 , isbn =

    Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , title =. 2025 , isbn =. doi:10.1145/3717823.3718205 , booktitle =

    2025 doi

  54. [63]

    2025 , isbn =

    Brakensiek, Joshua and Guruswami, Venkatesan , title =. 2025 , isbn =. doi:10.1145/3717823.3718212 , booktitle =

    2025 doi

  55. [64]

    Sparsifying Cayley Graphs on Every Group , booktitle =

    Jun. Sparsifying Cayley Graphs on Every Group , booktitle =. 2026 , url =. doi:10.1137/1.9781611978971.215 , timestamp =

    2026 doi

  56. [65]

    Lee , editor =

    James R. Lee , editor =. Spectral Hypergraph Sparsification via Chaining , booktitle =. 2023 , url =. doi:10.1145/3564246.3585165 , timestamp =

    2023 doi

  57. [66]

    Liu and Aaron Sidford , editor =

    Arun Jambulapati and Yang P. Liu and Aaron Sidford , editor =. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification , booktitle =. 2023 , url =. doi:10.1145/3564246.3585136 , timestamp =

    2023 doi

  58. [67]

    Kothari and Yang P

    Arpon Basu and Pravesh K. Kothari and Yang P. Liu and Raghu Meka , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611978971.216 , URL =

    2026 doi

  59. [68]

    Karger , editor =

    David R. Karger , editor =. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm , booktitle =. 1993 , url =

    1993

  60. [69]

    A Theory of Spectral

    Sanjeev Khanna and Aaron Putterman and Madhu Sudan , editor =. A Theory of Spectral. 52nd International Colloquium on Automata, Languages, and Programming,. 2025 , url =. doi:10.4230/LIPIcs.ICALP.2025.107 , timestamp =

    2025 doi

  61. [70]

    2017 , url =

    Arnold Filtser and Robert Krauthgamer , title =. 2017 , url =. doi:10.1137/15M1046186 , timestamp =

    2017 doi

  62. [71]

    On Fully Dynamic Graph Sparsifiers , booktitle =

    Ittai Abraham and David Durfee and Ioannis Koutis and Sebastian Krinninger and Richard Peng , editor =. On Fully Dynamic Graph Sparsifiers , booktitle =. 2016 , url =. doi:10.1109/FOCS.2016.44 , timestamp =

    2016 doi

  63. [72]

    Benson and Jon M

    Nate Veldt and Austin R. Benson and Jon M. Kleinberg , title =. 2022 , url =. doi:10.1137/20m1321048 , timestamp =

    2022 doi

  64. [73]

    Sketching Cuts in Graphs and Hypergraphs , booktitle =

    Dmitry Kogan and Robert Krauthgamer , editor =. Sketching Cuts in Graphs and Hypergraphs , booktitle =. 2015 , url =. doi:10.1145/2688073.2688093 , timestamp =

    2015 doi

  65. [74]

    Spectral Sparsification of Hypergraphs , booktitle =

    Tasuku Soma and Yuichi Yoshida , editor =. Spectral Sparsification of Hypergraphs , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.159 , timestamp =

    2019 doi

  66. [75]

    Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00114 , timestamp =

    2021 doi

  67. [76]

    Towards tight bounds for spectral sparsification of hypergraphs , booktitle =

    Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , editor =. Towards tight bounds for spectral sparsification of hypergraphs , booktitle =. 2021 , url =. doi:10.1145/3406325.3451061 , timestamp =

    2021 doi

  68. [77]

    Sanjeev Khanna and Aaron Putterman and Madhu Sudan , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00105 , timestamp =

    2024 doi

  69. [78]

    Near-linear Size Hypergraph Cut Sparsifiers , booktitle =

    Yu Chen and Sanjeev Khanna and Ansh Nagda , editor =. Near-linear Size Hypergraph Cut Sparsifiers , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00015 , timestamp =

    2020 doi

  70. [79]

    CoRR , volume =

    Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2508.13345 , eprinttype =

    2025 doi

  71. [80]

    Analyzing graph structure via linear measurements , booktitle =

    Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Analyzing graph structure via linear measurements , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.40 , timestamp =

    2012 doi

  72. [81]

    Graph sketches: sparsification, spanners, and subgraphs , booktitle =

    Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Graph sketches: sparsification, spanners, and subgraphs , booktitle =. 2012 , url =. doi:10.1145/2213556.2213560 , timestamp =

    2012 doi

  73. [82]

    Sparsification of Directed Graphs via Cut Balance , booktitle =

    Ruoxu Cen and Yu Cheng and Debmalya Panigrahi and Kevin Sun , editor =. Sparsification of Directed Graphs via Cut Balance , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ICALP.2021.45 , timestamp =

    2021 doi

  74. [83]

    and Panigrahi, Debmalya , title =

    Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993647 , abstract =

    2011 doi

  75. [84]

    Sparsification of

    Butti, Silvia and. Sparsification of. 2020 , month = jan, journal =

    2020

  76. [85]

    On Redundancy in Constraint Satisfaction Problems , booktitle =

    Cl. On Redundancy in Constraint Satisfaction Problems , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.CP.2022.11 , timestamp =

    2022 doi

  77. [86]

    Joshua Brakensiek and Venkatesan Guruswami and Bart M. P. Jansen and Victor Lagerkvist and Magnus Wahlstr. The Richness of. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2507.07942 , eprinttype =

    2025 doi

  78. [87]

    Chen, Hubie and Jansen, Bart M. P. and Pieterse, Astrid , year =. Best-. Algorithmica , volume =. doi:10.1007/s00453-019-00660-y , langid =

    doi

  79. [88]

    Sparsification of

    Lagerkvist, Victor and Wahlstr. Sparsification of. 2020 , month = jun, journal =. doi:10.1145/3389411 , langid =

    2020 doi

  80. [89]

    Bessiere, Christian and Carbonnel, Cl. Chain. 2020 , month = apr, journal =. doi:10.1609/aaai.v34i02.5499 , copyright =

    2020 doi

  81. [90]

    Constraint Acquisition via Partial Queries , booktitle =

    Christian Bessiere and Remi Coletta and Emmanuel Hebrard and George Katsirelos and Nadjib Lazaar and Nina Narodytska and Claude. Constraint Acquisition via Partial Queries , booktitle =. 2013 , url =

    2013

  82. [91]

    Optimal Lower Bounds for Sketching Graph Cuts , booktitle =

    Charles Carlson and Alexandra Kolla and Nikhil Srivastava and Luca Trevisan , editor =. Optimal Lower Bounds for Sketching Graph Cuts , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.158 , timestamp =

    2019 doi

  83. [92]

    Bart M. P. Jansen and Astrid Pieterse , title =. 2019 , url =. doi:10.1145/3349618 , timestamp =

    2019 doi

  84. [93]

    Satisfiability

    Dell, Holger and van Melkebeek, Dieter , year =. Satisfiability. J. ACM , volume =

  85. [94]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=. 2026 , doi=

    2026

  86. [95]

    2026 , archivePrefix=

    Classification of Non-redundancy of Boolean Predicates of Arity 4 , author=. 2026 , archivePrefix=

    2026

  87. [96]

    Whiston, Julius , TITLE =. J. Algebra , FJOURNAL =. 2000 , NUMBER =. doi:10.1006/jabr.2000.8399 , URL =

    2000 doi

  88. [97]

    Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =

    Thomas Schiex and H. Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =. 1995 , url =

    1995

  89. [98]

    1965 , publisher=

    Analytic Functions of Several Complex Variables , author=. 1965 , publisher=

    1965

  90. [99]

    Morampudi and Chris R

    Or Sattath and Siddhardh C. Morampudi and Chris R. Laumann and Roderich Moessner , title =. Proceedings of the National Academy of Sciences , volume =. 2016 , doi =

    2016

  91. [100]

    Communications in Mathematical Physics , volume=

    Stability of frustration-free Hamiltonians , author=. Communications in Mathematical Physics , volume=. 2013 , publisher=

    2013

  92. [101]

    Quantum Hamiltonian complexity and the detectability lemma , author=

  93. [102]

    arXiv preprint arXiv:2003.14394 , year=

    Beyond product state approximations for a quantum analogue of max cut , author=. arXiv preprint arXiv:2003.14394 , year=

    2003

  94. [103]

    arXiv preprint arXiv:2504.15276 , year=

    Improved algorithms for quantum maxcut via partially entangled matchings , author=. arXiv preprint arXiv:2504.15276 , year=

  95. [104]

    Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    Product-state approximations to quantum ground states , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

  96. [105]

    arXiv preprint arXiv:1909.08846 , year=

    Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut , author=. arXiv preprint arXiv:1909.08846 , year=

    1909

  97. [106]

    arXiv preprint arXiv:2504.11120 , year=

    Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs , author=. arXiv preprint arXiv:2504.11120 , year=

  98. [107]

    arXiv preprint arXiv:2411.04120 , year=

    Second order cone relaxations for quantum Max Cut , author=. arXiv preprint arXiv:2411.04120 , year=

  99. [108]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  100. [109]

    Quantum , volume=

    An improved approximation algorithm for quantum max-cut on triangle-free graphs , author=. Quantum , volume=. 2023 , publisher=

    2023

  101. [110]

    arXiv preprint arXiv:2401.03616 , year=

    An improved Quantum Max Cut approximation via matching , author=. arXiv preprint arXiv:2401.03616 , year=

  102. [111]

    arXiv preprint arXiv:2510.07995 , year=

    Quantum Max-Cut is NP hard to approximate , author=. arXiv preprint arXiv:2510.07995 , year=

  103. [112]

    arXiv preprint arXiv:2206.08342 , year=

    An optimal product-state approximation for 2-local quantum Hamiltonians with positive terms , author=. arXiv preprint arXiv:2206.08342 , year=

  104. [113]

    Cross disciplinary advances in quantum computing , SERIES =

    Bravyi, Sergey , TITLE =. Cross disciplinary advances in quantum computing , SERIES =. 2011 , ISBN =. doi:10.1090/conm/536/10552 , URL =

    2011 doi

  105. [114]

    Niel de Beaudrap and Sevag Gharibian , editor =

    J. Niel de Beaudrap and Sevag Gharibian , editor =. A Linear Time Algorithm for Quantum 2-SAT , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.CCC.2016.27 , timestamp =

    2016 doi

  106. [115]

    2016 , url =

    David Gosset and Daniel Nagaj , title =. 2016 , url =. doi:10.1137/140957056 , timestamp =

    2016 doi

  107. [116]

    Quantum Inf

    Stephen Piddock and Ashley Montanaro , title =. Quantum Inf. Comput. , volume =. 2017 , url =. doi:10.26421/QIC17.7-8-6 , timestamp =

    2017 doi

  108. [117]

    Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =

    Yeongwoo Hwang and Joe Neeman and Ojas Parekh and Kevin Thompson and John Wright , editor =. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.ch48 , timestamp =

    2023 doi

  109. [118]

    CoRR , volume =

    Stephen Piddock , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2510.07995 , eprinttype =

    2025 doi

  110. [119]

    Cubitt and Ashley Montanaro , title =

    Toby S. Cubitt and Ashley Montanaro , title =. 2016 , url =. doi:10.1137/140998287 , timestamp =

    2016 doi

  111. [120]

    Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =

    Sevag Gharibian and Ojas Parekh , editor =. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.31 , timestamp =

    2019 doi

  112. [121]

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=

    Filmus, Yuval , year=. An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=. The Electronic Journal of Combinatorics , publisher=. doi:10.37236/4567 , number=

    doi

  113. [122]

    Alon, Gil and Kozma, Gady , TITLE =. Ann. Inst. Henri Poincar\'. 2020 , NUMBER =. doi:10.1214/20-AIHP1054 , URL =

    2020 doi

  114. [123]

    and Richthammer, Thomas , TITLE =

    Caputo, Pietro and Liggett, Thomas M. and Richthammer, Thomas , TITLE =. J. Amer. Math. Soc. , FJOURNAL =. 2010 , NUMBER =. doi:10.1090/S0894-0347-10-00659-4 , URL =

    2010 doi

  115. [124]

    and Peres, Yuval , TITLE =

    Morris, B. and Peres, Yuval , TITLE =. Probab. Theory Related Fields , FJOURNAL =. 2005 , NUMBER =. doi:10.1007/s00440-005-0434-7 , URL =

    2005 doi

  116. [125]

    Dunkl , journal =

    Charles F. Dunkl , journal =. A Krawtchouk Polynomial Addition Theorem and Wreath Products of Symmetric Groups , urldate =

  117. [126]

    Combinatorica , year =

    Dikstein, Yotam and Dinur, Irit and Filmus, Yuval and Harsha, Prahladh , title =. Combinatorica , year =. doi:10.1007/s00493-024-00084-5 , url =

    doi

  118. [127]

    2010 , url =

    Chris Godsil , title =. 2010 , url =

    2010

  119. [128]

    2026 , eprint=

    Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut , author=. 2026 , eprint=

    2026

  120. [129]

    , title =

    Grigoriev, D. , title =. computational complexity , year =. doi:10.1007/s00037-001-8192-0 , url =

    doi

  121. [130]

    2026 , eprint=

    Many Hamiltonians Are Sparsifiable , author=. 2026 , eprint=

    2026

  122. [131]

    Diaconis, Persi and Shahshahani, Mehrdad , TITLE =. Z. Wahrsch. Verw. Gebiete , FJOURNAL =. 1981 , NUMBER =. doi:10.1007/BF00535487 , URL =

    1981 doi

  123. [132]

    Diaconis, Persi and Saloff-Coste, Laurent , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 1993 , NUMBER =

    1993

  124. [133]

    and Peres, Yuval and Wilmer, Elizabeth L

    Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L. , TITLE =. 2009 , PAGES =. doi:10.1090/mbk/058 , URL =

    2009 doi

  125. [134]

    and Odlyzko, A

    Flatto, L. and Odlyzko, A. M. and Wales, D. B. , TITLE =. Ann. Probab. , FJOURNAL =. 1985 , NUMBER =

    1985

  126. [135]

    Cesi, Filippo , TITLE =. J. Algebraic Combin. , FJOURNAL =. 2010 , NUMBER =. doi:10.1007/s10801-009-0208-x , URL =

    2010 doi

  127. [136]

    Handjani, Shirin and Jungreis, Douglas , TITLE =. J. Theoret. Probab. , FJOURNAL =. 1996 , NUMBER =. doi:10.1007/BF02214260 , URL =

    1996 doi

  128. [137]

    , TITLE =

    Chen, Joe P. , TITLE =. Electron. Commun. Probab. , FJOURNAL =. 2017 , PAGES =. doi:10.1214/17-ECP82 , URL =

    2017 doi

  129. [138]

    Alon, Gil and Kozma, Gady and Puder, Doron , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 2025 , NUMBER =. doi:10.1017/S0305004125000179 , URL =

    2025 doi

  130. [139]

    and Manohar, Peter , title =

    Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter , title =. 2022 , isbn =. doi:10.1145/3519935.3519955 , booktitle =

    2022 doi

  131. [140]

    Kothari and Sidhanth Mohanty , title =

    Jun-Ting Hsieh and Pravesh K. Kothari and Sidhanth Mohanty , title =. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611977554.ch89 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch89 , year =

    2023 doi

  132. [141]

    Kothari and Peter Manohar , title =

    Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the 55th Annual

  133. [142]

    Kothari and Peter Manohar , title =

    Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the 56th Annual

  134. [143]

    and Lin, Andrew D

    Basu, Arpon and Hsieh, Jun-Ting and Kothari, Pravesh K. and Lin, Andrew D. , booktitle=. Improved Lower Bounds for all Odd-Query Locally Decodable Codes , year=

  135. [144]

    2025 , pages =

    Janzer, Oliver and Manohar, Peter , booktitle =. 2025 , pages =. doi:10.1109/FOCS63196.2025.00009 , url =

    2025 doi

  136. [145]

    2025 , issue_date =

    Wein, Alexander and El Alaoui, Ahmed and Moore, Cristopher , title =. 2025 , issue_date =. doi:10.1145/3762806 , articleno =

    2025 doi

  137. [146]

    Stronger Cell Probe Lower Bounds via Local PRGs , year=

    Korten, Oliver and Pitassi, Toniann and Impagliazzo, Russell , booktitle=. Stronger Cell Probe Lower Bounds via Local PRGs , year=

  138. [147]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Venkatesan Guruswami and Xin Lyu and Weiqiang Yuan , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611978971.17 , year =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611978971.17 , abstract =

    2026 doi

  139. [148]

    ArXiv , year=

    Conjectured Bounds for 2-Local Hamiltonians via Token Graphs , author=. ArXiv , year=

  140. [149]

    2026 , eprint=

    Aldous-type Spectral Gaps in Unitary Groups , author=. 2026 , eprint=

    2026

  141. [150]

    Spielman , title =

    Daniel A. Spielman , title =. 2025 , url =

    2025

  142. [151]

    2002 , NOTE =

    Aldous, David and Fill, James Allen , TITLE =. 2002 , NOTE =

    2002

  143. [152]

    Stanley , journal =

    Richard P. Stanley , journal =. Differential Posets , volume =. 1988 , url =

    1988

  144. [153]

    Feige, Uriel , booktitle=

  145. [154]

    Allen and Ryan O'Donnell and David Witmer , title =

    Sarah R. Allen and Ryan O'Donnell and David Witmer , title =

  146. [155]

    Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer , title =

    Pravesh K. Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer , title =. Proceedings of the 49th Annual

  147. [156]

    Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold , booktitle =

    Venkatesan Guruswami and Jun. Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold , booktitle =

  148. [157]

    Lin and Peter Manohar , year=

    Arpon Basu and Jun-Ting Hsieh and Andrew D. Lin and Peter Manohar , year=. Solving Random Planted CSPs below the n^. 2507.10833 , archivePrefix=

  149. [158]

    Kothari , title =

    Pravesh K. Kothari , title =. Private Communication , year =

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.