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.