Hamiltonian representations based on the sum-of-squares (SOS) hierarchy provide rigorous lower bounds on ground-state energies and facilitate the design of efficient classical and quantum simulation algorithms. This work presents a unified framework connecting SOS decompositions with variational two-particle reduced density matrix (v2RDM) theory. We demonstrate that the ``weighted'' SOS ansatz naturally recovers the dual of the v2RDM program, enabling the strict enforcement of symmetry constraints such as particle number and spin. We provide explicit SOS constructions for the Hubbard model and electronic structure Hamiltonians, ranging from spin-free approximations to full rank-2 expansions. We also highlight theoretical connections to block-invariant symmetry shifts. Numerical benchmarks on molecular systems and Iron-Sulfur clusters validate these near frustration-free representations, demonstrating their utility in improving spectral gap amplification and reducing block encoding costs in quantum algorithms.
The sum-of-squares method can give rigorous lower bounds on the energy of quantum Hamiltonians. Unfortunately, typically using this method requires solving a semidefinite program, which can be computationally expensive. Further, the typically used degree-
4 sum-of-squares (also known as the 2RDM method) does not correctly reproduce second order perturbation theory. Here, we give a general method, an analogue of Wigner's
2n+1 rule for perturbation theory, to compute the order of the error in a given sum-of-squares ansatz. We also give a method for finding solutions of the dual semidefinite program, based on a perturbative ansatz combined with a self-consistent method. As an illustration, we show that for a class of model Hamiltonians (with a gap in the quadratic term and quartic terms chosen as i.i.d. Gaussians), this self-consistent sum-of-squares method significantly improves over the 2RDM method in both speed and accuracy, and also improves over low order perturbation theory. We then explain why the particular ansatz we implement is not suitable for use for quantum chemistry Hamiltonians (due to presence of certain large diagonal terms), but we suggest a modified ansatz that may be suitable, which will be the subject of future work.
We develop MIQCR-FR, a framework for exact convex reformulation from facially reduced semidefinite relaxations of equality-constrained binary quadratic problems. Standard mixed-integer quadratic convex reformulation (MIQCR) uses dual multipliers of the original relaxation. Facial reduction (FR) reduces the semidefinite matrix order, but recovery of the original dual multipliers is not guaranteed in general. For this class of problems, we identify how retaining the linear equalities and their products with each binary variable enables this recovery. An established dual recovery formula gives an explicit extension of every feasible solution of the reduced dual to the original dual, preserving its bound. For approximate multiplier estimates, we give a spectral shift restoring dual feasibility and two constructions optimizing different bounds within a restricted multiplier family. Maximizing the dual bound yields a trust-region subproblem; maximizing the continuous MIQCR bound requires only a reduced eigenvalue calculation. The latter construction enforces convexity directly, rather than full dual feasibility. We implement it using multiplier estimates from the alternating direction method of multipliers (ADMM). On 431 instances from six problem families, the complete method certifies 296 optima, compared with 156 for the conic-bundle method MIQCR-CB and 187 for direct Gurobi under a common time budget.
In multiparameter quantum estimation, incompatible measurements can impose trade-offs among estimation errors. Understanding the precision attainable with a finite number of jointly measured copies is therefore important, but direct optimization becomes costly as the tensor product space grows exponentially. For independent and identically distributed (i.i.d.) copies, the quantum statistical model is invariant under permutations of the copies. We exploit this symmetry through Schur--Weyl duality to remove permutation multiplicity spaces while using their dimensions as weights. This gives a reduced statistical model equivalent to the original under arbitrary collective measurements. On this reduced model, we derive an exact conic formulation of the tight Cramér--Rao bound and a semidefinite program for its Nagaoka--Hayashi (NH) relaxation. For fixed single-copy dimension, the reduced operator representation grows polynomially rather than exponentially with the number of copies. To approximate the tight bound, we use an exact quadratic identity to correct finite-ray dual solutions and obtain rigorous upper and lower bounds. For fixed copy number and parameter dimension, sufficiently fine meshes admit feasible primal points, and dual solutions with bounded objective gaps have uniformly bounded compact-search radii. These results yield quadratic convergence in the projective covering radius. Numerical examples illustrate the quadratic scaling of the mesh correction term and the computational reach of the reduced NH formulation.
Abstract We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective functions and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
The SU
(N) matrix-model potential
V=−4g2∑I,JTr[XI,XJ]2, the interaction of the BFSS/BMN family, whose thermal large-
N states are dual to black holes, is diagonal in the coordinate basis and is compiled in the literature as a phase polynomial with
O(d2N4Q4) rotations per Trotter step. That cost is close to optimal for its gate class: we show that for a generic Trotter step the Walsh support
mmin lower-bounds both the rotation count and the two-qubit count of every circuit over
{CNOT,CZ,CPhase,RZZ,SWAP,X,Rz}, ancillas included, and we build a parity network attaining
1.01--
1.10mmin. Improvement therefore requires a gate outside that class, and the exact factorisation of
V into a sum of squared commutator entries supplies one in each era. For NISQ, Hadamard: each squared entry is added into a Fourier register and squared there,
Θ(d2N3Q3) two-qubit gates. For fault tolerance,
T: reversible arithmetic with one phase-gradient injection per squared entry,
Θ(d2N3Q2) T gates and no arbitrary-angle rotation. Both are built and verified. With a native
RZZ the NISQ circuit uses fewer two-qubit gates than every parity network from
Q=6 at SU(2) and
Q=2 at SU(5); the oracle beats a precision-matched Hamming-weight-phasing incumbent at every point built except the smallest, by up to
11.9× in T count and, at equal width,
25.5× in surface-code spacetime. An ablation with the same arithmetic but no factorisation costs up to
21× more and loses to that incumbent at
15 of
17 points, so the factorisation, not the arithmetic, produces the win. Both constructions survive the supersymmetric deformation to mini-BMN with fermions, and complete Trotter evolutions on a statevector simulator reproduce the exact product formula to
2×10−12.