Quantum Algorithms for Representation-Theoretic Multiplicities
Authors:
Open Access
- 2 July 2025
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 135 (1) , 010602
Abstract
Kostka, Littlewood-Richardson, Plethysm, and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric group that play an important role in representation theory, geometric complexity, and algebraic combinatorics. We give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the representations is polynomial. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups. The conjecture about Kronecker coefficients was disproved by Panova [Polynomial time classical versus quantum algorithms for representation theoretic multiplicities, ] with a classical algorithm which, if optimal, points to a O ( n 4 + 2 k ) vs Ω ˜ ( n 4 k 2 + 1 ) polynomial gap in quantum vs classical computational complexity for an integer parameter k .Keywords
All Related Versions
Funding Information
- Los Alamos National Laboratory
- Laboratory Directed Research and Development (20230049DR)
This publication has 30 references indexed in Scilit:
- The Computational Complexity of Plethysm Coefficientscomputational complexity, 2020
- On vanishing of Kronecker coefficientscomputational complexity, 2017
- On the complexity of computing Kronecker coefficientscomputational complexity, 2015
- Symmetry, Representations, and Invariants2009
- Nonzero Kronecker Coefficients and What They Tell us about SpectraCommunications in Mathematical Physics, 2007
- The Spectra of Quantum States and the Kronecker Coefficients of the Symmetric GroupCommunications in Mathematical Physics, 2005
- The Symmetric Group2001
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982
- Spin Eigenfunctions1979
- Linear Representations of Finite Groups1977