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

Ainesh Bakshi, Arpon Basu, Pravesh Kothari, Anqi Li · arXiv:2605.14994 · submitted 15 May 2026 · score 8/10 (HIGH)

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

Bakshi, Basu, Kothari, and Li resolve all four Apte–Parekh–Sud (APS) spectral conjectures by proving the sharp bound λ_max(L_G^{(k)}) ≤ m + k for both the signed and unsigned Laplacian of every level-k Kikuchi (token) graph. Plugged into the APS framework, this delivers the current best worst-case approximation ratios for Quantum Max Cut (0.614) and the XY Hamiltonian (0.674), beating the prior 0.611 / 0.6XX state of the art, with simple tensor-product-of-1-and-2-qubit-states ansätze. For Yuan, this paper sits in the same Goemans-Williamson-style "low-degree product-state SDP-relaxation" pipeline that Y5 reformulates via Gibbs states and Pauli sparsity, and on the Quantum Max Cut family that is the natural quantum extension of the 3-regular MaxCut target in Y1.

Main contribution

The technical heart of the paper is Theorem 1: 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. This single chain confirms all four APS conjectures (C1–C4) — bounds on signed Laplacian, signless Laplacian, and adjacency spectrum of the Kikuchi graph. The previous best general result was Lew's m + 4k − 2 for the unsigned Laplacian, so the improvement is by a factor of roughly 4 on the k-dependent term. Tightness is verified: disjoint unions of k stars saturate the Laplacian bound, and disjoint unions of k edges (giving a k-dimensional hypercube as the level-k Kikuchi graph) saturate the adjacency bound.

Key theorems / lemmas

Theorem 1 (Main): Resolves the APS conjectures C1–C4 via the unified chain on L_G^{(k)}, Q_G^{(k)}, A_G^{(k)}.
Theorem 2 (Consequences for local Hamiltonians): Existence of tensor-product-of-1-or-2-qubit-state ansatz achieving ratio 5/8 for QMC, 5/7 for XY, (√5+1)/4 for EPR; efficient algorithms achieve 0.614 (QMC) and 0.674 (XY) by composing the new spectral bound with the APS algorithms.
Theorem 3 (Brouwer): ε_r(G) ≤ C(r+1,2) + (4/3) r^{3/2} − r + √r, improving Lew's leading-order constant on the partial-eigenvalue sum from 4 to 4/3 — a 3× improvement on the asymptotic correction.
Theorem (Section 3, token-Laplacian bound): λ_max(L_{b,G}^{(k)}) ≤ m + k for both b∈{−1,+1}, proved by induction on k via a unified "edge-gradient" device: for an oriented edge e=(i,j), define g_e(R) = x_{R∪{i}} + b·x_{R∪{j}}; the edge-gradient eigenvalue equation h_e = λ g_e reduces the level-k spectrum to controlled combinations of level-(k−1) operators on edge-deleted subgraphs plus signed coordinate permutations of neighbouring derivatives.
Proposition 1 (Adjacency–Laplacian relationship): −½·λ_max(L_G^{(k)}) ≤ λ_min(A_G^{(k)}) ≤ λ_max(A_G^{(k)}) ≤ ½·λ_max(Q_G^{(k)}) via PSD-ness of L and Q; this is what allows the Laplacian-side bounds to subsume the adjacency-side conjectures.

Detailed walkthrough

The Kikuchi-as-token-graph picture (Section 2). Given a base graph G=([n],E), the level-k Kikuchi (token) graph F_k(G) has vertices ([n] choose k) and joins two k-sets S, T iff their symmetric difference S⊕T is an edge of G. Physically: place k indistinguishable tokens on distinct vertices of G; an edge corresponds to sliding one token across a base edge to an unoccupied site. This is also exactly the action of the relevant 2-local Hamiltonians (QMC, XY, EPR) on the Hamming-weight-k sector after decomposing the n-qubit Hilbert space into total-Z sectors. So spectral bounds on Kikuchi graphs translate directly into bounds on the maximum eigenvalue of these Hamiltonians, which is the quantum-CSP analogue of the maximum constraint-satisfaction value.

Why APS conjectured m+k. Apte, Parekh, and Sud (2025) studied algorithms that round product-state ansätze onto small (1- or 2-qubit-block) "AGM-style" entangled states. The approximation ratio they derive is governed by the largest eigenvalue of the level-k Kikuchi-graph adjacency/Laplacian. They conjectured the sharp bound m+k; before the present paper, only Lew's m + 4k − 2 (for the unsigned Laplacian only) was known unconditionally. The conjectured bound is tight on natural extremal graphs and would unlock the next round of approximation-ratio improvements; this paper supplies the missing ingredient.

Proof strategy (Section 3). Treat the signed (b=−1) and signless (b=+1) cases simultaneously via L_{b,G}^{(k)} = D_G^{(k)} + b·A_G^{(k)}. The proof is by induction on k; the base cases k=0 and k=n are trivial single-vertex graphs. The key device is the edge-gradient: orient every edge of G arbitrarily; for an oriented edge e=(i,j) and a background configuration R on [n]\{i,j}, set g_e(R) = x_{R∪{i}} + b·x_{R∪{j}}. The eigenvector equation L_{b,G}^{(k)} x = λ x then induces h_e = λ g_e on every edge, where h_e is the corresponding gradient applied to L_{b,G}^{(k)} x. Decomposing h_e over the three edge types relative to e (the edge itself, edges sharing a vertex with e, edges disjoint from e) turns the global Kikuchi-graph problem into a level-(k−1) token-Laplacian on the edge-deleted graph (where induction applies) plus controlled "permutation" terms across neighbouring edges. Summing the resulting Rayleigh-quotient identities across all e and using the induction hypothesis yields the m+k bound.

Cashing in: approximation ratios (Theorem 2). Apte, Parekh, and Sud (Corollaries 5–10 of [APS25]) had already shown that a sharp Kikuchi-Laplacian bound of the form m+k implies the following ratios. Existence: there is a tensor product of 1- and 2-qubit states with energy at least 5/8 of OPT for QMC and 5/7 for XY. Efficient algorithms: combining the new bound with the APS rounding algorithm yields polynomial-time algorithms with worst-case ratios 0.614 (QMC) and 0.674 (XY). For QMC this beats the previous best 0.611 (Apte–Lee–Marwaha–Parekh–Sud 2025) and continues a long sequence of improvements: 0.498 → 0.5 → 0.526 → 0.531 → 0.533 → 0.562 → 0.595 → 0.599 → 0.603 → 0.611 → 0.614. The hardness side: QMC is QMA-complete and APX-hard, and under a vector-Borell conjecture a (0.956+ε)-approximation is Unique-Games-hard; so the room left is substantial but not unbounded.

Side result: Brouwer's conjecture (Section 4). Brouwer conjectured ε_r(G) := Σ_{i=1}^{r} λ_i(L(G)) − |E| ≤ C(r+1,2) for every graph G and every r. The paper proves ε_r(G) ≤ C(r+1,2) + (4/3) r^{3/2} − r + √r, improving Lew's recent + 4 r^{3/2} − r − 2√r by a factor of 1/3 on the leading correction term. This is independent of the QMC application but uses the same Kikuchi-Laplacian machinery.

Section 3 induction details (lines 593–760 of main.tex). The induction step uses an orientation of G's edges, the gradient identity g_e(R) = x_{R∪{i}} + b·x_{R∪{j}}, and the operator-derivative identity h_e = (L_{b,G}^{(k)} x)_{R∪{i}} + b·(L_{b,G}^{(k)} x)_{R∪{j}} = λ g_e. The disjoint-edge case yields a (k−1)-token Laplacian on the edge-deleted graph; the shared-vertex case yields signed coordinate permutations of neighbouring derivatives that are controlled exactly in norm. The technical work, beyond the bookkeeping, is a careful one-edge/star/derivative sequence (Lemmas in Section 4, lines 925–1164) that gives the Brouwer-bound improvement as a corollary.

Figures

No figures extracted from source — the paper is purely theoretical (proof and bookkeeping); the LaTeX source contains no \includegraphics or figure environments.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography. (Author+title scan also returned no hits.)

Overlap with Y1–Y6

Y5 (Yuan–Franca–Luchnikov–Tiunov–Haug–Aolita, arXiv:2510.08292, "Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity"): Strong method-and-scope parallel. Y5 develops quantum and quantum-inspired relaxations of Goemans-Williamson-style SDPs by leveraging Pauli-sparse Gibbs-state oracles; Bakshi et al. develop a classical structural/spectral bound that powers GW-style product-state rounding for the quantum-CSP analogue (Quantum Max Cut). Both sit in the "approximation algorithms for MaxCut-family problems via low-degree relaxation" tradition. Direct interaction: the Kikuchi/token-graph spectrum encodes the action of 2-local Pauli Hamiltonians on Hamming-weight sectors — which is exactly a Pauli-sparse decomposition. There is a real possibility that Y5's Gibbs-state oracle could be applied to the same Hamiltonian families to produce a quantum-time analogue of the 0.614 / 0.674 ratios, or that Y5's Pauli-sparsity bounds could be sharpened using the new Laplacian bound.
Y1 (Yuan–Yang–Barnes, arXiv:2502.09704, "Iterative quantum optimisation with a warm-started quantum state"): Scope parallel. Y1 improves the 3-regular MaxCut approximation ratio via warm-started QAOA; the present paper improves the Quantum Max Cut approximation ratio via tensor-product rounding. Quantum Max Cut is the operator-theoretic generalisation of (classical) MaxCut to non-commuting X_iX_j+Y_iY_j+Z_iZ_j interactions, so the two papers attack adjacent corners of the same MaxCut-family approximation landscape — one quantum-algorithm-side (Y1, QAOA + warm starts), one classical-rounding-side (this paper, product-state ansatz + Kikuchi bounds).
Y4 (Yuan–Wu–Chen–Cheng–Barnes, arXiv:2603.14744, "Exponential Quantum Improvements in Cardinality-Constrained Binary Optimization"): Indirect connection through the Hamming-weight-sector decomposition. Both papers organise computation by Hamming-weight subspaces — Y4 to enforce cardinality constraints for Grover-style search; this paper to decompose 2-local Hamiltonians into level-k Kikuchi-graph problems. The mathematical apparatus around Hamming-weight sectors is shared; the constraint-preserving "hard mixer" of Y2 and the cardinality oracle of Y4 both live on the same sectors that Kikuchi graphs index.

Recommended action for Yuan

Cite in the next Y5-follow-up draft. If Yuan and collaborators extend Y5 to quantum-CSP problems (Quantum Max Cut, XY) — a natural sequel to the classical-GW direction — this paper supplies the current SOTA classical baseline (0.614, 0.674) that any quantum-time improvement must beat. It also gives the Kikuchi-Laplacian spectral handle that meshes with Y5's Pauli-sparsity argument.
Read deeper, then estimate the Pauli-sparsity gap. The Kikuchi-graph adjacency matrix is a sparse Pauli operator on the n-qubit space (it preserves Hamming weight, so it lives in the cardinality-k sector). Yuan's Y5 machinery for Pauli-sparse Gibbs states might let Y5's quantum SDP solver tackle the SDP relaxations underlying APS rounding — potentially yielding a quantum speed-up for the same 0.614 / 0.674 ratios, or a tighter classical bound by simulating the resulting Gibbs state.
Email Pravesh Kothari / Ainesh Bakshi. The Princeton/NYU group has been the lead group on Kikuchi-graph spectral methods (cf. their hypergraph Moore bound and refutation-algorithm work). Y5's quantum-time GW relaxation is a natural extension into the quantum-CSP world; a short note linking the two directions would be timely and could seed a collaboration.