  Simulating quantum dynamics is one of the most promising applications of
quantum computers. While the upper bound of the simulation cost has been
extensively studied through various quantum algorithms, much less work has
focused on establishing the lower bound, particularly for the simulation of
open quantum system dynamics. In this work, we present a general framework to
calculate the lower bound for simulating a broad class of quantum Markov
semigroups. Given a fixed accessible unitary set, we introduce the concept of
convexified circuit depth to quantify the quantum simulation cost and analyze
the necessary circuit depth to construct a quantum simulation scheme that
achieves a specific order. Our framework can be applied to both unital and
non-unital quantum dynamics, and the tightness of our lower bound technique is
illustrated by showing that the upper and lower bounds coincide in several
examples.
