Plethysm is in #BQP

Resumo Técnico: "Plethysm is in #BQP"

1. O Problema

O artigo aborda o cálculo de multiplicidades de representação, um problema central na teoria de representações, combinatória algébrica, teoria da complexidade geométrica (GCT) e informação quântica. Especificamente, o foco recai sobre os coeficientes de plethysm ($a^\lambda_{\mu,\nu}$), que medem a multiplicidade de uma representação irredutível em uma composição de outras duas representações.

Embora coeficientes como os de Littlewood-Richardson pertençam à classe de complexidade #P (contagem de objetos combinatórios verificáveis em tempo polinomial), os coeficientes de plethysm e de Kronecker são muito mais complexos. Atualmente, sabe-se que eles são #P-difíceis e que decidir sua positividade é NP-difícil, mas não se sabia se eles pertenciam a classes de complexidade quântica específicas, como #BQP (o análogo quântico de #P).

2. Metodologia

Os autores propõem uma abordagem baseada na dualidade de Schur-Weyl e no uso de transformadas de Schur quânticas. A estratégia principal consiste em tratar o problema como um problema de multiplicidades de ramificação (branching multiplicities).

A metodologia segue um framework de dois passos (formalizado no Apêndice A):

1. Embutimento (Embedding): Embutir o módulo de representação que se deseja decompor em um "modelo de representação" ($V_{model}$) maior, que seja mais fácil de manipular computacionalmente. Para o plethysm, isso é feito através de camadas de Transformada de Schur inversa, mapeando o espaço de testemunhas para um espaço de tensores de dimensão $n$.
2. Amostragem de Fourier Forte (Strong Fourier Sampling): Aplicar uma Transformada de Schur (ou de Fourier do grupo) no espaço de modelo e realizar medições para identificar a etiqueta da representação irredutível ($\lambda$) e um estado de base fixo no módulo de Weyl.

O diferencial técnico é o uso de versões recentes da Transformada de Schur que dependem apenas polilogaritmicamente da dimensão local, permitindo lidar com dimensões que crescem exponencialmente em relação ao tamanho da entrada.

3. Principais Contribuições

• Unificação: O trabalho unifica resultados anteriores sobre coeficientes de Kronecker e casos especiais de plethysm, tratando-os todos como casos particulares de um problema geral de multiplicidades de ramificação para produtos de grupos lineares gerais ($GL$).
• Generalização do Problema de Ramificação: Os autores definem formalmente o problema de ramificação para produtos de $GL$ de forma que a codificação da entrada seja eficiente (polinomial), permitindo que o problema de plethysm seja reduzido a ele.
• Framework de Complexidade: Estabelecem um método geral para provar que multiplicidades de representação estão em #BQP baseando-se na existência de embutimentos equivariantes e amostragem de Fourier eficiente.

4. Resultados Principais

• Teorema 1.2: O problema de calcular coeficientes de plethysm está em #BQP. Consequentemente, decidir se um coeficiente de plethysm é positivo está em QMA (o análogo quântico de NP).
• Teorema 1.3: O problema geral de multiplicidades de ramificação para produtos de grupos lineares gerais está em #BQP.
• Teorema 1.4: Mostram que essas multiplicidades também pertencem à classe GapP (a diferença entre dois números de #P), o que fornece uma perspectiva de complexidade clássica.
• Algoritmos Clássicos: Demonstram que, quando certos parâmetros (como o número de partes da partição $\lambda$ e o tamanho de $\mu$) são fixos, o coeficiente de plethysm pode ser calculado em tempo polinomial clássico (FP).

5. Significância

Este trabalho tem implicações profundas em várias frentes:

• Teoria da Complexidade: Se alguém provar que os coeficientes de plethysm não estão em #P, isso implicaria uma separação histórica entre as classes #P e #BQP, sugerindo que computadores quânticos podem contar objetos de uma forma que computadores clássicos não conseguem.
• Teoria da Complexidade Geométrica (GCT): Fornece ferramentas para entender os obstáculos de multiplicidade usados para tentar separar as classes de complexidade algébrica VP e VNP.
• Química Quântica e Física: O resultado tem aplicação direta no problema de N-representabilidade (um problema fundamental para descrever estados de muitos férmions), mostrando que a computação quântica possui uma vantagem natural para lidar com essas simetrias.