dorsal/arxiv
View SchemaA decision procedure for unitary linear quantum cellular automata
| Authors | Christoph Durr, Miklos Santha |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9604007 |
| URL | https://arxiv.org/abs/quant-ph/9604007 |
| Journal | Proceeding of the 37th IEEE Symposium on Foundations of Computer Science, 38--45, 1996 |
Abstract
Linear quantum cellular automata were introduced recently as one of the models of quantum computing. A basic postulate of quantum mechanics imposes a strong constraint on any quantum machine: it has to be unitary, that is its time evolution operator has to be a unitary transformation. In this paper we give an efficient algorithm to decide if a linear quantum cellular automaton is unitary. The complexity of the algorithm is O(n^((3r-1)/(r+1))) = O(n^3) in the algebraic computational model if the automaton has a continuous neighborhood of size r, where $n$ is the size of the input.
{
"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
}