Abstract
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.
Funding Information
  • Government of Canada
  • Canadian Institute for Advanced Research
  • International Business Machines Corporation
  • Institut Périmètre de physique théorique

This publication has 34 references indexed in Scilit: