One-dimensional quantum cellular automata over finite, unbounded configurations
| dc.creator | Arrighi, Pablo | |
| dc.creator | Nesme, Vincent | |
| dc.creator | Werner, Reinhard | |
| dc.date | 2007-11-22 | |
| dc.date.accessioned | 2026-07-07T09:32:26Z | |
| dc.date.available | 2026-07-07T09:32:26Z | |
| dc.description | One-dimensional quantum cellular automata (QCA) consist in a line of identical, finite dimensional quantum systems. These evolve in discrete time steps according to a local, shift-invariant unitary evolution. By local we mean that no instantaneous long-range communication can occur. In order to define these over a Hilbert space we must restrict to a base of finite, yet unbounded configurations. We show that QCA always admit a two-layered block representation, and hence the inverse QCA is again a QCA. This is a striking result since the property does not hold for classical one-dimensional cellular automata as defined over such finite configurations. As an example we discuss a bijective cellular automata which becomes non-local as a QCA, in a rare case of reversible computation which does not admit a straightforward quantization. We argue that a whole class of bijective cellular automata should no longer be considered to be reversible in a physical sense. Note that the same two-layered block representation result applies also over infinite configurations, as was previously shown for one-dimensional systems in the more elaborate formalism of operators algebras [9]. Here the proof is made simpler and self-contained, moreover we discuss a counterexample QCA in higher dimensions. | |
| dc.description | 9 pages, revtex, 8 figures | |
| dc.identifier | https://arxiv.org/abs/0711.3517 | |
| dc.identifier | http://arxiv.org/abs/0711.3517 | |
| dc.identifier | 2nd Int. Conf. on Language and Automata Theory and Applications, LATA 2008, Spain. Proceedings to appear in LNCS. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158776 | |
| dc.subject | Quantum Physics | |
| dc.title | One-dimensional quantum cellular automata over finite, unbounded configurations | |
| dc.type | text |