Stratified Sampling for Quasi-Probability Decompositions

Resumo Técnico: Amostragem Estratificada para Decomposições de Quase-Probabilidade

1. O Problema

As Decomposições de Quase-Probabilidade (QPDs) são técnicas fundamentais em algoritmos quânticos de curto prazo (NISQ) e em estágios iniciais de computação tolerante a falhas. Elas permitem substituir um circuito quântico "difícil" (ou ruidoso) por um conjunto de circuitos "mais fáceis" (implementáveis), cujos resultados ponderados reproduzem o observável alvo.

No entanto, a QPD introduz uma fonte adicional de variância além do ruído intrínseco de medição (ruído de disparo de Born): a variância de configuração. Isso ocorre porque o protocolo requer a amostragem aleatória de diferentes variantes de circuitos.

• Consequência: Para atingir uma precisão alvo fixa, essa variância extra exige um aumento no número de execuções do circuito (overhead), escalando exponencialmente com o tamanho do circuito através da norma-1 da QPD ($\|g\|_1$).
• Desafio: Mesmo quando o fator exponencial é tolerável, reduzir os fatores constantes na variância é crucial para expandir a utilidade prática desses métodos. Métodos de amostragem padrão ("naive sampling") tratam todas as configurações de forma independente e ignoram a estrutura subjacente da distribuição.

2. Metodologia

Os autores propõem uma mudança de perspectiva: tratar a variância de configuração como um problema de design de amostragem estatística clássica, importando ferramentas de redução de variância da estatística tradicional.

• Decomposição da Variância: Utilizando a Lei da Variância Total, eles separam a variância total do estimador em duas partes:

  1. Ruído de Born (Shot Noise): Variância intrínseca da medição quântica para uma configuração fixa.
  2. Variância de Configuração: Variância entre as diferentes médias condicionais de cada circuito variante.
     A estratégia visa reduzir apenas a segunda componente sem alterar a expectativa alvo (viés zero).

• Amostragem Estratificada (Stratified Sampling):

  • O espaço de configurações é dividido em "estratos" baseados em uma estatística determinística $S(\ell)$.
  • Em vez de amostrar configurações $i.i.d.$ (independentes e identicamente distribuídas) da distribuição global, o método aloca um número fixo de amostras para cada estrato.
  • Alocação Proporcional: O artigo foca na alocação onde o número de amostras em cada estrato é proporcional à sua massa de probabilidade ($K_s \propto w_s$).
  • Teorema Principal: Eles provam que, sob alocação proporcional ideal, a variância do estimador estratificado é nunca pior do que a amostragem ingênua, sendo estritamente melhor sempre que as médias dos estratos não forem idênticas.

• Estratificação por Vetor de Contagens (Counts-Vector Stratification):

  • Para QPDs na forma de produto (comuns em PEC e PAI), eles definem um estatístico invariante por permutação: o vetor de contagens $M$. Este vetor conta quantas vezes cada primitiva local (ex: porta Pauli específica ou ângulo de rotação) aparece no circuito, ignorando a ordem das portas.
  • Configurações que diferem apenas pela permutação das portas pertencem ao mesmo estrato.

• Algoritmo Dinâmico (Dynamic Programming - DP):

  • Para tornar a estratificação viável, os autores desenvolvem um algoritmo de programação dinâmica clássico que:
    1. Calcula exatamente os pesos de cada estrato ($w_m = Pr(M=m)$) para uma distribuição Poisson-Multinomial.
    2. Gera amostras condicionais exatas de configurações $\ell$ dado um vetor de contagens $M=m$.
  • Complexidade: Pré-processamento $O(d \nu^d)$ e geração por amostra $O(\nu d)$, onde $d$ é a largura local e $\nu$ a profundidade do circuito. Isso é polinomial em $\nu$ para $d$ fixo.

• Correção de Viés (Residual-Aware Allocation):

  • Como o número de amostras por estrato deve ser um inteiro, a alocação proporcional ideal (não inteira) requer arredondamento. O artigo propõe um método de alocação de Hamilton com um "estrato residual" para garantir que o estimador permaneça exatamente não tendencioso (unbiased) mesmo com orçamentos finitos.

3. Contribuições Principais

1. Prova de "Nunca Pior": Estabelecimento teórico de que a estratificação proporcional em QPDs reduz a variância ou a mantém igual à amostragem ingênua, sem custo adicional de recursos quânticos.
2. Estrutura Universal: Desenvolvimento de uma técnica de pré-processamento clássico (DP) que é independente do observável ou do hardware específico, aplicável a qualquer QPD na forma de produto.
3. Algoritmo Eficiente: Implementação de um amostrador condicional exato que permite a execução prática da estratificação sem alterar o tempo de execução quântica (apenas troca o plano de amostragem clássico).
4. Análise de Custo-Benefício: Demonstração de que, embora a estratificação não altere a escala exponencial fundamental do overhead ($\|g\|_1$), ela reduz significativamente os fatores constantes, expandindo o regime de utilidade prática.

4. Resultados Numéricos

Os autores validaram a abordagem em circuitos de evolução temporal do Modelo de Ising com Campo Transverso (TFIM) usando duas técnicas QPD comuns:

• Interpolação de Ângulo Probabilístico (PAI): Substituição de rotações ideais por combinações de rotações discretas.
• Cancelamento de Erro Probabilístico (PEC): Mitigação de ruído de despolarização.

Desempenho Observado:

• Regime de Oráculo (Sem ruído de Born): Reduções de variância de 60% a 80%. Isso indica que o vetor de contagens explica uma grande fração da variância entre configurações.
• Regime de Disparo Único (Single-shot, dominado por ruído de Born): Reduções robustas de ~10%. Mesmo com ruído de medição alto, a estratificação oferece ganhos significativos.
• Custo Computacional: O pré-processamento clássico é viável para profundidades moderadas (ex: $\nu \approx 100$) em hardware convencional.

5. Significado e Impacto

• Otimização Imediata: A técnica pode ser aplicada imediatamente a protocolos QPD existentes (como PEC e PAI) sem exigir recursos quânticos adicionais ou mudanças no hardware. Apenas o software de controle (pré e pós-processamento) precisa ser atualizado.
• Relevância para Tolerância a Falhas: Em computadores quânticos tolerantes a falhas iniciais, onde as taxas de relógio lógico são lentas e os orçamentos de medição são apertados, reduções constantes de 10-20% no número de execuções necessárias podem ser o diferencial entre a viabilidade e a inviabilidade de um algoritmo.
• Generalização: O framework de decomposição de variância e estratificação pode ser estendido para outros esquemas de randomização quântica, como randomized compiling, twirling e sombras clássicas.

Em resumo, o trabalho demonstra que a variância de configuração em protocolos quânticos estocásticos não é um limite fundamental, mas sim um problema de design de amostragem que pode ser mitigado eficientemente através de métodos estatísticos clássicos bem estabelecidos, adaptados para a estrutura específica das QPDs.