The Department of Physics presents a talk on the Schur transform.
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. Bacon, Chuang and Harrow gave a quantum algorithm for this transform that is polynomial in n, d and log(1/ϵ), where ϵ is the precision. In a footnote in Harrow’s thesis, a brief description of how to make this algorithm polynomial in log(d) is given using the unitary group representation theory (however, this has not been explained in detail anywhere). We present a quantum circuit for the Schur transform that is polynomial in n, log(d) and log(1/ϵ) using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a “dual” algorithm. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules, which could have other applications.
This event was first published on January 23, 2020 and last updated on January 29, 2020.