Classical and Quantum Algorithms for Characters of the Symmetric Group
Open Access
- 7 August 2025
- journal article
- Published by American Physical Society (APS) in PRX Quantum
- Vol. 6 (3)
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.Keywords
All Related Versions
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:
- An efficient quantum algorithm for preparation of uniform quantum superposition statesQuantum Information Processing, 2024
- Positivity of the Symmetric Group Characters Is as Hard as the Polynomial Time HierarchyInternational Mathematics Research Notices, 2023
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in $\mathsf{{NP}}$ NPQuantum Information Processing, 2014
- The density-matrix renormalization group in the age of matrix product statesAnnals of Physics, 2011
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchyProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2010
- Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic GroupCommunications in Mathematical Physics, 2006
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- Enumerative Combinatorics1999
- Noncommutative schur functions and their applicationsDiscrete Mathematics, 1998
- Asymptotic of the largest and the typical dimensions of irreducible representations of a symmetric groupFunctional Analysis and Its Applications, 1985