Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
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
- A 0.8395-approximation algorithm for the EPR problem
- Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
- Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
- Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
- A simple and sharper proof of the hypergraph Moore bound
- Second order cone relaxations for quantum Max Cut
- Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians
- Improved approximation algorithms for the EPR Hamiltonian
- An Improved Approximation Algorithm for Quantum Max-Cut
- An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
- An approximate version of Brouwer's Laplacian conjecture
- Quantum Max-Cut is NP hard to approximate
- An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements