  We describe an efficient quantum algorithm for the quantum Schur transform.
The Schur transform is an operation on a quantum computer that maps the
standard computational basis to a basis composed of irreducible representations
of the unitary and symmetric groups. We simplify and extend the algorithm of
Bacon, Chuang, and Harrow, and provide a new practical construction as well as
sharp theoretical and practical analyses. Our algorithm decomposes the Schur
transform on $n$ qubits into
$O\left(n^4\log\left(\frac{n}{\epsilon}\right)\right)$ operators in the
Clifford+T fault-tolerant gate set and uses exactly
$2\lfloor\log_2(n)\rfloor-1$ ancillary qubits. We extend our qubit algorithm to
decompose the Schur transform on $n$ qudits of dimension $d$ into
$O\left(d^{1+p}n^{3d}\log^p\left(\frac{d n}{\epsilon}\right)\right)$ primitive
operators from any universal gate set, for $p\approx3.97$.
