Locally Acting Grover Mixers for Constraint-Preserving QAOA

Este artigo propõe misturadores de Grover de atuação local que substituem as dispendiosas portas de deslocamento de fase multicontroladas globais no GM-QAOA por operações locais eficientes em subsistemas de qubits disjuntos, alcançando convergência comparável ao método original enquanto reduz significativamente a profundidade do circuito e a contagem de portas para problemas como o de cobertura exata e o do caixeiro viajante.

O essencial

Imagine que você está tentando resolver um quebra-cabeça massivo e complexo, como encontrar a rota perfeita para um caixeiro-viajante visitar cada cidade exatamente uma vez. Você tem um computador superinteligente (um computador quântico) que pode tentar milhões de possibilidades de uma só vez. No entanto, este computador é atualmente um pouco "barulhento" e frágil, como uma delicada escultura de vidro. Se você pedir que ele faça algo muito complicado, ele quebra ou comete erros.

Este artigo apresenta uma nova maneira de guiar este computador frágil para que ele possa resolver esses quebra-cabeças melhor sem quebrar.

O Problema: O Livro de Regras "Global"

Os pesquisadores estão trabalhando com um método chamado QAOA (Algoritmo de Otimização Aproximada Quântica). Pense no QAOA como um trilheiro tentando encontrar o ponto mais baixo em um vale com neblina (a melhor solução). Para fazer isso, o trilheiro precisa de duas ferramentas:

1. Um Mapa (Separação de Fase): Mostra ao trilheiro onde estão os pontos "ruins".
2. Uma Bússola (O Mixer): Ajuda o trilheiro a se movimentar para explorar novos pontos.

Na versão padrão deste método (chamada GM-QAOA), a "Bússola" é um Portão de Controle Múltiplo Global.

• A Analogia: Imagine tentar organizar uma festa de dança para 100 pessoas. A Bússola padrão é como uma regra única e gigante que diz: "Se todas as pessoas na sala estiverem em uma formação específica, então todos devem se mover juntos".
• O Problema: Para impor essa regra em um computador quântico frágil, você precisa de uma máquina enorme e complexa para verificar todas as 100 pessoas de uma vez. Essa máquina é grande, ocupa muito espaço e é muito provável que quebre (cometa erros) nos computadores ruidosos de hoje.

A Solução: A Vigilância Comunitária "Local"

Os autores, Minjin Choi, Dongkeun Lee e Junghee Ryu, propõem uma maneira mais inteligente de construir esta Bússola. Eles a chamam de Misturadores de Grover de Atuação Local (Locally Acting Grover Mixers).

• A Analogia: Em vez de uma regra gigante para a sala inteira, eles dividem as 100 pessoas em grupos menores e independentes (como 10 mesas de 10 pessoas). Agora, em vez de uma única máquina gigante verificando todos, você tem 10 máquinas pequenas e simples. Cada máquina verifica apenas sua própria mesa.
  • A máquina da Mesa 1 diz: "Se todos na Mesa 1 estiverem em formação, mova-se".
  • A máquina da Mesa 2 diz: "Se todos na Mesa 2 estiverem em formação, mova-se".
• O Resultado: Essas máquinas pequenas são muito mais fáceis de construir, ocupam menos espaço e são muito menos propensas a quebrar. Crucialmente, como os grupos são independentes, o resultado geral é tão bom quanto o da máquina gigante.

Como Eles Fizeram

Os pesquisadores perceberam que, para muitos quebra-cabeças, você não precisa forçar todas as regras na configuração inicial.

1. Codificação Parcial: Em vez de forçar o computador a começar com uma solução que obedece a todas as regras, eles permitem que ele comece com uma solução que obedece a algumas regras. Isso cria uma "estrutura de produto" (os grupos independentes mencionados acima).
2. Mistura Local: Eles então usam seu novo "Compasso Local" para misturar as coisas dentro desses pequenos grupos.

A Prova: Cobertura Exata e Caixeiro-Viajante

Eles testaram essa ideia em dois quebra-cabeças famosos:

1. O Problema da Cobertura Exata (Exact Cover Problem): Um quebra-cabeça lógico sobre cobrir itens exatamente uma vez.
2. O Problema do Caixeiro-Viajante (Traveling Salesman Problem - TSP): Encontrar a rota mais curta visitando várias cidades.

As Descobertas:

• Mesma Qualidade: O novo método "Local" encontrou soluções tão boas quanto o antigo método "Global".
• Muito Mais Simples: O novo método usou 87% menos portões de "emaranhamento" complexos (as partes do circuito que são mais propensas a quebrar).
• A Troca (Trade-off): O novo método exige que o computador execute o circuito algumas vezes a mais para ajustar suas configurações (porque há mais botões para girar). No entanto, como o circuito em si é muito mais simples e menos propenso a quebrar, essa troca é uma grande vitória para os computadores ruidosos de hoje.

A Grande Conclusão

O artigo argumenta que, para os computadores quânticos que temos agora (que são pequenos e ruidosos), é melhor usar uma estratégia "Local".

• Jeito Antigo: Construir uma máquina enorme e complexa que tenta fazer tudo perfeitamente, mas quebra facilmente.
• Novo Jeito: Construir muitas máquinas pequenas e simples que trabalham juntas. Elas podem precisar de algumas tentativas extras para acertar as configurações, mas são muito mais confiáveis e cabem no hardware de hoje.

Em suma, os autores encontraram uma maneira de tornar os algoritmos quânticos para problemas com restrições mais leves, mais simples e mais robustos, sem sacrificar a qualidade das respostas que encontram.

Resumo técnico

Resumo Técnico: Misturadores de Grover de Atuação Local para QAOA com Preservação de Restrições

Definição do Problema
O Algoritmo de Otimização Aproximada Quântica (QAOA) e sua generalização, o Algoritmo de Operador Alternado Quântico (QAOA), são algoritmos variacionais proeminentes para otimização combinatória. Um desafio crítico ao aplicar esses algoritmos a problemas com restrições é garantir que a evolução quântica permaneça confinada ao subespaço viável definido pelas restrições do problema. O Grover Mixer QAOA (GM-QAOA) aborda isso empregando um operador de mistura gerado pelo projetor sobre o estado inicial, o que garante matematicamente a preservação do subespaço viável.

No entanto, o misturador padrão do GM-QAOA requer uma porta de deslocamento de fase multi-controlada global atuando em todos os $n$ qubits. Em dispositivos quânticos de escala intermediária ruidosa (NISQ) de curto prazo, que suportam nativamente apenas operações de um e dois qubits, a decomposição de tal porta global em portas elementares resulta em um overhead substancial de circuito. A profundidade e a contagem de portas dessas decomposições crescem rapidamente com o número de qubits, impondo uma barreira significativa para a implementação prática e aumentando a suscetibilidade ao ruído do hardware.

Metodologia
Os autores propõem uma variante "de atuação local" do misturador de Grover adaptada para estados iniciais que admitem uma estrutura de produto sobre subsistemas de qubits disjuntos. Esta abordagem aproveita a observação de que, em muitos problemas combinatórios, as restrições podem ser parcialmente codificadas na preparação do estado inicial, deixando as restrições restantes para serem tratadas via termos de penalidade no Hamiltoniano de custo.

1. Estados Iniciais com Estrutura de Produto: O método assume que o estado inicial $|\psi_0\rangle$ pode ser fatorizado como $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$, onde cada $|\psi^{(j)}_0\rangle$ reside em um subconjunto disjunto de qubits. Esta estrutura é alcançada codificando apenas um subconjunto das restrições do problema durante a preparação do estado.
2. Unitária de Mistura Local: Em vez de um único misturador global $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$, o método proposto constrói a unitária de mistura como um produto tensorial de unitárias locais:
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   Cada unitária local atua independentemente em seu respectivo subsistema usando uma porta de deslocamento de fase multi-controlada confinada a esse subsistema.
3. Parametrização: O ansatz introduz parâmetros variacionais independentes $\beta^{(j)}$ para cada subsistema. Para um circuito de $p$ camadas com $\ell$ subsistemas, o número total de parâmetros de mistura é $p\ell$, comparado a $p$ no GM-QAOA original. Embora isso aumente a dimensão do landscape de otimização clássica, substitui uma enorme porta global por $\ell$ portas locais menores.

Principais Contribuições

• Eficiência de Circuito: A principal contribuição é a substituição da porta de deslocamento de fase multi-controlada global por $\ell$ operações locais. Isso reduz drasticamente o número de portas de emaranhamento (especificamente CNOTs) e a profundidade do circuito necessários para o passo de mistura.
• Estratégia de Codificação de Restrições: O artigo investiga o compromisso entre codificar todas as restrições no estado inicial versus codificar apenas um subconjunto. Demonstra-se que a codificação parcial de restrições, que permite a estrutura de produto necessária para o misturador local, pode resultar em circuitos globais mais compactos do que a codificação total, mesmo que esta última reduza o tamanho do espaço de busca.
• Preservação de Viabilidade: O método mantém a vantagem central do GM-QAOA: o operador de mistura preserva o espaço de busca definido pelo estado inicial, garantindo que o algoritmo não derive para regiões inviáveis.

Resultados
Os autores avaliaram o método proposto no problema de Exact-Cover e no Problema do Caixeiro Viajante (TSP) usando simulações numéricas.

• Problema de Exact-Cover: Para uma instância de sete qubits, o método proposto alcançou um comportamento de convergência comparável ao GM-QAOA original. Crucialmente, a decomposição da unitária de mistura no conjunto de portas $\{RX, RY, RZ, CNOT\}$ reduziu a contagem de CNOT de 218 (original) para 28 (proposto), uma redução aproximada de 87%.
• Problema do Caixeiro Viajante (TSP): Simulações em instâncias de TSP de quatro cidades (nove qubits) mostraram que o método proposto mantém probabilidades de solução comparáveis ao GM-QAOA através de várias profundidades de camada $p$.
  • Resiliência ao Ruído: Sob um modelo de ruído de despolarização, o método proposto exibiu um erro relativo significativamente menor no valor esperado do Hamiltoniano de custo em comparação com o GM-QAOA original, atribuído à redução da profundidade do circuito e da contagem de portas.
  • Compromisso de Recursos: Embora o método proposto exija mais execuções de circuito durante a otimização clássica devido ao aumento do número de parâmetros variacionais, a redução da complexidade do circuito quântico (a contagem de CNOT caiu de 572 para 54 por operador de mistura) torna-o mais viável para hardware ruidoso.
  • Codificação Parcial vs. Total: Para o TSP, codificar apenas a restrição de tempo-passo ($P_1$) no estado inicial (codificação parcial) combinada com o misturador local resultou em uma profundidade de circuito de 450 no desempenho ideal ($p=7$). Em contraste, codificar tanto a restrição de tempo-passo quanto a de visita à cidade ($P_1$ e $P_2$) no estado inicial (codificação total) exigiu um misturador global e resultou em uma profundidade de circuito de 4142 em $p=1$, apesar de atingir uma alta probabilidade de solução mais rapidamente. Os autores concluem que a codificação parcial produz uma complexidade de circuito global mais favorável.

Significância e Alegações
O artigo afirma que os misturadores de Grover de atuação local propostos oferecem um caminho prático para implementar o QAOA com preservação de restrições em dispositivos quânticos de curto prazo. Ao explorar a estrutura de produto dos subespaços viáveis, o método reduz significativamente o custo de implementação (contagem de portas e profundidade) enquanto preserva a capacidade do algoritmo de convergir para soluções de alta qualidade.

Os autores observam modestamente que, embora o aumento de parâmetros introduza um maior overhead de otimização clássica e potencialmente um landscape de otimização mais complexo, a redução da complexidade do circuito quântico é o fator dominante para dispositivos NISQ, onde a fidelidade da porta é a principal limitação. O trabalho sugere que o compromisso entre contagem de parâmetros e profundidade de circuito favorece a abordagem proposta para o hardware atual. O artigo não pretende resolver a questão teórica de por que a estrutura de mistura relaxada alcança uma convergência comparável, identificando isso como uma direção aberta para pesquisas futuras.