2026/02/23 by Ria Stevens, Fangshuo Liao, Barbara Su +3
#cs.DS #cs.LG #math.OC #quant-ph
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^⋆ ∈ ℂn × 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(‖H‖2 / δ⋆))-approximation guarantee, where δ⋆ 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/εr-1) candidates achieves a (1-ε)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 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 ≥ 106.