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.