Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
Greta Panova
Littlewood-Richardson,Kronecker和plethysm coefficients是代表性理论和代数组合学中兴趣的基本多样性。 确定Kronecker和plethysm系数的组合解释是一个主要开放问题,并促使考虑其计算复杂性。 最近,它们表明在量子计算方面表现相对较好,对于一些大家庭来说,有多项式时间量子算法[Larocca,Havlicek,arXiv:2407.17649](也[BCGHZ,arXiv:2302.11454])。 在本文中,我们表明,对于其中许多情况,Kronecker和plethysm系数也可以通过经典算法在多项式时间计算,从而驳斥了[LH24]中的一些猜想。 这极大地限制了实现所需的超多项式量子加速的情况。
Littlewood-Richardson, Kronecker and plethysm coefficients are fundamental multiplicities of interest in Representation Theory and Algebraic Combinatorics. Determining a combinatorial interpretation for the Kronecker and plethysm coefficients is a major open problem, and prompts the consideration of their computational complexity. Recently it was shown that they behave relatively well with respect to quantum computation, and for some large families there are polynomial time quantum algorithms [L...