近日，上海交通大学物理与天文学院金贤敏、唐豪课题组在综合性学术期刊Science Bulletin上以“TensorFlow Solver for Quantum PageRank in Large-Scale Networks”为题发表最新研究成果，展示了团队基于TensorFlow实现的目前最高效的大规模量子网页排序及量子随机行走求解器。Science Bulletin是由中国科学院和国家自然科学基金委员会共同主办、《中国科学》杂志社与Elsevier共同出版的自然科学综合性学术期刊，最新影响因子为9.511。
量子网页排序(Quantum PageRank)是一个基于量子随机行走（Quantum Stochastic Walk，QSW）的量子算法，前人的研究表明这一算法相较传统的谷歌PageRank有诸多优势，例如能够提高排序结果的准确性、减少不同节点排序结果的简并现象、突出网络中的二级节点等。运用经典计算机模拟各种量子随机行走是目前国际上广泛开展的研究方向。这涉及矩阵张量积的指数运算，计算所需要的空间、时间资源关于网络的节点数均呈约4次方增长。受制于此，目前往往只在十几个节点的小型网络进行原理性演示。然而，现实中的网页节点数目往往成百上千，量子随机行走模拟各种生物领域的开放量子系统也需要很大的哈密顿量演化空间，因此可实现尺寸的突破对于量子信息技术的实用化具有重要意义。
图 1 量子随机行走、矩阵张量积求解、及本求解器框架示意图
金贤敏、唐豪课题组经过反复研究论证，采用Runge-Kutta数值方法，使得空间资源的量级从节点数的4次方降为2次方，同时采用TensorFlow 进行GPU并行计算，明显地缩小了计算的时间量级。与目前常用的QSWalk软件求解同一个1000节点Erdos-Renyi网络的量子网页排序，本TensorFlow求解器仅需内存226MB及用时3.6s，分别仅为QSWalk的0.2%和0.05%。在笔记本电脑常见的6GB显存(RTX 2060 GPU)上可以完成高达6000节点网络的量子网页排序，而此前计算150-200个节点就将耗尽该电脑内存。这个突破极大地方便未来的相关研究。
图 2 本TensorFlow求解器与目前现有求解器求解Erdos-Renyi网络节点量子排序所需的
(a)内存 及(b)运算时间对比
在开发出了这款求解器后，团队又进一步在两个不同的场景应用了这一模拟器。第一个场景是在美国的航空网络中（922节点）进行QPR，这一模拟器的结果显示了QPR能更好地突出次级枢纽，并能对不同的节点给出更具差异化的结果，验证了前人的结论。
图 3 通过量子网页排序得出的美国十大主要机场。量子排序(QPR)相比于传统的网页排序(PR)，可以更加有效地区分主要节点和二级节点。
第二个场景是6层3叉地粘合树网络上的量子随机行走（2186个节点），用于分析经典随机扰动对于量子快速到达加速算法鲁棒性的影响。这一结果充分地展示了该求解器应对数千节点大规模网络的能力。值得一提的是，Runge-Kutta算法与量子随机行走随时间演化的过程相契合，因此该求解器只需要一次运算就可以求解出全过程中概率演化的情况，而在前人的求解器中，求解出每一个时间点的状态都需要调用一次求解器，因此本求解器对于量子随机行走时间演化过程的求解具有明显的优势。
图4 （a）层数为6，分叉数为3的粘合二叉树，共计有2186个节点（b）不同ω下到达效率随时间的变化关系。
论文的第一作者为物理与天文学院助理研究员唐豪博士及其指导的本科学生时若曦、何天深，通讯作者为物理与天文学院金贤敏教授。值得一提的是，学生加入这项研究初，时为上海中学高中学生，在金贤敏和唐豪老师指点下，不断加深对量子信息技术的学习和兴趣，曾以本工作的早期版本入选丘成桐中学科学奖计算机组半决赛。自2017年以年，金贤敏和唐豪老师持续为上海中学高中学生开展量子信息技术的科普教育。
研究团队感谢上海市科委重大项目和国家自然科学基金重点项目的雪中送炭，感谢国家重点研发计划、上海市教委的大力支持。
论文链接：https://www.sciencedirect.com/science/article/pii/S2095927320305880
微信公众号
