量子科技中心_量科网

该研究团队探究了量子分布式算法在消息复杂度（算法运行过程中通信总量）方面能超越经典分布式算法的程度。近期Dufoulon、Magniez和Pandurangan（PODC 2025）已证明在领导者选举和共识协议等任务中存在多项式量级的量子优势。本文则展示了一个基础性任务——在网络特定节点间路由信息——存在指数级的量子优势。研究人员通过Childs、Cleve、Deotto、Farhi、Gutmann和Spielman（STOC 2003）开创性工作中提出的「焊接树」结构证明：存在一种量子分布式算法，其将消息从图结构入口传输至出口所需的消息复杂度，比任何经典算法呈指数级降低。该量子算法基于Li、Li和Luo（SODA 2024）近期提出的焊接树上量子行走的「简明」实现方案。经典下界则是通过将Childs等人（STOC 2003）在查询复杂度上的下界结果「提升」至消息复杂度而获得。