The idea of quantum cellular automata is clearly present already in the work of Feynman. A satisfactory formal definition, however, was lacking so far, if we require the following features: (1) A QCA is specified in terms of a local transition rule, which readily determines and is in turn determined by the global evolution time step. (2) There is an effective way of verifying whether a proposed local rule is legitimate. (3) The same local rule generates global transition rules for an infinite system but also for any lattice with periodic boundary conditions. (4) The concatenation of QCAs and the inverse of a QCA is a QCA with appropriately enlarged neighbourhood scheme. (5) All classical reversible CAs are restrictions of QCAs to the diagonal subalgebra.
In this talk we present a satisfactory definition of reversible QCAs, and show that all such QCAs are ``structurally reversible'' in the sense that they can be represented by two steps of blockwise unitary operations for suitable Margolus-type block decompositions.