Unitarity plus causality implies localizability

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 neighboring nodes. We take quantum cellular automata as an example application of this representation theorem: this analysis bridges the gap between the axiomatic and the constructive approaches to defining QCA. (C) 2010 Elsevier Inc. All rights reserved.