【期刊】研究快讯 | 最大独立集的量子近似算法 | CPL

扫码阅读全文

原文已发表在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问题的是物理学家而不是数学家。

文章来源：“ChinesePhysicsLetters”公众号

Chinese Physics Letters (CPL)于1984年创办，是中国物理学会的旗舰期刊，也是我国目前唯一的快报类综合性物理学英文学术期刊。创刊三十多年来，CPL已经成为国内物理科研工作者发表重要原创科研成果的首选期刊之一，发表了国内著名物理学家的诸多代表作，包括“国家自然科学一等奖”、“未来科学大奖”、“中国科协优秀论文”、“中国物理学会最有影响力论文”等诸多奖项的研究成果。CPL是一本综合性物理学英文期刊，发文类型主要包括：1. Letters：报导高质量原创研究成果 ；2. Express Letters：PRL录用标准，发表周期7天左右；3.Views and Comments：权威专家点评，以CPL发表的最具重要性和创新性的工作为点评对象。
期刊专栏：https://www.koushare.com/periodical/periodicallist?ptid=103

——往期回顾——

为满足更多科研工作者的需求，蔻享平台开通了各科研领域的微信交流群。进群请添加微信18019902656（备注您的科研方向）小编拉您入群哟！
蔻享网站www.koushare.com已开通自主上传功能，期待您的分享！

---

欢迎大家提供各类学术会议或学术报告信息，以便广大科研人员参与交流学习。

联系人：李盼 18005575053（微信同号）戳这里，查看详情哟！