content_image/384062.jpg content_image/384061.jpg content_image/384065.jpg content_image/384066.jpg content_image/384073.jpg content_image/384056.jpg content_image/384055.jpg
cations: 

Because of this property, we refer to (5) as an algebraic Fourier transform. We get 

<img src='content_image/384062.jpg'>

In the following, we will omit the hat “ˆ” and the variable u for the sake of a short notation. Furthermore, we will replace ξ$_{X}$ by ξ$_{+}$ , ξ$_{Z}$ by ξ$_{−}$ , and t$_{X}$$_{→}$$_{X}$ by t$_{11}$ etc. to be consistent with the notation introduced in [1]. We then have 

Our example glider CQCA now looks like this: 

We have already seen that the CQCAs have to ful- fill certain conditions, namely the local rule has to be a translation-invariant homomorphism which maps Pauli products to Pauli products. Furthermore, it has to obey commutation relations with its translates. We have to translate these conditions to the polynomial picture. The matrix we use does not have any dependence on the po- sition on the chain, so translation invariance is already included in this formulation. The commutation relations are encoded in the symplectic form, as we can see from (3). For T to conserve the commutation relations, the corresponding classical automaton has to conserve the symplectic form. This is why the classical CAs that corre- spond to CQCAs are called symplectic cellular automata (SCAs). In [1] it was proven that a 2 × 2 matrix t with Laurent-polynomial entries is a SCA if and only if it ful- fills the following conditions: 

1. det( t ) = u 2 $^{a}$, a ∈ $^{Z}$; 

2. all entries t$_{ij}$ are symmetric polynomials centered around the same (but arbitrary) lattice point a ; 

<img src='content_image/384061.jpg'>

<img src='content_image/384065.jpg'>

<img src='content_image/384066.jpg'>

3. the entries t$_{1}$$_{j}$ , t$_{2}$$_{j}$ of both column vectors, which are the pictures of (1 , 0) and (0 , 1), are coprime. 

Furthermore, it was shown that to every CQCA there exists a SCA and an appropriate translation-invariant phase function λ ( ξ ) such that 

and | λ ( ξ ) | = 1 ∀ ξ hold. Additionally, λ ( ξ ) is uniquely determined for all ξ by the choice of λ on one site. On the other hand, we can find CQCAs for any given SCA by adding a phase function. Thus, CQCAs and SCAs are equivalent up to a phase. We will therefore only refer to CQCAs, even if we talk about the corresponding SCAs. 

The last condition, the homomorphism property, is automatically fulfilled because the choice of the phase function and the conservation of the symplectic form σ ( t ξ, t η ) = σ ( ξ, η ). The multiplication of Pauli matri- ces is mapped to the addition (modulus two) of phase- space vectors. As our matrices are linear transforma- tions they obey t ( ξ + η ) = t ξ + t η . This translates to T([ w ( ξ ) w ( η )] = T[ w ( ξ )]T[ w ( η )] via 

<img src='content_image/384073.jpg'>

A very simple CQCA is the shift on the lattice, which has the matrix u $^{a}$1 . It obviously commutes with all other CQCAs. Thus, we can multiply a CQCA with determi- nant u 2 a which has entries that are centered around a by a shift by − a sites to obtain a centered CQCA with de- terminant 1. From now on we will only consider centered CQCAs. 

A nice property of these centered CQCAs, which we will need to prove that the entanglement generation is linear, is that their matrices form a multiplicative group. Multiplying the matrices means concatenating the CQ- CAs. 

CQCAs show a variety of time evolutions that can be roughly grouped into three classes. The first class shows periodic behavior, the second class consist of CQCAs that have glider observables, which just move on the lattice as shown in Figure 2, and the last case generates fractal 

<img src='content_image/384056.jpg'>

<img src='content_image/384055.jpg'>

## 2. Classes of CQCAs 

