  Pauli-based computation (PBC) is a universal measurement-based quantum
computation model steered by an adaptive sequence of independent and compatible
Pauli measurements on separable magic-state qubits. Here, we propose several
new ways of decreasing the weight of the Pauli measurements and their
associated \textsc{cnot} complexity; we also demonstrate how to reduce this
model's computational depth. Inspired by known state-transfer methods, we
introduce incPBC, a universal model for quantum computation requiring a larger
number of (now incompatible) Pauli measurements of weight at most 2. For usual
PBC, we prove new upper bounds on the required weights and computational depth,
obtained via a pre-compilation step. We also propose a heuristic algorithm that
can contribute reductions of over 30\% to the average weight of Pauli
measurements (and associated \textsc{cnot} count) when simulating and compiling
Clifford-dominated random quantum circuits with up to 22 $T$ gates and over
20\% for instances with larger $T$ counts.
