Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.20376

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Ria Stevens, Fangshuo Liao, Barbara Su, Thanasis Hadjidimoulas, Jianqiang Li, Anastasios Kyrillidis

cs.DScs.LGmath.OCquant-phSubmitted Feb 23, 2026• Announced Feb 25, 2026• Revised Jul 18, 2026 (v3)
v1 · Feb 23, 2026v2 · Apr 23, 2026v3 · Jul 18, 2026
arXivHTMLPDF

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(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 / δ^{\star}))$-approximation guarantee, where $δ^{\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(π/ 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$.

Related papers

Bounds for Random Binary Quadratic Programs

Karthik Natarajan, Dongjian Shi, Kim-Chuan Toh

In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.

SIAM Journal on Optimization•Jan 1, 2018•4 citations

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $r$, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time $O(m\cdot\mathrm{poly}(\log n,r,1/\varepsilon))$ given access to a sampling-based low-overhead data structure for the constraint matrices, where $\varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: $\bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},\ldots,A_τ$, we propose a procedure that gives a good approximation of $A=A_{1}+\cdots+A_τ$. $\bullet$ Symmetric approximation: we propose a sampling procedure that gives the \emph{spectral decomposition} of a low-rank Hermitian matrix $A$. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

arXiv:1901.03254•Leibniz international proceedings in informatics•Jan 10, 2019•4 citations

Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Chinonso Onah, Kristel Michielsen

When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.

quant-pharXiv:2608.01121•Aug 4, 2026•0 citations

Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity

Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun

In this paper, we study the discrete complex quadratic optimization problem, where the goal is to maximize a multivariate Hermitian quadratic objective function over complex m’th roots of unity. This problem is a generalization of the well-studied quadratic unconstrained binary optimization problem (QUBO), and has applications in signal processing, including in maximal likelihood estimation and multiple-input multiple-output detection, in addition to applications in statistical physics, in particular the computation of ground states of the Potts model. We study the sum-of-squares hierarchy for this problem, which is a sequence of semidefinite relaxations that is known to converge to the optimal solution after at most n steps. A previous result of Fawzi, Saunderson and Parrilo showed that in the the binary case ( $$m=2$$ ), at most $$\lceil n/2 \rceil $$ levels of the hierarchy are actually needed. In this paper we generalize this result and establish that the hierarchy converges after at most $$\lfloor n/2\rfloor +1$$ level for any $$m \ge 2$$ . Our proof generalizes the ideas used in the $$m=2$$ case, and is based on constructing chordal covers of appropriate Cayley graphs.

Optimization Letters•Mar 21, 2026•0 citations

Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences

Kinjal Basu, Ankan Saha, Shaunak Chatterjee

We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.

arXiv:1710.01163•neural information processing systems•Oct 2, 2017•5 citations

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming.

Nai-Hui Chia, Tongyang Li, Han Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: - Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ. - Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

Mathematical Foundations of Computer Science•Aug 1, 2020•10 citations
We study the problem of maximizing a complex-valued quadratic form over the KthK^{\text{th}}Kth roots of unity. We show that when the objective matrix Q⋆∈Cn×n\mathbf{Q}^\star \in \mathbb{C}^{n \times n}Q⋆∈Cn×n of the quadratic has rank rrr, the global maximizer belongs to a candidate set of size O(rn2r−1)O(rn^{2r-1})O(rn2r−1). This set can be constructed deterministically in O(rn2r+1)O(rn^{2r+1})O(rn2r+1) time by enumerating the vertices of a hyperplane arrangement in R2r.\mathbb{R}^{2r}.R2r. The algorithm is embarrassingly parallel; with~PPP processors, the time complexity drops to O(rn2r+1/P)O(r n^{2r+1}/P)O(rn2r+1/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-rrr matrix, we prove that applying our framework to a spectral truncation yields a multiplicative (1−O(∥H∥2/δ⋆))(1 - O(\left\|\mathbf{H}\right\|_2 / δ^{\star}))(1−O(∥H∥2​/δ⋆))-approximation guarantee, where δ⋆δ^{\star}δ⋆ denotes the eigengap of the underlying rank-rrr matrix and H\mathbf{H}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)S \geq O(1/\varepsilon^{r-1})S≥O(1/εr−1) candidates achieves a (1−ε)cos⁡2(π/K)(1-\varepsilon)\cos^2(π/ K)(1−ε)cos2(π/K)-approximation of the optimal rank-rrr solution with high probability. Crucially, this sample size is entirely independent of nnn, reducing the overall runtime to O(S⋅n2)O(S \cdot n^2)O(S⋅n2). 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≥106n \geq 10^6n≥106.
In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with mmm constraint matrices, each of dimension nnn and rank rrr, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log⁡n,r,1/ε))O(m\cdot\mathrm{poly}(\log n,r,1/\varepsilon))O(m⋅poly(logn,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε\varepsilonε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: ∙\bullet∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,AτA_{1},\ldots,A_τA1​,…,Aτ​, we propose a procedure that gives a good approximation of A=A1+⋯+AτA=A_{1}+\cdots+A_τA=A1​+⋯+Aτ​. ∙\bullet∙ Symmetric approximation: we propose a sampling procedure that gives the \emph{spectral decomposition} of a low-rank Hermitian matrix AAA. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.
When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.
In this paper, we study the discrete complex quadratic optimization problem, where the goal is to maximize a multivariate Hermitian quadratic objective function over complex m’th roots of unity. This problem is a generalization of the well-studied quadratic unconstrained binary optimization problem (QUBO), and has applications in signal processing, including in maximal likelihood estimation and multiple-input multiple-output detection, in addition to applications in statistical physics, in particular the computation of ground states of the Potts model. We study the sum-of-squares hierarchy for this problem, which is a sequence of semidefinite relaxations that is known to converge to the optimal solution after at most n steps. A previous result of Fawzi, Saunderson and Parrilo showed that in the the binary case ( m=2m=2m=2 ), at most ⌈n/2⌉\lceil n/2 \rceil ⌈n/2⌉ levels of the hierarchy are actually needed. In this paper we generalize this result and establish that the hierarchy converges after at most ⌊n/2⌋+1\lfloor n/2\rfloor +1⌊n/2⌋+1 level for any m≥2m \ge 2m≥2 . Our proof generalizes the ideas used in the m=2m=2m=2 case, and is based on constructing chordal covers of appropriate Cayley graphs.
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: - Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ. - Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.