dorsal/arxiv
View SchemaThe Computational Power of the W and GHZ states
| Authors | Ellie D'Hondt, Prakash Panangaden |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0412177 |
| URL | https://arxiv.org/abs/quant-ph/0412177 |
| Journal | Journ. Quantum Inf. and Comp., vol. 6(2), pages 173-183, 2005 |
Abstract
It is well understood that the use of quantum entanglement significantly enhances the computational power of systems. Much of the attention has focused on Bell states and their multipartite generalizations. However, in the multipartite case it is known that there are several inequivalent classes of states, such as those represented by the W-state and the GHZ-state. Our main contribution is a demonstration of the special computational power of these states in the context of paradigmatic problems from classical distributed computing. Concretely, we show that the W-state is the only pure state that can be used to exactly solve the problem of leader election in anonymous quantum networks. Similarly we show that the GHZ-state is the only one that can be used to solve the problem of distributed consensus when no classical post-processing is considered. These results generalize to a family of W- and GHZ-like states. At the heart of the proofs of these impossibility results lie symmetry arguments.
{
"annotation_id": "fe19c474-86d2-4a5f-af97-e490fa355526",
"date_created": "2026-03-02T18:02:13.623000Z",
"date_modified": "2026-03-02T18:02:13.623000Z",
"file_hash": "be4604ac0a42315ca8b9b858be260c330688d16e4d2b230bdb7f942249520f5c",
"private": false,
"record": {
"abstract": "It is well understood that the use of quantum entanglement significantly\nenhances the computational power of systems. Much of the attention has focused\non Bell states and their multipartite generalizations. However, in the\nmultipartite case it is known that there are several inequivalent classes of\nstates, such as those represented by the W-state and the GHZ-state. Our main\ncontribution is a demonstration of the special computational power of these\nstates in the context of paradigmatic problems from classical distributed\ncomputing. Concretely, we show that the W-state is the only pure state that can\nbe used to exactly solve the problem of leader election in anonymous quantum\nnetworks. Similarly we show that the GHZ-state is the only one that can be used\nto solve the problem of distributed consensus when no classical post-processing\nis considered. These results generalize to a family of W- and GHZ-like states.\nAt the heart of the proofs of these impossibility results lie symmetry\narguments.",
"arxiv_id": "quant-ph/0412177",
"authors": [
"Ellie D\u0027Hondt",
"Prakash Panangaden"
],
"categories": [
"quant-ph"
],
"journal_ref": "Journ. Quantum Inf. and Comp., vol. 6(2), pages 173-183, 2005",
"title": "The Computational Power of the W and GHZ states",
"url": "https://arxiv.org/abs/quant-ph/0412177"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a0d5b51f-046d-4c5c-983e-752a111009b2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}