An improved Quantum Max Cut approximation via matching

Resumo Técnico: Aproximação Melhorada para o Corte Máximo Quântico via Emparelhamento Máximo

1. O Problema: Corte Máximo Quântico (QMC)

O problema do Corte Máximo Quântico (Quantum Max Cut - QMC) é um problema de otimização quântica fundamental. Dado um grafo ponderado $G = (V, E, w)$, o objetivo é encontrar um estado quântico de alta energia (estado fundamental) para um Hamiltoniano antiferromagnético de Heisenberg definido como:
$$H = \sum_{(i,j) \in E} w_{ij} \frac{I - X_iX_j - Y_iY_j - Z_iZ_j}{4}$$
Onde $X_i, Y_i, Z_i$ são as matrizes de Pauli no qubit $i$. O problema é classificado como QMA-difícil, o que significa que encontrar a solução exata é computacionalmente intratável, mesmo para computadores quânticos, exigindo o uso de algoritmos de aproximação.

O desafio central reside em encontrar um estado quântico (que pode ser emaranhado) que maximize a energia esperada, superando as limitações dos algoritmos clássicos que operam apenas sobre estados de base ou produtos de estados.

2. Metodologia Proposta

Os autores propõem um algoritmo de aproximação clássico que combina duas abordagens distintas e seleciona a melhor delas. A inovação principal reside na simplificação drástica da etapa de "arredondamento" (rounding) da solução do Programa Semidefinido (SDP).

O algoritmo (Algoritmo 1) executa os seguintes passos:

1. Solução do SDP Nível-2: Resolve-se a hierarquia de Lasserre quântica no nível 2 para obter um vetor de solução que satisfaz certas restrições de momentos de Pauli.
2. Candidato 1: Estado de Produto (Roteamento de Gharibian-Parekh):
   • Utiliza-se a solução do SDP para gerar um estado de produto (não emaranhado) através de um arredondamento aleatório (amostragem de uma matriz gaussiana).
   • Este estado $\rho_1$ é um produto tensorial de estados de 1 qubit.
3. Candidato 2: Estado via Emparelhamento Máximo (Abordagem Nova):
   • Em vez de usar a solução do SDP para construir um estado emaranhado complexo (como feito em trabalhos anteriores), o algoritmo resolve o problema de Emparelhamento Máximo de Peso (Maximum Weight Matching - MWM) no grafo de entrada original.
   • Para as arestas no emparelhamento $M$, atribui-se o estado singlete (um estado emaranhado de 2 qubits: $(|01\rangle - |10\rangle)/\sqrt{2}$), que maximiza a energia localmente para aquela aresta.
   • Para os qubits não emparelhados, atribui-se o estado misto máximo ($I/2$).
   • O resultado é um estado $\rho_2$ que é um produto de estados de 1 e 2 qubits.
4. Seleção Final: O algoritmo calcula a energia esperada de ambos os estados ($\rho_1$ e $\rho_2$) e retorna aquele com a energia mais alta.

Diferenciação Chave: Diferente dos algoritmos anteriores (como Lee [10] e King [8]) que utilizam a solução do SDP nível-2 para gerar estados globalmente emarançados complexos, este algoritmo usa o SDP apenas para garantir que, se o estado de produto for ruim, o emparelhamento máximo fornecerá uma garantia de energia alta. O estado $\rho_2$ é construído independentemente da solução detalhada do SDP, dependendo apenas da estrutura do grafo.

3. Contribuições Teóricas e Técnicas

• Novas Desigualdades de "Convexgamy" de Emaranhamento: Os autores refinam o conceito de "monogamia de emaranhamento" em estrelas (grafos com um nó central conectado a vários vizinhos). Eles demonstram que, ao considerar triângulos no grafo, é possível derivar desigualdades não lineares mais fortes (chamadas de entanglement convexgamy) que definem uma região viável convexa para os valores de energia das arestas.
• Relacionamento entre SDP e Emparelhamento: Eles provam que os valores de energia derivados da solução do SDP nível-2 satisfazem as restrições de um Programa Linear (LP) relaxado para o problema de Emparelhamento Máximo. Especificamente, mostram que os valores $h^+_{ij}$ (relacionados à energia) formam um emparelhamento fracionário que pode ser escalado por um fator $\alpha = 4/5$ para se tornar viável para o LP de emparelhamento máximo.
• Simplificação do Arredondamento: A metodologia elimina a necessidade de arredondar soluções de SDP para estados emaranhados globais complexos, substituindo-a por uma combinação simples de estados de produto e estados singlete locais baseados em emparelhamento.

4. Resultados Principais

• Razão de Aproximação: O algoritmo alcança uma razão de aproximação de 0.595.
• Comparação com o Estado da Arte:
  • Supera o algoritmo anterior de Lee [10] (0.562) para grafos gerais.
  • Supera o algoritmo anterior de King [8] (0.582) para grafos sem triângulos.
• Limites Teóricos: Os autores observam que, mesmo com melhorias futuras nas desigualdades de monogamia (levando o fator de escala $\alpha$ a 1), o limite superior teórico para esta abordagem específica seria de 0.606.

5. Significado e Impacto

• Eficiência e Simplicidade: O algoritmo é significativamente mais simples de implementar do que os métodos anteriores que geram estados emaranhados globais. A etapa de emparelhamento máximo é polinomial e não depende da complexidade do arredondamento de SDP para estados quânticos complexos.
• Estrutura do Estado de Saída: O estado final é um produto de estados de no máximo 2 qubits. Isso é fisicamente mais realizável e menos suscetível a erros de decoerência em comparação com estados altamente emaranhados, mantendo uma garantia de desempenho superior.
• Avanço na Teoria de Aproximação Quântica: O trabalho demonstra que, para o QMC, a combinação inteligente de estados de produto e emaranhamento local (via emparelhamento) pode superar abordagens que tentam otimizar emaranhamento global complexo. Isso sugere que a "monogamia de emaranhamento" pode ser explorada de forma mais eficiente através de estruturas combinatórias clássicas (como emparelhamentos) do que apenas através de hierarquias de SDP puramente quânticas.
• Definição de Algoritmos Clássicos para Otimização Quântica: O artigo também discute a definição formal do que significa um algoritmo clássico resolver um problema de otimização quântica, propondo um quadro de verificador (Verifier) e provador (Prover) para classificar algoritmos cc, qc, cq e qq.

Em resumo, este trabalho estabelece um novo marco para a aproximação do Corte Máximo Quântico, demonstrando que uma abordagem híbrida, baseada em emparelhamento máximo e estados locais simples, supera os métodos anteriores mais complexos, oferecendo uma garantia de desempenho de 0.595.