Colloquium: Hari Krovi - An Efficient High Dimentional Schur Transformation

Abstract:
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.

Speaker's Bio:
Dr. Hari Krovi is a senior scientist in the quantum engineering and computing group at Raytheon BBN Technologies. He obtained his PhD from the University of Southern California and did postdocs at NEC labs and the University of Connecticut. His interests are in the mathematical aspects of quantum algorithms and quantum error correction. He has also worked on quantum key distribution and quantum networks.