Classical and Quantum Algorithms for Characters of the Symmetric Group
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}. Th...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-08-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/bq28-r2r7 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2691-3399 |