Agnostic learning of qudit stabilizer states

Resumo Técnico: Aprendizado Agnóstico de Estados Estabilizadores de Qudits

Definição do Problema
O artigo aborda a tarefa fundamental de aprender eficientemente uma descrição clássica de um estado quântico desconhecido. Embora o aprendizado de estados arbitrários sofra com a maldição da dimensionalidade, o aprendizado de estados estruturados (como estados estabilizadores) é mais tratável. No entanto, os algoritmos existentes para estados estabilizadores operam tipicamente no cenário "realizável", assumindo que o estado desconhecido coincide exatamente com um estado estabilizador. Em cenários realistas, o ruído afasta o estado alvo dessa estrutura ideal. Isso motiva o problema do aprendizado agnóstico: dados cópias de um estado desconhecido $|\psi\rangle$ que possui uma fidelidade $\tau$ com algum estado estabilizador desconhecido, o objetivo é produzir um estado estabilizador $|\phi\rangle$ tal que $F(|\psi\rangle, |\phi\rangle) \ge \max_{|\phi'\rangle \in \mathcal{C}} F(|\psi\rangle, |\phi'\rangle) - \varepsilon$, onde $\mathcal{C}$ é a classe dos estados estabilizadores.

Embora Chen et al. [STOC '25] tenham resolvido recentemente isso para sistemas de qubits ($d=2$), o problema para sistemas de qudits (onde a dimensão local $d > 2$ é um primo ímpar) permaneceu amplamente inexplorado. A generalização direta das técnicas de qubits falha devido a diferenças estruturais fundamentais, particularmente em relação ao comportamento dos operadores de Weyl e à distribuição dos resultados de medição.

Metodologia e Técnicas Principais
Os autores generalizam a estrutura de bootstrapping de estabilizadores para sistemas de qudits, superando três desafios técnicos primários:

1. Falha da Amostragem de Diferença de Bell Padrão: Em sistemas de qubits, a amostragem de diferença de Bell produz amostras da distribuição de Weyl $q_\psi$. Em sistemas de qudits, uma generalização direta produz uma distribuição distorcida que falha em se concentrar no grupo estabilizador. Os autores empregam a amostragem de diferença de Bell enviesada (skewed Bell difference sampling, introduzida por Allcock et al. [23] para o cenário realizável). Este protocolo utiliza uma unitária de emaranhamento construída a partir de resíduos quadráticos módulo $d$ para processar quatro cópias do estado. Para lidar com a complexidade da distribuição conjunta no cenário agnóstico, os autores analisam a distribuição marginal $B_\psi$ de uma única string de saída.

2. Anti-concentração da Distribuição Marginal: Um requisito crucial para o bootstrapping é que a distribuição de amostragem coloque massa suficiente nos elementos do grupo estabilizador fora do subgrupo atualmente conhecido (anti-concentração). Os autores provam que, para qualquer subespaço próprio $T$ do grupo estabilizador alvo $S$, a distribuição marginal satisfaz $\sum_{x \in S \setminus T} B_\psi(x) \ge \Omega(\tau^6)$.

   • Insight Chave: A prova evita uma otimização multivariada complexa necessária para $d$ geral ao reduzir o problema a um caso de um único qudit. Eles estabelecem um limite inferior para a fidelidade estabilizadora de qualquer estado de um único qudit ($2/(d+1)$ ao aproveitar o fato de que estados estabilizadores de um único qudit formam um 2-design projetivo complexo e constituem $d+1$ bases mutuamente não unbiased).

3. Não-Hermiticidade dos Operadores de Weyl: No cenário de qubits, os operadores de Weyl são Hermitianos, permit que a estimativa em lote de correlações seja feita via estimativa de média de Bernoulli. Para qudits ($d>2$), os operadores de Weyl são geralmente não-Hermitianos, tornando $\langle \psi | W_x | \psi \rangle$ complexo. Os autores abordam isso estimando as correlações ao quadrado $|\langle \psi | W_x | \psi \rangle|^2$ individualmente usando o teste SWAP, em vez de depender de observáveis Hermitianos.

Estrutura Algorítmica
O algoritmo proposto segue um procedimento iterativo de bootstrapping de estabilizador:

1. Amostragem: Realiza a amostragem de diferença de Bell enviesada para obter strings de Pauli a partir da distribuição marginal $B_\psi$.
2. Filtragem: Estima a correlação ao quadrado das strings amostradas com o estado de trabalho atual. Retém as strings de "alta correlação" (aquelas com correlação $> 1 - 1/(12d^2)$).
3. Construção de Base: Forma uma base a partir das strings de alta correlação que comutam. Se a base estiver incompleta (não gera o grupo estabilizador completo), a propriedade de anti-concentração garante que, com probabilidade $\Omega(\tau^6)$, uma nova string estabilizadora fora do espaço atual será amostrada.
4. Bootstrapping: Se um elemento estabilizador de baixa correlação for encontrado, mede-se o estado em seu autoestado e realiza-se a pós-seleção. Isso amplifica a fidelidade com o estado estabilizador alvo por um fator constante.
5. Iteração: Repete o processo com o estado amplificado até que o grupo estabilizador completo seja identificado.

Adicionalmente, para o regime de alta fidelidade ($\tau > \cos^2(\pi/8)$), os autores apresentam um algoritmo simplificado. Eles provam que, neste regime, as correlações ao quadrado dos operadores de Weyl dentro do grupo estabilizador estão estritamente separadas das de fora. Isso permite uma abordagem direta baseada em limiar que evita a maquinaria de bootstrapping iterativa, resultando em complexidade polinomial.

Resultados e Complexidade
O artigo apresenta o primeiro algoritmo quântico eficiente para o aprendizado agnóstico de estados estabilizadores de qudits puros ($d > 2$ primo).

• Regime Geral: Dado um estado de $n$-qudits desconhecido com fidelidade estabilizadora $\tau$, o algoritmo produz um estado estabilizador com fidelidade de pelo menos $\tau - \varepsilon$ com alta probabilidade.

  • Complexidade de Amostra: $O(n \log n) \cdot (d/\tau)^{O(d^2 \log(1/\tau))} + O(d/\varepsilon^2 \log^2(1/\tau))$.
  • Complexidade de Tempo: $O(n^3/\varepsilon^2) \cdot (d/\tau)^{O(d^2 \log(1/\tau))}$.
  • A complexidade é quase-polinomial quando $\tau = 1/\text{poly}(n)$, correspondendo aos melhores resultados conhecidos para qubits.

• Regime de Alta Fidelidade ($\tau > \cos^2(\pi/8) + \gamma$):

  • Complexidade de Amostra: $O(d^4 n \log n / \gamma^2)$.
  • Complexidade de Tempo: $O(n^3 + n^2 d^4 \log n / \gamma^2)$.
  • Este regime admite uma solução de tempo polinomial.

• Corolários:

  • Estimativa de Magia: O algoritmo permite a estimação eficiente da "magia" de um estado quântico (quantificada pela fidelidade estabilizadora) com erro aditivo $\varepsilon$.
  • List-Decoding (Decodificação de Lista): O método pode ser estendido para produzir uma lista de todos os estados estabilizadores com fidelidade $\ge \tau$.

Significância e Alegações
Os autores afirmam que este trabalho completa o quadro do aprendizado agnóstico para estados estabilizadores ao estender os resultados de qubits para qudits. A significância reside em:

1. Preenchimento da Lacuna: Fornecer a primeira solução eficiente para o aprendizado agnóstico no cenário de qudits, que anteriormente estava aberto devido a obstruções estruturais na generalização da amostragem de diferença de Bell.
2. Robustez: O algoritmo é projetado para lidar com ruído (cenário agnóstico), tornando-o aplicável a sistemas quânticos realistas onde os estados não são estabilizadores perfeitos.
3. Ferramentas Fundamentais: O artigo estabelece novos limites de anti-concentração para a amostragem de diferença de Bell enviesada e prova limites inferiores para a fidelidade estabilizadora de um único qudit usando propriedades de 2-design, que podem ter utilidade independente.
4. Quantificação de Magia: Ao permitir a estimativa eficiente da fidelidade estabilizadora, o trabalho fornece uma ferramenta prática para quantificar a magia quântica, um recurso chave para a vantagem quântica.

Os autores observam que seus resultados estão atualmente restritos a dimensões de primos ímpares e que estender para dimensões compostas ou estados mistos permanece um desafio em aberto. Eles também destacam que a dependência quase-polinomial de $1/\tau$ é uma limitação compartilhada com algoritmos de qubits, e melhorar isso para tempo polinomial mantendo a dependência polinomial de $n$ e $1/\varepsilon$ é um grande problema em aberto.