{"id":"arxiv/2602.20376","url":"https://arxiv.org/abs/2602.20376","tags":["cs.DS","cs.LG","math.OC","quant-ph"],"score":0,"title":"Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization","domain":"cs.DS","source":"arxiv","authors":["Ria Stevens","Fangshuo Liao","Barbara Su","Thanasis Hadjidimoulas","Jianqiang Li","Anastasios Kyrillidis"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-23","reactions":{}}