2026-08-15T10:29:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14151 2024-03-06T10:53:36Z ddc:004 open_access

Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension Jee, Hyejung H. Sparaciari, Carlo Fawzi, Omar Berta, Mario non-local game semidefinite programming quantum correlation approximation algorithm Lasserre hierarchy de Finetti theorem In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hyejung H. Jee and Carlo Sparaciari and Omar Fawzi and Mario Berta 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.82 urn:nbn:de:0030-drops-141514 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.82 eng https://creativecommons.org/licenses/by/4.0/legalcode