Quantum Algorithms for Representation-Theoretic Multiplicities

Area of Science:

• Representation Theory
• Algebraic Combinatorics
• Quantum Computing

Background:

• Kostka, Littlewood-Richardson, Plethysm, and Kronecker coefficients are crucial in representation theory, geometric complexity, and algebraic combinatorics.
• These coefficients represent multiplicities in the decomposition of symmetric group representations.

Purpose of the Study:

• To develop quantum algorithms for computing these important coefficients.
• To investigate the existence of efficient classical algorithms for these computations.

Main Methods:

• Development of quantum algorithms for coefficient computation under specific dimension ratio conditions.
• Analysis of classical algorithm feasibility for different coefficient types.

Main Results:

• Quantum algorithms are presented for computing coefficients when representation dimension ratios are polynomial.
• An efficient classical algorithm for Kostka numbers is demonstrated.
• Conjectures are made regarding classical algorithms for Littlewood-Richardson coefficients and quantum speedups for Plethysm and Kronecker coefficients.

Conclusions:

• The study provides new quantum algorithmic approaches for key representation-theoretic computations.
• While classical algorithms exist for some coefficients (e.g., Kostka), quantum algorithms offer potential advantages for others.
• Recent work has disproven conjectures about classical vs. quantum complexity for Kronecker coefficients, highlighting a significant polynomial gap.