Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity

In this paper, we study the discrete complex quadratic optimization problem, where the goal is to maximize a multivariate Hermitian quadratic objective function over complex m’th roots of unity. This problem is a generalization of the well-studied quadratic unconstrained binary optimization problem (QUBO), and has applications in signal processing, including in maximal likelihood estimation and multiple-input multiple-output detection, in addition to applications in statistical physics, in particular the computation of ground states of the Potts model. We study the sum-of-squares hierarchy for this problem, which is a sequence of semidefinite relaxations that is known to converge to the optimal solution after at most n steps. A previous result of Fawzi, Saunderson and Parrilo showed that in the the binary case ( $$m=2$$ ), at most $$\lceil n/2 \rceil $$ levels of the hierarchy are actually needed. In this paper we generalize this result and establish that the hierarchy converges after at most $$\lfloor n/2\rfloor +1$$ level for any $$m \ge 2$$ . Our proof generalizes the ideas used in the $$m=2$$ case, and is based on constructing chordal covers of appropriate Cayley graphs.