{
  "annotation_id": "788718c5-7580-473a-8b5f-004232cb34c9",
  "date_created": "2026-03-02T18:02:37.380000Z",
  "date_modified": "2026-03-02T18:02:37.380000Z",
  "file_hash": "83118ee19758fa6547bc6757816d2fb79b6d1b0702eeeb71a65476ce3c2a05c5",
  "private": false,
  "record": {
    "abstract": "Linear quantum cellular automata were introduced recently as one of the\nmodels of quantum computing. A basic postulate of quantum mechanics imposes a\nstrong constraint on any quantum machine: it has to be unitary, that is its\ntime evolution operator has to be a unitary transformation. In this paper we\ngive an efficient algorithm to decide if a linear quantum cellular automaton is\nunitary. The complexity of the algorithm is O(n^((3r-1)/(r+1))) = O(n^3) in the\nalgebraic computational model if the automaton has a continuous neighborhood of\nsize r, where $n$ is the size of the input.",
    "arxiv_id": "quant-ph/9604007",
    "authors": [
      "Christoph Durr",
      "Miklos Santha"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "journal_ref": "Proceeding of the 37th IEEE Symposium on Foundations of Computer\n  Science, 38--45, 1996",
    "title": "A decision procedure for unitary linear quantum cellular automata",
    "url": "https://arxiv.org/abs/quant-ph/9604007"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "28ece1d3-3a19-4846-94f2-3fd2544f38e6",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}