dorsal/arxiv
View SchemaAn efficient algorithm to recognize local Clifford equivalence of graph states
| Authors | Maarten Van den Nest, Jeroen Dehaene, Bart De Moor |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0405023 |
| URL | https://arxiv.org/abs/quant-ph/0405023 |
| DOI | 10.1103/PhysRevA.70.034302 |
| Journal | Phys. Rev. A 70, 034302 (2004) |
Abstract
In [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action of local Clifford operations on graph states in terms of a graph transformation rule, known in graph theory as \emph{local complementation}. It was shown that two graph states are equivalent under the local Clifford group if and only if there exists a sequence of local complementations which relates their associated graphs. In this short note we report the existence of a polynomial time algorithm, published in [Combinatorica 11 (4), 315 (1991)], which decides whether two given graphs are related by a sequence of local complementations. Hence an efficient algorithm to detect local Clifford equivalence of graph states is obtained.
{
"annotation_id": "19fbdb06-5795-4e98-b995-821c780e7bb4",
"date_created": "2026-03-02T18:02:07.093000Z",
"date_modified": "2026-03-02T18:02:07.093000Z",
"file_hash": "9817ab8f90c1755d5126cc763ad705385a5452ef4988b5b81f366a2214194c13",
"private": false,
"record": {
"abstract": "In [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action\nof local Clifford operations on graph states in terms of a graph transformation\nrule, known in graph theory as \\emph{local complementation}. It was shown that\ntwo graph states are equivalent under the local Clifford group if and only if\nthere exists a sequence of local complementations which relates their\nassociated graphs. In this short note we report the existence of a polynomial\ntime algorithm, published in [Combinatorica 11 (4), 315 (1991)], which decides\nwhether two given graphs are related by a sequence of local complementations.\nHence an efficient algorithm to detect local Clifford equivalence of graph\nstates is obtained.",
"arxiv_id": "quant-ph/0405023",
"authors": [
"Maarten Van den Nest",
"Jeroen Dehaene",
"Bart De Moor"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.70.034302",
"journal_ref": "Phys. Rev. A 70, 034302 (2004)",
"title": "An efficient algorithm to recognize local Clifford equivalence of graph states",
"url": "https://arxiv.org/abs/quant-ph/0405023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d4434d44-cb0d-48b4-bf3d-8aa387ea4e8d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}