首页
下载应用
提交文章
关于我们
🔥 热搜 🔥
1
上海
2
习近平
3
新疆
4
鄂州父女瓜
5
乌鲁木齐
6
疫情
7
H工口小学生赛高
8
习明泽
9
芊川一笑图包
10
印尼排华
分类
社会
娱乐
国际
人权
科技
经济
其它
首页
下载应用
提交文章
关于我们
🔥
热搜
🔥
1
百度
2
今日热点
3
微信公众平台
4
贴吧
5
opgg
6
dnf私服
7
百度贴吧
8
知乎
9
dnf公益服
10
百度傻逼
分类
社会
娱乐
国际
人权
科技
经济
其它
李光耀:过早翘起尾巴与美国对抗 是中国厄运的开始!
劲爆!为了姜萍两位女CEO互揭老底!
又一女明星涉毒被判刑!自称为了“刺激大脑”创作,央视网发文痛批
谁会想到,裁员会裁到总编辑头上
“我的存在就是低俗”!前一姐惨遭某音各种拿下!尺度太严不敢乱来!弹幕、礼物
生成图片,分享到微信朋友圈
查看原文
其他
首个超越经典算法的寻找MIS近似解的量子算法诞生
Original
FuLin Sun
量子客
2022-07-07
收录于合集 #科研学术
129个
最近,由美国石溪大学的研究生余泓烨,麻省理工教授和李政道研究所所长维尔切克(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
[2]https://mp.weixin.qq.com/s/YO1KhvY1F666Mck15EgFeQ
声明:此文出于传递更多信息。若有错误或侵权,请联系
延 伸 阅 读
01
初创公司用量子算法助力制药巨头进行药物研发
02
IBM使用高性能经典模拟为变分量子算法重设标准
03
新诞生的量子算法终于破解了非线性方程
04
突破性新算法 量子计算机的新应用指日可待
05
英特尔带来了抗得住量子计算机攻击的算法
06
首个用于表征大型量子计算机噪声的算法诞生
您可能也对以下帖子感兴趣
{{{title}}}
文章有问题?点此查看未经处理的缓存