Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization

Resumo Técnico: QAOA com Restrições Particionadas (PC-QAOA)

Declaração do Problema
Problemas de otimização combinatória com restrições (COPs) permanecem um desafio significativo para algoritmos quânticos, particularmente para o Algoritmo Quântico de Otimização Aproximada (QAOA). A abordagem padrão para lidar com restrições envolve converter problemas com restrições em problemas de Otimização Binária Quadrática sem Restrições (QUBO) desimpedidos, adicionando termos de penalidade ao Hamiltoniano de custo. Este método, conhecido como PenaltyQAOA, introduz várias dificuldades: frequentemente requer variáveis de folga auxiliares, aumenta a densidade do QUBO resultante e necessita de um ajuste cuidadoso dos coeficientes de penalidade. Penalidades grandes podem distorcer a paisagem de energia, criando barreiras íngremes que suprimem a sensibilidade a melhorias no objetivo ou induzem paisagens de otimização altamente oscilatórias. Por outro lado, abordagens totalmente estruturais (como QAOA+ ou Grover-Mixer QAOA) que confinam a busca ao subespaço viável por meio de misturadores específicos do problema e preparação de estado frequentemente exigem designs de circuitos complexos e específicos do problema, que são difíceis de preparar e podem sofrer de platôs áridos ou conectividade limitada.

Metodologia: Framework PC-QAOA
Os autores introduzem o QAOA com Restrições Particionadas (PC-QAOA), um framework híbrido que interpola entre a aplicação de penalidades totalmente baseada em penalidades e a aplicação totalmente estrutural. A ideia central é particionar o conjunto de restrições $C$ em dois subconjuntos disjuntos:

1. Restrições Estruturais ($C_{str}$): Aplicadas via preparação de estado e operadores de mistura que preservam a viabilidade.
2. Restrições de Penalidade ($C_{pen}$): Aplicadas via termos de penalidade energética no Hamiltoniano de custo.

O algoritmo procede da seguinte forma:

• Particionamento de Restrições: Um algoritmo ganancioso de duas passagens atribui restrições a $C_{str}$ se admitirem preparação de estado eficiente e tiverem suporte disjunto das restrições estruturais selecionadas anteriormente. As restrições restantes são atribuídas a $C_{pen}$.
• Aplicação Estrutural: Para restrições em $C_{str}$, o algoritmo prepara um estado inicial $|F_{str}\rangle$ que é uma superposição de atribuições viáveis.
  • Para famílias específicas (cardinalidade, atribuição, conservação de fluxo), circuitos exatos (por exemplo, preparação de estado de Dicke) são utilizados.
  • Para restrições gerais de baixo suporte que carecem de construções exatas, os autores introduzem Engrenagens de Restrição Variacionais (VCGs). Estes são circuitos quânticos parametrizados treinados offline (usando um procedimento de QAOA multi-ângulo) para aproximar a superposição uniforme sobre o conjunto viável de uma única restrição.
• Mistura: O operador de mistura é construído para preservar o subespaço viável definido por $C_{str}$. Para engrenagens exatas, misturadores específicos são empregados (por exemplo, misturadores XY para cardinalidade, misturadores de Grover para VCGs). Qubits não cobertos por engrenagens estruturais usam misturadores X padrão.
• Aplicação Energética: O Hamiltoniano de custo inclui a função objetivo original mais termos de penalidade apenas para as restrições residuais em $C_{pen}$. Como a busca é restrita a $F_{str}$, os coeficientes de penalidade necessários podem ser menores, uma vez que a faixa da função objetivo sobre o espaço viável reduzido é tipicamente menor do que sobre o espaço binário completo.

Contribuições Principais

1. Tratamento Híbrido de Restrições: O artigo propõe um framework inovador que equilibra a complexidade do circuito e a redução do espaço de busca codificando seletivamente a estrutura de restrições no estado inicial e na dinâmica, enquanto retém penalidades para restrições complexas ou sobrepostas.
2. Engrenagens de Restrição Variacionais (VCGs): Os autores introduzem um método para construir preparações de estado viável aproximadas para restrições arbitrárias de baixo suporte. Estas engrenagens são treinadas offline para minimizar um Hamiltoniano específico da restrição e podem ser reutilizadas em diferentes instâncias de problemas, fornecendo uma alternativa flexível quando construções exatas não estão disponíveis.
3. Garantias Teóricas sobre Composição: O artigo estabelece (Proposição IV.1) que engrenagens de restrição com suportes disjuntos aos pares compõem-se exatamente sem interferência, permitindo que a superposição viável conjunta seja preparada em paralelo. O Corolário IV.2 demonstra que o acúmulo de erro na probabilidade viável conjunta é limitado pela soma dos erros individuais das engrenagens, garantindo alta viabilidade mesmo com engrenagens aproximadas.
4. Construção de Conservação de Fluxo: Apresenta-se uma nova construção de circuito exata para restrições de conservação de fluxo, utilizando preparações de estado de Dicke correlacionadas para impor peso de Hamming igual entre conjuntos de variáveis.

Resultados
Os autores avaliaram o PC-QAOA em 413 instâncias concluídas abrangendo sete famílias de restrições (incluindo cardinalidade, atribuição, conservação de fluxo, mochila e mochila quadrática) com tamanhos de problema $n \in \{3, \dots, 8\}$.

• Viabilidade e Qualidade da Solução: O PC-QAOA superou substancialmente o PenaltyQAOA. Em profundidade rasa ($p=1$), o PC-QAOA alcançou uma razão de aproximação viável média ($AR_{feas}$) de 0,588, comparado a 0,219 para o PenaltyQAOA. Em $p=5$, a lacuna ampliou-se para 0,783 versus 0,305.
• Probabilidade de Viabilidade: O PC-QAOA manteve uma alta probabilidade de amostrar uma solução viável ($P(feas) \approx 0,912$ em $p=1$), enquanto o PenaltyQAOA degradou-se significativamente ($P(feas) \approx 0,420$ em $p=1$).
• Probabilidade de Solução Ótima: O PC-QAOA mostrou uma melhoria relativa de 215% na probabilidade de amostrar a solução ótima ($P(opt)$) em $p=1$ comparado ao PenaltyQAOA.
• Eficiência de Recursos: O PC-QAOA exigiu menos qubits (sem variáveis de folga para restrições estruturais) e menos portas de dois qubits. Em $p=1$, exigiu 1,35$\times$ menos portas de dois qubits que o PenaltyQAOA; em $p=5$, esta vantagem cresceu para 1,45$\times$.
• Desempenho das VCGs: As VCGs treinadas alcançaram uma probabilidade viável de $P_{Fk} = 1$ e uma entropia viável normalizada ($S_{norm}$) média de 0,9186, indicando cobertura quase uniforme do subespaço viável.

Significado e Alegações
O artigo alega que o PC-QAOA demonstra o valor da aplicação estrutural parcial na otimização quântica. Ao codificar seletivamente a estrutura de restrições no estado inicial e na dinâmica, o método melhora significativamente a probabilidade de medir soluções viáveis e ótimas em profundidades de circuito rasas, comparado a abordagens puramente baseadas em penalidades. Os autores argumentam que esta abordagem oferece um compromisso prático para hardware quântico de curto prazo, reduzindo a dependência de grandes coeficientes de penalidade e variáveis de folga auxiliares, ao mesmo tempo que mitiga a complexidade de projetar misturadores totalmente específicos do problema. O trabalho sugere que codificar seletivamente a estrutura de restrições é uma direção promissora para otimização quântica com restrições escalável, particularmente para problemas onde as restrições podem ser particionadas em subconjuntos disjuntos e estruturalmente aplicáveis. Os autores observam que a eficácia depende da disponibilidade de uma partição útil e que trabalhos futuros poderiam envolver pré-processamento clássico (por exemplo, desigualdades de cobertura) para reduzir os tamanhos de suporte das restrições, tornando mais restrições passíveis de aplicação estrutural.