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

Global optimization of standard quadratic problems including parallel approaches

Volker Stix

Published Jan 1, 2000• 0 citations
OpenAlex

Related papers

Separable standard quadratic optimization problems

Immanuel M. Bomze, Marco Locatelli

Optimization Letters•Mar 25, 2011•5 citations

Asymptotic bounds on quantum partial search algorithm and its applications to parallel search

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang +1 more

Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.

quant-pharXiv:2603.01462•Physical Review A•Mar 3, 2026•2 citations

Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Wei Xia, Juan C. Vera, Luis F. Zuluaga

We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

arXiv:1511.02423•INFORMS journal on computing•Jul 19, 2019•55 citations

Parallel splitting method for large-scale quadratic programs

Matteo Vandelli, Francesco Ferrari, Daniele Dragoni

arXiv:2503.16977•Journal of Heuristics•Sep 20, 2026•6 citations

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Ria Stevens, Fangshuo Liao, Barbara Su +3 more

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$.

cs.DSCross-listedarXiv:2602.20376•Feb 25, 2026

Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables

Sunyoung Kim, Masakazu Kojima

We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients and the right-hand side value in integer is considered as a candidate for a valid inequality. The validity of the linear inequality is determined by solving a conic relaxation of a subproblem such as the doubly nonnegative relaxation, under the assumption that an upper bound for the unknown optimal value of the problem is available. Moreover, the candidates generated for the multiple cutting inequalities are tested simultaneously for their validity in parallel. Preliminary numerical results on 60 quadratic unconstrained binary optimization problems with a simple implementation of the successive cutting inequalities using an 8- or 32-core machine show that the exact optimal values are obtained for 70\% of the tested problems, demonstrating the strong potential of the proposed technique.

arXiv:2107.08665•Jul 19, 2021•0 citations
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .
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.
We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions ⊂{0,1}n\subset \{0, 1\}^n⊂{0,1}n, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients and the right-hand side value in integer is considered as a candidate for a valid inequality. The validity of the linear inequality is determined by solving a conic relaxation of a subproblem such as the doubly nonnegative relaxation, under the assumption that an upper bound for the unknown optimal value of the problem is available. Moreover, the candidates generated for the multiple cutting inequalities are tested simultaneously for their validity in parallel. Preliminary numerical results on 60 quadratic unconstrained binary optimization problems with a simple implementation of the successive cutting inequalities using an 8- or 32-core machine show that the exact optimal values are obtained for 70\% of the tested problems, demonstrating the strong potential of the proposed technique.