Physics – Quantum Physics
Scientific paper
2003-06-29
Physics
Quantum Physics
10 pages, no figures, LaTeX
Scientific paper
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.
Kumar Somesh
Pal Sudebkumar Prasant
Singh Sudhir Kumar
No associations
LandOfFree
Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-32265