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:2610.20737

A constructive solution to the nnn-representability problem

Nicholas C. Rubin, A. Eugene DePrince

quant-phphysics.chem-phSubmitted Oct 14, 2026• Announced Oct 16, 2026• 0 citations• Revised Oct 21, 2026 (v2)
v1 · Oct 14, 2026v2 · Oct 21, 2026
arXivHTMLPDF

Abstract

We present an instantiation of the constructive solution to the fermionic quantum marginal problem by building the complete family of two-body witnesses at each level of a weighted sum-of-squares hierarchy. Our construction combines positive-semidefinite Gram matrices with explicit linear nullspace constraints that exactly cancel all higher-body contributions following a similar idea to the existing solution but made explicit in open source software. We demonstrate the weighted sum-of-squares construction numerically by solving the associated semidefinite program and recovering the exact ground-state energy of a Richardson Hamiltonian in the three-fermion sector. We further prove that higher-degree particle-number multipliers are unnecessary when the full sum-of-squares generating algebra is used.

Related papers

Quantum Many-Body Theory from a Solution of the N -Representability Problem

David A. Mazziotti

Here we present a many-body theory based on a solution of the N-representability problem in which the ground-state two-particle reduced density matrix (2-RDM) is determined directly without the many-particle wave function. We derive an equation that re-expresses physical constraints on higher-order RDMs to generate direct constraints on the 2-RDM, which are required for its derivation from an N-particle density matrix, known as N-representability conditions. The approach produces a complete hierarchy of 2-RDM constraints that do not depend explicitly upon the higher RDMs or the wave function. By using the two-particle part of a unitary decomposition of higher-order constraint matrices, we can solve the energy minimization by semidefinite programming in a form where the low-rank structure of these matrices can be potentially exploited. We illustrate by computing the ground-state electronic energy and properties of the H_{8} ring.

arXiv:2304.08570•Physical Review Letters•Apr 12, 2023•41 citations

Near-frustration-free electronic structure Hamiltonian representations and lower bound certificates

Nicholas C. Rubin, Guang Hao Low, A. Eugene DePrince

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.

quant-pharXiv:2602.05069•Journal of Chemical Theory and Computation•Feb 6, 2026•0 citations

Entanglement witnesses and semidefinite programming

Pablo A. Parrilo, Andrew C. Doherty, Federico M. Spedalieri

We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.

IEEE Conference on Decision and Control (CDC)•Jan 23, 2004•2 citations

Solving cluster moment relaxation with hierarchical matrix

Yi Wang, Huang, Rizheng, Yuehaw Khoo

Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy.

arXiv:2408.00235•Aug 1, 2024•0 citations

Exact quantum solutions of extraordinary N -body problems

D. Lynden-Bell, R. M. Lynden-Bell

The wave functions of boson and fermion gases are known even when the particles have harmonic interactions. Here we generalize these results by solving exactly the N–body Schrödinger equation for potentials V that can be any function of the sum of the squares of the distances of the particles from one another in three dimensions. For the harmonic case that function is linear in r2. Explicit N–body solutions are given when U(r) = –2Mh–2V(r) = 𝛇r–1 – 𝛇2r–2. Here M is the sum of the masses and r2 = 1/2 M–2ΣmImJ(xI – xJ)2. For general U(r) the solution is given in terms of the one– or two–body problem with potential U(r) in three dimensions. The degeneracies of the levels are derived for distinguishable particles, for bosons of spin zero and for spin 1/2 fermions. The latter involve significant combinatorial analysis which may have application to the shell model of atomic nuclei. For large N the fermionic ground state gives the binding energy of a degenerate white dwarf star treated as a giant atom with an N–body wave function. The N–body forces involved in these extraordinary N–body problems are not the usual sums of two–body interactions, but nor are forces between quarks or molecules. Bose–Einstein condensation of particles in three dimensions interacting via these strange potentials can be treated by this method.

arXiv:cond-mat/9904019•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Sep 8, 1999•11 citations

Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians

Igor Klep, Nando Leijenhorst, Victor Magron

The $k$-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For $k$-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most $C(k)ξ^{n,4}_{d+1}/n$, where $ξ^{n,4}_{d+1}$ is the smallest root of a Krawtchouk polynomial and $C(k)$ is independent of the number of qubits $n$ and the hierarchy level $d$. General $k$-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.

quant-pharXiv:2605.29959•May 29, 2026•0 citations
We present an instantiation of the constructive solution to the fermionic quantum marginal problem by building the complete family of two-body witnesses at each level of a weighted sum-of-squares hierarchy. Our construction combines positive-semidefinite Gram matrices with explicit linear nullspace constraints that exactly cancel all higher-body contributions following a similar idea to the existing solution but made explicit in open source software. We demonstrate the weighted sum-of-squares construction numerically by solving the associated semidefinite program and recovering the exact ground-state energy of a Richardson Hamiltonian in the three-fermion sector. We further prove that higher-degree particle-number multipliers are unnecessary when the full sum-of-squares generating algebra is used.
Here we present a many-body theory based on a solution of the N-representability problem in which the ground-state two-particle reduced density matrix (2-RDM) is determined directly without the many-particle wave function. We derive an equation that re-expresses physical constraints on higher-order RDMs to generate direct constraints on the 2-RDM, which are required for its derivation from an N-particle density matrix, known as N-representability conditions. The approach produces a complete hierarchy of 2-RDM constraints that do not depend explicitly upon the higher RDMs or the wave function. By using the two-particle part of a unitary decomposition of higher-order constraint matrices, we can solve the energy minimization by semidefinite programming in a form where the low-rank structure of these matrices can be potentially exploited. We illustrate by computing the ground-state electronic energy and properties of the H_{8} ring.
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.
We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.
Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy.
The wave functions of boson and fermion gases are known even when the particles have harmonic interactions. Here we generalize these results by solving exactly the N–body Schrödinger equation for potentials V that can be any function of the sum of the squares of the distances of the particles from one another in three dimensions. For the harmonic case that function is linear in r2. Explicit N–body solutions are given when U(r) = –2Mh–2V(r) = 𝛇r–1 – 𝛇2r–2. Here M is the sum of the masses and r2 = 1/2 M–2ΣmImJ(xI – xJ)2. For general U(r) the solution is given in terms of the one– or two–body problem with potential U(r) in three dimensions. The degeneracies of the levels are derived for distinguishable particles, for bosons of spin zero and for spin 1/2 fermions. The latter involve significant combinatorial analysis which may have application to the shell model of atomic nuclei. For large N the fermionic ground state gives the binding energy of a degenerate white dwarf star treated as a giant atom with an N–body wave function. The N–body forces involved in these extraordinary N–body problems are not the usual sums of two–body interactions, but nor are forces between quarks or molecules. Bose–Einstein condensation of particles in three dimensions interacting via these strange potentials can be treated by this method.
The kkk-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For kkk-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most C(k)ξd+1n,4/nC(k)ξ^{n,4}_{d+1}/nC(k)ξd+1n,4​/n, where ξd+1n,4ξ^{n,4}_{d+1}ξd+1n,4​ is the smallest root of a Krawtchouk polynomial and C(k)C(k)C(k) is independent of the number of qubits nnn and the hierarchy level ddd. General kkk-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.