InterJournal Complex Systems, 91
Status: Accepted
Manuscript Number: [91]
Submission Date: 971206
A universal quantum cellular automaton
Author(s): Wim van Dam

Subject(s): CX.04

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.

Retrieve Manuscript
Submit referee report/comment

Public Comments: