|InterJournal Complex Systems, 91
|Manuscript Number: |
Submission Date: 971206
|A universal quantum cellular automaton|
Category: Brief Article
We will prove the existence of a universal quantum cellular automaton. Such QCA are defined as the quantum-mechanical pendant of classical one-dimensional cellular automata. As is the case with quantum Turing machines, the well-formedness restriction plays an important role. It will be shown that every proper QCA obeys a local constraint which is comparable with the "inverse neighborhood" of classical reversible cellular automata. This allows us to describe every QCA as a periodic quantum gate array, which can be simulated (with a bounded error) by a universal automaton U. The time complexity of this simulation does not depend on the size of the QCA to be simulated.
|Submit referee report/comment|