Universally Programmable Quantum Cellular Automaton

We discuss the role of classical control in the context of reversible quantum cellular automata. Employing the structure theorem for quantum cellular automata, we give a general construction scheme to turn an arbitrary cellular automaton with external classical control into an autonomous one, thereby proving the computational equivalence of these two models. We use this technique to construct a universally programmable cellular automaton on a one-dimensional lattice with single cell dimension 12.

Figure 1

Two time steps of the CCQCA. The clocks indicate the time before and after application of the unitaries for comparison to Fig. 2.

Figure 2

Four time steps of the autonomous QCA. As the cells are updated sequentially, the clocks indicate the local time of the cells corresponding to the time of the CCQCA.

Figure 3

Structure of the “three-band“ QCA with pointer, data, and ancilla band. Localization of the homomorphisms (2) is indicated.

Figure 4

Structure of the autonomous QCA. Indicated are three cells with one program qutrit and two data qubits each; identification of the data qubits corresponding to Fig. 3.