Fast quantum algorithms for approximating some irreducible representations of groups

Details Fast quantum algorithms for approximating some irreducible representations of groups Fast quantum algorithms for approximating some irreducible representations of groups

2008-11-04

arxiv.org/abs/0811.0562v2

Physics

Quantum Physics

added simplified algorithms using quantum Schur and Fourier transforms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fast quantum algorithms for approximating some irreducible representations of groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast quantum algorithms for approximating some irreducible representations of groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast quantum algorithms for approximating some irreducible representations of groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184568