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

CREATORFabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE164 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15529

Browse the full library · About the Tower of Babel