南京大学马小松，祝世宁团队与合作者利用光量子游走实现有向图中心度排序
图释：利用光量子游走实现四节点中心度排序，超越谷歌PageRank算法中心度排序的准确性。
随着量子信息科学的发展，量子游走逐渐成为实现超越经典信息处理效率的数据库搜索与量子计算的重要途径。近日，南京大学物理学院马小松教授，祝世宁院士团队利用宇称-时间对称的量子游走，成功实现了多个有向图的节点中心度排序，并且得到比谷歌PageRank算法更为准确的排序结果。该项成果为更多量子算法的实现奠定了基础，也为新颖经典算法提供了新思路。
"图"是由若干顶点及连接顶点的边所构成的结构。顶点代表事物，连接两顶点的边代表两个事物间的关系。图不单在数学、物理、化学、信息等众多科研领域中有着重要应用，图在我们日常生活也扮演着重要角色，比如互联网搜索引擎。谷歌搜索引擎的基石PageRank算法就是一种基于图的算法。它把互联网中的网页抽象成顶点，网页与网页之间的超链接抽象成边。通过每个顶点上边的指向与数目多少，谷歌判断该顶点所代表的网页的重要性。尽管PageRank算法在互联网时代大获成功，但它对某些特定图的顶点中心度无法给出准确判断。 如何实现快速精准的中心度排序是互联网搜索引擎亟待解决的难题之一。
量子游走是经典随机游走在量子力学中的拓展。粒子可以同时沿着不同路径游走形成叠加和干涉。这些独特的量子性质在量子信息中具有多种应用，特别为网络分析提供了比一些经典算法更优越的方案，比如对图中顶点中心度进行排序。在量子力学中，图可以对应成哈密顿量，然后通过计算该哈密顿量的演化得到图中顶点的中心度。由于传统量子游走的哈密顿量是幺正的，所对应的图是无向图。然而，大部分需要中心度排序的图都是有向图，它们对应的哈密顿量是非幺正的而且所有顶点的总概率不守恒。这对实现有向图上的量子游走造成了极大的挑战。
2017年，该团队通过理论分析发现可以通过宇称-时间对称的量子游走实现概率守恒的非幺正演化，从而实现有向图的中心度排序【Phys. Rev. A 96, 032305 (2017)】。该工作发表后引起多方关注，知名物理学杂志NaturePhysics将该工作列为研究亮点【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