Classical and Quantum Algorithms for Characters of the Symmetric Group - Sergey Bravyi; David Gosset; Vojtech Havlicek; Louis Schatzki (PRX Quantum)
Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group S_{n} is a challenging problem known to be #P-hard in the worst case. Here we describe a matrix product state (MPS) algorithm for characters of S_{n}. The algorithm computes an MPS encoding all irreducible characters of a given permutation. It relies on a mapping from characters of S_{n} to quantum spin chains proposed by Crichigno and Prakash. We also provide a simpler derivation of this mapping. 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 S_{n}. 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.