Quantum Approximation Complexity of Classical Optimization Problems

Título: Complexidade de Aproximação Quântica de Problemas de Otimização Clássicos
Autor: Stuart Hadfield

Enunciado do Problema

O artigo aborda a falta de garantias rigorosas de desempenho no pior caso para algoritmos de otimização quântica. Embora muitos métodos quânticos (por exemplo, QAOA, DQI) demonstrem pontuações altas em instâncias específicas ou forneçam limites sobre valores esperados (médias decodificadas), eles frequentemente carecem de algoritmos uniformes que garantam uma razão de aproximação específica para todo dado de entrada com erro limitado. O trabalho busca definir formalmente análogos quânticos às classes de complexidade de aproximação clássica (APX, PTAS, FPTAS) e determinar se a computação quântica pode melhorar estritamente os algoritmos clássicos randomizados em termos de qualidade de solução garantida ou do tempo necessário para atingir uma precisão solicitada.

Metodologia

O autor estende o framework dos problemas de Otimização NP (NPO) para incluir algoritmos quânticos de erro limitado.

1. Definição de Classes Quânticas: O artigo define BQ-APX, BQ-PTAS e BQ-FPTAS. A participação nessas classes requer um algoritmo quântico uniforme que, para cada entrada, retorne uma solução clássica viável alcançando a razão de aproximação reivindicada com probabilidade de pelo menos $2/3$. Crucialmente, o tempo de execução inclui todas as etapas: seleção de parâmetros, preparação do estado, medição, decodificação e repetição. A pontuação da solução deve ser eficientemente computável classicamente.
2. Transferência de Média Decodificada para Saída: Uma ferramenta técnica fundamental é o Lema 6 e o Corolário 7, que estabelecem uma relação entre a pontuação esperada de uma solução decodificada e uma garantia de saída clássica de erro limitado. Isso permite a tradução das análises baseadas em expectativa (comuns na literatura quântica) para as garantias estritas de saída exigidas para a participação na classe.
3. Separações Condicionais: O artigo constrói problemas específicos para demonstrar inclusões estritas entre classes quânticas e clássicas sob suposições de complexidade padrão (por exemplo, $NP \not\subseteq BQP$ e $Factor \notin FBPP$). Essas construções baseiam-se em "preenchimento de busca" (search padding) e dureza criptográfica.

Principais Contribuições e Resultados

1. Hierarquia Formal de Classes de Aproximação Quântica
O artigo estabelece uma hierarquia estrita para classes de aproximação quântica sob a suposição de que $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Esta hierarquia é testemunhada por problemas clássicos:

• Max-E3SAT: Possui uma aproximação de razão constante determinística (em APX), mas não possui um PTAS quântico.
• Vertex Cover Planar: Possui um PTAS determinístico, mas não possui um FPTAS quântico.
  Estes resultados mostram que as classes quânticas são distintas entre si, embora ainda não separem as classes quânticas das classes clássicas randomizadas para esses problemas específicos.

2. Ordem Máxima Certificada (CMO): Uma Separação Quântica–Clássica Forte
O artigo introduz o problema da Ordem Máxima Certificada (CMO), onde o objetivo é encontrar a ordem multiplicativa de um elemento módulo $N que seja certificada por uma fatoração de números primos da ordem.

• Resultado Quântico: Um algoritmo quântico de erro limitado pode encontrar o ótimo exato (a função de Carmichael $\lambda(N)$) em tempo polinomial usando fatoração e busca de período. Assim, $CMO \in BQ\text{-}FPTAS$.
• Barreira Clássica: Qualquer algoritmo de tempo polinomial randomizado que garanta mesmo uma aproximação de fator polinomial para CMO implicaria em um algoritmo de fatoração em tempo polinomial randomizado.
• Conclusão: Assumindo que $Factor \notin FBPP$, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Isso estabelece uma separação condicional onde algoritmos quânticos fornecem soluções exatas enquanto algoritmos clássicos randomizados não conseguem sequer alcançar aproximações de fator polinomial.

3. Ajuste de Logaritmo Discreto (DLog-Fit): Uma Separação de Limiar
O artigo define DLog-Fit, um problema envolvendo a previsão de rótulos em uma amostra baseada em logaritmos discretos.

• Linha de Base Clássica: Um algoritmo determinístico alcança uma aproximação de $1/2$ (prevendo o rótulo majoritário).
• Vantagem Quântica: Um algoritmo quântico pode encontrar um ajuste perfeito (ótimo exato).
• Barreira Clássica: Qualquer melhoria fixa sobre a razão de $1/2$ por um algoritmo clássico randomizado resolveria o problema do logaritmo discreto em um subgrupo de primo seguro.
• Conclusão: Sob a suposição de que o logaritmo discreto de primo seguro não está em $FBPP$, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Isso demonstra um hiato no limiar de aproximação de $1/2$.

4. Preenchimento de Busca Geral (Teorema 8)
O artigo fornece uma construção genérica mostrando que qualquer problema de busca com testemunhas eficientemente verificáveis pode ser transformado em um problema NPO com um limiar de aproximação de $1/2$. Se um resolvedor quântico existe para a busca, mas um resolvedor clássico randomizado não, o problema de otimização resultante reside em $BQ\text{-}FPTAS$, mas fora de $R\text{-}PTAS$.

5. Análise de Métodos Quânticos Existentes
O artigo aplica estas definições a algoritmos existentes:

• QAOA: Para QAOA de profundidade fixa em MaxCut 3-regular, o artigo usa a transferência de média decodificada para mostrar que a repetição pode gerar uma garantia de saída de erro limitado (por exemplo, excedendo $2/3$ do ótimo), colocando esta família específica de grafos em $BQ\text{-}APX$.
• Interferometria Quântica Decodificada (DQI): O artigo observa que, embora o DQI mostre melhorias nas pontuações esperadas em famílias específicas (como OPI dobrado), estabelecer uma separação no modelo de tempo de entrada explícito requer provar que algoritmos clássicos randomizados não podem alcançar a mesma razão, o que permanece um desafio aberto para problemas irrestritos.

Significância e Alegações

O artigo afirma fornecer as primeiras definições rigorosas para classes de aproximação quântica de erro limitado e provar que, sob suposições de complexidade explícitas, a computação quântica pode melhorar estritamente as garantias de aproximação no pior caso em comparação com a computação clássica randomizada.

• Escopo Modesto: O autor afirma explicitamente que, para problemas comuns e irrestritos como MaxCut ou MaxSAT, uma lacuna quântica–clássica em razões de saída no pior caso permanece aberta. As separações estabelecidas dependem de construções de problemas específicas, frequentemente criptográficas (CMO, DLog-Fit), ou famílias de grafos restritas.
• Framework Teórico: O trabalho faz a ponte entre o desempenho quântico heurístico (frequentemente medido por valores de expectativa) e a teoria da complexidade rigorosa (garantias de saída de erro limitado). Ele esclarece que pontuações de benchmark altas sozinhas não estabelecem a participação em uma classe de aproximação sem uniformidade e limites de tempo.
• Direção Futura: O artigo identifica a busca por um algoritmo quântico uniforme que garanta uma razão melhor que o limiar de dureza clássica para problemas padrão (como MaxCut irrestrito) como o problema central aberto no campo.