{
  "annotation_id": "47f925a3-43a4-4de7-bca1-042a33edd927",
  "date_created": "2026-03-02T18:02:13.324000Z",
  "date_modified": "2026-03-02T18:02:13.324000Z",
  "file_hash": "ab065afe4ce572701be30dee35be7d22f6043224811bec36846549c79579581f",
  "private": false,
  "record": {
    "abstract": "The graph state formalism is a useful abstraction of entanglement. It is used\nin some multipartite purification schemes and it adequately represents\nuniversal resources for measurement-only quantum computation. We focus in this\npaper on the complexity of graph state preparation. We consider the number of\nancillary qubits, the size of the primitive operators, and the duration of\npreparation. For each lexicographic order over these parameters we give upper\nand lower bounds for the complexity of graph state preparation. The first part\nmotivates our work and introduces basic notions and notations for the study of\ngraph states. Then we study some graph properties of graph states,\ncharacterizing their minimal degree by local unitary transformations, we\npropose an algorithm to reduce the degree of a graph state, and show the\nrelationship with Sutner sigma-game.\n  These properties are used in the last part, where algorithms and lower bounds\nfor each lexicographic order over the considered parameters are presented.",
    "arxiv_id": "quant-ph/0412071",
    "authors": [
      "Mehdi Mhalla",
      "Simon Perdrix"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Complexity of Graph State Preparation",
    "url": "https://arxiv.org/abs/quant-ph/0412071"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "3451e36b-c871-41d2-a62a-f07b05f8dcf0",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}