  We propose a linear-size synthesis of the multi-controlled Toffoli gate on
qudits with at most one borrowed ancilla. This one ancilla can even be saved
when the qudit dimension is odd. Our synthesis leads to improvements in various
quantum algorithms implemented on qudits. In particular, we obtain (i) a
linear-size and one-clean-ancilla synthesis of multi-controlled qudit gates;
(ii) an optimal-size and one-clean-ancilla synthesis of unitaries on qudits;
(iii) a near-optimal-size and ancilla-free/one-borrowed-ancilla implementation
of classical reversible functions as qudit gates.
