The linked paper explicitly assumes that
The evolution operator T is invertible.
But if you use QM in the conventional way, then this assumption doesn't hold. Suppose you have a state X1 which can evolve into either X2 or X3 with equal probability. You would say that state X1 evolves into the weighted set [1/2 X2 + 1/2 X3]. Shalizi proves that this set has no more entropy than X1 did.
But we, as observers or as part of that system, only get to look at one of the branches, either X2 or X3. Picking which of those two branches we get to look at adds one bit of new entropy, and this selection is not invertible. This is where the increase in entropy with time comes from. What Shalizi has done, is to use math in which all entropy originates in quantum branching, then forget that quantum branching happens.
Evolving into 1/2 x2 + 1/2 x3 is not a quantum operation that can occur in a closed system (it requires at the very least tracing over an auxiliary qubit).
Link to the Question
I haven't gotten an answer on this yet and I set up a bounty; I figured I'd link it here too in case any stats/physics people care to take a crack at it.