Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2407.17649 · Physical Review Letters

Quantum Algorithms for Representation-Theoretic Multiplicities

Martín Larocca, Vojtěch Havlíček

Published May 12, 2025• 5 citations
arXivHTMLPDF

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, arXiv:2502.20253] with a classical algorithm which, if optimal, points to a O(n^{4+2k}) vs Ω[over ˜](n^{4k^{2}+1}) polynomial gap in quantum vs classical computational complexity for an integer parameter k.

DOI
10.1103/k5tx-xtr3

Related papers

Plethysm is in #BQP

Matthias Christandl, Aram W. Harrow, Greta Panova +2 more

Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #P. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients. Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. In particular, our result implies that the plethysm coefficients are in #BQP, which was only known in special cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform. Recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures our approach as well as the approaches of prior work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.

quant-pharXiv:2602.08441•Leibniz international proceedings in informatics•Feb 10, 2026•0 citations

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities

Greta Panova

Abstract 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 (Larocca and Havlicek in Quantum algorithms for representation-theoretic multiplicities, 2024. arXiv:2407.17649 ) (also Bravyi et al. in PRX Quantum 5(1):010329, 2024). In this paper, we show that for many of those cases the Kronecker and plethysm coefficients can also be computed in polynomial time via classical algorithms, thereby refuting some of the conjectures in Larocca and Havlicek (2024). This vastly limits the cases in which the desired superpolynomial quantum speedup could be achieved.

arXiv:2502.20253•Computational Complexity•Dec 18, 2025•0 citations

Kronecker Coefficients in #BQP

Christian Ikenmeyer, Sathyawageeswar Subramanian

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.

ACM Transactions on Quantum Computing•Aug 22, 2025•0 citations

A remark on the quantum complexity of the Kronecker coefficients

Christian Ikenmeyer, Sathyawageeswar Subramanian

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 only the quantum computing tools that are used in their paper and additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients.

arXiv:2307.02389•Jul 5, 2023•1 citation

Quantum Speedups Require Structure or Depth

Guy Blanc, Jordan Docter, Carmen Strassle +1 more

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

quant-pharXiv:2608.19158•Aug 20, 2026•0 citations

Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

Daniel Stilck França, Ngoc Hoang Anh Mai

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.

quant-pharXiv:2511.14389•Nov 19, 2025•0 citations
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, arXiv:2502.20253] with a classical algorithm which, if optimal, points to a O(n^{4+2k}) vs Ωover ˜ polynomial gap in quantum vs classical computational complexity for an integer parameter k.
Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #P. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients. Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. In particular, our result implies that the plethysm coefficients are in #BQP, which was only known in special cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform. Recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures our approach as well as the approaches of prior work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.
Abstract 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 (Larocca and Havlicek in Quantum algorithms for representation-theoretic multiplicities, 2024. arXiv:2407.17649 ) (also Bravyi et al. in PRX Quantum 5(1):010329, 2024). In this paper, we show that for many of those cases the Kronecker and plethysm coefficients can also be computed in polynomial time via classical algorithms, thereby refuting some of the conjectures in Larocca and Havlicek (2024). This vastly limits the cases in which the desired superpolynomial quantum speedup could be achieved.
One of the most basic conjectures in quantum complexity theory states that every ttt-query quantum algorithm can be simulated on most inputs by a poly(t)\mathrm{poly}(t)poly(t)-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every ttt-query ddd-round quantum algorithm can be simulated on most inputs with tO(d2)t^{O(d^2)}tO(d2) classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of BPP\mathsf{BPP}BPP vs. BQP\mathsf{BQP}BQP relative to a random oracle, a similarly longstanding problem.
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gmf,g_1,\ldots,g_mf,g1​,…,gm​ be real polynomials in nnn variables and f⋆f^\starf⋆ the infimum of fff over the semialgebraic set S(g)={x:gi(x)≥0}S(g)=\{x: g_i(x)\ge 0\}S(g)={x:gi​(x)≥0}. Let λkλ_kλk​ be the value of the order-kkk Lasserre relaxation. Assume either (i) f⋆=λkf^\star=λ_kf⋆=λk​ and the optimum is attained in the ℓ1\ell_1ℓ1​-ball of radius 1/21/21/2, or (ii) S(g)S(g)S(g) lies in the simplex {x≥0:∑jxj≤1/2}\{x\ge 0: \sum_j x_j\le 1/2\}{x≥0:∑j​xj​≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λkλ_kλk​ to accuracy ε>0\varepsilon>0ε>0 with runtime, for fixed kkk, O(nkε−4+nk/2ε−5),O ⁣(sg ⁣[nkε−4+ ⁣(nk+ ⁣∑i=1mnk−di)1/2 ⁣ε−5]), O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), O(nkε−4+nk/2ε−5),O(sg​[nkε−4+(nk+∑i=1m​nk−di​)1/2ε−5]), where sgs_gsg​ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε))O(n^{3k}\mathrm{poly}(1/\varepsilon))O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5)O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})O(nε−4+n​ε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log⁡(1/ε))O(n^{ω+1}\log(1/\varepsilon))O(nω+1log(1/ε)) bound with ω≈2.373ω\approx2.373ω≈2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.