  For certain quantum operations acting on qubits, there exist bases of
measurement operators such that estimating the average fidelity becomes
efficient. The number of experiments required is then independent of system
size and the classical computational resources scale only polynomially in the
number of qubits. Here we address the question of how to optimally choose the
measurement basis for efficient gate characterization when replacing two-level
qubits by $d$-level qudits. We define optimality in terms of the maximal number
of unitaries that can be efficiently characterized. Our definition allows us to
construct the optimal measurement basis in terms of their spectra and
eigenbases: The measurement operators are unitaries with $d$-nary spectrum and
partition into $d+1$ Abelian groups whose eigenbases are mutually unbiased.
