Figure 2: Time evolution of the glider CQCA T G : On the left side the individual evolutions of single Z and X observables are shown. They both generate “checkerboards” which are shifted against each other by one time-step. By shifting the original X also in space we overlap the checkerboards such that they cancel out leaving only a small strip in the space-time picture. This strip is generated by the original observable moving on the spin chain. Such observables are called gliders. 3 x t 0 1 2 3 4 -1 -2 -3 -4 0 1 2 3 4 ⊙ = -4 -3 -2 -1 0 1 2 4 3 2 1 0 -1 $_{=}$Z $_{=}$X the symplectic form. Thus, the commutation relations are encoded in the symplectic form. To further simplify our classical description, we trans- form the binary strings to Laurent polynomials using tensor products of Pauli matrices: The ones in ξ$_{X}$ account for the Pauli X matrices, the ones in ξ$_{Z}$ for the Y matrices, and if ξ$_{X}$ ( x$_{0}$ ) = ξ$_{Y}$ ( x$_{0}$ ) = 1, there is a Y at x$_{0}$ : We use these polynomials as abstract objects without ever evaluating them for some value of u . Our example observable then looks like ˆ ξ ( u ) = ∑ x ∈ Z ξ ( x ) u $^{x}$. (5) w ( ξ ) = ⊗ x ∈ Z w ( ξ ( x )) , ξ ( x ) = ( ξ$_{X}$ ( x ) , ξ$_{Z}$ ( x )) ∈ Z 2 $_{2}$. (2) ( · · · 0 1 1 0 1 0 · · · 0 0 1 1 0 0 $_{· · ·}$) ↦→ ( u − 1 + 1 + u 2 1 + u ) . w ( · · · 0 1 1 0 1 0 · · · 0 0 1 1 0 0 $_{· · ·}$) = · · · 1 ⊗ X ⊗ iY ⊗ Z ⊗ X ⊗ 1 · · · . We change the function w in a way that it maps vectors of Laurent polynomials to tensor products of Pauli ma- trices. By a slight abuse of notation, we will also name it w . The binary strings are infinitely long, but, as we always deal with localized observables, only finitely many posi- tions have non-zero entries. We omit the zeros before and after the observable to get a more convenient notation. Similarly, we will omit the identities before and after the observable. The binary strings form a vector space over $^{Z$_{2}$}$, which we call phase space. The addition in the classical description is commuta- tive, so we have to encode the commutation relations in an auxiliary function. Our operators fulfill the condition which is known from the Pauli matrices as w ( ξ + η ) = ( − 1) η X ξ Z w ( ξ ) w ( η ) , σ$_{k}$ = i ε$_{ijk}$σ$_{i}$σ$_{j}$, w ( ξ ) w ( η ) = ( − 1) ξ X η Z − ξ Z η X w ( η ) w ( ξ ) . (3) σ ( ξ, η ) = ξ$_{X}$ η$_{Z}$ − ξ$_{Z}$ η$_{X}$ (4) Now we want to describe CQCAs in this picture. A CQCA T maps every Pauli matrix to a tensor product of those. Because it is an automorphism and determined by the local transformation T$_{0}$, we can calculate the image of any observable from the image of the Pauli matrices it can be decomposed into. Of course, the images of neigh- boring Pauli matrices in general overlap and have to be multiplied. Because we required them to commute, this multiplication is uniquely defined. In the phase-space picture with binary strings this multiplication becomes an addition. The CQCA’s action is thus a convolution of the observable’s vector of binary strings ( ξ t X ξ t Z ) with the automaton’s single cell images ( t$_{X}$$_{→}$$_{X}$ t$_{X}$$_{→}$$_{Z}$ ) and t$_{Z}$$_{→}$$_{X}$ t$_{Z}$$_{→}$$_{Z}$ ) : ( ξ t +1 X ( x ) ξ t +1 Z ( x ) ) = (( t$_{X}$$_{→}$$_{X}$ t$_{Z}$$_{→}$$_{X}$ t$_{X}$$_{→}$$_{Z}$ t$_{Z}$$_{→}$$_{Z}$ ) ⋆ ( ξ t X ξ t Z )) ( x ) = ( t$_{X}$$_{→}$$_{X}$ ⋆ ξ t $_{X}$)( x ) + ( t$_{Z}$$_{→}$$_{X}$ ⋆ ξ t $_{Z}$)( x ) ( t$_{X}$$_{→}$$_{Z}$ ⋆ ξ t $_{X}$)( x ) + ( t$_{Z}$$_{→}$$_{Z}$ ⋆ ξ t $_{Z}$)( x ) ) . The transformation (5) to the Laurent polynomials has the nice property of turning convolutions into multipli- 2 The definition of a scalar product is possible, because there are always only finitely many non-zero entries. In both cases terms of the type ξ$_{X}$ η$_{Z}$ are scalar products where the addition is carried out modulo 2. 2 We call the function where σ$_{1}$ = X , σ$_{2}$ = Y , σ$_{3}$ = Z , and ε$_{ijk}$ = 1 if ( i, j, k ) is an even permutation of (1 , 2 , 3), ε$_{ijk}$ = − 1 if ( i, j, k ) is an odd permutation of (1 , 2 , 3), and ε$_{ijk}$ = 0 otherwise. In our definition we have no i, because we chose w (1 , 1) = i Y . Therefore, the w ( ξ ) fulfill the commutation relations