Quantum Algorithms for Representation-Theoretic Multiplicities
Authors:
Preprint
Abstract
Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are multiplicities of irreducible representations (irreps) of the symmetric group in restrictions and products of irreps. They play an important role in representation theory and are notoriously hard to compute. We give quantum algorithms that efficiently compute these coefficients whenever the ratio of dimensions of the representations is polynomial. Using that the Kostka numbers admit combinatorial interpretation, we show that there is an efficient classical algorithm for polynomially-bounded Kostka numbers and conjecture existence of a similar algorithm for the Littlewood-Richardson coefficients. We argue why the same classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients, give evidence on how our quantum algorithm may avoid some hardness obstructions in their computation, and conjecture that the problem could lead to superpolynomial quantum speedups on some inputs. We finally use Frobenius reciprocity to derive another quantum algorithm that estimates these coefficients using induction and has a different cost-to-input dependence.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Sylow Branching Coefficients and Hook PartitionsVietnam Journal of Mathematics, 2023
- The Computational Complexity of Plethysm Coefficientscomputational complexity, 2020
- On vanishing of Kronecker coefficientscomputational complexity, 2017
- On the complexity of computing Kronecker coefficientscomputational complexity, 2015
- Eigenvalue Distributions of Reduced Density MatricesCommunications in Mathematical Physics, 2014
- 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 many aspects of counting lattice points in polytopesMathematische Semesterberichte, 2005
- The Symmetric Group2001
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982