  We define quantum cellular automata as infinite quantum lattice systems with
discrete time dynamics, such that the time step commutes with lattice
translations and has strictly finite propagation speed. In contrast to earlier
definitions this allows us to give an explicit characterization of all local
rules generating such automata. The same local rules also generate the global
time step for automata with periodic boundary conditions. Our main structure
theorem asserts that any quantum cellular automaton is structurally reversible,
i.e., that it can be obtained by applying two blockwise unitary operations in a
generalized Margolus partitioning scheme. This implies that, in contrast to the
classical case, the inverse of a nearest neighbor quantum cellular automaton is
again a nearest neighbor automaton.
  We present several construction methods for quantum cellular automata, based
on unitaries commuting with their translates, on the quantization of
(arbitrary) reversible classical cellular automata, on quantum circuits, and on
Clifford transformations with respect to a description of the single cells by
finite Weyl systems. Moreover, we indicate how quantum random walks can be
considered as special cases of cellular automata, namely by restricting a
quantum lattice gas automaton with local particle number conservation to the
single particle sector.
