Universally Programmable Quantum Cellular Automaton

We discuss the design of a universal 1-dimensional reversible nearest-neighbour quantum cellular automaton, efficiently simulating arbitrary gate model computations. Program and data are both encoded in the preparation of the initial state, and no further classical control is needed to run the machine. In the proof we use the structure theorem for quantum cellular automata (Margolus partitioning) to convert any device, whose program is a classical sequence of different quantum cellular automaton steps, into an autonomously running device with program stored in the quantum cells. We then describe an explicit example with cell-dimension 12.