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

Ainesh Bakshi (NYU), Arpon Basu (Princeton), Pravesh Kothari (Princeton), Anqi Li (Stanford) · arXiv:2605.14994 · new submission, 15 May 2026 · score 8/10

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.

Executive summary

This paper resolves the four Apte–Parekh–Sud (APS) conjectures on the spectral radii of Kikuchi (token) graphs by a single short induction, yielding the tight bound λ_max(L_b,G^(k)) ≤ m + k for both signed and unsigned Laplacians. As a consequence, the previous state-of-the-art worst-case approximation ratios for the Quantum Max Cut (QMC) and XY Hamiltonian problems on general graphs are pushed from 0.611 (Apte–Lee–Marwaha–Parekh–Sud 2025) up to 0.614 for QMC and 0.674 for XY, achieved by efficient algorithms that output simple product-state ansatze (tensor products of one- and two-qubit states). For Yuan: this sits squarely in the line of provable approximation algorithms for graph-structured Hamiltonians—the same family as the structured GW relaxations Y5 attacks via Pauli-sparse Gibbs states—and it strengthens the worst-case baseline that any quantum-algorithmic claim for QMC must beat.

Main contribution

The technical heart is a sharp Laplacian eigenvalue bound for the level-k Kikuchi graph F_k(G): the maximum eigenvalue of the (signed or unsigned) Laplacian is at most m + k, where m is the number of edges of the base graph G. This is tight (disjoint stars saturate the Laplacian bound; a perfect matching saturates the adjacency bound). Previously the best general estimate was Lew's m + 4k − 2. Because Apte–Parekh–Sud had already shown that the maximum energy of the QMC, XY, and EPR Hamiltonians can be expressed via extremal Kikuchi-graph eigenvalues after passing to the low-Hamming-weight sector decomposition, the sharp spectral bound transports verbatim into improved structural and algorithmic approximation ratios for these Hamiltonians, plus a side improvement to the leading constant in Brouwer's conjecture on partial sums of Laplacian eigenvalues.

Key theorems / lemmas / algorithms

Theorem 1 (main): For any graph G with m edges and any 0 ≤ k ≤ n, −(m + k) ≤ −λ_max(L_G^(k)) ≤ 2λ_min(A_G^(k)) ≤ 2λ_max(A_G^(k)) ≤ λ_max(Q_G^(k)) ≤ m + k. Resolves APS conjectures C1–C4.
Theorem (token-Laplacian bound, §3): For b ∈ {−1, +1}, λ_max(L_b,G^(k)) ≤ m + k, proved by induction on k via an edge-gradient identity.
Theorem (applications): Tensor products of one- and two-qubit states achieve approximation ratios 5/8 for QMC, 5/7 for XY, and (√5 + 1)/4 for EPR. With APS's rounding algorithm, this becomes efficient approximations 0.614 for QMC and 0.674 for XY.
Theorem 3 (Brouwer): ε_r(G) ≤ C(r+1,2) + (4/3) r^3/2 − r + √r, improving Lew's 4 r^3/2 leading coefficient to 4/3.
Proposition (A/L/Q relationship, §2): Standard identity tying adjacency to signed/unsigned Laplacians, used to derive C3 and C4 once C1 and C2 are known.

Detailed walkthrough

The Kikuchi (a.k.a. token) graph F_k(G) has the k-subsets of [n] as vertices, and two k-sets S, T are adjacent iff their symmetric difference is an edge of G. Intuitively, place k indistinguishable tokens on distinct vertices; a legal move slides one token across a G-edge into an empty vertex. Kikuchi graphs already underlie the proof of Feige's hypergraph Moore bound, refutation algorithms for random CSPs, and exponential lower bounds for locally correctable codes. Apte–Parekh–Sud (APS, 2025) added a quantum-information motivation: after decomposing the n-qubit Hilbert space into low-Hamming-weight sectors, the restriction of common 2-local Hamiltonians (QMC, EPR, XY) to the weight-k sector is exactly governed by the Laplacian/adjacency of F_k(G). APS conjectured four sharp spectral inequalities (C1–C4) and showed that any bound of the form m + k on the Laplacian would propagate to non-trivial approximation guarantees.

The paper's central proof (Section 3, Theorem on L_b,G^(k)) treats the signed and unsigned cases simultaneously by introducing L_b,G^(k) = D_G^(k) + b A_G^(k) for b ∈ {±1}. Fixing an eigenvector x with eigenvalue λ, they orient each edge e = (i, j) of G and define an “edge gradient” vector g_e(R) = x_R∪{i} + b x_R∪{j} on the background configurations R ∈ D_e = C([n]∖{i,j}, k−1). A parallel vector h_e is built from L_b,G^(k)x, so the eigenvalue equation reduces to h_e = λ g_e. A short case analysis (the differentiated edge itself; edges disjoint from e; edges sharing exactly one endpoint with e) produces the derivative identity

h_e = (2I + L_b,G−{i,j}^(k−1)) g_e + Σ_|f∩e|=1 σ_e,f g_f ∘ π_e,f,

where the “twist” map π_e,f is an explicit bijection between background sets that preserves Euclidean norm (Eq. 2.21 in §3). The induction hypothesis bounds λ_max(L_b,G−{i,j}^(k−1)) ≤ (m − d_i − d_j + 1) + (k−1); combining with the twist isometry and summing over all edges e, the coefficient of each ‖g_f‖₂ collects exactly to 2 + (m − d_u − d_v + 1) + (k−1) + (d_u + d_v − 2) = m + k. Dividing through (or arguing that λ = 0 in the degenerate case) yields the bound. The proof is striking for how cleanly the degree contributions cancel: the −d_u − d_v from the induction step exactly cancels the +d_u + d_v from the “adjacent edges” combinatorics, leaving the universal m + k.

Once the Laplacian bound is in hand, the adjacency bounds C3 and C4 follow from a standard A/L/Q identity (Proposition in §2). The quantum-information consequences are then transported via Corollaries 5–10 of APS: for QMC, the maximum energy on the weight-k sector is upper-bounded by the spectral radius of the unsigned Kikuchi Laplacian, so the sharp m + k bound directly improves the analysis of APS's rounding algorithm. The structural ratios 5/8 (QMC) and 5/7 (XY) are achieved by tensor products of one- and two-qubit states, which is a much smaller ansatz than the AGM (Anshu–Gosset–Morenz) circuits that earlier papers (King 2023; Anshu–Gosset–Morenz 2020; Apte–Lee–Marwaha–Parekh–Sud 2025) had to use. The efficient algorithmic ratios 0.614 (QMC) and 0.674 (XY) come from feeding the same bound into APS's rounding scheme.

Section 4 turns the same eigenvalue toolkit on Brouwer's conjecture, which predicts Σ_i≤rλ_i(L(G)) − m ≤ C(r+1, 2). The authors recast the partial sum as the largest eigenvalue of an operator on the r-th exterior power of Rⁿ, then push through analogous edge-gradient arguments. The improvement is a factor of 3 on the leading r^3/2 correction term (4/3 vs. Lew's 4). This isn't direct quantum content, but it tightens the same spectral inequalities that underlie token-graph analysis broadly.

Two things to note about scope and limits. First, the “efficient algorithm” ratio 0.614 for QMC is a worst-case bound on general graphs; structured instance families (bipartite, triangle-free, etc.) often admit better ratios via different ansatze, and the question of matching these provable ratios with NISQ-runnable circuits is left open. Second, the structural ratio of (√5 + 1)/4 ≈ 0.809 for EPR does not beat the best known 0.8395 (Apte–Lee–Marwaha–Parekh–Sinjorgo–Sud), but it does so with a much simpler product-state certificate—a useful contrast if one wants to understand what AGM-style entanglement buys beyond block-product ansatze.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y5 (Gibbs-state Goemans–Williamson + Pauli sparsity): Strongest overlap. Both papers are in the line of provable approximation algorithms for graph-structured Hamiltonian objectives. Y5 attacks structured GW relaxations via quantum/quantum-inspired Pauli-sparse Gibbs states; this paper attacks the quantum analogue of MaxCut (QMC) directly with combinatorial/spectral methods. Different machinery, same target ecosystem—the 0.614 QMC ratio here is the worst-case baseline against which any quantum-inspired or Gibbs-sampled QMC approximation must be compared.
Y1 (iterative warm-started QAOA on 3-regular MaxCut): Same combinatorial object family. Y1 is about warm-starting a heuristic quantum algorithm for the classical MaxCut on 3-regular graphs; this paper concerns a worst-case provable algorithm for the quantum MaxCut Hamiltonian on general graphs. Y1's approximation-ratio improvements live in the heuristic-quantum regime; this paper's are worst-case classical-rounding guarantees. The natural cross-reference is “how does iterative warm-started QAOA compare to a 0.614-product-state baseline on QMC, if anyone has tried it?”
Y4 (Grover + ADMM cardinality-constrained binary optimization): Mild scope overlap via combinatorial optimization on graph-structured objectives. No methodological tie—Y4 is amplitude-amplification-based, this paper is purely classical spectral/combinatorial.
Y2, Y3, Y6: No meaningful overlap. Y2/Y3 are QAOA for portfolio optimization; Y6 is a foundations/hardware paper on PBR.

Recommended action for Yuan

Read deeper, especially §3 (the m + k proof) and the APS reference [AptePS25]. If you ever want to write a follow-up to Y5 on QMC specifically, the APS/Bakshi–Basu–Kothari–Li 0.614 ratio is the public worst-case baseline you'd benchmark against. It also gives a clean classical certificate to compare against any Gibbs-sampled / Pauli-sparse approximation.
Cite it when next discussing approximation guarantees for graph Hamiltonians. The Kikuchi/token-graph spectral approach is a clean alternative to SDP-based proofs and worth mentioning alongside GW-style bounds in the related-work section of any future Y5 follow-up.
No urgent outreach needed. The paper does not cite Y1–Y6 (bibliography scan came up empty), and the methods are sufficiently different from yours that a courtesy email is optional rather than warranted.