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

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.

Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem
Fredy Yip
arXiv13 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Combinatorics & discrete mathematicsarXiv
New distance bounds for one-generator quasi-cyclic codes with applications to Hermitian LCD codes and entanglement-assisted quantum codes
Kanat Abdukhalikov, Duy Ho, Rasha M. Shat
arXiv25 Sep 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
Flaviano Morone, Shivang Rawat, Dries Sels
arXiv12 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Condensed matterarXiv
On Hamming Eigenvalues and Hamming Energy of Graphs
Harishchandra S. Ramane, Mallappa P. Mellikeri, Daneshwari D. Patil +1
Discrete Mathematics Letters25 Oct 2026Peer-reviewedCC BYFull textGeometry & topologyDOAJ
Sharp bounds for higher mixed Steklov-Robin eigenvalues on domains with holes
Sagar Basak
arXiv18 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{bakshi2026sharp,
  title = {{Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut}},
  author = {Ainesh Bakshi and Arpon Basu and Pravesh Kothari and Anqi Li},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2605.14994},
  eprint = {2605.14994},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.14994},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
AU  - Ainesh Bakshi
AU  - Arpon Basu
AU  - Pravesh Kothari
AU  - Anqi Li
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2605.14994
UR  - https://arxiv.org/abs/2605.14994
AB  - 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.
ER  -

Abstract

Related

Cite