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

Journal of Combinatorial Optimization

Bivalent quadratic optimization with sum-of-square of quadratic penalties

Tongli Zhang, Yong Xia

Published Aug 1, 2025• 0 citations
Publisher
DOI
10.1007/s10878-025-01339-7

Related papers

Unconstrained binary quadratic optimization

Erich Steiner, Th. M. Liebling, Komei Fukuda +1 more

•Jan 1, 2000•1 citation

Quadratic Optimization in 0–1 Variables

Alain Billionnet

This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.

Wiley eBooks•Jul 10, 2014•2 citations

Quadratic Optimization in 0–1 Variables

Alain Billionnet

Wiley eBooks•Jan 21, 2013•1 citation

A New Computational Model for the Spin-Free Sum-of-Squares Energy Bounds of Electronic Hamiltonian

Yuming Bao, Yancheng Wu, Dongdong Ge +1 more

Optimizing spin-free sum-of-squares (SOS) energy bounds for electronic Hamiltonians leads to semidefinite programs whose expanded size grows rapidly with the orbital dimension. We derive an exact reformulation of an established spin-free SOS model as a convex quadratic problem over a single symmetric matrix constrained between zero and the identity. Explicit recovery maps connect feasible quadratic-program iterates to certificates in the original SOS formulation, and identify the Frank--Wolfe gap with the separation between recovered primal and dual objectives. We implement the quadratic action through GPU-accelerated Coulomb contractions and solve the reformulated problem using a cached implementation of fully corrective Frank--Wolfe, referred to here as the dimension-reduced simplicial method (DRSM) that caches operator products and optimizes convex-combination weights in a small corrective quadratic program. Numerical experiments cover 65 FCIDUMP models, molecular geometries, and regular hydrogen rings, including original-coordinate recovery checks on nine instances and comparisons with FISTA and a boundary-point SDP solver. On eight H100 GPUs, a cold-start calculation for C$_{720}$ with 10,080 spatial orbitals reaches a freshly recomputed Frank--Wolfe gap of $8.82\times10^{-9}$ hartree in 5.02 hours. Full-space hydrogen-ring calculations reach 10,000 orbitals, with cyclic reduction providing further computational savings. These results show how exact reformulation, data structure exploitation and reuse of Coulomb actions make optimization of the selected large-scale SOS relaxation practical.

arXiv:2611.14319•Nov 10, 2026•0 citations

Binary Unconstrained Quadratic Optimization Problem

Gary A. Kochenberger, Fred Glover, Haibo Wang

Springer eBooks•Jan 1, 2013•9 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.

arXiv:2508.02006•Optimization Letters•Mar 21, 2026•1 citation
This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.
Optimizing spin-free sum-of-squares (SOS) energy bounds for electronic Hamiltonians leads to semidefinite programs whose expanded size grows rapidly with the orbital dimension. We derive an exact reformulation of an established spin-free SOS model as a convex quadratic problem over a single symmetric matrix constrained between zero and the identity. Explicit recovery maps connect feasible quadratic-program iterates to certificates in the original SOS formulation, and identify the Frank--Wolfe gap with the separation between recovered primal and dual objectives. We implement the quadratic action through GPU-accelerated Coulomb contractions and solve the reformulated problem using a cached implementation of fully corrective Frank--Wolfe, referred to here as the dimension-reduced simplicial method (DRSM) that caches operator products and optimizes convex-combination weights in a small corrective quadratic program. Numerical experiments cover 65 FCIDUMP models, molecular geometries, and regular hydrogen rings, including original-coordinate recovery checks on nine instances and comparisons with FISTA and a boundary-point SDP solver. On eight H100 GPUs, a cold-start calculation for C720_{720}720​ with 10,080 spatial orbitals reaches a freshly recomputed Frank--Wolfe gap of 8.82×10−98.82\times10^{-9}8.82×10−9 hartree in 5.02 hours. Full-space hydrogen-ring calculations reach 10,000 orbitals, with cyclic reduction providing further computational savings. These results show how exact reformulation, data structure exploitation and reuse of Coulomb actions make optimization of the selected large-scale SOS relaxation practical.
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.