# A Practical Quantum Algorithm for the Schur Transform. (arXiv:1709.07119v1 [quant-ph])

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(n^4 \log(n/{\epsilon}))$ operators in the

Clifford+T fault-tolerant gate set. We extend our qubit algorithm to decompose

the Schur transform on $n$ qudits of dimension $d$ into $O(d^{1+p} n^{2d+1}

\log^p (dn/{\epsilon})$) primitive operators from any universal gate set, for

$p {\approx} 3.97$.