Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916013149257728 |
|---|---|
| author | Bakshi, Ainesh Basu, Arpon Kothari, Pravesh Li, Anqi |
| author_facet | Bakshi, Ainesh Basu, Arpon Kothari, Pravesh Li, Anqi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_14994 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut Bakshi, Ainesh Basu, Arpon Kothari, Pravesh Li, Anqi Quantum Physics Data Structures and Algorithms Combinatorics 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. |
| title | Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut |
| topic | Quantum Physics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2605.14994 |