  We provide a precise definition and analysis of quantum causal histories
(QCH). A QCH consists of a discrete, locally finite, causal pre-spacetime with
matrix algebras encoding the quantum structure at each event. The evolution of
quantum states and observables is described by completely positive maps between
the algebras at causally related events. We show that this local description of
evolution is sufficient and that unitary evolution can be recovered wherever it
should actually be expected. This formalism may describe a quantum cosmology
without an assumption of global hyperbolicity; it is thus more general than the
Wheeler-DeWitt approach. The structure of a QCH is also closely related to
quantum information theory and algebraic quantum field theory on a causal set.
