量子科技中心_量科网

该研究团队探讨了带有建议的分布式唤醒问题，其中节点具备关于全局网络的初始知识。当敌手唤醒部分节点后，预言机为每个节点计算一个比特串（"建议"），目标在于高效唤醒所有休眠节点。研究人员首次提出了量子路由模型（由Dufoulon、Magniez和Pandurangan在PODC 2025会议上提出）中唤醒问题的消息复杂度上下界。具体而言，该团队给出了一种分布式建议方案：假设每个节点获得α比特建议，该方案能以高概率实现O(n^(3/2) * max{⌊(α−1)/2⌋,0} * log n)的消息复杂度完成全网唤醒。这一结果突破了传统（非量子）端口编号模型在稠密图场景下Ω(n^2 * 2^α)的已知下界。为完善算法研究，该工作同时给出了分布式量子算法的消息复杂度下界：通过结合查询复杂度模型中单比特描述符问题的下界结果，研究人员证明无建议时的量子消息复杂度下界为Ω(n^(3/2))，该下界与算法运行时间无关。在由敌手决定算法启动节点的设定下，多数重要图问题都隐含着唤醒问题的求解需求，因此相同下界也适用于单源广播和生成树构造等基础问题。