Resumo Técnico: O Problema do Hamiltoniano Local Comutativo: Evidência Relativizada Contra a Dificuldade BQP

1. Enunciado do Problema e Contexto

O problema do Hamiltoniano Local Comutativo (CLH) questiona se a energia do estado fundamental de um Hamiltoniano local, onde todos os termos locais comutam entre si, está abaixo de um limiar $\alpha$ ou acima de $\beta$. Embora o problema do Hamiltoniano Local geral seja QMA-completo, a complexidade da variante comutativa permanece uma questão central na teoria da complexidade quântica.

Trabalhos anteriores demonstraram que, para famílias específicas de Hamiltonianos comutativos (ex: 2-locais, certos 3-locais, ou aqueles em redes específicas), o problema reside em NP. No entanto, não existia evidência formal para descartar a possibilidade de que o problema CLH geral seja QMA-completo.

A classe de complexidade QIMA (Merlin-Arthur Interativo Quântico com unidades Comutativas) foi introduzida por Bostanci e Hwang para capturar o poder de verificadores quânticos cujas unidades de teste locais são reflexões mutuamente comutativas. O problema CLH é completo para QIMA. Consequentemente, a questão de saber se o CLH é QMA-completo é equivalente a perguntar se QIMA = QMA.

Este artigo investiga a relação entre QIMA e BQP (Tempo Quântico de Erro Limitado) em um cenário relativizado. Especificamente, busca determinar se existe um oráculo clássico $O$ tal que BQP$^O \not\subseteq$ QIMA$^O$. Um resultado positivo forneceria evidência relativizada contra a possibilidade de que o problema CLH geral seja difícil para BQP e, portanto, contra a possibilidade de que seja QMA-completo.

2. Metodologia e Definições

2.1 O Modelo de Oráculo QIMA$^O$

Os autores definem um análogo relativizado de QIMA, denotado por QIMA$^O$, com restrições específicas para garantir que o modelo permaneça uma restrição não trivial de QMA$^O$:

• Estrutura do Verificador: No input $x$, o verificador realiza pré-processamento clássico (fazendo consultas adaptativas a $O$) para gerar um conjunto de "unidades" $W_1^O, \dots, W_m^O$ atuando sobre um testemunho quântico.
• Comutatividade: Em instâncias prometidas, todas as unidades devem comutar entre si: $[W_i^O, W_j^O] = 0$.
• Requisito de Reflexão: Crucialmente, qualquer unidade $W_j^O$ que contenha pelo menos uma consulta ao oráculo deve ser uma reflexão exata (ou seja, $(W_j^O)^\dagger = W_j^O$ e $(W_j^O)^2 = I$). Unidades sem consulta ao oráculo podem ser unitários arbitrários.
• Verificação: O verificador utiliza o teste de Hadamard para verificar se o testemunho está no autoespaço $+1$ de cada unidade.
• Ausência de Ancila Confiável: O verificador não possui um espaço de trabalho confiável além dos qubits de controle frescos usados para os testes de Hadamard.

Os autores argumentam que o Requisito de Reflexão é essencial. Eles mostram que relaxar isso para permitir unidades comutativas arbitrárias (mesmo aquelas próximas de reflexões) ou permitir qubits ancila confiáveis colapsa a classe para QMA$^O$.

2.2 O Problema da Forrelation

A separação baseia-se no problema da Forrelation, definido por Aaronson. Dado acesso a oráculo a duas funções booleanas $f, g: \{0,1\}^n \to \{-1, +1\}$, a tarefa é distinguir entre:

• Sim: $f$ está altamente correlacionada com a transformada de Fourier de $g$ ($\Phi(f,g) \ge \alpha$).
• Não: A correlação é pequena ($|\Phi(f,g)| \le \beta$).

A Forrelation é solucionável por um algoritmo BQP com um número constante de consultas quânticas. O artigo visa provar que qualquer verificador QIMA$^O$ para Forrelation requer um número exponencial de consultas.

3. Contribuições Principais e Resultados

3.1 Separação de Oráculo: BQP$^O \not\subseteq$ QIMA$^O$

O principal resultado é a construção de um oráculo clássico $O$ tal que BQP$^O \not\subseteq$ QIMA$^O$. Isso é alcançado provando um limite inferior de consultas exponencial para o problema da Forrelation contra verificadores QIMA$^O$.

Teorema 1.7 (Informal): Qualquer verificador QIMA$^O$ decidindo Forrelation para todos os pares prometidos $(f, g)$ deve satisfazer:
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
onde $C(n)$ é o número de consultas de pré-processamento clássico e $T(n)$ é o número total de consultas ao oráculo quântico.

Esboço da Prova:

1. Método Polinomial: A probabilidade de aceitação do verificador é expressa como um polinômio nas entradas da tabela de verdade do oráculo.
2. Comutatividade e Reflexões: Como as unidades contendo o oráculo são reflexões exatas e comutam, seu operador de aceitação combinado é um produto de projetores ortogonais. Isso permite que os autores definam um único projetor $P_f$ representando a interseção de todos os subespaços de aceitação.
3. Limite de Grau: O grau do polinômio que representa a probabilidade de aceitação é limitado pelo número total de consultas quânticas $T(n)$.
4. Pares de Forrelation Perfeita: Os autores utilizam "pares de Forrelation perfeita" (funções bent) onde $\Phi(g, h) = 1$. Eles mostram que perturbar $h$ por $k$ bits altera o valor da Forrelation linearmente: $\Phi(g, f) = 1 - 2k/N$.
5. Simetrização: Ao fixar o transcrito clássico e realizar a média sobre funções com uma distância de Hamming fixa de um par perfeito, eles constroem um polinômio univariado $q(k)$.
6. Contagem de Raízes: O polinômio $q(k)$ deve ser zero para todas as instâncias "Não" (um amplo intervalo de $k$) e não-zero para a instância "Sim" ($k=0$). Um polinômio não-nulo não pode ter mais raízes do que seu grau, forçando o grau (e assim o número de consultas) a ser exponencial.

3.2 Robustez da Separação

O artigo demonstra que a separação se mantém mesmo sob relaxamentos leves do modelo:

• Desvios Negligenciáveis: Se as unidades contendo o oráculo puderem ser negligenciavelmente próximas (em norma de operador) de reflexões exatas, a classe permanece QIMA$^O$, e o limite inferior ainda se mantém.
• Suporte de Endereçamento Restrito: Os autores estendem o limite inferior para unidades que não são reflexões, mas realizam apenas uma única consulta, desde que os circuitos sem oráculo ao redor da consulta atuem de forma não-trivial apenas em um pequeno número de qubits de endereço ($k$). Se $n - k(n) = \omega(\log n)$, o limite inferior de consultas permanece superpolinomial.

3.3 Rigidez do Modelo (Resultados de Colapso)

Para justificar as restrições específicas de QIMA$^O$, os autores provam que o relaxamento dessas restrições colapsa a classe para QMA$^O$:

• Desvios de Ordem Inversa-Polinomial: Se as unidades puderem estar a uma distância inversa-polinomial de uma reflexão (em vez de negligenciável), a classe colapsa para QMA$^O$. Isso é demonstrado usando uma variação do gadget de amplificação de Marriott-Watrous, construindo uma única unidade que simula um verificador QMA.
• Consulta Única sem Reflexão: Se o requisito de reflexão for removido inteiramente, mas as unidades forem restritas a uma única consulta, a classe ainda colapsa para QMA$^O$. Isso utiliza uma construção de relógio cíclico (semelhante a Feynman-Kitaev) para codificar uma simulação de múltiplas consultas em uma única consulta.
• Ancila Confiável: Permitir que o verificador tenha um único qubit ancila confiável (inicializado em $|0\rangle$) colapsa QIMA para QMA e QIMA$^O$ para QMA$^O$. Isso depende do problema do "Hamiltoniano Local Comutativo com Pino" (Pinned Commuting Local Hamiltonian), que é conhecido por ser QMA-completo.

4. Significância e Alegações

O artigo afirma fornecer evidência relativizada contra a possibilidade de que o problema CLH geral seja difícil para BQP. Como BQP está contido em QMA, se o CLH fosse difícil para BQP, isso implicaria propriedades estruturais fortes sobre QMA. A separação $BQP^O \not\subseteq QIMA^O$ sugere que a restrição de comutatividade em QIMA (e, por extensão, no CLH) é uma restrição significativa que impede a classe de capturar todo o poder de BQP, mesmo na presença de oráculos.

Além disso, o trabalho esclarece a rigidez da definição de QIMA. Os autores argumentam que a combinação específica de comutatividade, o requisito de reflexão para consultas ao oráculo e a ausência de ancilas confiáveis é necessária para definir uma classe que seja estritamente mais fraca que QMA. O relaxamento de qualquer uma dessas condições recupera imediatamente todo o poder de QMA, sugerindo que a "natureza quântica" de QIMA é frágil e depende precisamente dessas restrições estruturais.

Os resultados não resolvem a questão não-relativizada de se o CLH é QMA-completo, mas estabelecem que qualquer prova de tal completude exigiria técnicas não-relativizadas, já que a afirmação falha em relação ao oráculo construído.