Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

We study the problem of maximizing a complex-valued quadratic form over the Kth roots of unity. We show that when the objective matrix Q^star ∈ mathbbCn × n of the quadratic has rank r, the global maximizer belongs to a candidate set of size O(rn2r-1). This set can be constructed deterministically in O(rn2r+1) time by enumerating the vertices of a hyperplane arrangement in ℝ2r. The algorithm is embarrassingly parallel; with~P processors, the time complexity drops to O(r n2r+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|Hright|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 ≥ O(1/varepsilonr-1) candidates achieves a (1-varepsilon)cos2(π / 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 · n2). Computational experiments on synthetic benchmarks and large-scale graphs for textscMax-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 ≥ 106.