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

This paper proves that the maximum eigenvalue of the level-$k$ Kikuchi graph Laplacian is at most $m+k$, confirming four conjectures and enabling improved approximation ratios and efficient algorithms for Quantum Max Cut and the XY Hamiltonian.

The Gist

The Big Picture: A New Way to Count "Moves"

Imagine you have a map of a city (the Graph) with streets connecting intersections. Now, imagine you have a fleet of identical delivery trucks (the Tokens) that you can park on the intersections.

The paper introduces a new way of looking at how these trucks can move. Instead of just watching one truck drive down a street, the authors look at the entire fleet moving at once. They created a special "super-map" (called a Kikuchi Graph) where every possible arrangement of the trucks is a single dot, and a line connects two dots if you can get from one arrangement to the other by sliding just one truck across a street.

The main goal of the paper is to answer a very specific question: What is the maximum "energy" or "tension" this super-map can have? In math terms, they are looking for the highest number (eigenvalue) associated with this map.

The Big Discovery: A Perfect Limit

For a long time, mathematicians had a guess (a conjecture) about what this maximum number would be. They thought it would be the total number of streets in the city ($m$) plus the number of trucks ($k$).

The authors proved this guess is exactly right.

They showed that no matter how complicated the city map is, or how many trucks you have, the maximum "tension" in this super-map will never exceed Streets + Trucks.

• The Formula: Max Tension $\le$ (Number of Streets) + (Number of Trucks).

They proved this for two different ways of measuring tension:

1. Signed Tension: Where moving a truck might cancel out another move (like positive and negative numbers).
2. Unsigned Tension: Where all moves just add up.

They also proved similar limits for the "speed" of moving around this map (the adjacency matrix), showing the limits are tight and cannot be improved.

Why Does This Matter? (The Quantum Connection)

The paper connects this abstract math problem to Quantum Physics.

Think of a quantum computer as a giant, complex machine made of tiny switches called qubits. These switches interact with each other, and physicists want to know the maximum amount of energy the machine can hold. This is a very hard problem to solve.

The authors found that the "maximum energy" of certain quantum machines is mathematically identical to the "maximum tension" of the truck super-map they just studied.

Because they proved the limit for the trucks is Streets + Trucks, they can now immediately say what the limit is for these quantum machines. This allows them to build better, more efficient algorithms to approximate the answers for quantum problems.

Specific Results for Quantum Problems:

• Quantum Max Cut: They found a method to get a solution that is 5/8 (62.5%) of the best possible answer. When combined with other existing tools, this improves to 0.614 (61.4%).
• XY Hamiltonian: They found a method to get 5/7 (71.4%) of the best answer, improving to 0.674 (67.4%) with other tools.
• EPR Hamiltonian: They confirmed a specific ratio of 0.809 (using the golden ratio formula), which is a simpler way to prove a result that others had found using much more complex methods.

Note: The paper explicitly states these are improvements for "Quantum Max Cut" and "XY Hamiltonian" problems. It does not claim these results apply to medical treatments, clinical uses, or future technologies beyond these specific mathematical and quantum computing contexts.

A Side Bonus: Fixing an Old Math Puzzle

The paper also makes a small improvement on a famous, unsolved puzzle called Brouwer's Conjecture.

• The Puzzle: It asks how much the sum of the top "energy levels" of a graph can exceed a simple prediction based on the number of edges.
• The Improvement: Previous mathematicians had a formula that was slightly too high. The authors tightened this formula, making the prediction more accurate by a small but significant amount (improving the error term by a factor of 1/3).

Summary

In short, the authors solved a long-standing math puzzle about how "active" a network of moving tokens can be. By proving the exact limit of this activity, they unlocked better ways to solve difficult energy problems in quantum physics, specifically for finding the maximum energy states of certain quantum systems. They did this without needing complex, messy calculations, using a clever "induction" method (building the solution step-by-step) that works for any graph.

Technical Summary

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

1. Problem Statement

The paper addresses the spectral properties of Kikuchi graphs (also known as token graphs), which are constructed from a base graph $G = ([n], E)$ with $m$ edges. The level-$k$ Kikuchi graph, denoted $F_k(G)$, has a vertex set consisting of all $k$-subsets of $[n]$. Two vertices $S$ and $T$ are adjacent if their symmetric difference $S \oplus T$ is an edge in $G$.

The central problem is to establish sharp upper bounds on the maximum eigenvalues of the following matrices associated with $F_k(G)$:

1. The signed Laplacian $L^{(k)}_G = D^{(k)}_G - A^{(k)}_G$.
2. The unsigned (signless) Laplacian $Q^{(k)}_G = D^{(k)}_G + A^{(k)}_G$.
3. The adjacency matrix $A^{(k)}_G$.

Prior to this work, the best known general bound for the unsigned Laplacian was $\lambda_{\max}(L^{(k)}_G) \leq m + 4k - 2$ (Lew, 2026). Apte, Parekh, and Sud (APS) recently conjectured that for any graph $G$ and $0 \leq k \leq n$, the maximum eigenvalues satisfy $\lambda_{\max}(L^{(k)}_G) \leq m + k$ and $\lambda_{\max}(Q^{(k)}_G) \leq m + k$. These conjectures are critical because the spectral bounds of Kikuchi graphs directly translate to upper bounds on the maximum energies of specific 2-local quantum Hamiltonians.

2. Methodology

The authors employ a novel edge-gradient induction technique to prove the spectral bounds. The methodology proceeds as follows:

• Unified Operator Definition: The authors define a unified operator $L^{(k)}_{b,G} = D^{(k)}_G + bA^{(k)}_G$ for $b \in \{-1, 1\}$, covering both the signed Laplacian ($b=-1$) and the unsigned Laplacian ($b=1$).
• Inductive Framework: The proof proceeds by induction on $k$. For a fixed eigenvector $x$ of $L^{(k)}_{b,G}$ with eigenvalue $\lambda$, the authors define "edge gradient" vectors $g_e$ for each edge $e = (i, j)$ in the base graph $G$. These gradients are constructed by differentiating the eigenvector across the edge $e$ in the token graph.
  • For $b=-1$, $g_e$ represents the standard difference $x_{R \cup \{i\}} - x_{R \cup \{j\}}$.
  • For $b=1$, it represents the sum $x_{R \cup \{i\}} + x_{R \cup \{j\}}$.
• Decomposition of Operators: The action of the operator $L^{(k)}_{b,G}$ on the gradient vectors is decomposed into three components based on the relationship between a fixed edge $e$ and other edges $f$ in $G$:
  1. Self-edge ($f=e$): Contributes a factor of 2.
  2. Disjoint edges ($f \cap e = \emptyset$): These induce a $(k-1)$-token operator on the graph $G - \{i, j\}$ (the base graph with vertices $i$ and $j$ removed).
  3. Adjacent edges ($|f \cap e| = 1$): These produce "twist" terms involving signed coordinate permutations. The authors show these terms preserve Euclidean norms via bijections between configuration spaces.
• Norm Summation: By summing the squared norms of the gradient vectors over all edges and applying the induction hypothesis to the subgraph $G - \{i, j\}$, the authors derive an inequality relating $\lambda$ to the number of edges $m$ and the token count $k$.

For Brouwer's Conjecture (concerning partial sums of Laplacian eigenvalues), the authors adapt this edge-gradient technique to the exterior power of the vector space. They define an auxiliary operator $B_r(G)$ related to the $r$-th additive compound of the Laplacian. By analyzing the "edge gradient" in the exterior algebra (involving contractions and projections), they bound the quadratic form of $B_r(G)$ and subsequently the partial sums of eigenvalues.

3. Key Contributions and Results

A. Resolution of APS Conjectures
The paper proves Theorem 1.2, confirming the four conjectures of Apte, Parekh, and Sud:

• $\lambda_{\max}(L^{(k)}_G) \leq m + k$
• $\lambda_{\max}(Q^{(k)}_G) \leq m + k$
• $\lambda_{\max}(A^{(k)}_G) \leq \frac{1}{2}(m + k)$
• $\lambda_{\min}(A^{(k)}_G) \geq -\frac{1}{2}(m + k)$

The authors note these bounds are tight, demonstrated by disjoint unions of stars (for Laplacians) and disjoint unions of edges (perfect matchings, for adjacency matrices).

B. Applications to Quantum Hamiltonians
Using the spectral bounds, the paper derives improved approximation guarantees for the maximum energy of 2-local Hamiltonians. Specifically, it shows that tensor products of one- and two-qubit product states achieve the following structural ratios:

• Quantum Max Cut (QMC): Approximation ratio of $5/8 = 0.625$.
• XY Hamiltonian: Approximation ratio of $5/7 \approx 0.714$.
• EPR Hamiltonian: Approximation ratio of $(\sqrt{5} + 1)/4 \approx 0.809$.

Furthermore, by combining these bounds with the algorithms analyzed by Apte, Parekh, and Sud, the authors demonstrate the existence of efficient algorithms achieving:

• QMC: $0.614$
• XY: $0.674$
• EPR: $(\sqrt{5} + 1)/4$ (matching the structural bound).

These results improve upon the previous best-known worst-case ratios for QMC (previously $0.611$) and XY. For EPR, while the ratio does not surpass the $0.8395$ achieved by more complex AGM circuits, the paper provides a simpler certificate using a much smaller ansatz (block-product states) compared to the commuting two-qubit rotations used in prior works.

C. Progress on Brouwer's Conjecture
The paper improves the bound on the partial sums of Laplacian eigenvalues, $\epsilon_r(G) = \sum_{i=1}^r \lambda_i(L(G)) - |E|$.

• Previous Bound (Lew, 2026): $\epsilon_r(G) \leq \binom{r+1}{2} + 4r^{3/2} - r - 2\sqrt{r}$.
• New Bound (Theorem 1.4): $\epsilon_r(G) \leq \binom{r+1}{2} + \frac{4}{3}r^{3/2} - r + \sqrt{r}$.
  This represents an asymptotic improvement by a factor of $1/3$ on the leading error term.

4. Significance

The paper claims significance in three primary areas:

1. Spectral Graph Theory: It resolves four open conjectures regarding the extremal eigenvalues of Kikuchi graphs, providing tight bounds that were previously unknown.
2. Quantum Approximation Algorithms: It establishes that simple product states (tensor products of 1- and 2-qubit states) are sufficient to achieve approximation ratios of $0.614$ for QMC and $0.674$ for XY, improving the state-of-the-art. It highlights that complex entangled ansatzes (like AGM circuits) may not be strictly necessary to achieve these specific bounds, offering a simpler structural certificate.
3. Combinatorial Optimization: It provides the best known estimates for Brouwer's conjecture on the sum of the top-$k$ Laplacian eigenvalues, refining the understanding of the spectral distribution of graph Laplacians.

The authors emphasize that their results are derived from sharp spectral bounds on Kikuchi graphs, which serve as a bridge between high-dimensional incidence structures and standard graph spectral theory, with direct implications for the computational complexity of quantum many-body systems.