量子科技中心_量科网

量子优化算法本质上是概率性的，但通常被用于寻找单一的高质量解。本文则研究超图划分问题，其期望输出本身就是一种关于划分的概率分布。该团队引入了一种基于分布的视角来研究超图划分，该视角源于最大最小和最小最大目标（如公平割覆盖），并展示了这些目标如何与QAOA产生的测量分布自然对齐。为阐述这一框架，该团队提出了一个受劳动力调度启发的玩具问题——最大期望不平衡问题，其目标是使超边上的最坏期望不平衡最小化。随后，该团队开发了基于QAOA的量子求解器，通过量子态原生地表示分布解，同时构建了适用于标准QAOA和多目标QAOA的二次超图目标函数。这些公式将平衡超图划分、极化社区发现和分布公平性统一在一个量子优化框架下。作为对比，该团队提供了基于半定规划和超平面舍入的最优多项式时间经典近似算法。在真实世界和合成超图上的实验表明，低深度多角度QAOA能够在所提出的目标函数上超越这些经典近似基线，凸显了量子算法在解为分布而非单一划分的优化问题中的潜力。