  In previous papers we have considered mutual simulation of n-partite
pair-interaction Hamiltonians. We have focussed on the running time overhead of
general simulations, while considering the required number of time steps only
for special cases (decoupling and time-reversal). These two complexity measures
differ significantly. Here we derive lower bounds on the number of time steps
for general simulations. In particular, the simulation of interaction graphs
with irrational spectrum requires at least n steps. We discuss as examples
graphs that correspond to graph codes and nearest neighbor interactions in 1-
and 2-dimensional lattices. In the latter case the lower bounds are almost
tight.
