Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan · 2026
Read Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model by Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15529.txt.
Description
Dufoulon and colleagues design distributed quantum algorithms for leader election, broadcast, minimum spanning tree, and breadth-first search tree in arbitrary networks. They work in the quantum routing model from PODC 2025. Their message costs are near-optimal: roughly linear in node count for the first three tasks, and roughly the square root of nodes times edges for breadth-first search. Matching lower bounds show these costs can hardly be beaten in the model.
The gains over past work are sharp, since the prior leader election cost scaled with the square root of nodes times edges. Classical methods need at least on the order of edge count messages for all four tasks, so the quantum routes give a quadratic edge in general. Quantum walks built on electric networks supply the main tool, and the authors package that tool as a reusable frame for cutting communication in distributed quantum design.
Catalog record
| CREATOR | Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 164 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-15529