Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
For researchers in quantum Hamiltonian complexity and approximation algorithms, the conjectures provide improved bounds and simpler combinatorial insights, though the results are partially conjectural.
The paper relates the maximum energy of certain 2-local Hamiltonians to spectral radii of token graphs, and conjectures new bounds that tighten analysis of existing algorithms, yielding state-of-the-art approximation ratios for Quantum MaxCut, XY, and EPR Hamiltonians.
We explain how the maximum energy of the Quantum MaxCut, XY, and EPR Hamiltonians on a graph $G$ are related to the spectral radii of the token graphs of $G$. From numerical study, we conjecture new bounds for these spectral radii based on properties of $G$. We show how these conjectures tighten the analysis of existing algorithms, implying state-of-the-art approximation ratios for all three Hamiltonians. Our conjectures also provide simple combinatorial bounds on the ground state energy of the antiferromagnetic Heisenberg model, which we prove for bipartite graphs.