Fast quantum algorithms for approximating some irreducible representations of groups
arXiv:0811.0562
Abstract
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.
added simplified algorithms using quantum Schur and Fourier transforms
References in corpus (9)
- A modular functor which is universal for quantum computation
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- A Basis for Representations of Symplectic Lie Algebras
- Quantum Computation Beyond the Circuit Model
- The Quantum Schur Transform: I. Efficient Qudit Circuits
- On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
- Implementing high dimensional unitary representations of SU(2) on a Quantum Computer
- Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
- A PromiseBQP-complete String Rewriting Problem