Exact algorithms for quadratic optimization over roots of unity

Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun · 2025

Read Exact algorithms for quadratic optimization over roots of unity by Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02006.txt.

Introduction

Ahmad Al-Sulami, Hamza Fawzi, and Shengding Sun give exact methods for a hard optimization problem, in a 2025 paper. Each variable in the problem must be a complex root of unity, a point evenly spaced on the unit circle, and the goal is a quadratic score. Such problems arise in signal processing, signal detection in wireless systems, and ground-state searches in physics.

First, the team proves that a ladder of relaxations, the sum-of-squares hierarchy, reaches the exact answer after roughly half the levels once expected. Second, they recast the problem with half as many binary variables by using shapes called zonotopes. On test problems the new form solved up to ten times faster.

Catalog record

CREATORAhmad Al-Sulami, Hamza Fawzi, Shengding Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02006

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact algorithms for quadratic optimization over roots of unity Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun Abstract We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex m 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 ⌊ n / 2 ⌋ + 1 \lfloor n/2\rfloor+1 levels (as opposed to n n levels). Our proof follows and generalizes the techniques and results used for the binary m = 2 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. 1 Introduction Quadratic unconstrained binary optimization, henceforth QUBO, is the problem of maximizing a quadratic objective over binary variables. This problem is most commonly stated in the following form: \displaystyle\text{max } \displaystyle x^{T}Qx (1) \displaystyle\text{s.t. } \displaystyle x\in\{-1,1\}^{n} where Q is a symmetric matrix of size n\times n . This NP-hard problem has attracted interest within the mathematical programming community, in part because it can model graph partitioning problems, but also because it has various applications in electrical engineering, statistical physics, and machine learning [ 24 , 8 , 4 ] . There has been renewed interest in such problems recently, driven by the appearance of new quantum devices which are particularly tailored for problems of the form ( 1 ). This has driven optimization researchers to find new performant classical algorithms for solving QUBO problems, see e.g., [ 9 , 13 , 17 , 25 ] . In this paper we are interested in the generalization of QUBO where the binary set \{-1,1\}^{n} is replaced by the set of m ’th roots of unity, namely: \displaystyle\text{max } \displaystyle z^{*}Qz=\sum_{ij}Q_{ij}z_{i}^{*}z_{j} (2) \displaystyle\text{s.t. } \displaystyle z\in B_{m}^{n} where B_{m}^{n}:=\{z\in\mathbb{C}^{n}:z_{i}^{m}=1\text{ for }i=1,\dots,n\}. (3) Here, Q is a general n\times n Hermitian matrix. Problems of the form ( 2 ) appear in modern signal processing and maximal likelihood estimation problems [ 29 ] , including in angular synchronization [ 3 ] , the multiple-input multiple-output detection problem [ 15 , 20 , 22 ] , phase retrieval [ 32 ] , and unimodular radar code design [ 31 , 21 ] . The problem ( 2 ) is also directly related to the problem of computing the ground state of the well-known vector Potts model [ 33 ] from statistical physics, where the coefficients Q_{ij} play the role of the (negative) coupling coefficients. 1.1 Contributions In this paper, we focus on algorithms to solve ( 2 ) exactly. Our contributions are twofold: Tightness of Lasserre hierarchy Our first result concerns the Lasserre hierarchy to solve ( 2 ). The Lasserre hierarchy is a semidefinite-programming based hierarchy which gives increasingly accurate upper bounds on the solution of ( 2 ). We adopt in this paper the sum-of-squares point of view, wherein the k ’th level of the hierarchy is defined as the best upper bound that can be obtained via degree k sum-of-squares certificates. In order to introduce the hierarchy more precisely, we need a few technical definitions. First, note that any function f:B_{m}^{n}\to\mathbb{R} can be expanded in the monomial (Fourier) basis given by \mathcal{M}^{n}_{m}:=\{z^{\alpha}=\prod_{i=1}^{n}z_{i}^{\alpha_{i}}:\alpha\in\mathbb{Z}^{n}_{m}=\{0,\dots,m-1\}^{n}\}. (In the binary case, \mathcal{M}^{n}_{m} is the set of square-free monomials.) Due to the cyclic nature of \mathbb{Z}_{m} the notion of degree of monomials is not clearly defined. Hence, we need to define the signature for a monomial z^{\alpha} which will allow us to grade the monomials in \mathcal{M}^{n}_{m} and index the levels of hierarchy. Definition 1 . Given a monomial z^{\alpha}\in\mathcal{M}^{n}_{m} , its signature is the ordered (m-1) tuple (n_{1}(\alpha),\ldots,n_{m-1}(\alpha)) , where n_{i}(\alpha)=|\{j\in\{1,\ldots,n\}:\alpha_{j}=i\}| is the number of variables in z^{\alpha} whose exponent is i . The set of all monomials with signature (n_{1},\ldots,n_{m-1}) is denoted by M(n_{1},\ldots,n_{m-1}) . The level k monomials \mathcal{M}^{n}_{m}(k) (or \mathcal{M}(k) when n and m are clear from context) consist of monomials z^{\alpha} such that n_{i}(\alpha)\leq k for all 1\leq i\leq m-1 . It is obvious to check that in the case m=2 , the signature of a monomial z^{\alpha} is a single integer equal to its degree (as square-free monomial). We are now ready to state the main theorem concerning the sum of squares relaxation: Theorem 1 . Let Q be an n\times n Hermitian matrix and consider the function f:B_{m}^{n}\to\mathbb{R} defined by f(z)=z^{*}Qz=\sum_{1\leq i,j\leq n}Q_{ij}z_{i}^{-1}z_{j}. (4) Assume that f(z)\geq 0 for all z\in B_{m}^{n} . Then f admits a sum-of-squares certificate of the form f(z)=\sum_{j=1}^{r}|g_{j}(z)|^{2} on B_{m}^{n} where each g_{j}:B_{m}^{n}\to\mathbb{R} is supported on \mathcal{M}(\lfloor n/2\rfloor+1)=\{z^{\alpha}:~n_{j}(\alpha)\leq\lfloor n/2\rfloor+1,\quad\forall 1\leq j\leq m-1\}. (5) In short, the level- k sum-of-squares hierarchy for ( 2 ) is exact for k=\lfloor n/2\rfloor+1 . As a comparison, [ 10 , Theorem 2] proves that for m=2 , the level \lceil n/2\rceil sum-of-squares hierarchy is exact. Our result works for general m , and matches the same level bound for all odd n , and differs by one for all even n . While the techniques we use are similar to the previously cited paper and rely on the careful construction of chordal completions of the so-called Cayley graph, this generalization is highly nontrivial because the Cayley graph in our setting is significantly more complex than in the case where m=2 . We note that the result we are actually able to prove is considerably stronger than the statement in Theorem 1 . What we show is that the level \lfloor n/2\rfloor+1 is exact for any polynomial f which is a linear combination of monomials in at most two variables each, where degree can be arbitrary (see Theorem 4 ). However we are not aware of optimization applications beyond the quadratic case so that is why we decided to focus only on functions of the form ( 4 ). We also note that a previous generalization of the theorem in [ 10 ] was given in [ 26 ] , however the latter concerned nonquadratic functions f in binary variables. An exact real binary reformulation of ( 2 ) The second contribution of this paper concerns the practical computation of the optimal value of problems of the form ( 2 ). Noting that most existing integer programming solvers do not natively support complex discrete variables in B_{m} , but many do support quadratic objectives for binary variables, (e.g., Gurobi [ 12 ] , SCIP [ 6 ] , CPLEX [ 7 ] , etc.) we study the question of what the best way is to reformulate the problem ( 2 ) as a purely binary quadratic optimization problem, with possibly additional linear constraints. We first present a simple reformulation of ( 2 ) as a binary maximization problem in mn variables and n linear equality constraints. We then proceed to construct a nontrivial reformulation in the case of m even, which uses only mn/2 binary variables. Our construction

Read the complete text