Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Language and automata theory and applications |
| Herausgeber/-innen | Carlos Martin-Vide, Friedrich Otto, Henning Fernau |
| Erscheinungsort | Berlin |
| Herausgeber (Verlag) | Springer Nature |
| Seiten | 64-75 |
| Seitenumfang | 12 |
| Band | 5196 |
| Publikationsstatus | Veröffentlicht - 2008 |
Publikationsreihe
| Name | Lecture Notes in Comput. Sci. |
|---|---|
| Herausgeber (Verlag) | Springer |
Abstract
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Language and automata theory and applications. Hrsg. / Carlos Martin-Vide; Friedrich Otto; Henning Fernau. Band 5196 Berlin: Springer Nature, 2008. S. 64-75 (Lecture Notes in Comput. Sci.).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Beitrag in Buch/Sammelwerk › Forschung › Peer-Review
}
TY - CHAP
T1 - One-dimensional quantum cellular automata over finite, unbounded configurations
AU - Arrighi, Pablo
AU - Nesme, Vincent
AU - Werner, Reinhard F.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-540-88282-4_8
DO - 10.1007/978-3-540-88282-4_8
M3 - Contribution to book/anthology
VL - 5196
T3 - Lecture Notes in Comput. Sci.
SP - 64
EP - 75
BT - Language and automata theory and applications
A2 - Martin-Vide, Carlos
A2 - Otto, Friedrich
A2 - Fernau, Henning
PB - Springer Nature
CY - Berlin
ER -