{"id":"arxiv/2605.14994","url":"https://arxiv.org/abs/2605.14994","tags":["quant-ph","cs.DS","math.CO"],"score":0,"title":"Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut","domain":"quant-ph","source":"arxiv","authors":["Ainesh Bakshi","Arpon Basu","Pravesh Kothari","Anqi Li"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-14","reactions":{}}