We use techniques of quantum information theory to analyze the quantum causal histories approach to quantum gravity. 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 those causal structures that can be represented as quantum computational networks. Dynamics of the subsystems should not be unitary or even completely positive. However, we show that other commonly made assumptions ensure the complete positivity of the reduced dynamics.