paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Classical Simulation of Quantum CSP Strategies

量子 CSP 策略的经典模拟
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 1/10 · 该论文研究量子 CSP 博弈中完美量子策略的经典模拟,属于量子复杂性、逻辑与组合数学方向,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关联。引用 0 inbox
Demian Banakh, Lorenzo Ciardo, Marcin Kozik, Jan Tułowiecki
crossref: 2026-09-12

AI 速览

一句话:证明两证明者 CSP 博弈的完美量子策略可由带额外经典通信的完美经典策略模拟,通信量受量子系统与 CSP 模板约束。

论文研究编码约束满足问题(CSP)的两证明者博弈中,完美量子策略与经典策略之间的模拟关系。方法上,作者首先组合刻画了带额外经典通信通道的完美经典策略,并对量子策略中的投影值测量引入几何舍入过程;关键中间步骤是证明当共享量子信息规模有界时,图的经典色数与量子色数之差有界。主要结果表明,任意完美量子策略都可由一个完美经典策略加额外经典通信来模拟,且该通信通道的大小仅依赖于共享量子系统的大小与 CSP 模板的结构参数。

问题
完美量子策略能否在编码 CSP 的两证明者博弈中被经典策略模拟,以及所需额外经典通信量如何受共享量子系统和 CSP 结构限制。
方法
通过带额外通信的完美经典策略的组合刻画,以及对量子投影值测量的几何舍入;关键步骤是证明有界量子共享信息下经典色数与量子色数之差有界。
评估
以数学证明和构造性模拟给出定量界:额外经典通信通道的大小仅依赖共享量子系统大小与 CSP 模板结构参数。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot8648,
  title = {Classical Simulation of Quantum CSP Strategies},
  author = {Demian Banakh and Lorenzo Ciardo and Marcin Kozik and Jan Tułowiecki},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00035}
}