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$.

Article web page: