dorsal/arxiv
View SchemaMulti-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks
| Authors | Sudebkumar Prasant Pal, Sudhir Kumar Singh, Somesh Kumar |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0306195 |
| URL | https://arxiv.org/abs/quant-ph/0306195 |
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.
{
"annotation_id": "038b4f42-e0c9-4d0b-ae32-1a653fb02af4",
"date_created": "2026-03-02T18:01:59.865000Z",
"date_modified": "2026-03-02T18:01:59.865000Z",
"file_hash": "f55f615d5bded0c82a0d3d40a3b96abf7a4a1838d5114386698a2a8a788961a8",
"private": false,
"record": {
"abstract": "In this paper we show that sufficient multi-partite quantum entanglement\nhelps in fair and unbiased election of a leader in a distributed network of\nprocessors with only linear classical communication complexity. We show that a\ntotal of $O(\\log n)$ distinct multi-partite maximally entanglement sets (ebits)\nare capable of supporting such a protocol in the presence of nodes that may lie\nand thus be biased. Here, $n$ is the number of nodes in the network. We also\ndemonstrate the difficulty of performing unbiased and fair election of a leader\nwith linear classical communication complexity in the absence of quantum\nentanglement even if all nodes have perfect random bit generators. We show that\nthe presence of a sufficient number $O(n/\\log n)$ of biased agents leads to a\nnon-zero limiting probability of biased election of the leader, whereas, the\npresence of a smaller number $O(\\log n)$ of biased agents matters little. We\ndefine two new related complexity classes motivated by the our leader election\nproblem and discuss a few open questions.",
"arxiv_id": "quant-ph/0306195",
"authors": [
"Sudebkumar Prasant Pal",
"Sudhir Kumar Singh",
"Somesh Kumar"
],
"categories": [
"quant-ph"
],
"title": "Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks",
"url": "https://arxiv.org/abs/quant-ph/0306195"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d4c2f2d7-48c3-456f-a5b9-570c804a308d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}