Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks

Abstract

In this paper we show that sufficient multi-partite quantum entanglement helps in fair and unbiased election of a leader in a distributed network of processors with only linear classical communication complexity. We show that a total of $O(\log n)$ distinct multi-partite maximally entanglement sets (ebits) are capable of supporting such a protocol in the presence of nodes that may lie and thus be biased. Here, $n$ is the number of nodes in the network. We also demonstrate the difficulty of performing unbiased and fair election of a leader with linear classical communication complexity in the absence of quantum entanglement even if all nodes have perfect random bit generators. We show that the presence of a sufficient number $O(n/\log n)$ of biased agents leads to a non-zero limiting probability of biased election of the leader, whereas, the presence of a smaller number $O(\log n)$ of biased agents matters little. We define two new related complexity classes motivated by the our leader election problem and discuss a few open questions.

10 pages, no figures, LaTeX

References in corpus (4)

• Quantum Entanglement and Communication Complexity
• Multiparty Quantum Communication Complexity
• Introduction to Quantum Computation
• Characterizing the combinatorics of distributed EPR pairs for multi-partite entanglement

Cited by in corpus (7)

• Can quantum mechanics help distributed computing?
• Combinatorial Approaches in Quantum Information Theory
• The Computational Power of the W and GHZ states
• Computing on Anonymous Quantum Network
• What Can be Observed Locally? Round-based Models for Quantum Distributed Computing
• Can Quantum Communication Speed Up Distributed Computation?
• A Fast Exact Quantum Algorithm for Solitude Verification