OSC Colloquium: Hari Krovi

The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V⊗n of a vector space V of dimension d. This would have numerous applications in quantum information processing. Bacon, Chuang and Harrow (BCH) gave a quantum algorithm for this transform that is polynomial in n, d and logϵ−1, where ϵ is the precision. Following this, it had been an open question whether one can obtain an algorithm that is polynomial in logd. In a footnote in Harrow's thesis, a brief description of how to make the algorithm of BCH polynomial in logd is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n, logd and logϵ−1 using a different approach. We build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a "dual" algorithm to BCH. A novel feature of our algorithm is that we construct the quantum Fourier transform over permutation modules that could have other applications.