首个超越经典算法的寻找MIS近似解的量子算法诞生 / 开普饭

最近，由美国石溪大学的研究生余泓烨，麻省理工教授和李政道研究所所长维尔切克（Wilczek），和北京大学吴飙教授合作，提出了一个寻找MIS近似解的量子算法，这是首个提出超越经典算法的寻找最大独立集近似解的量子算法。

团队提出了一种基于量子非阿贝利绝热混合（non-Abelian adiabatic mixing）图的最大独立集的近似量子算法，在简并的基态的亚-希尔伯特空间中产生二次哈密顿量的量子退火。

对于稀疏和密集的随机图𝐺，数值模拟表明，该研究小组的算法平均能在低多项式时间内找到一个大小接近最大尺寸的独立集𝛼(𝐺)。相反，最好的经典算法在多项式时间内产生大小约为𝛼(𝐺)一半的独立集。

1. 最大独立子集

图1 | 最大独立子集说明（来源：CPL）

找到一个图的最大独立子集（Maximum Independent Set, MIS）是一个NP-hard问题。图1中含有8个顶点（顶点与颜色无关）和7条边，它的MIS是{x2,x5,x6,x8}，含有4个顶点。

数学家发现，即使是寻找MIS的近似解，也是一个很难的问题。近似解是指尽力找一个独立集，越大越好，使得它的顶点数尽量接近MIS中的顶点数α(G)。

2. 量子超经典一半

目前，已知最好的经典算法在多项式时间内找到的近似解，其顶点数平均只有α(G)的一半。对于有些类型的图，这个结论可以有的严格证明。

图2｜经典-量子对比（来源：CPL）

算法能在二次多项式时间内找到非常好的MIS的近似解，其平均顶点数远超过α(G)的一半，非常接近α(G)。图2中的竖轴κ是近似解的顶点数和α(G)的比值，横轴是图的顶点数，图2中每一个点是1000张Erdos-Renyi图的平均结果。

可以看到，当n>5时，量子算法得到的比率非常接近于1；最重要的是，随着图的顶点数n增大，这个比率一直不下降，非常稳定。

两个经典算法Greeedy和Metropolis得到的比率首先小于量子结果，而且随着n增加会减少，这是MIS问题上第一个超越经典算法的量子算法。如果大规模量子计算硬件可用，对于应用的开发，可能产生出新的解决方案。

引用：

[1]http://cpl.iphy.ac.cn/EN/article/downloadArticleFile.do?attachType=PDF&id=105854

声明：此文出于传递更多信息。若有错误或侵权，请联系

延伸阅读

01 初创公司用量子算法助力制药巨头进行药物研发

首个超越经典算法的寻找MIS近似解的量子算法诞生