量子科技中心_量科网

该研究团队从最大化复值二次型的视角切入Max-3-Cut问题，证明了目标矩阵的低秩结构可被有效利用，从而产生了替代经典半定规划（SDP）松弛和启发式技术的新算法。研究人员提出了一种在规模为K的定义域上最大化这类二次型的算法，该算法通过枚举并评估一组𝒪(n²ʳ⁻¹)候选解来实现，其中n表示矩阵维度，r代表目标矩阵近似解的秩。该团队证明：当K=3（对应Max-3-Cut问题）且目标函数为低秩时，该候选解集必然包含精确最大值解；当目标函数是低秩矩阵的扰动形式时，算法仍能提供近似保证。这一理论构建衍生出一系列具有内在并行性且理论依据新颖的Max-3-Cut算法。大量实验结果表明，该方法在各类图结构上均能达到与现有算法相当的性能，同时具备高度可扩展性。