Exact algorithms for quadratic optimization over roots of unity

Ahmad Al-Sulami; Hamza Fawzi; Shengding Sun

REVIEW 1 major objections 5 minor 5 references

Exact algorithms for quadratic optimization over roots of unity

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For quadratic optimization over m-th roots of unity, the sum-of-squares hierarchy reaches the exact optimum at level floor(n/2)+1, and for even m the problem can be rewritten as a binary quadratic program with nm/2 variables and n convex…

desk verdict Sound generalization of SOS tightness to roots of unity plus a useful zonotope reformulation; one small missing lemma in the chordal proof, easily fixed. read the letter →

arxiv 2508.02006 v1 pith:5A7WTTHP submitted 2025-08-04 math.OC

Ahmad Al-Sulami , Hamza Fawzi , Shengding Sun This is my paper

classification math.OC MSC 90C2290C2090C26

keywords rootsofunityquadraticoptimizationsum-of-squareshierarchyLasserrechordalgraphszonotopesbinaryreformulationMIMOdetection

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

At its core, this paper concerns optimizing a Hermitian quadratic form over n complex variables constrained to be m-th roots of unity—a discrete problem behind MIMO symbol detection, angular synchronization, phase retrieval, and ground states of the vector Potts model. The paper's first main claim is that the sum-of-squares (moment-SOS) hierarchy for this problem is exact at level floor(n/2)+1: whenever f(z)=z*Qz is nonnegative on the feasible set, it admits an SOS certificate using monomials whose signatures have entries at most floor(n/2)+1. The second claim is a practical factorization: for even m, the regular m-gon is a zonotope, which yields an exact reformulation of the original problem as a binary quadratic program with nm/2 binary variables and n convex inequality constraints, halving the number of variables in the straightforward one-hot reformulation. These results give both a finite certificate scale for a general class of discrete quadratic problems and a way to hand complex-root problems to standard integer-programming solvers.

What carries the argument

The carrying objects are: (i) the signature of a monomial z^α = (n_1(α),...,n_{m-1}(α)), where n_j counts variables with exponent j, which replaces degree as the grading for the SOS hierarchy; (ii) the Cayley graph of the monomial group with edges between monomials differing in at most two coordinates; (iii) a chordal cover Γ of that graph built from cliques on the sets V_0 = {signatures with all entries ≤ floor(n/2)+1} and V_j = {n_j ≥ floor(n/2)} for j=1,...,m-1, whose running intersection property is used to certify chordality; and (iv) the character translations χ_j that move each V_j into V_0, so that the abstract SOS theorem produces the claimed support. For the binary reformulation, the machinery is the zonotope identity: for even m, the regular m-gon is the projection T({±1}^{m/2}) with T(e_k) = -i sin(π/m) exp((2k-1)πi/m), and the cube vertices mapping onto polygon vertices are exactly those with at most one sign change, i.e. Σ_{j=1}^{m/2-1}|ε_j-ε_{j+1}| ≤ 2.

What would settle it

Take a small instance, say n=6, m=5 so the claimed level is k=4, build the graph Γ as the union of cliques on V_0,...,V_4, and enumerate its maximal cliques; if any maximal clique C is not contained in some V_j, or if some character translation χ_j C fails to lie in V_0, then Theorem 4's SOS support claim collapses. Equivalently, solving the level-k moment-SDP for a random nonnegative two-variable polynomial and finding no certificate, or finding a nonnegative quadratic whose level-k upper bound is strictly above the true optimum, would refute the exactness claim.

Watch

Extended reading notes

Core claim

The central discovery is a support bound for sparse nonnegative functions on the group B_m^n ≅ Z_m^n. The paper proves that every nonnegative polynomial made of monomials that involve at most two variables each—in particular every nonnegative Hermitian quadratic form z*Qz—is a sum of squares of functions supported on the monomial set {z^α : n_j(α) ≤ floor(n/2)+1 for all j}, where n_j(α) counts variables with exponent j. By the standard equivalence with the moment-SOS hierarchy, this makes the level-floor(n/2)+1 relaxation exact for the maximization problem, for every m and every Hermitian Q. The proof constructs a chordal cover Γ of the Cayley graph of monomials with respect to the two-variable support, via sets V_0,...,V_{m-1} that satisfy the running intersection property, then translates each set by characters χ_j = $z_1^{{-j}}$...$z_n^{{-j}}$ to land inside the level set; this is stated as Theorem 4, with the quadratic statement as Theorem 1. A second, independent result reduces the even-m case to a pure binary quadratic program with half the variables of the one-hot model.

Load-bearing premise

For the SOS certificate to have the claimed support, every maximal clique of the chordal graph built from the sets V_0,...,V_{m-1} must lie inside one of those sets so it can be translated into the target support; the paper proves this for each V_j but never explicitly proves it for all maximal cliques.

Editorial extensions

If this is right

For any n and m, the level floor(n/2)+1 moment-SOS relaxation of max z*Qz over B_m^n has the same value as the discrete optimum, so no higher hierarchy level is ever needed for quadratic objectives.
Since the stronger theorem covers all nonnegative polynomials whose monomials touch at most two variables, the same support bound applies to a wider class of sparse trigonometric polynomials on the root-of-unity grid.
For even m, every instance of the problem becomes a pure binary quadratic program with nm/2 variables and n convex sign-change constraints, which standard MIQP solvers can read directly.
In the special case m=4, the reformulation is an unconstrained QUBO in 2n binary variables, obtained by the rotation w=(1+i)z.
On tested MIMO and vector-Potts instances, the zonotope reformulation solves faster than the one-hot model, with speedups up to 10x.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One testable consequence the paper leaves implicit: for odd n its SOS level matches the binary-case bound ceil(n/2), while for even n it is one level higher; checking whether the extra level is genuinely needed for some m≥3 would separate a proof artifact from an intrinsic complexity gap.
The zonotope reformulation identifies the regular m-gon with the image of a cube under a fixed map; the same construction might carry over to any centrally symmetric polygon or to constellations that are affine images of regular polygons, giving analogous binary models with fewer variables, but this is not claimed by the paper.
If the level-floor(n/2)+1 exactness is sharp in practice, then the SDP relaxation at that level gives a deterministic exact algorithm for small n; comparing its solve time to the binary reformulation on MIMO instances would be a natural benchmark.
The paper's open question about m odd suggests looking for cube-liftings of odd regular polygons with dimension growing linearly in m; a positive answer would yield the halved reformulation for all m.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Quick take on arXiv:2508.02006. It proves that the level floor(n/2)+1 SOS hierarchy is exact for maximizing a Hermitian quadratic over m-th roots of unity, and it gives a new binary reformulation for even m that uses mn/2 variables instead of mn. Both results look correct to me.

The SOS proof is a genuine generalization of the m=2 machinery in Fawzi-Saunderson-Parrilo. The signature-based grading is the right tool, and the chordal cover argument goes through. The one gap I found is small: the paper applies their Theorem 3 (which is Theorem 1 of [10]) to the chordal cover Γ built from the sets V_j, but never states that every maximal clique of Γ is contained in some V_j. Without that, the translation characters are not defined on maximal cliques. The missing claim is true and easy to prove: if a clique K has an element outside V_0, pick p with n_p ≥ k+1; any vertex with n_p ≤ k-2 cannot be adjacent to it, so the whole clique sits in V_p. This should be inserted after Proposition 2. It's a one-paragraph fix, not a flaw in the strategy.

The zonotope reformulation is the other solid contribution. Lemma 3 correctly identifies the cube vertices mapping to the roots of unity, and the inequality constraint in Theorem 5 is exactly the total-variation condition. The m=4 case reduces to a pure QUBO with 2n variables, which is a nice special case. The numerical experiments are honest but lightweight: no error bars, no seeds, and for the Potts runs only 15 instances per (m,n). I would not hang a strong claim about 'up to 10x' on those numbers alone, but the trend is plausible and the reformulation's variable count advantage is real.

The reliance on [10] is a dependency, not circularity: that theorem is published and independently proved. The paper states that Theorem 4 covers any function whose monomials span at most two variables each, and the quadratic case is the application.

Who should read this: anyone working on complex quadratic programming, Lasserre hierarchies for discrete sets, or exact reformulations for MIMO and Potts models. It deserves a serious referee. I'd recommend conditional acceptance, asking for the clique-containment lemma and better experimental reproducibility (seeds, error bars).

Regards,

Referee Report

1 major / 5 minor

Summary. The paper considers quadratic optimization over the complex m-th roots of unity, max z*Qz subject to z_i^m=1. Its first contribution is a sum-of-squares exactness result: every nonnegative quadratic form on this feasible set admits an SOS certificate supported on monomials whose signature entries are at most floor(n/2)+1, which makes the corresponding level of the Lasserre hierarchy exact. The proof generalizes the chordal-cover technique of Fawzi, Saunderson, and Parrilo. The second contribution is a binary reformulation: a standard one-hot reformulation with mn binary variables, and for even m a zonotope-based reformulation with mn/2 binary variables and n convex inequality constraints per variable block. Numerical experiments on MIMO detection and vector Potts model instances report speedups up to 10x compared with the standard reformulation.

Significance. If correct, the SOS result is a clean finite-convergence bound for a non-binary discrete optimization problem, matching the known binary result up to one level and extending a previously binary-only technique to complex roots of unity. The zonotope reformulation is a practically useful reduction in problem size, and the reported speedups, while from a modest experimental setup, are consistent and plausible. The proofs are mostly detailed and self-contained except for one missing containment step in the proof of Theorem 4. The paper does not ship code or detailed reproducibility data, but the numerical section is adequate for a first report.

major comments (1)

[Proof of Theorem 4] After Proposition 2 the proof states "Thus Theorem 3 holds with T=V_0=M(k)". Theorem 3 requires, for every maximal clique C of the chordal cover Gamma, a character chi_C such that chi_C C is contained in the target set V_0. The paper constructs chi_0,...,chi_{m-1} with chi_j V_j subset V_0, but it does not prove that every maximal clique of Gamma is contained in some V_j. This is not automatic from the text as written; the missing argument is load-bearing because without it the translation chi_C is not defined for all maximal cliques. The gap is easily repaired: if K is a clique of Gamma not contained in V_0, choose alpha in K outside V_0 and p with n_p(alpha) >= k+1; for any beta in K, the edge alpha beta lies in some C(V_l), and l cannot be 0 (since alpha is not in V_0) and cannot differ from p (since then n_p(alpha) >= k+1 and n_l(alpha) >= k-1 would force n >= 2k > n), so l=p and beta lies in V_p. Thus every maximal clique is contained in some V_j, and the proof can choose chi_C=chi_j for that j. I recommend inserting this argument explicitly before invoking Theorem 3.

minor comments (5)

[Section 6] The concluding paragraph says the hierarchy "converges at level ceil(n/2)", but Theorem 1 proves level floor(n/2)+1, which is one larger than ceil(n/2) for even n; the conclusion should be corrected to floor(n/2)+1.
[Theorem 4] In the statement of Theorem 4, each g_j is said to map B_m^n to R, but the certificate f=sum |g_j|^2 requires complex-valued g_j; this should be corrected to C-valued functions.
[Proof of Lemma 2] There is a typo: "the statment is trivial" should read "the statement is trivial".
[Figures 3 and 4] The numerical section reports only average runtimes; adding standard deviations, quartiles, or per-instance scatter would make the speedup claims more informative.
[Figure 4 caption] The caption says the panels are in "row major order", but the panels are actually ordered by increasing m; the wording should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 4 is a legitimate application of the general SOS theorem from [10], with a minor unproven maximal-clique containment that is a fillable proof gap, not a circular reduction.

full rationale

No significant circularity found. The central SOS theorem (Theorems 1 and 4) is proved by applying Theorem 3 of [10] (Fawzi, Saunderson, Parrilo), a published, parameter-free theorem about sum-of-squares certificates on finite abelian groups whose stated assumptions do not include the target result. Although the author sets overlap, this is independent support rather than a self-citation chain. The paper verifies the needed hypotheses: edge coverage of the Cayley graph by the clique cover (Proposition 1) and chordality of the graph Gamma via the running intersection property (Proposition 2), and it constructs characters chi_j with chi_j V_j subset of V0. There is an omitted proof step: Theorem 3 requires a character chi_C for every maximal clique C of Gamma, while the paper only defines chi_j for the generating sets V_j; one must show every maximal clique of Gamma is contained in some V_j. This is a genuine but easily repairable gap, not circularity, since it does not make the conclusion equivalent to an input by construction. The zonotope reformulation (Theorem 5, Lemma 3) is proved directly by trigonometric identities and is self-contained against the binary reformulation benchmarks. The numerical experiments compare runtime only; they involve no fitted parameters presented as predictions. The concluding sentence stating convergence at level ceil(n/2) is a minor inconsistency with Theorem 1's floor(n/2)+1, but it has no circularity content.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted, and no new physical or mathematical entities are postulated. The 'signature' grading and the zonotope lift are constructions, not invented entities in the sense of new postulates. The axioms are standard background used to build the proofs.

assumptions (3)

standard math Chordal decomposition theorem: positive semidefinite matrices with chordal sparsity patterns decompose as sums of PSD matrices supported on maximal cliques.
Invoked in Section 3 via Theorem 3 of [10]; standard result cited as [1, Theorem 2.3].
standard math Theorem 3 of [10]: For S a subset of characters, a chordal cover of the Cayley graph, and translations of maximal cliques by characters, any nonnegative function with support S admits an SOS certificate with translated support T.
Published theorem from [10], used as a black box; author overlap with the current paper is notable but the result is independently published.
standard math Cayley graph adjacency criterion: two monomials z^beta and z^gamma are adjacent in Cay(Ghat, S) iff beta and gamma differ in at most two coordinates.
Used in Lemma 2; direct from the definition of S as monomials with at most two non-identity exponents.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exact algorithms for quadratic optimization over roots of unity." pith.science (2026). https://pith.science/paper/5A7WTTHP

@misc{pith2026250802006,
  author       = {Pith},
  title        = {Pith review of: Exact algorithms for quadratic optimization over roots of unity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5A7WTTHP}},
  note         = {Machine review of arXiv:2508.02006}
}

abstract

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/2\rfloor+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.

Figures

Figures reproduced from arXiv: 2508.02006 by the authors.

**Figure 1.** A simplified Venn diagram for the sets V0, V1, . . . , V4 (m = 5) We now prove that the graph Γ we constructed is chordal. Proposition 2. Γ = (G, ˆ Sm−1 j=0 C(Vj )) is chordal. Proof of Proposition 2. To show Γ is chordal, note for any distinct p, q ∈ {1, . . . , m − 1} we have Vp ∩ Vq = {z α ∈ Gˆ : np(α) ≥ k −1, nq(α) ≥ k −1}. From np(α) ≥ k −1 we get that nj (α) ≤ n−np(α) ≤ n−k + 1 ≤ k for all j ̸= p and nq(α) ≥ k… view at source ↗

**Figure 2.** The zonotope reformulation for m = 6 and m = 8. The black dots are precisely Bm, which are the projection of the points ϵ satisfying the inequality constraint. The red dots are the projections of ek and −ek for k = 1, . . . m 2 An illustration of Lemma 3 is shown in [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Average running time of zonotope reformulation vs. basic reformulation on a MIMO detection [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Average running time of basic reformulation vs. zonotope reformulation on vector Potts model [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

5 extracted references · 4 canonical work pages

[1]

Agler, W

[1]J. Agler, W. Helton, S. McCullough, and L. Rodman,Positive semidefinite matrices with a given sparsity pattern, Linear algebra and its applications, 107 (1988), pp. 101–149. [2]F. Bach and A. Rudi,Exponential convergence of sum of squares hierarchies for trigonometric poly- nomials, SIAM Journal on Optimization, 33 (2023), pp. 2137–2159. [3]A. S. Bande...

work page 1988
[157]

[8]C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon,A min-max cut algorithm for graph partitioning and data clustering, in Proceedings 2001 IEEE international conference on data mining, IEEE, 2001, pp. 107–114. [9]I. Dunning, S. Gupta, and J. Silberholz,What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO, INFORMS Journal on C...

work page 2018
[2008]

[30]A. M.-C. So, J. Zhang, and Y. Ye,On approximating complex quadratic optimization problems via semidefinite programming relaxations, Mathematical Programming, 110 (2007), pp. 93–110. [31]M. Soltanalian and P. Stoica,Designing unimodular codes via quadratic optimization, IEEE Trans- actions on Signal Processing, 62 (2014), pp. 1221–1234. [32]I. W aldspu...

work page 2007
[2012]

Bolusani, M

[6]S. Bolusani, M. Besanc ¸on, K. Bestuzheva, A. Chmiela, J. Dionisio, T. Donkiewicz, J. van Doornmalen, L. Eifler, M. Ghannam, A. Gleixner, et al.,The SCIP optimization suite 9.0, arXiv preprint arXiv:2402.17702, (2024). [7]Cplex, IBM ILOG,V12. 1: User’s Manual for CPLEX, International Business Machines Corporation, 46 (2009), p

arXiv 2024
[2024]

Tightness and Equivalence of Semidefinite Relaxations for MIMO Detection

[13]T. Hrga and J. Povh,MADAM: a parallel exact solver for Max-Cut based on semidefinite program- ming and ADMM, Computational Optimization and Applications, 80 (2021), pp. 347–375. [14]Y. Huang and S. Zhang,Approximation algorithms for indefinite complex quadratic maximization problems, Science China Mathematics, 53 (2010), pp. 2697–2708. 13 [15]R. Jiang...

work page Pith review arXiv 2021

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Agler, W

[1]J. Agler, W. Helton, S. McCullough, and L. Rodman,Positive semidefinite matrices with a given sparsity pattern, Linear algebra and its applications, 107 (1988), pp. 101–149. [2]F. Bach and A. Rudi,Exponential convergence of sum of squares hierarchies for trigonometric poly- nomials, SIAM Journal on Optimization, 33 (2023), pp. 2137–2159. [3]A. S. Bande...

work page 1988

[2] [157]

[8]C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon,A min-max cut algorithm for graph partitioning and data clustering, in Proceedings 2001 IEEE international conference on data mining, IEEE, 2001, pp. 107–114. [9]I. Dunning, S. Gupta, and J. Silberholz,What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO, INFORMS Journal on C...

work page 2018

[3] [2008]

[30]A. M.-C. So, J. Zhang, and Y. Ye,On approximating complex quadratic optimization problems via semidefinite programming relaxations, Mathematical Programming, 110 (2007), pp. 93–110. [31]M. Soltanalian and P. Stoica,Designing unimodular codes via quadratic optimization, IEEE Trans- actions on Signal Processing, 62 (2014), pp. 1221–1234. [32]I. W aldspu...

work page 2007

[4] [2012]

Bolusani, M

[6]S. Bolusani, M. Besanc ¸on, K. Bestuzheva, A. Chmiela, J. Dionisio, T. Donkiewicz, J. van Doornmalen, L. Eifler, M. Ghannam, A. Gleixner, et al.,The SCIP optimization suite 9.0, arXiv preprint arXiv:2402.17702, (2024). [7]Cplex, IBM ILOG,V12. 1: User’s Manual for CPLEX, International Business Machines Corporation, 46 (2009), p

arXiv 2024

[5] [2024]

Tightness and Equivalence of Semidefinite Relaxations for MIMO Detection

[13]T. Hrga and J. Povh,MADAM: a parallel exact solver for Max-Cut based on semidefinite program- ming and ADMM, Computational Optimization and Applications, 80 (2021), pp. 347–375. [14]Y. Huang and S. Zhang,Approximation algorithms for indefinite complex quadratic maximization problems, Science China Mathematics, 53 (2010), pp. 2697–2708. 13 [15]R. Jiang...

work page Pith review arXiv 2021