在复杂性理论中,间隙保护降低在研究近似硬度和分析多端交互式证明系统的相对复杂性方面起着至关重要的作用。 在量子设置中,具有纠缠的证明器的多端交互式证明系统对应于非本地游戏的间隙 promise 问题,而最近的结果 MIP^*=RE (Ji et al., arXiv:2001.04383)表明这些一般是不可决定的。 然而,MIP^*问题本身的相对复杂性仍然没有得到很好的理解,因为建立量子设置中的差距保护减少带来了新的挑战。 在本文中,我们引入了一个框架来研究这种减少,并用它来为独立游戏的自然类建立 MIP^*- 差距承诺问题的完成度。 在这样的游戏中,目标是确定给定的图形是否包含指定大小的独立集。 我们构建了具有恒定问题大小的独立游戏家族,其中间隙 promise 问题不可判定。 相比之下,同样的问题在经典设定中的多项式时间中是可以决定的。 为了进行我们的还原,我们建立了一个新的稳定性定理,这可能是独立的兴趣,使我们能够扰动几乎PVM的家族到真正的PVM。
在这个说明中,我们展示了如何扩展Rahaman引入的运算代数方法,以证明任何原始Schwarz地图的广义指数最多是2(D-1)^2,其中D是底层矩阵代数的维度。 这种不平等首先由Rahaman为Schwarz地图证明,这些地图都是统一的和痕迹保存的。 我们在这里表明,对于原始施瓦茨地图,统一性的假设是自动的(归一化),但是,一般来说,并非所有原始统一式施瓦茨地图都是痕迹保存。 因此,本说明的精确目的是展示如何将Rahaman的证明应用于任意的原始Schwarz地图。 作为这个定理的必然结果,我们表明任何原始2正图的广义的索引最多是2(D-1)^2,所以特别是这个绑定持有任意的原始完全正图。 我们简要讨论了这如何与Perez-Garcia,Verstraete,Wolf和Cirac关于矩阵产品状态的母公司Hamiltonians属性的猜想有关。
No more items to load.