  For qubits, Monte Carlo estimation of the average fidelity of Clifford
unitaries is efficient -- it requires a number of experiments that is
independent of the number $n$ of qubits and classical computational resources
that scale only polynomially in $n$. Here, we identify the requirements for
efficient Monte Carlo estimation and the corresponding properties of the
measurement operator basis when replacing two-level qubits by $p$-level qudits.
Our analysis illuminates the intimate connection between mutually unbiased
measurements and the existence of unitaries that can be characterized
efficiently. It allows us to propose a 'hierarchy' of generalizations of the
standard Pauli basis from qubits to qudits according to the associated scaling
of resources required in Monte Carlo estimation of the average fidelity.
