  We introduce magic measures for multi-qubit quantum gates and establish lower
bounds on the non-Clifford resources for fault-tolerant quantum computation.
First, we introduce the stabilizer nullity of an arbitrary multi-qubit unitary,
which is based on the subgroup of the quotient Pauli group associated with the
unitary. This unitary stabilizer nullity extends the state stabilizer nullity
by Beverland et al. to a dynamic version. We in particular show this magic
measure has desirable properties such as sub-additivity under composition and
additivity under tensor product. Second, we prove that a given unitary's
stabilizer nullity is a lower bound for the T-count, utilizing the above
properties in gate synthesis. Third, we compare the state and the unitary
stabilizer nullity, proving that the lower bounds for the T-count obtained by
the unitary stabilizer nullity are never less than the state stabilizer
nullity. Moreover, we show an explicit $n$-qubit unitary family of unitary
stabilizer nullity $2n$, which implies that its T-count is at least $2n$. This
gives an example where the bounds derived by the unitary stabilizer nullity
strictly outperform the state stabilizer nullity by a factor of $2$. We further
connect the unitary stabilizer nullity and the state stabilizer nullity with
auxiliary systems, showing that adding auxiliary systems and choosing proper
stabilizer states can strictly improving the lower bound obtained by the state
stabilizer nullity.
