Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Abstract

We study the problem of maximizing a complex-valued quadratic form over the $K^{\text{th}}$ roots of unity. We show that when the objective matrix ${\mathbf{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(r{n}^{2r-1})$. This set can be constructed deterministically in $O(r{n}^{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({\Vert \mathbf{H}\Vert }_2/\hat{I}{´}^{\star }))$-approximation guarantee, where $\hat{I}{´}^{\star }$ denotes the eigengap of the underlying rank-$r$ matrix and $\mathbf{H}$ represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling $S\ge O(1/{\epsilon }^{r-1})$ candidates achieves a $(1-\epsilon ){\cos }^2(\ddot{I}€/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 \textsc{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\ge 10^6$.