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 maximum 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 maximum energy to at least $1\mathrm{/}d$ for general graphs and to at least $1\mathrm{/}d+\mathrm{\Theta }(1\mathrm{/}D)$ for graphs with bounded degree, $D$. This outperforms random assignment, which, in expectation, achieves energy of only $1\mathrm{/}{d}^2$ of the maximum energy for general graphs. Notably, on $D$-regular graphs with degree, $D\le 5$, and for any local dimension, $d$, we show that this simple matching-based algorithm has an approximation guarantee of $1\mathrm{/}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 an approximation ratio of $1\mathrm{/}2$.