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
v1 · Oct 14, 2026v2 · Oct 21, 2026
arXivHTMLPDF

Abstract

We present a solution to the fermionic quantum marginal problem by constructing 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, replacing the search for individual representability conditions with a systematic algebraic procedure. Beyond the completeness proof, we demonstrate the 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. These results establish a unified constructive framework for verifying the physicality of a candidate two-particle reduced density matrix through a complete characterization of all two-body witnesses.

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

A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding

Hoang Ta, Hoang Anh Tran

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

quant-pharXiv:2609.09629•Sep 10, 2026•0 citations
We present a solution to the fermionic quantum marginal problem by constructing 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, replacing the search for individual representability conditions with a systematic algebraic procedure. Beyond the completeness proof, we demonstrate the 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. These results establish a unified constructive framework for verifying the physicality of a candidate two-particle reduced density matrix through a complete characterization of all two-body witnesses.
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.
Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.