2025/07/16 by Julius A. Zeiss, Zeiss, Julius A., Gereon Koßmann +5 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.2507.12302
58 pages + 54 pages supplementary material, 5 figures
openalex publication_date 2025/07/16 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28 · arxiv created 2026/08/05 · arxiv updated 2026/08/06
We show that ε-additive approximations of the optimal value of fixed-size two-player free games with fixed-dimensional entanglement assistance can be computed in time poly(1/ε). This stands in contrast to previous analytic approaches, which focused on scaling with the number of questions and answers, but yielded only strict exp(1/ε) guarantees. Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems. These results give rise to semidefinite programming (SDP) outer hierarchies for approximating the entangled value of such games. By employing representation-theoretic symmetry reduction techniques, we demonstrate that these SDPs can be formulated and solved with computational complexity poly(1/ε), thereby enabling efficient ε-additive approximations. In addition, we introduce a measurement-based rounding scheme that translates the resulting outer bounds into certifiably good inner sequences of entangled strategies. These strategies can, for instance, serve as warm starts for see-saw optimization methods. We believe that our techniques are of independent interest for broader classes of constrained separability problems in quantum information theory.