Quasi-polynomial time algorithms for free quantum games in bounded dimension

Understand

We give a converging semidefinite programming hierarchy of outer approximations for the set of quantum correlations of fixed dimension and derive analytical bounds on the convergence speed of the hierarchy.

• In particular, we give a semidefinite program of size $\exp(\mathcal{O}\big(T^{12}(\log^2(AT)+\log(Q)\log(AT))/\epsilon^2\big))$ to compute additive $\epsilon$-approximations on the values of two-player free games with $T\times T$-dimensional quantum assistance, where $A$ and $Q$ denote the numbers 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.