Optimal Quantum de Finetti Theorems via Argmax Rounding

Fernando Granha Jeronimo, Pei Wu, Haochen Xu

Aug 3, 2026arXiv:2608.02590v1

quant-phcs.CC

Scorecard· 16/16

8.0/10 impact

A conceptually novel technique that simultaneously resolves the optimal dimension dependence of a foundational theorem and refutes/removes several long-standing conjectures and assumptions, with matching lower bounds.

Abstract

We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state $ρ_N\in D(\mathrm{Sym}^N(\mathbb C^d))$ , there is a probability measure $ν$ on the unit sphere such that $\left\| ρ_N^{(2)}-\int |u\rangle\langle u|^{\otimes 2}\,dν(u) \right\|_1 \le \frac{\sqrt{d-1}}{N-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(t\sqrt d/N)$ bosonic and $O (t d / 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 $\varepsilon\in(0,1)$ , we construct a channel with input dimension $D=\exp(O_\varepsilon(\sqrt d\log d))=\exp(o(d))$ whose outputs are $\varepsilon$ -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(\widetilde O(\sqrt d/\varepsilon))$ -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.

AI Impact Assessments

(1 models)

Scientific Impact Assessment

Core Contribution

This paper proves optimal finite quantum de Finetti upper bounds, resolving a dimension-dependence question left explicitly open by Christandl, König, Mitchison, and Renner (2007). The central result improves the two-site bosonic trace-norm error from the long-standing O(d/N) to the optimal O(√d/N), with matching lower bounds. The technical engine is "argmax rounding": the authors reformulate de Finetti approximation as the integrality gap of a symmetric-extension SDP, and via trace-norm duality replace the standard Haar-averaged universal rounding map by an *objective-dependent* extremal choice — rounding the top eigenvector of the SDP relaxation for a specific distinguishing witness. The √d saving arises precisely from passing from the Hilbert–Schmidt norm to the trace norm of a (d−1)×(d−1) matrix.

The sharp bound is leveraged into three advances on problems open for one to two decades: (1) refutation of Watrous's disentangler conjecture via an (ε,0)-disentangler of subexponential input dimension exp(O(√d log d)); (2) the first subexponential-time algorithm for explicit Best Separable State *without* perfect completeness, removing an assumption from Barak–Kothari–Steurer (2017); (3) the first subexponential trace-norm separability testing algorithm. Finally, a spectral-truncation argument yields the first dimension-free bosonic de Finetti theorem in Hilbert–Schmidt norm, at the optimal rate Θ(N^{−1/2}), a quantum analogue of the classical Diaconis–Freedman phenomenon.

Methodological Rigor

The paper is methodologically strong. The dual formulations (Lemma 2.1, 3.2) are exact, the argmax lemmas are derived from first- and second-order optimality conditions with clean variational arguments, and the integrality-gap bounds follow from Takagi/Schatten duality. Crucially, matching lower bounds are supplied in the appendix (rectangular Werner constructions, Jiang–Tacla–Caves-type pairs, and a representation-theoretic analysis of t-dependence via Jucys–Murphy elements and Schur–Weyl majorization), so optimality claims are substantiated rather than asserted. A caveat: the core argmax principle is imported from a companion "manuscript 2026" (JWX26) not available here, so full self-containment rests partly on unpublished work. The acknowledgment of GPT-assisted exploration plus Lean formalization is notable and, if the Lean formalization covers key lemmas, would strengthen confidence.

Potential Impact

The quantum de Finetti theorem is a foundational structural result feeding SDP/SoS hierarchies for separability, QMA(2) analysis, quantum cryptography, and mean-field/bosonic physics. Sharpening a two-decade-old constant is not cosmetic here: the √d improvement is *exactly* the factor that converts several exponential-in-dimension algorithms to subexponential ones, and refutes a conjectured exponential barrier. This makes the work likely to be cited and built upon across quantum complexity and quantum information theory. The disentangler refutation reshapes intuitions about QMA(2), even though it does not collapse QMA(2)=QMA. The dimension-free HS theorem opens a new line for polynomial-time Euclidean separability optimization.

Timeliness & Relevance

Highly timely: it directly targets named open problems (CKMR07 §II.C/V, Lewin–Nam–Rougerie Remark 2.2, Rougerie's dimension-free question, BKS17 Remark 1.4, the Watrous conjecture recorded in ABD⁺08). Concurrent work (Malavolta 2026 on Euclidean separability) confirms this is an active frontier. The unification of all these threads under one technique is a significant conceptual consolidation.

Strengths & Limitations

Strengths: (a) a genuinely new and conceptually clean rounding paradigm; (b) optimal bounds with matching lower bounds; (c) an unusually broad payoff — one core theorem resolves four distinct long-standing problems; (d) excellent organization (dependency diagrams, technical overview, self-contained proofs of most lemmas).

Limitations: (a) reliance on an unpublished companion manuscript for the foundational argmax method; (b) the disentangler result is structural, not an algorithmic collapse — QMA(2)=QMA remains open, and the strong-disentangler lower bound (Akibue–Kato–Tani) still stands; (c) the dimension-free HS theorem does not extend to arbitrary exchangeable states (purification does not contract HS norm), an acknowledged gap; (d) applications are complexity-theoretic and not near deployment. The unusual future arXiv date (2608.02590, 2026) is a metadata curiosity but does not bear on content quality.

Additional Observations

The argmax-as-integrality-gap reformulation is a transferable primitive: it reframes information-theoretic de Finetti bounds as TCS rounding questions, and its dimension-independence for classes with τ(M)=O(‖M‖∞) (Remark 3.6) suggests further exploitation. The representation-theoretic lower-bound machinery is also reusable. This is a "building block" paper whose technique may outlive any single result.

Rating:8/ 10

Significance 8.5Rigor 8.5Novelty 8.5Clarity 8

Generated Aug 4, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

8.0/10 impact