9 ends of the spin chain. However, for special cases the cut images still fulfill the commutation relations. Fortu- nately, the much used glider CQCA is of this type. So, in this case the only influence from the ends of the chain is that the outermost sites miss the influence from one neighbor. As we still have an automorphism and thus a reversible operation on the whole chain, no information can be lost at the ends of the chain. So, the ends have to be reflective. We can observe that in the case of an incoming glider in the left part of Figure 9. This leads to the fact that observables are mirrored by the chain. For single-site Pauli matrices, this can be seen in the right- hand part of Figure 9. Arbitrary observables are sums of tensor products of single-site Pauli matrices. Because the single-site Pauli matrices are mirrored, the tensor prod- ucts will be mirrored, too. Thus, also sums are mirrored and therefore any observable is mirrored on the chain. This property and the spreading of observables in this process is used in applications of CQCAs like [7, 8]. Figure 8: Evolution of entanglement of a subchain of 30 consecutive spins for an initial stabilizer state with w ( ξ ) = Y ⊗ X ⊗ X ⊗ X ⊗ X ⊗ X ⊗ Y for different CQCAs. The entanglement first grows as in the bipartite case, but then saturates at 30 qubit pairs. per iod i c C Q C A, tr = 0 T$_{F}$ , t r = u $_{−}$1 + 1 + u 2- s te p gl i der C Q C A , t r = u $_{−}$2 + u 2 T$_{G}$ , tr = u $_{−}$1 + u t E ( t ) 20 15 10 5 0 30 20 10 0 CQCAs are used in different quantum computational schemes. Of course they are not capable of doing any computations efficiently; a classical computer couldn’t do efficiently as well, because they are essentially classical cellular automata. But, nevertheless they can be of great use when accompanied by non-Clifford operations. This is used in different approaches. translation-invariant operation that generates more en- tanglement per step, while having the same size of neigh- borhood, than a CQCA whose trace has maximal degree with respect to the neighborhood. VI. APPLICATIONS A. Measurement Based Quantum Computation V. NOTES ON FINITE CHAINS The most famous model of quantum computation in- volving a CQCA (indirectly) is the idea of measurement based quantum computation or the “one way quantum computer” by Raussendorf and Briegel [6]. The resource state used to perform the quantum computation by suc- cessively measuring the single qubits is a so-called cluster state on a 2-dimensional (finite) lattice of qubits. It can be generated by a CQCA, namely a 2-dimensional version of the glider CQCA (7). Thus, one time-step of a CQCA together with measurements of single qubits suffices for universal quantum computation. In our whole analysis we used an infinite spin chain to obtain translation invariance, which would be broken by the ends of the spin chain. For finite chains we gen- erally have to take the effects of the ends into account. But when we deal with observables which are localized far away from the ends of the chain and time periods T which are much smaller than the length of the chain, for locality reasons the time evolution of the observables has to be the same as for the infinite chain. Information from the ends of the chain can only travel with the same finite speed, as all other information, so e.g. a one-site observ- able localized in the middle of a chain of length L = 2 l +1 can only interfere with influences from the ends after l/ 2 time steps. Admittedly the applications of CQCAs make heavy use of the effects occurring at the ends of the spin chains. Thus, our above statement is not applicable. To take ef- fects at the ends of the spin chains into account, we have to deal with the fact that they break the translation in- variance. The one-site images of the sites at the ends of the chain whose neighborhoods would reach over one end of the chain, if they were the same as on the rest of the chain, have to be adapted. Like in the case of stabilizer states above, in general the cut images don’t fulfill the necessary commutation relations any more. There is no general theory yet of how to adapt the CQCAs at the In this scheme of translation-invariant quantum com- putation [7], again the glider CQCA is used, in this case the one-dimensional version. The property of generat- ing patterns from single-site observables, thus spreading them over the spin-chain (a finite chain is used here), is used to immunize observables against special global transformations. The time steps in which certain ob- servables are immune against these operations depend B. Raussendorf’s Scheme of Translation Invariant Quantum Computation