Abstract

Characters of irreducible representations are ubiquitous in group theory yet prove challenging to compute. Here we describe a Matrix Product State (MPS) algorithm for characters of Sn building on a mapping from characters of Sn to quantum spin chains proposed by Crichigno and Prakash (of which we also provide a simplified derivation). We complement this result by presenting a poly(n) size quantum circuit that prepares the corresponding MPS obtaining an efficient quantum algorithm for certain sampling problems based on characters of Sn. To assess classical hardness of these problems we present a general reduction from strong simulation (computing a given probability) to weak simulation (sampling with a small error). This reduction applies to any sampling problem with a certain granularity structure and may be of independent interest. Joint work with Sergey Bravyi, David Gosset, and Vojtech Havlicek.