Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Resumo Técnico: Esquemas de Aproximação Quântica de Tempo Polinomial Informados pela Geometria para Otimização com Restrições

Enunciado do Problema
A otimização combinatória com restrições envolve encontrar configurações ótimas sujeitas a restrições rígidas (ex: atribuição, emparelhamento, roteamento). Embora existam algoritmos clássicos para subclasses específicas tratáveis, muitos desses problemas são NP-difíceis. Abordagens quânticas, particularmente o Algoritmo de Aproximação de Otimização Quântica (QAOA), enfrentam desafios em dispositivos de curto prazo:

1. Viabilidade: O QAOA padrão frequentemente amostra fora do subespaço viável definido pelas restrições rígidas.
2. Ruído: O ruído do dispositivo induz violações de restrição, degradando a qualidade das amostras.
3. Garantias: Métodos existentes muitas vezes carecem de garantias rigorosas de ponta a ponta de desempenho (tempo de execução polinomial com alta probabilidade de encontrar um ótimo) sob condições de ruído realistas.

O artigo aborda a questão: Quando um amostrador quântico ruidoso permite um algoritmo de tempo polinomial de ponta a ponta com garantias de desempenho?

Metodologia
Os autores propõem o algoritmo Noisy Polytime Hybrid Quantum-Classical (NP-HQ), um pipeline completo que integra amostragem quântica com pós-processamento clássico determinístico. A metodologia baseia-se em três pilares:

1. O Kernel OFM e o CE-QAOA:
   A abordagem utiliza o kernel Onah–Firt–Michielsen (OFM), que define uma codificação específica para problemas como o Problema do Caixeiro Viajante (TSP) e o Problema de Atribuição Quadrática (QAP).

   • Codificação: Utiliza uma codificação one-hot onde cada bloco lógico possui exatamente uma excitação.
   • Dinâmica: Emprega o CE-QAOA (Constraint-Enhanced QAOA) com um misturador XY local por bloco que preserva o subespaço one-hot.
   • Garantias: Baseando-se em trabalhos anteriores [1], mostra-se que o amostrador CE-QAOA ideal atribui uma massa de probabilidade inverso-polinomial ($p_0 = \Omega(n^{-k})$) ao conjunto de soluções ótimas, desde que condições geométricas específicas (separação de fase) sejam atendidas.

2. Reparo e Pontuação Determinísticos:
   Para lidar com ruído e amostras inviáveis, o pipeline inclui um pós-processador clássico:

   • Verificação de Viabilidade: Verifica as restrições one-hot.
   • Reparo: Utiliza algoritmos determinísticos de tempo polinomial (especificamente o algoritmo Húngaro para problemas de atribuição ou heurísticas baseadas em trocas/swaps) para projetar bit-strings ruidosas e inviáveis de volta à solução viável mais próxima (ex: uma permutação válida).
   • Pontuação: Avalia a função objetivo exata nas candidatas reparadas.
   • Base Teórica: O mapa de reparo é mostrado como uma contração na distância de variação total e não diminui a massa de probabilidade do conjunto ótimo.

3. Análise de Robustez ao Ruído:
   Os autores derivam um limite do tipo Lipschitz relacionando o ruído do dispositivo à degradação da massa de amostragem ótima. Eles estabelecem uma "janela de ruído" onde, se o erro efetivo por camada for suficientemente baixo, a massa ótima ruidosa permanece inverso-polinomial. Isso permite o cálculo de um orçamento de shots polinomial necessário para recuperar um ótimo com alta probabilidade.

Principais Contribuições

1. FPRAS$_q$ (Exact-Hit):
   No regime de baixo ruído, onde o amostrador ideal atribui massa inverso-polinomial ao ótimo, o pipeline NP-HQ constitui um Esquema de Aproximação Aleatorizada Totalmente Polinomial (FPRAS$_q$). Ele garante encontrar o ótimo global com probabilidade $1-\delta$ em tempo polinomial (chamadas de circuito quântico + pós-processamento clássico).

2. $\varepsilon$-PTQAS (Aproximação):
   Além do regime de acerto exato, o pipeline fornece um Esquema de Aproximação Quântica de Tempo Polinomial $\varepsilon$ ($\varepsilon$-PTQAS). Se a inflação do objetivo induzida pelo reparo for controlada, o algoritmo produz uma aproximação de $(1+\varepsilon)$ com tempo de execução polinomial.

3. Separação Quântico-Clássica:
   O artigo estabelece uma separação condicional entre o pipeline NP-HQ e estratégias puramente clássicas. Mesmo que um amostrador clássico receba:

   • Acesso aos mesmos mapas de reparo eficientes (projeção Húngara).
   • Acesso perfeito às estruturas de restrição (ex: amostrar uniformemente de strings row-one-hot).
   • Tempo polinomial.
     Ele não consegue reproduzir a sobreposição ótima inverso-polinomial em famílias admissíveis ao kernel NP-difícil, a menos que NP $\subseteq$ BPP. A vantagem quântica reside estritamente na geração da distribuição de amostragem, não no processamento clássico.

4. Heavy-Hitter QAOA (HH-QAOA):
   Um refinamento que reduz os custos de pós-processamento clássico. Ao aproveitar a geometria da distribuição quântica, o algoritmo identifica "heavy hitters" (amostras de alta frequência) e filtra o conjunto de candidatos. Isso reduz a complexidade de pós-processamento clássico de $O(n^{k+4})$ para $O(n^{k+3})$ (ou menor com compressão adicional) sem sacrificar as garantias de aproximação.

5. Demonstração em Hardware:
   O pipeline completo foi executado em dois processadores distintos IBM Eagle-r3 de 127 qubits (ibm_brisbane e ibm_sherbrooke) usando instâncias QOptlib TSP com até 100 variáveis lógicas.

   • Resultados: Apesar do forte ruído (taxas de erro de dois qubits $\sim 10^{-3}$ a $10^{-2}$), o reparo determinístico restaurou a viabilidade para todas as amostras.
   • Desempenho: As soluções reparadas igualaram ou melhoraram os roteiros de referência publicados em todos os casos testados, demonstrando a viabilidade da abordagem em hardware atual.

Significância e Alegações
O artigo alega fornecer a primeira garantia de otimização de ponta a ponta para um pipeline híbrido quântico-clássico sob ruído de dispositivo que combina:

• Recuperação de ótimo com número finito de shots.
• Restauração de viabilidade determinística.
• Limites explícitos de ruído finito sobre a massa ótima recuperada.
• Complexidade de shots polinomial e tempo de execução de pós-processamento polinomial.

Os autores argumentam que a otimização quântica com restrições deve ser vista como um pipeline unificado onde a estrutura do problema é explorada tanto na dinâmica quântica (via kernel OFM) quanto no processamento clássico (via mapas de reparo). O trabalho demonstra que, mesmo na era NISQ, circuitos restritos rasos combinados com pós-processamento clássico rigoroso podem produzir esquemas de aproximação prováveis e resultados competitivos em hardware real.

Limitações e Escopo

• As garantias são dependentes da instância, dependendo da existência de uma separação de fase positiva ($\delta > 0$) e peso de envelope do misturador suficiente.
• A garantia de "acerto exato" mantém-se apenas dentro de uma janela de ruído específica; fora dela, o esquema degrada-se para um esquema de aproximação.
• A separação quântico-clássica é condicional à suposição de que NP $\not\subseteq$ BPP.
• Os experimentos de hardware usaram parâmetros de warm-start fixos de otimização genérica de QAOA, em vez de reotimização nativa de hardware, testando a transferibilidade de parâmetros para dispositivos ruidosos.