研究快讯 | 最大独立集的量子近似算法

原文已发表在CPL Express Letters栏目

Received 25 January 2021; 

online 26 February 2021

EXPRESS LETTER

Quantum Algorithm for Approximating Maximum Independent Sets

Hongye Yu(余泓烨), Frank Wilczek, and Biao Wu(吴飙)

Chin. Phys. Lett. 2021, 38 (3): 030304

文章亮点

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

最大独立集的量子近似算法

研究背景

找到一个图的最大独立子集（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问题的是物理学家而不是数学家。

原文链接

HTML

PDF

研究快讯集锦

纳米金属玻璃颗粒的动力学转变现象

线性非厄米系统中受对称性保护的散射

PandaX-II对太阳轴子和中微子反常磁矩的搜寻

水二聚体中氢键作用的反协同效应

应变调控单层WSe2中的贝里曲率偶极矩、轨道磁化与非线性霍尔效应

量子传感可突破经典探测盲区

BaCuS2: 一种具有中等关联强度的超导体

单层有机-无机杂化卤化铅钙钛矿中的激子涡旋

反应率加权的多层核反应网络

X0(2900)和X1(2900)：强子分子态或者紧束缚四夸克态？

基于标准四电极法研究笼型富氢化物LaH10的高温超导电性

原子厚度磁性双层中的巨大自旋转移矩

双层CrI3铁磁耦合效应的增强

爱因斯坦热随机行走模型的重生：一个可以计算液体与非晶固体热导率的统一公式

双轨道量子反常霍尔模型

点此浏览所有Express Letters

CPL Express Letters栏目简介

为了保证重要研究成果的首发权和显示度，CPL于2012年6月开设了Express Letters栏目。此栏目发表速度快，学术质量高。截至2019年底，平均每篇被引用约20次，已经在国内物理学界建立起良好口碑与声望，来稿数量不断增加。