{"id":"arxiv/2602.15529","url":"https://arxiv.org/abs/2602.15529","tags":["quant-ph","cs.DC"],"score":0,"title":"Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model","domain":"quant-ph","source":"arxiv","authors":["Fabien Dufoulon","Frédéric Magniez","Gopal Pandurangan"],"reviews":0,"subject":"quant-ph","summary":"We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is $\\tilde{O}(n)$ for leader election, broadcast, and MST, and $\\tilde{O}(\\sqrt{mn})$ for BFS ($n$ and $m$ are the number of nodes and edges of the network, respectively).…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-17","reactions":{}}