一句话:证明两证明者 CSP 博弈的完美量子策略可由带额外经典通信的完美经典策略模拟,通信量受量子系统与 CSP 模板约束。
论文研究编码约束满足问题(CSP)的两证明者博弈中,完美量子策略与经典策略之间的模拟关系。方法上,作者首先组合刻画了带额外经典通信通道的完美经典策略,并对量子策略中的投影值测量引入几何舍入过程;关键中间步骤是证明当共享量子信息规模有界时,图的经典色数与量子色数之差有界。主要结果表明,任意完美量子策略都可由一个完美经典策略加额外经典通信来模拟,且该通信通道的大小仅依赖于共享量子系统的大小与 CSP 模板的结构参数。
We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on (i) the size of the shared quantum system used in the quantum strategy, and (ii) structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies.A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.