2 T$_{0}$ : A$_{i}$ → A$_{i}$ + N T t t + 1 Figure 1: Time evolution of a CQCA. The images of the observables on system A$_{i}$ are contained in the set of observables of the systems A$_{i}$ + N in the next time step. B. Clifford Quantum Cellular Automata define the operation ⊙ , which has the following prop- erties to resemble the multiplication of Pauli matrices: i ⊙ i = 0 , i ⊙ j = k for i, j, k = 1 , 2 , 3 with i = j = k and 0 i = i ⊙ 0 = i for i = 0 , . . . , 3 . Now we can illustrate the evolution of the observable Z − $^{1}$⊗ Y $^{0}$⊗ X 1 as follows (the underlined labels are situated at the origin.): Now we restrict ourselves to a special kind of QCAs, the Clifford quantum cellular automata (CQCAs), which employ the Clifford group operations. Clifford operations map tensor products of Pauli matrices to tensor products of Pauli matrices times a phase. Thus, the local rule T$_{0}$ of a CQCA maps single Pauli matrices to tensor products of Pauli matrices times a phase. Furthermore, we only consider one-dimensional lattices, i.e. spin chains. We will illustrate this with an example. We can see that this observable only moves on the lattice by one step. We call observables with this property “glid- ers” and the automata which allow for such observables glider automata. Figure 2 gives an explanation for this behavior. ♦ Example II.1. The so-called glider CQCA T$_{G}$ has the following local rule: T$_{G}$(3 2 1) = T$_{G}$(3 0 0) ⊙ T$_{G}$(0 2 0) ⊙ T$_{G}$(0 0 1) = 3 1 3 ⊙ 3 2 3 3 = 3 2 1 0 = (3 2 1) T$_{G,}$$_{0}$[ X$_{i}$ ] = Z$_{i}$, T$_{G,}$$_{0}$[ Z$_{i}$ ] = Z$_{i}$$_{−}$$_{1}$ ⊗ X$_{i}$ ⊗ Z$_{i}$$_{+1}$, 1. Classical Description of CQCA It is well known that Clifford operations are classically simulable in an efficient way [9]. We use this to derive a classical description of CQCAs, which greatly simplifies our further analysis. Heuristically speaking we replace the CQCAs acting on observables by a classical cellular automaton (CA) acting on the labels of Pauli matrices as we did with the example CQCA in the last section. Mathematically we do the following: first we introduce a function w that maps vectors over Z$_{2}$ to Pauli matrices $^{1}$: The global transformation T$_{G}$ has to be an automor- phism. We already constructed the image of Y$_{i}$ accord- ingly. Now we have to check if the commutation and anti-commutation relations between neighboring cells are preserved. We have where X$_{i}$ and Z$_{i}$ denote the Pauli matrices at system i . The image of Y$_{i}$ follows from the product of the images of X$_{i}$ and Z$_{i}$ , because we require T$_{0}$ to be a homomorphism: This way we gave the Pauli matrices classical labels from a vector space. A quantum cellular automaton mapping Pauli matrices to Pauli matrices can now be described as a classical automaton acting on the labels. But, be- fore we introduce the classical description of CQCAs, we have to introduce tensor products of Pauli matrices to our classical description. To do that we extend the func- tion w in a way that it maps vectors of binary strings to X = w (1 , 0) , Y = i w (1 , 1) , Z = w (0 , 1) , 1 = w (0 , 0) . (1) [T$_{G,}$$_{0}$ X $^{i}$, T$_{G,}$$_{0}$ X $^{j}$] = [ Z $^{i}$, Z$^{j}$] = 0 , T$_{G,}$$_{0}$[ Y$_{i}$ ] = − Z$_{i}$$_{−}$$_{1}$ ⊗ Y$_{i}$ ⊗ Z$_{i}$$_{+1}$. [T$_{G,}$$_{0}$ Z $^{i}$, T$_{G,}$$_{0}$ Z $^{j}$] = [ Z i − 1 ⊗ X i ⊗ Z i $^{+1}$, Z j − 1 ⊗ X j ⊗ Z j $^{+1}$] = 0 , and [T$_{G,}$$_{0}$ Z $^{i}$, T$_{G,}$$_{0}$ X $^{j}$] = [ Z i − 1 ⊗ X i ⊗ Z i $^{+1}$, Z $^{j}$] = 0 , i = j, { T$_{G,}$$_{0}$ Z $^{i}$, T$_{G,}$$_{0}$ X $^{i}$} = { Z i − 1 X i Z i $^{+1}$, Z $^{i}$} = 0 , so our local rule extends to a global automorphism. As the global rule acts in exactly the same way on single-site Pauli matrices as the global rule, we will from now on always use the global rule T$_{G}$ . By neglecting a global phase, we can also think of the CQCA T$_{G}$ as a classical automaton acting on the la- bels (1 ̂ = X, 2 ̂ = Y, 3 ̂ = Z, 0 ̂ = 1 ) of the Pauli matrices. We 1 Z$_{2}$ is the finite field consisting of 0 and 1 with addition modulo 2.