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.