该研究团队无条件证明了：在度数为常数的无权图上，计算量子最大割问题的常数乘性近似是NP困难的。该证明分为两个阶段：首先通过通用归约方法，将计算量子问题最优值转化为计算积态空间上的最优值；随后构建了从经典最大割问题到积态量子最大割（Product-QMC）的近似保持归约。
具体而言，在第二阶段中，研究人员构造了从Max-Cutk（带秩k约束的最大割问题）到Max-Cutk+1的PTAS归约，其中经典最大割与积态量子最大割分别对应Max-Cut1和Max-Cut3。由此证明：对于所有常数k，Max-Cutk问题均属于APX完全类。
作者所在地：
VIP可见
作者单位：
VIP可见
页数/图表：
登录可见
提交arXiv：
2025-10-09 09:32
