We consider a graph with a single quantum system at each node. The entire compound system evolves in discrete time steps by iterating a global evolution U. We require that this global evolution U be unitary, in accordance with quantum theory, and that this global evolution U be causal, in accordance with special relativity. By causal we mean that information can only ever be transmitted at a bounded speed, the speed bound being quite naturally that of one edge of the underlying graph per iteration of U. We show that under these conditions the operator U can be implemented locally; i.e. it can be put into the form of a quantum circuit made up with more elementary operators -- each acting solely upon neighbouring nodes. We apply this representation theorem to n-dimensional quantum cellular automata and show that they can be put into the form of an infinite tiling of more elementary, finite-dimensional unitary evolutions.
Joint work with: Vincent Nesme and Reinhard Werner.