原文已发表在CPL Express Letters栏目

Received 25 January 2021; 

online 26 February 2021

提出首个超越经典算法的寻找最大独立集近似解的量子算法。

找到一个图的最大独立子集（Maximum Independent Set, MIS）是一个NP-hard问题。图1中有8个顶点和7条边，它的MIS是{x2,x5,x6,x8}，含有4个顶点。有趣的是，数学家发现，即使是寻找MIS的近似解也是一个很难的问题。近似解是指尽力找一个独立集，越大越好，使得它的顶点数尽量接近MIS中的顶点数α(G)。已知最好的经典算法在多项式时间内找到的近似解，其顶点数平均只有α(G)的一半。对于有些类型的图，这个结论可以严格证明。

图1

最近，美国石溪大学的研究生余泓烨，麻省理工教授和李政道研究所所长维尔切克（Wilczek），和北京大学教授吴飙合作，提出了一个寻找MIS近似解的量子算法。这个算法能在二次多项式时间内找到非常好的MIS的近似解，其平均顶点数远超过α(G)的一半，非常接近α(G)。图2中的竖轴κ是近似解的顶点数和α(G)的比值，横轴是图的顶点数，图2中每一个点是1000张Erdos-Renyi图的平均结果。可以看到，当n>5时，量子算法得到的比率非常接近于1；最重要的是，随着图的顶点数n增大，这个比率一直不下降，非常稳定。两个经典算法Greeedy和Metropolis得到的比率首先小于量子结果，而且随着n增加会减少。这是MIS问题上第一个超越经典算法的量子算法。

图2

众所周知，NP-hard问题很难，一旦解决我们就能知道P是否等于NP。余泓烨、维尔切克和吴飙提出的量子算法是基于量子系统在简并子空间绝热演化的哈密顿算法，为理解这类问题的难度提供了一个崭新的物理视角，也为最终解决这类问题提供了新的思路。或许最终解决NP-hard问题的是物理学家而不是数学家。