删除或更新信息,请邮件至freekaoyan#163.com(#换成@)
南京大学马小松,祝世宁团队与合作者利用光量子游走实现有向图中心度排序
本站小编 Free考研考试/2021-02-15
图释:利用光量子游走实现四节点中心度排序,超越谷歌PageRank算法中心度排序的准确性。
随着量子信息科学的发展,量子游走逐渐成为实现超越经典信息处理效率的数据库搜索与量子计算的重要途径。近日,南京大学物理学院马小松教授,祝世宁院士团队利用宇称-时间对称的量子游走,成功实现了多个有向图的节点中心度排序,并且得到比谷歌PageRank算法更为准确的排序结果。该项成果为更多量子算法的实现奠定了基础,也为新颖经典算法提供了新思路。
“图”是由若干顶点及连接顶点的边所构成的结构。顶点代表事物,连接两顶点的边代表两个事物间的关系。图不单在数学、物理、化学、信息等众多科研领域中有着重要应用,图在我们日常生活也扮演着重要角色,比如互联网搜索引擎。谷歌搜索引擎的基石PageRank算法就是一种基于图的算法。它把互联网中的网页抽象成顶点,网页与网页之间的超链接抽象成边。通过每个顶点上边的指向与数目多少,谷歌判断该顶点所代表的网页的重要性。尽管PageRank算法在互联网时代大获成功,但它对某些特定图的顶点中心度无法给出准确判断。 如何实现快速精准的中心度排序是互联网搜索引擎亟待解决的难题之一。
量子游走是经典随机游走在量子力学中的拓展。粒子可以同时沿着不同路径游走形成叠加和干涉。这些独特的量子性质在量子信息中具有多种应用,特别为网络分析提供了比一些经典算法更优越的方案,比如对图中顶点中心度进行排序。在量子力学中,图可以对应成哈密顿量,然后通过计算该哈密顿量的演化得到图中顶点的中心度。由于传统量子游走的哈密顿量是幺正的,所对应的图是无向图。然而,大部分需要中心度排序的图都是有向图,它们对应的哈密顿量是非幺正的而且所有顶点的总概率不守恒。这对实现有向图上的量子游走造成了极大的挑战。
2017年,该团队通过理论分析发现可以通过宇称-时间对称的量子游走实现概率守恒的非幺正演化,从而实现有向图的中心度排序【Phys. Rev. A 96, 032305 (2017)】。该工作发表后引起多方关注,知名物理学杂志Nature Physics将该工作列为研究亮点【Nat. Phys. 13, 926 (2017)】。在最新工作中,该团队将理论与实际结合:以光量子的路径态和偏振态编码,利用线性光学器件构建演化算符,最后通过探测到的光子统计结果计算图中顶点的中心度。在初步实验的三顶点图中,团队通过高质量的实验结果,得到了与经典PageRank一致的排序结果。
然而这仅仅是这个任务的开始,更具挑战性的难题是:1. 相对于PageRank算法,量子游走的优势在哪里?2. 如何实现可拓展的量子游走算法对大规模图的中心度排序?为了回答第一个问题, 该团队进一步拓展单光子的纬度与线性光学网络的复杂度,在一个四顶点的图中,打破了顶点间的中心度简并,超越了PageRank排序的准确性。对于第二个问题的回答:量子游走信息处理能力会随着量子数量的增加而呈指数增长。该团队以双光子态作为输入,完成了一个九顶点有向图的中心度排序,从而证实了这种基于量子游走的中心度算法可以推广至具有更高顶点的复杂图。该工作通过实验展示了量子游走在网络分析中的优势,在中心度排序准确度上超越了广泛应用的PageRank算法,结合高效率的量子光源与高集成度微纳光学芯片,有望实现更复杂的网络的准确分析。
该成果近期发表在物理学知名期刊《Physical Review Letters》上,南京大学物理学院博士生吴通为文章第一作者,西澳大学Josh Izaac博士、Jingbo Wang教授、南京大学物理学院本科生黎子溪、博士生王凯、研究员陈召忠对本文有重要贡献。南京大学马小松教授为论文的通讯作者,祝世宁院士对本工作深入指导。该项研究得到南京大学卓越计划和国家重点研发计划、国家自然科学基金、中央高校基本科研业务费专项基金项目的资助。此项研究工作得到南京大学固体微结构国家重点实验室、物理学院和人工微结构科学与技术协同创新中心支持。
课题组链接:https://qoqi.nju.edu.cn
文章链接:https://link.aps.org/doi/10.1103/PhysRevLett.125.240501
前期工作:https://journals.aps.org/pra/abstract/10.1103/PhysRevA.96.032305
前期工作报道:https://www.nature.com/articles/nphys4291
相关话题/南京大学 工作
化院燕红教授课题组在电化学氧化巢式碳硼烷B-H键功能化方面的研究工作取得新进展
我校化学化工学院燕红教授课题组近期发展了一种电化学氧化的方法,成功地实现了巢式碳硼烷(7,8-C2B9H12?)B-H键选择性功能化。巢式碳硼烷在药物分子合成和发光材料制备等领域具有重要的价值,但是对巢式碳硼烷进行高效功能化的方法学研究却相对缺乏,尤其是高效、经济、环境友好且适用范围广泛的方法则更少 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15南京大学物理学院Craig D. Roberts教授发表核子结构方面重要综述
原子核由中子和质子(统称核子)组成,核子内部结构的相关研究一直是基础物理领域的前沿和热点,近日,南京大学物理学院CraigD.Roberts教授作为通讯作者的综述文章,详细解释了过去十年里人们对核子结构科学理解的发展和变化。从上个世纪流行的夸克模型至今,人们已经迈出了一大步:现在,核子波函数被视为描 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15南京大学余林蔚、徐骏教授课题组在柔性衬底上“激光-液滴”自加热驱动纳米线超高速生长集成新突破
在大面积柔性衬底上直接生长集成高品质晶硅纳米线沟道是突破高性能柔性电子逻辑、可穿戴传感和显示等应用的关键技术难点。然而,高品质晶体沟道的获得往往依赖高温生长过程(>800℃)--这恰恰是柔性聚合物衬底(熔点<150℃)所无法承受的!为此,南京大学电子科学与工程学院余林蔚教授、徐骏教授课题组基于自主创 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15物理学院程建春和邹欣晔课题组在声学拓扑晶体绝缘体方面的研究工作取得重要进展
我校物理学院声学研究所、人工微结构科学与技术协同创新中心程建春和邹欣晔课题组在声人工结构研究方面取得重要突破,基于声学拓扑晶体绝缘体,首次在不引入量子自旋霍尔效应的情况下,实现了具有"螺旋形"的高阶拓扑态。尽管传统声子晶体的缺陷态具有将声波局域在特定波导中传输的性质,但其强散射损耗和易被缺陷干扰的特 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15物理学院程建春和梁彬课题组在声超构神经网络方面 的研究工作取得重要进展
我校物理学院声学研究所、人工微结构科学与技术协同创新中心程建春和梁彬课题组在声人工结构研究方面取得重要突破,首次提出并在实验上实现了声超构材料构建的"类脑"人工结构,利用其完成了物体形状识别等机器学习任务。分析散射波来识别物体是波动物理研究中的关键问题之一,典型例子是声学领域中的医学超声检测、工业无 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15南京大学超导电子学研究所在人工自旋冰与超导异质结构器件研究中取得重要进展
第二类超导体中量子化磁通的运动行为对超导材料和器件的电磁输运性质起着关键作用。人为调控超导磁通量子的运动行为,不但可以有效提高超导体的临界电流密度,还可实现具有新功能的超导电子器件,如超导磁通整流器、磁通二极管等。以往的磁通量子调控手段往往缺乏原位可调性,极大限制了相应超导电子器件的应用。近日,南京 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15《Science》报道南京大学地理学科最新成果: 全球陆地生态系统二氧化碳施肥效应时空变化格局
南京大学国际地球系统科学研究所和地理与海洋科学学院张永光教授、居为民教授和陈镜明院士团队在全球变化和陆地碳循环领域取得重要进展。未来全球变暖的速率及陆地生态系统对全球变暖的响应是《Science》杂志列出的未来25年需要解决的125个重大科学问题之一。工业革命以来,人类活动造成大气中二氧化碳(CO2 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15“艺术教育与主题人物创作”研讨会在南京大学成功举行
2020年12月6日上午,由南京大学艺术学院、江苏省美术家协会共同主办的“艺术教育与主题人物创作”研讨会于南京大学仙林国际会议中心成功举办。中国美协副主席、江苏省美协主席周京新,江苏省油画学会主席陈世宁,中国美协油画艺委会副主任及国家重大题材美术创作艺委会委员、中国美术学院绘画学院院长何红舟,中国美 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15南京大学闻海虎团队和聂越峰团队合作在镍基新超导体机理研究中取得重要进展
铜氧化物超导体自从1986年被发现以来,其超导机理一直被本领域科学家高度关注。具有库仑排斥的两个电子,为什么在高达160多开尔文(约等于零下113度)下仍然能够相互吸引形成电子配对,并凝聚成为宏观的量子相干态,这是横亘在凝聚态物理领域的一个重大科学问题。2008年至今,铁基超导体家族的发现和壮大也为 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15南京大学丙交酯产业化项目成功打通工艺路线
2020年11月29日河南金丹乳酸科技股份有限公司(简称"金丹科技")发布公告,其控股子公司金丹生物新材料有限公司(简称"金丹生物")的丙交酯项目已于近期投料试车。截至目前,装置运行平稳,工艺路线打通,产品质量指标逐步提升。金丹生物将不断优化装置生产条件,完善工艺参数,逐步提高产能,保持整个系统的安 ...南京大学通知公告 本站小编 Free考研考试 2021-02-15