A 0.651-approximation to quantum Max Cut via Rydberg atoms

Resumo Técnico: Uma Aproximação de 0,651 para o Max Cut Quântico via Átomos de Rydberg

Definição do Problema
O artigo aborda o problema do Max Cut Quântico (QMC), que é equivalente a encontrar a energia do estado fundamental do Hamiltoniano de Heisenberg antiferromagnético. Este problema é QMA-completo, o que significa que não pode ser resolvido eficientemente mesmo com um computador quântico universal. O objetivo é encontrar um algoritmo de aproximação que garanta uma solução dentro de uma razão específica ($\alpha$) da energia do estado fundamental ideal. O estado da arte atual, baseado exclusivamente em relaxações de programação semidefinida (SDP), alcança uma razão de aproximação de $\alpha = 0,614$.

Metodologia: Uma Abordagem Híbrida Quântico-Clássica
Os autores propõem um algoritmo híbrido que integra a dinâmica quântica natural de sistemas de átomos de Rydberg com técnicas de otimização clássica (SDP e arredondamento aleatório). A metodologia procede em quatro estágios distintos:

1. Codificação e Recozimento (Annealing):
   Uma instância de QMC definida em um grafo $G=(V, E, \omega)$ é codificada em um arranjo de átomos de Rydberg. A parte estática do Hamiltoniano de Rydberg, $H_r$, é construída para conter os termos de interação $XX + YY$ correspondentes às arestas do grafo:
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   O sistema passa por um procedimento de recozimento para preparar um estado fundamental aproximado, denotado por $\varrho_r$.

2. Medição e Formulação de Restrições:
   Os valores de expectativa $\langle X_i X_j + Y_i Y_j \rangle$ são medidos para todas as arestas no estado recozido $\varrho_r$. Esses valores servem como restrições empíricas para uma etapa subsequente de otimização clássica.

3. Programação Semidefinida e Arredondamento:
   Uma matriz de pseudo-momentos $\Delta$ é otimizada via SDP, sujeita às restrições derivadas das medições de Rydberg e às relações algébricas dos operadores de Pauli. Esta matriz é então arredondada para um estado de produto $\varrho_p$ usando uma técnica de projeção aleatória (decomposição de Cholesky seguida de projeção aleatória de $\mathbb{R}^{4n}$ para $\mathbb{R}^3$).

4. Seleção do Estado Final:
   O algoritmo retorna o estado com a menor energia: ou o estado fundamental de Rydberg $\varrho_r$ ou o estado de produto classificado classicamente $\varrho_p$.

Principais Contribuições Teóricas
O artigo estabelece uma razão de aproximação condicional de 0,651, superando a melhor razão conhecida anteriormente de 0,614. A derivação baseia-se em dois insights teóricos principais:

• Limite Inferior via Estado Fundamental de Rydberg: Os autores provam que a energia do Hamiltoniano QMC completo ($H_{qmc}$) pode ser limitada inferiormente usando a energia do Hamiltoniano de Rydberg ($H_r$). Ao explorar a invariância $SU(2)$ do modelo de Heisenberg, eles mostram que os valores de expectativa de $XX$, $YY$e$ZZ$ são iguais no estado fundamental ideal. Isso permite a reconstrução da energia total do QMC a partir das medições parciais de $XX+YY$ obtidas do sistema de Rydberg.
• Limite Superior via Arredondamento: O artigo analisa a energia do estado de produto $\varrho_p$ gerado pelo arredondamento de SDP. Eles derivam uma expressão analítica para a energia esperada deste estado baseada nas correlações medidas.
• Otimização da Razão: Ao combinar o limite inferior (derivado do estado de Rydberg) e os limites superiores (do estado de Rydberg e do estado de produto), os autores formulam um problema de minimização sobre o parâmetro de correlação $t_{ij}$. A resolução deste problema resulta na razão de 0,651.

Resultos e Robustez

• Razão de Aproximação: O algoritmo alcança uma razão de aproximação condicional de $\kappa = 0,651$.
• Robustez ao Ruído: Um achado significativo é a resiliência do algoritmo à preparação imperfeita do estado fundamental. Os autores demonstram que a vantagem de 0,651 persiste mesmo se o procedimento de recozcimento de Rydberg produzir um estado com apenas 89% da energia do verdadeiro estado fundamental de Rydberg ($\eta = 0,89$). Abaixo deste limiar, a vantagem sobre os métodos puramente clássicos de SDP diminui.
• Complexidade Computacional: A abordagem híbrida reduz a dimensionalidade do problema de otimização clássica. Enquanto esquemas clássicos visando estados emaranhados exigem $O(n^4)$ variáveis reais, este método híbrido opera com $O(n^2)$ variáveis, aproveitando o sistema quântico para lidar com a complexidade da estrutura de emaranhamento.

Significância
O artigo afirma abrir um novo caminho para algoritmos híbridos quântico-clássicos. Ele demonstra que combinar hardware quântico (especificamente arranjos de átomos de Rydberg) com otimização clássica pode gerar garantias de aproximação mais fortes do que métodos clássicos isolados, mesmo quando o hardware quântico não resolve perfeitamente o problema do Hamiltoniano subjacente. O trabalho sugere que plataformas quânticas podem servir como "proxies" eficazes para fornecer limites inferiores de alta qualidade e pontos de partida para procedimentos de arredondamento clássico, contornando efetivamente algumas das limitações de escala computacional de abordagens puramente clássicas.