We consider the quantum complexity of estimating matrix elements of unitary
irreducible representations of groups. For several finite groups including the
symmetric group, quantum Fourier transforms yield efficient solutions to this
problem. Furthermore, quantum Schur transforms yield efficient solutions for
certain irreducible representations of the unitary group. Beyond this, we
obtain poly(n)-time quantum algorithms for approximating matrix elements from
all the irreducible representations of the alternating group A_n, and all the
irreducible representations of polynomial highest weight of U(n), SU(n), and
SO(n). These quantum algorithms offer exponential speedup in worst case
complexity over the fastest known classical algorithms. On the other hand, we
show that average case instances are classically easy, and that the techniques
analyzed here do not offer a speedup over classical computation for the
estimation of group characters.
