The Complexity of Stoquastic Sparse Hamiltonians

Declaração do Problema

O artigo aborda a complexidade computacional do problema do Hamiltoniano Esparsos Estoquástico (StoqSH). Embora a complexidade de Hamiltonianos estoquásticos locais seja bem compreendida (sabendo-se que é StoqMA-completa), a complexidade de Hamiltonianos estoquásticos esparsos não havia sido estabelecida diretamente.

Hamiltonianos esparsos constituem uma classe mais ampla do que Hamiltonianos locais; um Hamiltoniano $k$-local com $m$ termos é $2^{km}$-esparso. O problema StoqSH pergunta, dado um Hamiltoniano estoquástico $d$-esparso $H$ (onde os elementos fora da diagonal são não positivos) e parâmetros $\alpha, \beta$, se a energia do estado fundamental $\lambda_{\min}(H) \le \alpha$ ou $\lambda_{\min}(H) \ge \beta$, com a promessa de que um dos casos é verdadeiro.

O desafio central é que as técnicas padrão para provar a contenção em StoqMA para Hamiltonianos locais (que dependem da conversão de termos locais em projeções específicas) não se estendem ao cenário esparso. Além disso, métodos padrão de verificação quântica, como a Estimativa de Fase (usada para Hamiltonianos esparsos gerais em QMA), são inerentemente quânticos e não podem ser simulados pelos verificadores estoquásticos restritos, que são limitados a circuitos reversíveis clássicos e medições na base de Hadamard.

Metodologia

Os autores empregam um procedimento de verificação que preenche a lacuna entre a estrutura de Hamiltonianos esparsos e as limitações dos verificadores estoquásticos. A metodologia consiste em três componentes principais:

1. Decomposição Esparsa:
   Os autores utilizam uma decomposição conhecida (de [BCC+14]) onde qualquer Hamiltoniano $d$-esparso $H$ pode ser escrito como uma soma de $d^2$ termos 1-esparso ($H = \sum H_j$). Crucialmente, se $H$ for estoquástico, cada termo $H_j$ nesta decomposição também é estoquástico, e os elementos da matriz não nulos são atribuídos exclusivamente a termos específicos.

2. Verificadores StoqMA Generalizados (gStoqMA):
   Para lidar com a verificação, os autores introduzem uma generalização do verificador StoqMA. Verificadores StoqMA padrão medem um único qubit na base de Hadamard. Os autores definem gStoqMA, onde o verificador pode medir um número polinomial de qubits nas bases de Hadamard, $|0\rangle$ ou $|1\rangle$.

   • Eles provam que esta generalização não aumenta o poder computacional da classe; ela pode ser simulada por um verificador StoqMA padrão com uma perda linear na lacuna de completude/sombras (Teorema 1.2). Isso permite o uso de medições de múltiplos qubits (especificamente testes de Swap) dentro do framework estoquástico.

3. Procedimento de Verificação para StoqSH:
   A contribuição central é um protocolo de verificação para StoqSH que aceita um estado de testemunha $|\psi\rangle$ com uma probabilidade linearmente relacionada à expectativa de energia $\langle \psi | H | \psi \rangle$. O verificador escolhe aleatoriamente entre dois subprocedimentos ($V_1$ e $V_2$):

   • Procedimento $V_1$: Usa o oráculo para os elementos da matriz do Hamiltoniano para construir um estado dependente de $|\psi\rangle$ e do termo 1-esparso $H_j$. Ele realiza um teste "semelhante a Hadamard" envolvendo uma consulta controlada ao oráculo e medições nas bases $X$ e $Z$. A probabilidade de aceitação relaciona-se com os elementos fora da diagonal e a energia.
   • Procedimento $V_2$: Um procedimento complementar que mede o último qubit na base $Z$.
   • Resultado Combinado: Ao calcular a média das probabilidades de aceitação de $V_1$ e $V_2$, a probabilidade total de aceitação torna-se $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. Esta relação linear permite que o verificador distinga entre instâncias de baixa energia (SIM) e alta energia (NÃO).

Contribuições e Resultados Chave

1. StoqMA-Completude de StoqSH
O resultado primário é o Teorema 1.1, que afirma que o problema do Hamiltoniano Esparsos Estoquástico é StoqMA-completo.

• Dureza: Segue imediatamente porque Hamiltonianos estoquásticos locais são um caso especial de Hamiltonianos estoquásticos esparsos e já são conhecidos por serem StoqMA-difíceis.
• Contenção: Estabelecida via o procedimento de verificação descrito acima, provando que StoqSH $\in$ StoqMA.

2. Hamiltonianos Esparsos Estoquásticos Separáveis e StoqMA(2)
Os autores estendem sua análise para o problema do Hamiltoniano Esparsos Estoquástico Separável (SepStoqSH), onde a testemunha é restrita a ser um estado produto $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• Eles definem StoqMA(k), o análogo estoquástico de QMA(k), envolvendo $k$ provadores não emaranhados.
• Teorema 1.4 (Simplificado): Eles mostram que, para certos parâmetros de completude e sombra, $k$ provadores podem ser simulados por 2 provadores ($StoqMA(k) \subseteq StoqMA(2)$). A prova adapta o protocolo "Teste de Produto" de [HM13] para o cenário estoquástico, aproveitando a capacidade dos verificadores estoquásticos de realizar medições de múltiplos qubits (via a generalização gStoqMA).
• Teorema 4.5: O problema SepStoqSH é StoqMA(2)-completo. A prova de dureza adapta a construção de circuito-para-Hamiltoniano para Hamiltonianos esparsos separáveis [CS12] para o cenário estoquástico, utilizando teoria de perturbação para lidar com a falta de amplificação de erro em StoqMA(2).

3. Generalização de StoqMA
O artigo introduz gStoqMA e prova que permitir medições de tamanho polinomial não aumenta o poder da classe além de uma mudança de parâmetro (Teorema 3.5). Esta propriedade é destacada como potencialmente de interesse independente para o estudo de sistemas de prova estoquásticos.

Significância e Alegações

O artigo afirma avançar a compreensão da classe de complexidade StoqMA, que se situa entre as classes aleatórias MA e AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Completude: Ao identificar StoqSH como um problema completo para StoqMA, os autores fornecem um problema natural mais geral para esta classe, indo além de modelos locais restritos.
• Provas Separáveis: O trabalho posiciona StoqMA(2) como um modelo intermediário interessante entre a verificação estoquástica de um único provador e a verificação quântica geral de múltiplos provadores. Ele fornece um problema natural completo (SepStoqSH) para StoqMA(2), análogo ao papel dos Hamiltonianos esparsos separáveis para QMA(2).
• Robustez: Os resultados sugerem que o poder dos verificadores estoquásticos é robusto mesmo quando a testemunha é restrita a ser separável, desde que o Hamiltoniano seja esparso.

Os autores notam que, embora mostrem que StoqMA(k) colapsa para StoqMA(2) para parâmetros específicos, a robustez deste colapso sob limites de erro mais apertados permanece uma questão em aberto. Adicionalmente, a complexidade do problema do Hamiltoniano Local Estoquástico Separável permanece em aberto, pois as técnicas atuais para consistência de matriz de densidade local não se aplicam diretamente ao cenário estoquástico.

Em resumo, o artigo estabelece a dureza computacional de Hamiltonianos estoquásticos esparsos, introduz uma nova técnica de verificação utilizando medições de múltiplos qubits e caracteriza o poder dos sistemas de prova estoquásticos com múltiplos provadores não emaranhados.