dorsal/arxiv
View SchemaReversible quantum cellular automata
| Authors | B. Schumacher, R. F. Werner |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0405174 |
| URL | https://arxiv.org/abs/quant-ph/0405174 |
Abstract
We define quantum cellular automata as infinite quantum lattice systems with discrete time dynamics, such that the time step commutes with lattice translations and has strictly finite propagation speed. In contrast to earlier definitions this allows us to give an explicit characterization of all local rules generating such automata. The same local rules also generate the global time step for automata with periodic boundary conditions. Our main structure theorem asserts that any quantum cellular automaton is structurally reversible, i.e., that it can be obtained by applying two blockwise unitary operations in a generalized Margolus partitioning scheme. This implies that, in contrast to the classical case, the inverse of a nearest neighbor quantum cellular automaton is again a nearest neighbor automaton. We present several construction methods for quantum cellular automata, based on unitaries commuting with their translates, on the quantization of (arbitrary) reversible classical cellular automata, on quantum circuits, and on Clifford transformations with respect to a description of the single cells by finite Weyl systems. Moreover, we indicate how quantum random walks can be considered as special cases of cellular automata, namely by restricting a quantum lattice gas automaton with local particle number conservation to the single particle sector.
{
"annotation_id": "6ec6e506-3936-4bfa-85cf-881e3dd1b456",
"date_created": "2026-03-02T18:02:06.882000Z",
"date_modified": "2026-03-02T18:02:06.882000Z",
"file_hash": "f4461ff1f909e5e236191c7460187e786a45f678d6bf271693a801017e895a51",
"private": false,
"record": {
"abstract": "We define quantum cellular automata as infinite quantum lattice systems with\ndiscrete time dynamics, such that the time step commutes with lattice\ntranslations and has strictly finite propagation speed. In contrast to earlier\ndefinitions this allows us to give an explicit characterization of all local\nrules generating such automata. The same local rules also generate the global\ntime step for automata with periodic boundary conditions. Our main structure\ntheorem asserts that any quantum cellular automaton is structurally reversible,\ni.e., that it can be obtained by applying two blockwise unitary operations in a\ngeneralized Margolus partitioning scheme. This implies that, in contrast to the\nclassical case, the inverse of a nearest neighbor quantum cellular automaton is\nagain a nearest neighbor automaton.\n We present several construction methods for quantum cellular automata, based\non unitaries commuting with their translates, on the quantization of\n(arbitrary) reversible classical cellular automata, on quantum circuits, and on\nClifford transformations with respect to a description of the single cells by\nfinite Weyl systems. Moreover, we indicate how quantum random walks can be\nconsidered as special cases of cellular automata, namely by restricting a\nquantum lattice gas automaton with local particle number conservation to the\nsingle particle sector.",
"arxiv_id": "quant-ph/0405174",
"authors": [
"B. Schumacher",
"R. F. Werner"
],
"categories": [
"quant-ph"
],
"title": "Reversible quantum cellular automata",
"url": "https://arxiv.org/abs/quant-ph/0405174"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "84188055-525c-4e3f-a5f7-45418fad7a21",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}