Optimal Quantum de Finetti Theorems via Argmax Rounding

This paper establishes optimal finite quantum de Finetti theorems, which quantify how closely symmetric quantum states can be approximated by mixtures of product states. The authors prove that for a bosonic state on N sites with local dimension d, the trace-distance error to a Hartree mixture is O(sqrt(d)/N). This result resolves a major open question regarding the optimal dimension dependence, improving upon previous bounds that were O(d/N).

The authors frame the de Finetti approximation problem as a sum-of-squares (SoS) rounding task. By applying the argmax method—a technique for rounding solutions to semidefinite programs—they derive sharp bounds for both bosonic and exchangeable states. The proof extends to t-site marginals, maintaining the optimal dependence on the local dimension and the number of sites, and provides a unified framework for analyzing two-sided Bose-symmetric extendible states.

The improved bounds have significant implications for quantum complexity theory, allowing the authors to resolve three long-standing problems:

1. Disentanglers: They refute Watrous’s disentangler conjecture by constructing a channel with subexponential input dimension that covers the set of separable states.
2. Best Separable State (BSS): They provide the first algorithm for the BSS problem that runs in subexponential time without requiring the perfect-completeness assumption.
3. Separability Testing: They introduce the first subexponential-time algorithm for trace-norm separability testing of explicitly given states.

These results demonstrate that the O(sqrt(d)/N) scaling is the critical threshold for moving several quantum-complexity problems from exponential to subexponential dependence on the local dimension.