量子科技中心_量科网

量子计算在解决经典计算机无法处理的NP难组合（优化）问题方面具有显著潜力。挖掘这一潜力的方法之一是将组合问题重新表述为二次无约束二进制优化（QUBO）问题。该QUBO重构的解决方案可通过绝热量子计算设备或基于量子门的计算设备上运行的合适量子算法来实现。通常，通过对原问题目标函数中的约束违反情况进行适当惩罚，即可直接获得组合问题的QUBO重构。然而，为此确定紧致（即最小但充分）的惩罚系数对于在当前及近期的量子设备上求解重构后的QUBO问题至关重要。基于此，该研究工作聚焦于（加权）最大k割问题——这一推广了著名最大割问题的基础性组合问题，其应用范围广泛。研究人员针对最大k割问题的两种不同QUBO重构，提出了惩罚系数紧致性的闭式表征，其取值取决于问题定义图的顶点（加权）度数。这些发现为推动量子计算成为规模化解决组合问题的可行工具提供了新见解。该团队通过示例验证了理论结果，并利用量子计算机模拟器对所提QUBO重构方案进行了最大k割问题求解的基准测试。