



01345nas a2200109   4500008004100000245009200041210006900133260001500202520095700217100002401174856003701198       2008                        eng d00aFast quantum algorithms for approximating some irreducible  representations of groups
0 aFast quantum algorithms for approximating some irreducible repre  c2008/11/043 a  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.
1 aJordan, Stephen, P.  uhttp://arxiv.org/abs/0811.0562v2