量子科技中心_量科网

交换性构件（commutativity gadgets）使得经典约束满足问题（CSPs）的NP难证明可推广至对应纠缠CSP的不可判定性证明。例如，Culf和Mastel的研究中已针对NP完全布尔CSP和三色问题实现了这一目标。但对于更大字母表上的许多CSP（包括当k≥4时的k色问题），目前尚不清楚交换性构件是否存在，或纠缠CSP是否可判定。本文通过扩展图的量子自同构群定义至CSP的量子自同态幺半群，首次证明了其存在性的已知障碍：若某CSP具有非经典的量子自同态幺半群，则不存在交换性构件。该结论特别表明，当k≥4时，k色问题不存在交换性构件。但该团队为k色问题的另一种非局部游戏呈现方式（预言机设置）构造了交换性构件。此外，研究人员通过扩展Schmidt关于图量子自同构群的结果，提出了判断量子自同态幺半群非经典性的易验证充分条件，并借此给出不支持交换性构件的CSP实例。研究还表明：预言机交换性构件的存在性在图的笛卡尔积运算下保持；对于不含四环的图，交换性构件与预言机交换性构件的存在性等价；奇数阶圈图和奇数图具有交换性量子自同态幺半群——这意味着它们可能存在交换性构件，该问题仍有待探索。