Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

We study the problem of maximizing a complex-valued quadratic form over the K^{th} roots of unity. We show that when the objective matrix Q^\star \in \mathbb{C}^{n \times n} of the quadratic has rank r, the global maximizer belongs to a candidate set of size O(rn^{2r-1}). This set can be constructed deterministically in O(rn^{2r+1}) time by enumerating the vertices of a hyperplane arrangement in \mathbb{R}^{2r}. The algorithm is embarrassingly parallel; with P processors, the time complexity drops to O(r n^{2r+1}/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-r matrix, we prove that applying our framework to a spectral truncation yields a multiplicative (1 - O(\left|H\right|_2 / δ^{\star}))-approximation guarantee, where δ^{\star} denotes the eigengap of the underlying rank-r matrix and H represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling S \geq O(1/\varepsilon^{r-1}) candidates achieves a (1-\varepsilon)\cos^2(π/ K)-approximation of the optimal rank-r solution with high probability. Crucially, this sample size is entirely independent of n, reducing the overall runtime to O(S \cdot n^2). Computational experiments on synthetic benchmarks and large-scale graphs for Max-3-Cut confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where n \geq 10^6.