We use techniques of quantum information theory to analyze the quantum causal histories approach to quantum gravity. We show that while it is consistent to introduce closed timelike curves (CTCs), they cannot generically carry independent degrees of freedom. Moreover, if the effective dynamics of the chronology-respecting part of the system is linear, it should be completely decoupled from the CTCs. In the absence of a CTC not all causal structures admit the introduction of quantum mechanics. It is possible for those and only for those causal structures that can be represented as quantum computational networks. The dynamics of the subsystems should not be unitary or even completely positive. However, we show that other commonly maid assumptions ensure the complete positivity of the reduced dynamics.