量子科技中心_量科网

该研究团队提出了一种基于量子行走的新方法，用于解决最大度约束下的最小生成树问题。通过将经典最小生成树问题重构为图上的量子行走——其中顶点被编码为量子态，边权重经倒置运算定义修正哈密顿量——研究表明量子演化能通过最大化生成树上的累积转移概率（从而最大化香农熵）自然选出最小生成树。这项名为“带最大度约束的量子克鲁斯卡尔算法”的方法，在保持经典计算复杂度竞争力的同时，将量子资源需求显著降低至O(logN)量子比特。在多达10^4个顶点的全连接图上进行的数值实验证实：当最大度约束超过4时，该算法能输出总权重最优或接近最优的最小生成树；当约束值≤4时，虽存在次优解情况，但仍优于多种经典算法。这些成果为大规模图优化的量子-经典混合解决方案开辟了前景。