An algebraic study of unitary one dimensional quantum cellular automata.

One dimensional quantum cellular automata (1QCA) consist of a row of
identical, finite dimensional, quantum systems. These evolve in
discrete time steps according to a global evolution G -- which itself
arises from the application of a local transition function delta,
homogeneously and synchronously across space. But in order to grant
them the status of physically acceptable models, one must ensure that
the global evolution G is physically acceptable in a quantum
theoretical setting, i.e. one must ensure that $Delta$ is unitary.
Unfortunately this global property is non-trivially related to the
description of the local transition function $delta$ -- witness of
this the abundant literature on reversible cellular automata (RCA). We
provide algebraic characterizations of unitary one dimensional quantum
cellular automata. We do so both by algebraizing existing decision
procedures, and by adding constraints into the model which do not
change the quantum cellular automata's computational power. The
configurations we consider have finite but unbounded size.