A practical quantum algorithm for the Schur transform

Abstract

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(\frac{n}{\eps})) 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(d^{1+p}n^{3d}\log^p(\frac{d n}{\eps})) primitive operators from any universal gate set, for p~3.97.