Classical and quantum algorithms for characters of the symmetric group
Sergey Bravyi, David Gosset, Vojtech Havlicek, Louis Schatzki · 2025
Read Classical and quantum algorithms for characters of the symmetric group by Sergey Bravyi, David Gosset, Vojtech Havlicek, Louis Schatzki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12579.txt.
Introduction
Sergey Bravyi, David Gosset, Vojtech Havlicek, and Louis Schatzki find faster ways to compute characters, the key numerical fingerprints of the symmetric group's representations. These values appear across group theory, but for permutations they are notoriously hard: worst-case computation sits in the hardest counting class.
Their classical method encodes all the characters of one permutation in a matrix product state. That is a compact chain form borrowed from quantum physics. It uses a known bridge between characters and quantum spin chains, which they also re-derive more simply. A matching quantum circuit of polynomial size prepares the same state, giving an efficient quantum route to related sampling tasks. The authors also prove a general link between computing a probability exactly and merely sampling from it, for problems with the right grain, a result they note may stand on its own.
Catalog record
| CREATOR | Sergey Bravyi, David Gosset, Vojtech Havlicek, Louis Schatzki |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-12579
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Classical and quantum algorithms for characters of the symmetric group Sergey Bravyi, David Gosset, Vojtech Havlicek, Louis Schatzki Abstract Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group S n 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 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 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 p o l y ( n ) 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 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. I Introduction Representation theory provides a powerful set of tools for analyzing systems invariant under the action of some group such as a molecular symmetry group in chemistry or a gauge group in quantum field theory. For example, the eigenvalue spectrum of a quantum system is usually computed by decomposing the Hilbert space into a direct sum of irreducible representations of the symmetry group and diagonalizing each irreducible block of the Hamiltonian separately. The character of an irreducible representation (irrep) can be viewed as its fingerprint that uniquely identifies the irrep and facilitates many computational tasks. In the case of abelian groups such as the symmetry group of a periodic lattice, characters are basis functions of the Fourier transform associated with a given frequency or momentum. In general, the character of a group element g is defined as the trace of a matrix describing the action of g for a given irrep. Here we address the problem of computing characters of the symmetric group S_{n} , that is, the group of all possible permutations of n objects. Symmetric groups S_{n} with small values of n often emerge as molecular symmetries in chemistry. For example, S_{4} and S_{5} describe molecules with tetrahedral and icosahedral symmetries such as the methane and the fullerene. The group S_{6} is isomorphic to the symplectic group describing the action of two-qubit Clifford gates commonly used in quantum computation [ 1 ] . Moreover, Cayley’s theorem asserts that any finite group is isomorphic to a subgroup of S_{n} [ 2 ] . Unfortunately, characters of S_{n} lack a simple analytic formula. In fact, it was shown [ 3 , 4 ] that the problem of computing the character of a given permutation g\in S_{n} for a given irrep of S_{n} is #P-hard, that is, at least as hard as counting the number of solutions of an NP-hard problem. While this leaves little hope for an efficient algorithm with runtime scaling polynomially with n , one may ask how well can we do in practice and whether it is possible to compute characters of S_{n} for moderately large values of n , say n\leq 100 ? To motivate this problem, we note that characters of S_{n} with large values of n describe amplitudes of Laughlin states in the Fractional Quantum Hall Effect [ 5 , 6 , 7 , 8 ] . Having access to characters of S_{n} enabled computation of the electron density and correlation functions of Laughlin states [ 5 ] . Another application is computing integrals of high-degree polynomials over the unitary group [ 9 ] . Such integrals can be computed using Weingarten functions which depend on S_{n} characters [ 9 ] . Algorithms for S_{n} characters may also facilitate evaluation of kernel functions for solving ranking problems in machine learning [ 10 , 11 ] . Our first contribution is an algorithm for computing characters of S_{n} based on Matrix Product States (MPS). These are tensor networks commonly used for simulating ground state properties of quantum spin chains [ 12 ] . A deep connection between characters of S_{n} and quantum spin chains was recently established by Crichigno and Prakash [ 13 ] . These authors showed that characters of a given permutation g\in S_{n} associated with all possible irreps of S_{n} can be read off as amplitudes of a certain quantum state |\psi_{g}\rangle describing 2n fermionic modes. The state |\psi_{g}\rangle is defined in terms of current operators J_{\ell}=\sum_{i=1}^{2n-\ell}a_{i+\ell}^{\dagger}a_{i}, where \ell is an integer and a_{i}^{\dagger} ( a_{i} ) are fermionic creation (annihilation) operators. Specifically, |\psi_{g}\rangle=\prod_{j=1}^{c(g)}J_{\nu_{j}}|1^{n}0^{n}\rangle, where c(g) is the number of cycles in g , \nu_{j} is the length of the j -th cycle, and |1^{n}0^{n}\rangle is the Fock basis state with the first n modes occupied and remaining modes empty. The order in the product does not matter since the current operators pairwise commute [ 13 ] . For each irrep \lambda of S_{n} , the Crichigno and Prakash mapping gives a Fock basis vector x_{\lambda}\in\{0,1\}^{2n} such that the amplitude \langle x_{\lambda}|\psi_{g}\rangle coincides with the character of g associated with \lambda . Section III provides a simplified derivation of Crichigno and Prakash mapping. Our derivation may be slightly more accessible to physicists as it avoids the heavy machinery of non-commutative symmetric polynomials used in the original work [ 13 , 14 ] . Instead, we apply an elegant formula derived by Frobenius in 1900 [ 15 ] to express the characters in terms of fermionic Slater determinants. Rewriting this formula using the fermionic second quantization formalism reproduces the result of [ 13 ] . The standard Jordan Wigner transformation maps 2n fermionic modes to 2n qubits. We show that the image of the current operator J_{\ell} under this mapping is a Matrix Product Operator (MPO) with bond dimension \ell+2 . Applying a sequence of MPOs to an initial product state is a common subroutine in quantum spin chain simulations and a variety of highly optimized software libraries for this task is available such as \mathsf{quimb} [ 16 ] or \mathsf{mpnum} [ 17 ] . Our problem is particularly well suited for MPO-MPS simulation because characters of S_{n} are integer valued. Accordingly, a small error introduced by truncating singular values in the intermediate MPS can be tolerated. A detailed description of our algorithm and numerical experiments can be found in Section IV . As mentioned above, computing S_{n} characters is a #P-hard problem. Thus, neither classical nor quantum algorithms for this problem are expected to run in time poly(n) . The main obstacle for the classical MPS algorithm is a rapid growth of entanglement which results in an exponentially large MPS bond dimension. A natural question is whether a quantum computer can efficiently prepare the state |\psi_{g}\rangle ? Surprisingly, we show that the answer is YES. To this end, we construct a quantum circuit of size poly(n) that prepares the uniform superposition of all permutations in the conjugacy class of g . We show that applying the Quantum Fourier Transform (QFT)