Local unitary quantum cellular automata

In this paper we present a quantization of cellular automata. Our formalism is based on a lattice of qudits and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. It is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains, and others. Some results that show the benefits of basing the model on local unitary operators are shown: universality, strong connections to the circuit model, simple implementation on quantum hardware, and a wealth of applications.

Figure 1

Partitioned cellular automaton.

Figure 2

Past light cone of a region $S$: This represents a one-dimensional local unitary QCA. In order to obtain the state of the region of interest, the dark region at the bottom, one must consider not just the region itself, but anything that might affect the state of the region within the course of the simulation: its past light cone. One may then trace out the unneeded regions.

Figure 3

Quantum circuit simulation of a QCA update step: The dotted area represents the read phase. A read operator $U$ must be applied to each qubit, and its two neighbors. Since $U$ commutes with its translations, we are at liberty to apply the $U$ operators in any order. The update phase consists of the operator $V$ being applied to every qubit.

Figure 4

Decomposition of general qudit gates.

Figure 5

Universal QCA update rule.

Figure 6

Quantum walk on a lattice.

Figure 7

A simple quantum circuit that implements $U$.

Figure 8

Watrous partitioned QCA.

Figure 9

Watrous QCA expressed as a local unitary QCA.