Pith. sign in

REVIEW 1 minor 4 cited by

The maximum eigenvalue of the Laplacian of any level-k Kikuchi graph is at most m+k for a graph with m edges.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-30 20:26 UTC pith:DCVVTNSZ

load-bearing objection The paper proves the conjectured max-eigenvalue bound on level-k Kikuchi graphs and plugs it into QMC/XY approximation algorithms.

arxiv 2605.14994 v1 pith:DCVVTNSZ submitted 2026-05-14 quant-ph cs.DSmath.CO

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Ainesh Bakshi , Arpon Basu , Pravesh Kothari , Anqi Li This is my paper
classification quant-ph cs.DSmath.CO
keywords Kikuchi graphsLaplacian eigenvaluesQuantum Max Cutapproximation algorithmsXY Hamiltonianeigenvalue boundsproduct states
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves an upper bound of m+k on the largest eigenvalue of both signed and unsigned Laplacians of level-k Kikuchi graphs built from any m-edge graph. This bound confirms four recent conjectures and directly implies that one- and two-qubit product states achieve approximation ratios of 5/8 for Quantum Max Cut and 5/7 for the XY Hamiltonian. When combined with existing algorithmic techniques, the same bound produces polynomial-time algorithms with ratios 0.614 and 0.674 respectively. The result also yields modest progress on Brouwer's conjecture and a tighter bound on the sum of the top-k Laplacian eigenvalues.

Core claim

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level k Kikuchi graph of any graph G with m edges is at most m+k. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of 5/8 for Quantum Max Cut and 5/7 for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of 0.614 for Quantum Max Cut and 0.674 for the XY Hamiltonian.

What carries the argument

The level-k Kikuchi graph on an input graph G, whose Laplacian eigenvalues are bounded by a combinatorial counting argument that caps the largest one at m+k.

Load-bearing premise

The specific Kikuchi graphs that arise from Quantum Max Cut and XY instances meet the general conditions under which the m+k eigenvalue bound holds.

What would settle it

Exhibit any graph G with m edges and any k such that the largest eigenvalue of its level-k Kikuchi graph Laplacian exceeds m+k.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Tensor products of one- and two-qubit product states achieve a 5/8 approximation ratio for Quantum Max Cut.
  • The same states achieve a 5/7 approximation ratio for the XY Hamiltonian.
  • Polynomial-time algorithms reach approximation ratios 0.614 for Quantum Max Cut and 0.674 for the XY Hamiltonian.
  • A new upper bound holds on the sum of the top-k eigenvalues of any graph Laplacian, improving Lew's earlier result.
  • Modest progress is made toward Brouwer's conjecture on Laplacian eigenvalues.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The m+k bound may extend to other families of hypergraph or higher-order Laplacians that share the same edge-counting structure.
  • Similar eigenvalue control could improve approximation guarantees for additional two-local Hamiltonians beyond the XY and Max-Cut cases.
  • The proof technique might yield explicit constructions or counter-examples for related spectral conjectures on signed graphs.

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

0 major / 1 minor

Summary. The paper establishes that the maximum eigenvalue of both the signed and unsigned Laplacian of the level-k Kikuchi graph of any graph G with m edges is bounded above by m + k. This result confirms four conjectures by Apte, Parekh, and Sud. Applications include approximation ratios of 5/8 for Quantum Max Cut and 5/7 for the XY Hamiltonian using tensor products of product states, as well as improved ratios of 0.614 and 0.674 when combined with existing algorithms. The paper also reports modest progress on Brouwer's conjecture and an improvement to Lew's bound on the sum of the top-k eigenvalues of the graph Laplacian.

Significance. This provides a sharp and general bound on the eigenvalues of Kikuchi graphs, which directly yields improved approximation guarantees for Quantum Max Cut and the XY Hamiltonian. The result is significant because it applies to arbitrary graphs, thereby resolving the conjectures and enabling the algorithmic improvements without requiring special structure in the input graphs.

minor comments (1)
  1. [Abstract] Abstract: the claim that the approximation ratios follow directly from the main theorem would be strengthened by a one-sentence clarification that the Kikuchi graphs arising from the QMC/XY instances are constructed with exactly m edges matching the original graph (no inflation), consistent with the 'any G' hypothesis of the bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, accurate summary of our contributions, and recommendation for minor revision. The report correctly identifies the key result (sharp eigenvalue bounds of m+k for level-k Kikuchi graphs) and its applications to approximation algorithms for Quantum Max Cut and the XY Hamiltonian.

Circularity Check

0 steps flagged

No circularity: general mathematical proof of eigenvalue bound stands independently

full rationale

The paper's central result is a direct proof that the maximum eigenvalue of the (signed or unsigned) Laplacian of the level-k Kikuchi graph of any graph G with m edges is at most m+k. This is presented as a general theorem confirming external conjectures, with no reduction to fitted parameters, self-definitional constructions, or load-bearing self-citations. Applications to QMC and XY follow by applying the general bound to the relevant instances after stating that those instances satisfy the theorem's conditions; the derivation chain does not collapse to its inputs by construction. The paper is self-contained as a mathematical argument against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only, limited information on assumptions. The central claim rests on the standard mathematical definition of Kikuchi graphs and the validity of the conjectures being confirmed. No free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Standard definition of level-k Kikuchi graphs
    The bound is stated for these graphs, assuming the common definition in the literature.

pith-pipeline@v0.9.1-grok · 5697 in / 1117 out tokens · 43557 ms · 2026-06-30T20:26:48.590436+00:00 · methodology

0 comments
read the original abstract

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

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

  1. Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

    cs.CC 2026-07 conditional novelty 8.0

    Under UGC, MAX-3-CUT and product-state Quantum MAX-CUT are NP-hard to approximate beyond 0.8360 and 0.9563 times optimal, matching the best known algorithms.

  2. A 0.651-approximation to quantum Max Cut via Rydberg atoms

    quant-ph 2026-06 unverdicted novelty 7.0

    Hybrid Rydberg atom plus SDP algorithm achieves 0.651-approximation for quantum Max Cut, improving on the prior 0.614 SDP-only bound and remaining effective at 89% ground-state fidelity.

  3. On Brouwer's Laplacian conjecture

    math.CO 2026-06 unverdicted novelty 7.0

    Proves Brouwer's Laplacian conjecture and establishes its equivalence to the Grone-Merris-Bai theorem for split graphs.

  4. Kikuchi Graphs of Random Hypergraphs are Approximately Johnson

    cs.DS 2026-06 unverdicted novelty 7.0

    Level-ℓ Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate those of the complete hypergraph at near-optimal sampling rates for r ≤ ℓ ≤ n/2.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · cited by 4 Pith papers

  1. [1]

    Beyond Product State Approximations for a Quantum Analogue of Max Cut

    [AGM20] Anurag Anshu, David Gosset, and Karen Morenz. “Beyond Product State Approximations for a Quantum Analogue of Max Cut”. In: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Ed. by Steven T. Flammia. Vol

    work page 2020

  2. [2]

    Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, 7:1–7:15.DOI: 10

    Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, 7:1–7:15.DOI: 10 . 4230 / LIPIcs . TQC . 2020

    work page 2020

  3. [3]

    Improved Algorithms for Quantum MaxCut via Partially En- tangled Matchings

    arXiv: 2003 . 14394 [quant-ph].URL: https://drops.dagstuhl.de/entities/document/10. 4230/LIPIcs.TQC.2020.7(page 2). [ALMPS25] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. “Improved Algorithms for Quantum MaxCut via Partially En- tangled Matchings”. In:33rd Annual European Symposium on Algo- rithms (ESA 2025). Vol

    work page 2003

  4. [4]

    A 0.8395-approximation algorithm for the EPR problem

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Infor- matik, 2025, 101:1–101:14.DOI: 10.4230/LIPIcs.ESA.2025.101.URL: https : / / drops . dagstuhl . de / entities / document / 10 . 4230 / LIPIcs . ESA.2025.101(page 2). [ALMPSS25] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sin- jorgo, and Ja...

    work page doi:10.4230/lipics.esa.2025.101.url: 2025

  5. [5]

    Gribling, L

    Ed. by Dimitris Achlioptas and László A. Végh. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, 31:1–31:17.DOI: 10.4230/ LIPIcs . APPROX - RANDOM . 2019 . 31.URL: https : / / doi . org / 10 . 4230/LIPIcs.APPROX-RANDOM.2019.31(page 2). [GSS25] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov. “Improved Approximation Ratios for the Quan...

    work page doi:10.48550/arxiv.2504.11120 2019

  6. [6]

    Kothari, Yang P

    Ed. by Nikhil Bansal and Viswanath Nagarajan. SIAM, 2023, pp. 1319–1384.DOI: 10.1137/1. 9781611977554.ch48.URL: https://doi.org/10.1137/1.9781611977554. ch48(page 2). [HTPG24] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second Order Cone Relaxations for Quantum Max Cut”. In:CoRR abs/2411.04120 (2024).DOI: 10.48550/arXiv.2411.04120. arXiv:

    work page doi:10.1137/1 2023

  7. [7]

    Huber, K

    04120 [quant-ph].URL: https://doi.org/10.48550/arXiv.2411.04120 (page 2). [JKKSW24] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland. “Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamil- tonians”. In:CoRRabs/2410.15544 (2024).DOI: 10 . 48550 / arXiv . 2410.15544. arXiv: 2410....

    work page doi:10.48550/arxiv.2411.04120 2024

  8. [8]

    [KM24b] Pravesh K

    arXiv: 2209 . 02589 [quant-ph].URL: https : / / doi . org / 10 . 22331/q-2023-11-09-1180(page 2). [KM23] Pravesh K. Kothari and Peter Manohar. “An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes”. In:arXiv preprint arXiv:2311.00558(2023).DOI: 10.48550/arXiv.2311.00558 . arXiv: 2311.00558 [cs.CC].URL: https://arxiv.org/abs/2311.00558 (...

    work page doi:10.48550/arxiv.2311.00558 2023

  9. [9]

    An Approximate Version of Brouwer’s Laplacian Conjec- ture

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 48:1–48:16.DOI: 10.4230/LIPIcs.ISAAC.2022.48.URL: https://drops. dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.48 (page 2). [Lew26] Alan Lew. “An Approximate Version of Brouwer’s Laplacian Conjec- ture”. In:arXiv preprint arXiv:260...

    work page doi:10.4230/lipics.isaac.2022.48.url: 2022

  10. [10]

    Quantum Max-Cut is NP hard to approximate

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 105:1–105:11.DOI: 10.4230/LIPIcs.ICALP.2024.105 .URL: https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.ICALP.2024.105(page 2). 13 [MOA11] Albert W. Marshall, Ingram Olkin, and Barry C. Arnold.Inequalities: theory of majorization a...

    work page doi:10.4230/lipics.icalp.2024.105 2024

  11. [11]

    An Optimal Product-State Ap- proximation for 2-Local Quantum Hamiltonians with Positive Terms

    Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 102:1–102:20.DOI: 10.4230/LIPIcs.ICALP.2021. 102.URL: https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.ICALP.2021.102(page 2). [PT22] Ojas Parekh and Kevin Thompson. “An Optimal Product-State Ap- proximation for...

    work page doi:10.4230/lipics.icalp.2021 2021