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 / 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 2 of the maximum energy for general graphs. Notably, on D -regular graphs with degree, D ≤ 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 \cite{parekh_optimal_2022}, which gave an approximation ratio of 1 / 2 .