Quantum Leader Election
arXiv:0910.4952
Abstract
Leader election between n parties is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon in 2007, and recently published and simplified in Aharonov et al in 2016. A protocol with linear number of coin flipping rounds is quite simple to achieve; We further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009: many typos are corrected, proofs are more rigorous and accurate, and the analysis of complexity is significantly tightened which gives a stronger result in terms of efficiency; The first protocol with linear number of rounds, was achieved independently also by Aharon and Silman in 2010.
arXiv comment15 pages, 3 figures
References in corpus (3)
Cited by in corpus (6)
- NetQASM -- A low-level instruction set architecture for hybrid quantum-classical programs in a quantum internet
- Connecting Quantum Cities: Simulation of a Satellite-Based Quantum Network
- Computing on Anonymous Quantum Network
- Composable Security for Multipartite Entanglement Verification
- A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias
- A Fast Exact Quantum Algorithm for Solitude Verification