Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

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(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\|\mathbf{H}\right\|_2 / \delta^{\star}))$-approximation guarantee, where $\delta^{\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 \geq O(1/\varepsilon^{r-1})$ candidates achieves a $(1-\varepsilon)\cos^2(\pi / 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 \geq 10^6$.