标题： 带有近似对 commuting 的证明者的交互式证明 显示英文标题

标题： Interactive proofs with approximately commuting provers

摘要： 承诺问题类$\MIP^*$可以通过多个纠缠证明者的交互式证明系统进行判定，为探索纠缠的非局部性质提供了复杂性理论框架。 对这个类的能力了解甚少。 建立上限的唯一提出的办法是基于 Pironio 等人和 Doherty 等人独立提出的半定程序层次结构。 这个层次结构收敛到一个值，该值仅在合理的但难以证明的数学猜想——Connes 嵌入猜想下与给定证明系统中证明者的最大成功概率一致。 未知收敛速度的任何界限。 我们引入了该层次结构的舍入方案，证明其第$N$层的任何解都可以映射到证明者的一种策略，在这种策略中，不同证明者相关的测量算子之间的对易子在算子范数下被限制为$O(\ell^2/\sqrt{N})$，其中$\ell$是每个证明者可能的答案数量。 我们的舍入方案促使引入了$\MIP^*$的一种变体，称为$\MIP_\delta^*$，其中只要不同证明者执行的操作的对易子范数最多为$\delta$，就要求声音性成立。 我们的舍入方案意味着上界 $\MIP_\delta^* \subseteq \DTIME(\exp(\exp(\poly)/\delta^2))$。 就下界而言，我们证明了 $\MIP^*_{2^{-\poly}}$，其完备性为 $1$且可靠性为 $1-2^{-\poly}$，包含 $\NEXP$。 $\MIP_\delta^*$与 $\MIPstar$的关系与近似对易的数学文献有关。 我们的舍入方案给出了一个初等证明，即强Kirchberg猜想意味着$\MIPstar$是可计算的。我们讨论了在设备无关密码学中的应用。 显示英文摘要

摘要： The class $\MIP^*$ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Little is known about the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. This hierarchy converges to a value that is only known to coincide with the provers' maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes' embedding conjecture. No bounds on the rate of convergence are known. We introduce a rounding scheme for the hierarchy, establishing that any solution to its $N$-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by $O(\ell^2/\sqrt{N})$ in operator norm, where $\ell$ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of $\MIP^*$, called $\MIP_\delta^*$, in which the soundness property is required to hold as long as the commutator of operations performed by distinct provers has norm at most $\delta$. Our rounding scheme implies the upper bound $\MIP_\delta^* \subseteq \DTIME(\exp(\exp(\poly)/\delta^2))$. In terms of lower bounds we establish that $\MIP^*_{2^{-\poly}}$, with completeness $1$ and soundness $1-2^{-\poly}$, contains $\NEXP$. The relationship of $\MIP_\delta^*$ to $\MIPstar$ has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that $\MIPstar$ is computable. We discuss applications to device-independent cryptography.