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.
Comments
36 + 13 pages; Julius A. Zeiss and Gereon Koßmann contributed equally to this work
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.
We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy , which has previously been introduced for the study of polynomial optimization problems over state spaces of C ⁎ ⁎ -algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories , which are studied as possible generalizations of quantum mechanics . We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem . A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
De Finetti theorems convert permutation symmetry into approximate mixtures of product states and thereby justify a wide range of reductions in classical and quantum statistics. In this work we study de Finetti hierarchies in which the feasible states are additionally constrained to be fixed points of quantum channels, a condition that subsumes invariance under arbitrary compact symmetry groups. Combining the mean-ergodic theorem with the structure theory of conditional expectations, we prove a tight bound on the entanglement-assisted classical capacity of the dual of a conditional expectation, block-wise distortion bounds for informationally complete measurements adapted to fixed point algebras, and an exact type-based refinement of the chain rule for permutation-invariant states. From these tools we derive several de Finetti theorems: a double-sided extension theorem with O(logn/n) convergence, an interpolation theorem whose dimension dependence is governed solely by the block structure of the fixed point algebras and which recovers the dimension-independent classical behavior for maximal tori, and a Bose-symmetric variant. Exploiting Schur-Weyl duality and Gelfand-Tsetlin bases, we further show that the rounding scheme producing certifiably good separable inner approximations for (constrained) separability problems can be implemented in time polynomial in 1/ε for fixed local dimensions, complementing the known efficient outer hierarchies. Applications to bilinear optimization under symmetries and to approximate quantum error correction are discussed.
Abstract We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D⊗E)] Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2) O ( d k / 2 ) to poly(d,k) poly ( d , k ) , where d denotes local dimension and k the number of copies.
De Finetti theorems show how sufficiently exchangeable states are well-approximated by convex combinations of independent identically distributed states. Recently, it was shown that in many quantum information applications, a more relaxed de Finetti reduction (i.e., only a matrix inequality between the symmetric state and one of the de Finetti forms) is enough and that it leads to more concise and elegant arguments. Here we show several uses and general flexible applicability of a constrained de Finetti reduction in quantum information theory, which was recently discovered by Duan, Severini, and Winter. In particular, we show that the technique can accommodate other symmetries commuting with the permutation action and permutation-invariant linear constraints. We then demonstrate that, in some cases, it is also fruitful with convex constraints, in particular separability in a bipartite setting. This is a constraint particularly interesting in the context of the complexity class QMA(2) of interactive quantum Merlin-Arthur games with unentangled provers, and our results relate to the soundness gap amplification of QMA(2) protocols by parallel repetition. It is also relevant for the regularization of certain entropic channel parameters. As an aside, we present an alternative way of attacking this problem, relying on an entanglement measure theory rather than the de Finetti approach. Finally, we explore an extension to infinite-dimensional systems, which usually pose inherent problems to de Finetti techniques in the quantum case.
Standard finite quantum de Finetti theorems approximate the k-system marginals of permutation-invariant states of n-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our k/n error bound in max-relative entropy improves on the previously best known k2/n scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels N(n):A⊗n→B⊗n, where dA=dimA, we prove that the k-system reduced channel is CP-dominated by a mixture of tensor-power channels with error O(k/n) and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of r defects, the representation error is at most poly(n)(2dA4k3/(nr2))(r+1)/2 and decays exponentially in n for a suitable choice of parameters r and k.
We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state ρN∈D(SymN(Cd)), there is a probability measure ν on the unit sphere such that ρN(2)−∫∣u⟩⟨u∣⊗2dν(u)1≤N−1d−1. By purification, the bosonic theorem also gives the optimal O(d/N) upper bound for arbitrary exchangeable states. These results settle the dimension dependence left open by Christandl, König, Mitchison, and Renner (CMP 2007). The proof casts de Finetti approximation as sum-of-squares rounding and applies the argmax method of Jeronimo, Wu, and Xu (manuscript 2026).
More generally, t-site marginals satisfy O(td/N) bosonic and O(td/N) permutation-invariant bounds. Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program and rounds an optimum by the argmax principle. The sharp bounds have several consequences. For every fixed ε∈(0,1), we construct a channel with input dimension D=exp(Oε(dlogd))=exp(o(d)) whose outputs are ε-close to separable states of local dimension d and whose image contains every such separable state, thereby refuting Watrous's disentangler conjecture. We also obtain deterministic exp(O(d/ε))-time algorithms for explicit Best Separable State without perfect completeness and for trace-distance separability testing.
Finally, spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance, with the optimal rate Θ(N−1/2) when the dimension may grow.