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

arXiv:2605.14994 · quant-ph, cs.DS, math.CO · Submitted 2026-05-14 · Read on arXiv

quant-ph, cs.DS, math.CO

Submitted: 2026-05-14

Updated: 2026-11-03

Comments: Addressed reviewer comments and fixed typos

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

Terminology

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.

Sources

Related papers