For online events, details are sent out the week of the event. Join our community to receive them!
An efficient high dimensional quantum Schur transform
Krovi, Hari - Raytheon BBN Technologies
Presentation on Thursday, Feb. 7, 2019, 7 a.m.
Location: MIT Room 26-214
The Schur transform is a unitary operator that block diagonalizes the action of the symmetric
and unitary groups on an n fold tensor product 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/epsilon), where epsilon is the precision. Following this, it had been an open question whether one can obtain an algorithm that is polynomial in log(d). In a footnote in Harrow’s thesis, a brief description of how to make the algorithm of polynomial in log(d) is given using the unitary
group representation theory (however, this has not been explained in detail anywhere). In this
talk, we present a quantum algorithm for the Schur transform that is polynomial in n, log(d)
and log(1/epsilon) 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
Bacon et al., PRL, 97:170502 (2006). A novel feature of our algorithm is that we construct the quantum Fourier transform over permutation modules that could have other applications.