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

Simple item page
dc.creatorPal, Sudebkumar Prasant
dc.creatorSingh, Sudhir Kumar
dc.creatorKumar, Somesh
dc.date2003-06-29
dc.date.accessioned2026-07-07T06:07:12Z
dc.date.available2026-07-07T06:07:12Z
dc.descriptionIn 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.
dc.description10 pages, no figures, LaTeX
dc.identifierhttps://arxiv.org/abs/quant-ph/0306195
dc.identifierhttp://arxiv.org/abs/quant-ph/0306195
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91210
dc.subjectQuantum Physics
dc.titleMulti-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks
dc.typetext

Files

Collections

arXiv