Exact algorithms for quadratic optimization over roots of unity

We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex m'th root of unity. Such problems have applications in signal processing, MIMO detection, and the computation of ground states in statistical physics, among others. Our contributions in this paper are twofold. We first study the convergence of the sum-of-squares hierarchy and prove its convergence to the exact solution after only lfloor n/2rfloor+1 levels (as opposed to n levels). Our proof follows and generalizes the techniques and results used for the binary m=2 case developed by Fawzi, Saunderson, Parrilo. Second, we construct an integer binary reformulation of the problem based on zonotopes which reduces by half the number of binary variables in the simple reformulation. We show on numerical experiments that this reformulation can result in significant speedups (up to 10x) in solution time.