Quantum Communication Advantage for Leader Election and Agreement
This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies.
Authors
- Frédéric Magniez (ORCID: https://orcid.org/0000-0003-2384-9026)
- Fabien Dufoulon (ORCID: https://orcid.org/0000-0003-2977-4109)
- Gopal Pandurangan (ORCID: https://orcid.org/0000-0001-5833-6592)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Université Paris Cité (FR)
- University of Houston (US)
- Lancaster University (GB)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733509
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Agence Nationale de la Recherche
- QuantERA
- Army Research Office