Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, we show that a simple matching-based algorithm approximates the ground state energy to at least 1/d for general graphs and to at least 1/d + Θ(1/D) for graphs with bounded degree, D. This outperforms random assignment, which, in expectation, achieves energy of only 1/d² of the ground state energy for general graphs. Notably, on D-regular graphs with degree, D leq 5, and for any local dimension, d, we show that this simple matching-based algorithm has an approximation guarantee of 1/2. Lastly, when d=2, we present an algorithm achieving an approximation guarantee of 0.595, beating that of [PT22, arXiv:2206.08342] (which gave a tight approximation guarantee of 1/2).