Speaker
Description
We give a converging semidefinite programming hierarchy of outer approximations for the set of quantum correlations of fixed dimension. Starting from the Navascués-Pironio-Acín (NPA) hierarchy for general quantum correlations, we identify additional semidefinite constraints for any fixed dimension, leading to analytical bounds on the convergence speed of the resulting hierarchy. Additionally, we provide an algorithm, built upon our hierarchy, able to compute additive approximations on the value of two-player free games with an assisting quantum system of fixed dimension, and a given number of questions |Q| and answers |A|. The computational time of our algorithm scales polynomially in |Q| and quasi-polynomially in |A|, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees were at best exponential in |Q||A|. To derive our analytical bounds on the convergence of the hierarchy, we make a connection to the quantum separability problem and employ, as our main technical tool, an improved multipartite quantum de Finetti theorem with linear constraints.
