Abstract
Leveraging a recently proposed notion of relative entropy in general probabilistic theories (GPT), we prove a finite de Finetti representation theorem for general convex bodies. We apply this result to address a fundamental question in polynomial optimization: the existence of a convergent outer hierarchy for problems with inequality constraints and analytical convergence guarantees. Our strategy generalizes a quantitative monogamy-of-entanglement argument from quantum theory to arbitrary convex bodies, establishing a uniform upper bound on mutual information in multipartite extensions. This leads to a finite de Finetti theorem and, subsequently, a convergent conic hierarchy for a wide class of polynomial optimization problems subject to both equality and inequality constraints. We further provide a constructive rounding scheme that yields certified interior points with controlled approximation error. As an application, we express the optimal GPT value of a two-player non-local game as a polynomial optimization problem, allowing our techniques to produce approximation schemes with finite convergence guarantees.
Introduction
Polynomial optimization—the task of finding the optimal value of a polynomial function subject to constraints—is a cornerstone of fields ranging from robotics and control theory to quantum information. However, when these problems are defined over "convex bodies" (general geometric shapes representing allowed states in a physical theory), they become notoriously difficult (NP-hard). This paper bridges the gap between abstract information theory and numerical optimization, providing a new mathematical toolkit for solving complex problems in General Probabilistic Theories (GPTs) and beyond.
Addressing Limitations in Polynomial Optimization
Existing tools, such as the Doherty-Parrilo-Spedalieri (DPS) hierarchy used in quantum mechanics, have faced significant hurdles. Most "de Finetti-based" methods struggle to handle inequality constraints effectively and often lack "finite-level" guarantees—meaning they cannot specify how close an approximation is to the true answer at a given step $n$. Furthermore, many theorems are restricted to specific shapes, such as the set of quantum states, rather than arbitrary convex bodies.
As illustrated in the comparison above, this work introduces a hierarchy that provides local constraint handling, quantified finite-level guarantees, and certified interior points with accuracy bounds, marking a significant advancement over prior polarization-based methods.
Methodology: Information Theory and de Finetti
The authors develop several novel mathematical structures to overcome these limitations:
- GPT Relative Entropy: They adopt a recently proposed integral representation of relative entropy and extend it to the GPT framework, allowing for the definition of "Mutual Information" in non-classical and non-quantum systems.
- Monogamy of Entanglement: They prove a monogamy relation for general cones, showing that a single system cannot be highly correlated with an infinite number of other systems.
- Finite de Finetti Theorem: This core contribution proves that if a state is $n$-extendible (meaning it can be viewed as a piece of a larger, symmetric $n$-party system), it is close to a "separable" (independent) state. Crucially, they provide a specific error bound that scales as $1/\sqrt{n}$.
- Convergent Conic Hierarchy: They build a sequence of increasingly accurate approximations for polynomial optimization that, unlike previous versions, incorporates local inequality constraints.
Key Results and Convergence Rates
The primary theoretical result (Theorem 3.7) establishes that for any $n$-extendible state $x_{AB}$, there exists a separable state $\tilde{x}_{AB}$ such that the distance between them is at most $c(A, B) / \sqrt{n}$. This leads to Theorem 4.1, which demonstrates that the gap between the approximate value ($p^{(n)}$) and the true optimal value ($p^*$) is bounded by $O(1/\sqrt{n})$.
Additionally, the authors provide a constructive rounding scheme that produces feasible points with an error that also scales with $1/\sqrt{n}$. This allows for "sandwiching" the true answer between an upper and lower bound, providing a clear "speed limit" for the hierarchy's convergence. The paper also demonstrates that finding the maximum winning probability in a "non-local game" is a specific application of these polynomial optimization techniques.
Discussion and Future Directions
While this work provides a major advancement, several open problems remain. The current proof relies on a "chain rule" for mutual information that requires a measurement step; finding a version that works directly on the "cones" would be a major theoretical breakthrough. Furthermore, while the hierarchy is mathematically convergent, the size of the optimization problems grows significantly with $n$, necessitating future work to make these hierarchies more computationally tractable for very large systems.
Summary updated