Finite de Finetti for convex bodies and Polynomial Optimization

By generalizing a quantitative monogamy-of-entanglement argument to arbitrary convex bodies via a new relative entropy notion, this paper establishes a finite de Finetti theorem that enables a convergent conic hierarchy with certified interior points for solving polynomial optimization problems with both equality and inequality constraints.

The Gist

Imagine you are trying to solve a very difficult puzzle. The puzzle involves finding the best possible arrangement of two complex shapes (called "convex bodies") to minimize a specific score, while making sure they fit together according to strict rules. This is a problem that shows up in advanced physics and mathematics, but it is notoriously hard to solve exactly.

This paper introduces a new, powerful strategy to solve these puzzles. It combines ideas from information theory (how we measure knowledge and connections) with optimization (finding the best solution).

Here is the breakdown of their approach using simple analogies:

1. The Problem: The "Impossible" Puzzle

Think of the shapes in the puzzle as "states" in a physical theory. You want to find the perfect pair of states that gives the lowest score. However, the rules are tricky:

• The shapes must fit together perfectly (equality constraints).
• They must also stay within certain boundaries (inequality constraints).
• Previous methods could only guarantee a solution if you waited forever (asymptotic convergence), or they couldn't handle the boundary rules properly.

2. The New Tool: The "De Finetti" Magic Trick

The authors use a mathematical concept called a de Finetti theorem. In everyday terms, imagine you have a huge bag of marbles. If you pull out a handful of marbles and they all look exactly the same (they are "symmetric" or "permutation invariant"), a de Finetti theorem tells you that you can treat them as if they were independent copies of a single, simpler marble, with only a tiny bit of error.

In this paper, the authors prove a finite version of this trick for general shapes. They show that if you have a complex, connected system that looks the same no matter how you shuffle its parts, you can approximate it with a much simpler, "separable" system (one where the parts aren't deeply entangled) with a known, small error margin.

3. The Secret Sauce: "Monogamy of Entanglement"

How do they know the error is small? They use a concept from information theory called Mutual Information.

• The Analogy: Imagine two friends, Alice and Bob, who share a secret. If Alice shares that secret with a third person, Charlie, she has to "split" her secret. She can't give the entire secret to both Bob and Charlie at the same time. This is called the "monogamy of entanglement."
• The Paper's Insight: The authors proved that in these general shapes, there is a strict limit to how much "secret information" (correlation) one part can share with many other parts simultaneously. Because this shared information is capped, the "error" in their approximation trick shrinks predictably as they add more layers to their calculation.

4. The Solution: A Ladder with a Safety Net

Using this insight, the authors built a hierarchy (a ladder of approximations).

• Rung 1: A rough guess.
• Rung 2: A better guess.
• Rung N: A very precise guess.

Why is this special?

• Guaranteed Speed: Unlike previous methods that just said "it gets better eventually," this paper gives a formula for exactly how fast it gets better. They can tell you: "If you go to rung 10, your answer will be within 5% of the truth."
• Handling Rules: It works even when the puzzle has strict "do not cross" lines (inequality constraints), which previous methods struggled with.
• Certified Answers: They provide a "rounding scheme." Think of this as a safety net. If the math gives you a point that is almost inside the allowed area, their method can nudge it slightly to make it a certified, valid point inside the area, while telling you exactly how much the score changed.

5. Real-World Application: The "Game"

The authors tested their method on a specific type of problem: Non-local games.

• The Scenario: Imagine two players, Alice and Bob, who are in different rooms. A referee asks them questions, and they must answer without talking to each other. They win if their answers match a specific pattern.
• The Goal: Find the maximum probability they can win using the laws of physics (General Probabilistic Theories).
• The Result: The authors showed that this game problem is just a specific type of their "puzzle." Their new method can now calculate the best possible winning score for these games with a guaranteed, finite-time accuracy.

Summary

The paper takes a complex, abstract problem in physics and math and solves it by proving that "correlations have a limit." By quantifying this limit, they created a step-by-step calculator that gets closer and closer to the perfect answer, with a built-in ruler that tells you exactly how close you are at every step. This works even when the rules of the game are strict and complex.

Technical Summary

Technical Summary: Finite de Finetti for Convex Bodies and Polynomial Optimization

Problem Statement
The paper addresses the fundamental challenge of solving multivariate polynomial optimization problems over general convex bodies, particularly those arising in General Probabilistic Theories (GPTs) and quantum information. Specifically, the authors consider the problem of minimizing a polynomial objective function $p$ over the product of two convex bodies $K_A \times K_B$, subject to both equality and inequality constraints defined by affine maps.

While approximation hierarchies exist for such problems (e.g., the Lasserre hierarchy, the DPS hierarchy, and the polarization hierarchy), significant gaps remain. The DPS hierarchy provides convergence guarantees only in an averaged sense (approximating convex mixtures rather than individual states) and fails to enforce constraints on individual variables. The polarization hierarchy enforces constraints individually but, for general state spaces, offers only asymptotic convergence guarantees without analytical bounds at finite levels. Furthermore, existing methods struggle to incorporate inequality constraints while maintaining finite-level convergence guarantees. The central open question is whether a convergent hierarchy exists that accommodates both local equality and inequality constraints with explicit, finite-level error bounds.

Methodology
The authors develop a novel framework that bridges information theory and conic optimization. Their approach relies on three main pillars:

1. Information-Theoretic Foundations in GPTs:
   The authors extend the concept of relative entropy to general convex bodies using an integral representation recently proposed for GPTs. This allows for the definition of mutual information $I(A:B)$ for states in the maximal tensor product of convex bodies. Unlike quantum theory, where mutual information is defined via Umegaki relative entropy, the general conic setting lacks a canonical definition; the authors adopt a variational definition based on the infimum of relative entropy over product states.

2. Quantitative Monogamy of Entanglement:
   A core technical result is the proof that mutual information in multipartite extensions is uniformly bounded. Specifically, for a state $x_{AB}$, the mutual information $I(A:B)$ is bounded by a constant $c(A)$ that depends solely on the geometry of the state space $K_A$ (specifically, a parameter $\lambda_A$ related to the relative interior of the cone), independent of the system $B$ or the number of extensions. This establishes a "monogamy-of-entanglement" relation for arbitrary convex bodies, quantifying the limited shareability of correlations.

3. Finite de Finetti Representation:
   Leveraging the uniform bound on mutual information and a chain rule argument applied after informationally complete measurements, the authors prove a finite de Finetti theorem. They show that any permutation-invariant state on an $n$-fold extension is close (in a specific norm) to a separable state. The approximation error scales as $O(1/\sqrt{n})$, with the constant depending on the dimensions and geometry of the underlying state spaces.

Key Contributions and Results

• Finite de Finetti Theorem for Convex Bodies (Theorem 3.7): The paper proves that for any state $x_{AB}$ in the $n$-extendible set of the maximal tensor product, there exists a separable state $\tilde{x}_{AB}$ such that $\|\tilde{x}_{AB} - x_{AB}\| \leq \frac{c(A,B)}{\sqrt{n}}$. This provides a quantitative characterization of the convergence from the maximal tensor product (entangled states) to the minimal tensor product (separable states) at finite $n$.
• Convergent Hierarchy with Inequality Constraints (Theorem 4.1): The authors construct a hierarchy of outer approximations for polynomial optimization problems subject to local equality and inequality constraints. They prove that the optimal value of the $n$-th level of this hierarchy converges to the true optimal value with an explicit error bound of $O(1/\sqrt{n})$. Crucially, this is the first framework to provide such finite-level guarantees for problems involving inequality constraints.
• Constructive Rounding Scheme (Theorem 4.2): The proof technique yields a constructive method to generate "interior" feasible points (separable states) that satisfy the local constraints. This allows for the certification of upper and lower bounds on the optimal value, effectively "sandwiching" the solution.
• Application to Non-Local Games: The authors reformulate the problem of determining the optimal value of a two-player non-local game in GPTs as a polynomial optimization problem with local constraints. This allows the application of their hierarchy to approximate the GPT value of such games with finite convergence guarantees.
• Conic Lifts (Proposition 4.3): The paper connects the optimization over convex bodies to the theory of conic lifts. It demonstrates that if the underlying convex bodies admit efficient conic lifts (e.g., to spectrahedra), the optimization hierarchy can be implemented at the level of the lifted cones, potentially reducing computational complexity.

Significance
The paper claims to resolve a long-standing open problem regarding the existence of convergent hierarchies for polynomial optimization over convex bodies that handle inequality constraints with analytical finite-level guarantees. By generalizing the monogamy-of-entanglement argument from quantum theory to arbitrary convex bodies, the authors establish a rigorous link between information-theoretic de Finetti arguments and the theory of conic optimization.

The significance lies in three areas:

1. Theoretical: It provides a quantitative expression of the monogamy of entanglement for general probabilistic theories, showing that $n$-extendible states converge to separable states with a specific rate.
2. Algorithmic: It overcomes the limitations of previous methods (DPS and polarization hierarchies) by offering finite-level convergence rates and handling inequality constraints, which are essential for many physical and optimization problems.
3. Practical: The constructive rounding scheme allows for the generation of certified feasible points, addressing the difficulty of finding interior solutions in general convex optimization.

The authors note that their approach currently requires constraints to exhibit a specific structural form (local constraints that can be separated into maps acting on individual systems), which is a limitation compared to the broader scope of the polarization hierarchy, though they argue this restriction is necessary for their proof technique. They identify the establishment of a chain rule for mutual information directly at the cone level (without measurement) as a key open problem for future work.