量子科技中心_量科网

该研究团队提出了针对任意网络架构下分布式计算基础问题（包括领导者选举、广播、最小生成树MST及广度优先搜索BFS树）的新型分布式量子算法。这些算法在Dufoulon、Magniez和Pandurangan[PODC 2025]提出的量子路由模型中，其通信（消息）复杂度达到（本质上的）最优水平。具体表现为：在领导者选举、广播和MST任务中算法消息复杂度为Õ(n)（Õ表示隐藏了多对数因子），BFS任务中为Õ(√mn)（n和m分别代表网络节点数与边数）。这些消息边界在量子路由模型中近乎紧致，研究人员通过展示近乎匹配的量子消息下界证明了这一点。该工作显著改进了Dufoulon等人[PODC 2025]的先前成果——其提出的同模型下分布式量子算法在领导者选举任务中消息复杂度为Õ(√mn)。研究结果表明，量子路由在分布式计算中具有超越经典方法的显著通信优势，因为即使对于随机蒙特卡洛算法，领导者选举、广播、MST和BFS的经典消息下界Ω(m)（最高可达Ω(n²)）已被Kutten等学者[JACM 2015]严格证明。这意味着对于这些基础问题，量子算法通常能在通信成本上获得平方级的优势。该团队设计分布式算法的核心技术工具是基于电网路的量子行走。研究人员构建了一个在分布式环境中利用量子行走设计高效通信的分布式量子算法框架，该框架可作为"黑箱"大幅降低通信成本，其方法论可能具有独立研究价值。此外，用于确立分布式量子消息下界的技术也可推广至其他问题领域。