Approximating fixed size quantum correlations in polynomial time

Abstract:We show that $\varepsilon$-additive approximations of the optimal value of fixed-size two-player free games with fixed-dimensional entanglement assistance can be computed in time $\mathrm{poly}(1/\varepsilon)$. This stands in contrast to previous analytic approaches, which focused on scaling with the number of questions and answers, but yielded only strict $\mathrm{exp}(1/\varepsilon)$ 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 $\mathrm{poly}(1/\varepsilon)$, thereby enabling efficient $\varepsilon$-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.

arXiv:2507.12302 [quant-ph]

(or arXiv:2507.12302v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2507.12302 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.