论文标题
在有限维度中的免费量子游戏的准多项式时间算法
Quasi-polynomial time algorithms for free quantum games in bounded dimension
论文作者
论文摘要
我们为固定尺寸的量子相关性集合提供了外部近似值的收敛半决赛编程层次结构，并在层次结构的收敛速度上得出了分析界限。特别是，我们给出一个半尺寸$ \ exp（\ nathcal {o} \ big（t^{12}（\ log^2（\ log^2（at）+\ log（q） $ a $和$ q $分别表示游戏的答案和问题。对于固定尺寸$ t $，这以$ q $的多项式缩放，而准元素则以$ a $的形式缩放，从而改善了先前已知的近似算法，其中最差的运行时保证最多可以在$ q $和$ a $中获得指数。为了证明，我们与量子可分离性问题建立联系，并采用线性约束的改进的多部分量子finetti定理。我们还得出了一个信息完整的测量，该测量可最大程度地减少相对于量子侧信息的区分性损失，这可能具有独立的关注。
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))/ε^2\big))$ to compute additive $ε$-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. We also derive an informationally complete measurement which minimises the loss in distinguishability relative to the quantum side information - which may be of independent interest.
