August 22, 2025

Kronecker coefficients in #BQP

Key Points

Computing Kronecker coefficients in the symmetric group is within the #BQP complexity class, representing a substantial advancement.
The approach leverages quantum algorithmic tools alongside classical insights, improving prior results in computational complexity.
Findings also extend to plethysm coefficients and row sums of the symmetric group's character table, broadening the implications.
This work illustrates a significant intersection of quantum computing and representation theory, revealing new complexities.

Abstract

We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP . This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu. We use the same quantum algorithmic tools that are used in their paper, combined with additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients and the row sums of the symmetric group character table.

Ask AI

Mark Helpful

Bookmark

Relay