Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

Este artigo propõe o SBO-QAOA, um algoritmo quântico direcionado à temperatura baseado na teoria da correspondência quântico-clássica que alcança a amostragem justa de estados fundamentais degenerados ao convergir para uma distribuição de Gibbs uniforme, superando os vieses inerentes ao QAOA padrão mesmo com parâmetros variacionais mínimos.

O essencial

O Grande Problema: Encontrar o Vencedor "Justo"

Imagine que você está organizando um concurso para encontrar a melhor solução para um quebra-cabeça complexo. Em muitos casos, não existe apenas uma resposta perfeita; existem várias respostas diferentes que são todas igualmente perfeitas. Vamos chamá-las de "estados fundamentais degenerados".

No mundo real, se você tem cinco equipes diferentes que empataram em primeiro lugar, você quer escolher uma delas ao acaso para que nenhuma equipe se sinta prejudicada. Isso é chamado de amostragem justa (fair sampling). Você quer que o computador escolha a Equipe A, a Equipe B ou a Equipe C com igual probabilidade, não favorecendo uma só porque o funcionamento do computador assim o fez.

O problema é que o método líder atual para resolver esses quebra-cabeças em computadores quânticos (chamado QAOA) é um pouco como um árbitro tendencioso. À medida que o computador se aprofunda no cálculo (aumentando a "profundidade do circuito"), ele começa a favorecer acidentalmente certas equipes vencedoras sobre outras, embora todas sejam matematicamente iguais. Ele deixa de ser justo.

O Jeito Antigo vs. O Jeito Novo

Os pesquisadores, Tetsuro Abe e Shu Tanaka, observaram como corrigir isso.

• O Jeito Antigo (QAOA Padrão): Pense nisso como tentar encontrar o fundo de um vale. O computador usa uma ferramenta de "sacudida" padrão (um misturador de campo transversal) para ajudar a bola a rolar para baixo. O problema é que essa ferramenta de sacudida empurra a bola para pontos específicos no fundo do vale, ignorando os outros pontos igualmente profundos. É como um vento que sopra em apenas uma direção, empurrando a bola para um lado do chão do vale.
• O Jeito Novo (SBO-QAOA): Em vez de mudar a ferramenta de "sacudida", os pesquisadores decidiram mudar o formato do próprio vale. Eles usaram um truque matemático inteligente baseado na "correspondência quântico-clássica".

A Analogia Criativa: O Mapa Direcionado pela Temperatura

Imagine que você quer simular uma multidão de pessoas em uma sala.

• QAOA Padrão é como tentar fazer com que todos se sentem na única cadeira mais confortável. Funciona, mas força todos a um único lugar, ou faz com que o sistema fique preso favorecendo uma cadeira sobre outra.
• SBO-QAOA é como definir a temperatura da sala.
  • Se a sala estiver muito fria (temperatura baixa), todos querem sentar nos melhores assentos absolutos.
  • Se a sala estiver quente (temperatura mais alta), as pessoas estão mais relaxadas e espalhadas, sentando em vários bons assentos com uma probabilidade que condiz com o quão confortáveis elas estão.

Os pesquisadores projetaram um novo "mapa" (chamado Hamiltoniano SBO) que codifica esse conceito de temperatura diretamente nas regras do computador quântico. Em vez de apenas procurar pelo ponto de menor energia, o computador é programado para naturalmente se estabelecer em uma distribuição que parece uma sala quente, onde todos têm uma chance igual de sentar em qualquer um dos "melhores" assentos.

O Que Eles Fizeram (O Experimento)

Para testar isso, eles usaram um pequeno "modelo de brinquedo" com apenas 5 spins (como 5 pequenos ímãs). Este modelo foi desenhado para ter seis soluções diferentes que eram todas igualmente boas (um empate de seis vias).

Eles executaram dois tipos de simulações:

1. QAOA Padrão: Eles aumentaram a complexidade (profundidade do circuito) para ver se ele conseguia encontrar os vencedores.
2. SBO-QAOA: Eles usaram seu novo mapa "direcionado pela temperatura".

Os Resultados

• QAOA Padrão: À medida que tornavam o cálculo mais profundo, o computador encontrava as soluções vencedoras com muita frequência (quase 100% das vezes). No entanto, era injusto. Ele continuava escolhendo duas soluções vencedoras específicas e ignorando as outras quatro. O "árbitro" era tendencioso.
• SBO-QAOA: O computador encontrou as soluções vencedoras cerca de 83% das vezes (que é exatamente o que a física prevê para uma sala naquela "temperatura" específica). Crucialmente, quando encontrava um vencedor, ele escolhia todas as seis soluções com probabilidade igual. Foi perfeitamente justo.

Melhor ainda, eles testaram uma versão "simplificada" de seu novo método, onde reduziram o número de configurações que o computador precisava ajustar para apenas quatro botões. Mesmo com essa configuração simples, o computador permaneceu justo e direcionado pela temperatura.

A Conclusão

O artigo afirma que você não precisa inventar uma nova ferramenta de "sacudida" complicada para obter resultados justos. Em vez disso, se você mudar o alvo para o qual o computador está mirando (usando o Hamiltoniano SBO), o computador aprende naturalmente a escolher todos os vencedores empatados de forma justa, tal como pessoas se espalhando em uma sala a uma determinada temperatura.

Isso funciona mesmo se mantivermos as configurações simples (esquema linear), sugerindo que a amostragem justa é possível sem tornar o circuito do computador quântico excessivamente complexo. Os autores observam que, embora isso funcione muito bem em pequenas simulações, o próximo passo é descobrir como construir isso de forma eficiente em máquinas quânticas reais e de grande escala, já que o novo "mapa" envolve interações complexas que são difíceis de construir fisicamente.

Resumo técnico

Resumo Técnico: Amostragem Justa com QAOA de Alvo de Temperatura

Enunciado do Problema
Em problemas de otimização combinatória caracterizados por estados fundamentais degenerados, a capacidade de realizar uma "amostragem justa" (fair sampling) — obtendo uma distribuição uniforme sobre todos os estados soluções degenerados sem viés — é crítica. Embora o Recozimento Quântico (QA) e o Algoritmo de Otimização Aproximada Quântica (QAOA) sejam metaheurísticas promissoras para esses problemas, implementações padrão que utilizam um mixer de campo transversal frequentemente falham em alcançar uma amostragem justa. Evidências teóricas e experimentais sugerem que, à medida que a profundidade do circuito aumenta, o QAOA padrão induz vieses entre estados degenerados, favorecendo soluções específicas mesmo quando a razão de aproximação converge para a unidade. Soluções existentes, como mixers especializados ou pós-processamento híbrido, muitas vezes aumentam a complexidade do circuito ou exigem etapas computacionais clássicas adicionais.

Metodologia
Os autores propõem o SBO-QAOA, uma variante do QAOA que aborda o viés de amostragem não modificando o mixer, mas redesenhando o Hamiltoniano de custo (alvo) com base na teoria da correspondência quântico-clássica.

• Estrutura Teórica: Em vez de visar o estado fundamental do Hamiltoniano de Ising clássico $\hat{H}_0$, o SBO-QAOA visa o estado fundamental de um Hamiltoniano efetivo, $\hat{H}_S(T)$, derivado de Somma et al. Este Hamiltoniano é construído de tal forma que seu estado fundamental único corresponde a um estado quântico $|\psi_{Gibbs}(T)\rangle$, onde as amplitudes de probabilidade são as raízes quadradas dos fatores de Boltzmann do sistema clássico em uma temperatura específica $T$.
• Construção do Hamiltoniano: O Hamiltoniano SBO é definido como:
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  onde $\hat{H}_i$ representa os termos locais de $\hat{H}_0$ dependentes do spin $i$, e $\alpha$ é um fator de escala que evita a divergência conforme $T \to 0$. No SBO-QAOA, $\hat{H}_C$ é definido como $\hat{H}_S(T)$, enquanto o mixer de campo transversal padrão $\hat{H}_X$ é mantido.
• Esquemas de Parametrização: O estudo avalia duas estratégias de parametrização para os ângulos variacionais $\{\gamma_k, \beta_k\}$:
  1. Parâmetro Total (Full-parameter): $2p$ variáveis independentes para a profundidade do circuito $p$.
  2. Linearizada: Um esquema de redução onde os ângulos são funções lineares do índice de profundidade, reduzindo as variáveis de otimização para quatro ($\gamma_{slope}, \gamma_{intcp}, \beta_{slope}, \beta_{intcp}$), independentemente da profundidade.
• Configuração Experimental: Simulações numéricas foram realizadas em um modelo de brinquedo de Ising frustrado de 5 spins com degeneração de estado fundamental de seis vezes. O sistema foi simulado exatamente (evolução de matriz completa) para comparar o QAOA padrão e o SOB-QAOA através de diferentes profundidades de circuito ($p=1$ a $100$) e temperaturas.

Resultos Principais

• Viés do QAOA Padrão: No QAOA padrão (visando $\hat{H}_0$), o aumento da profundidade do circuito $p$ conduz a probabilidade total do estado fundamental ($P_{GS}$) para a unidade. No entanto, a distribuição dentro do subespaço degenerado permanece enviesada; pares de estados específicos tornam-se dominantes enquanto outros são suprimidos, independentemente de serem usados parâmetros totais ou linearizados.
• Justiça do SBO-QAOA: Ao visar $\hat{H}_S(T)$, o SBO-QAOA exibe um comportamento fundamentalmente diferente:
  • Alvo de Temperatura: A probabilidade total do estado fundamental $P_{GS}$ não se aproxima da unidade, mas satura em um valor consistente com a probabilidade da distribuição de Gibbs na temperatura $T$ especificada (ex: $\approx 0,83$ para $T=1$).
  • Amostragem Uniforme: À medida que $p$ aumenta, a distribuição de probabilidade entre os estados fundamentais degenerados torna-se uniforme. As probabilidades de distintos pares de estados convergem para valores idênticos, confirmando uma amostragem justa.
  • Distância de Variação Total (TVD): A TVD entre a distribuição de saída e a distribuição de Gibbs alvo diminui com o aumento de $p$, convergindo para próximo de zero. Isso confirma que o algoritmo reproduz a distribuição completa de temperatura finita, e não apenas os estados fundamentais.
• Robustez à Redução de Parâmetros: A amostragem justa e as propriedades de alvo de temperatura do SBO-QAOA são preservadas mesmo sob o esquema linearizado, onde o número de parâmetros variacionais é reduzido de $2p$ para apenas quatro.

Significância e Alegações
O artigo afirma que a amostragem justa no QAOA pode ser alcançada sem aumentar a complexidade do mixer ou adicionar etapas de pós-processamento clássico. Ao substituir o Hamiltoniano alvo pelo Hamiltoniano SBO, o algoritmo codifica inerentemente a distribuição de Gibbs como seu estado fundamental. Os autores demonstram que esta abordagem permite:

1. Amostragem Justa: Alcançar uma distribuição uniforme sobre estados fundamentais degenerados.
2. Alvo de Temperatura: Controlar a distribuição de amostragem via o parâmetro $T$.
3. Eficiência: Manter estas propriedades com um conjunto mínimo de parâmetros variacionais (quatro), tornando a abordagem potencialmente escalável em termos de complexidade de otimização.

Os autores observam que, embora o trabalho atual valide estas propriedades em um sistema pequeno via diagonalização exata, trabalhos futuros devem abordar a escalabilidade. Especificamente, implementar $\hat{H}_S(T)$ em dispositivos baseados em portas exige expansões de cadeias de Pauli e decomposições de circuito eficientes, já que o Hamiltoniano geralmente induz interações de muitos corpos.