Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

Título: Separação da Verificação Clássica Não Interativa de Computação Quântica de Suposições Falsificáveis

Autores: Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki e Takashi Yamakawa.

---

1. O Problema

A verificação clássica de computação quântica (CVQC) é um desafio central na criptografia quântica, permitindo que usuários clássicos deleguem computações a servidores quânticos e verifiquem a correção dos resultados sem possuir recursos quânticos.

• Contexto Atual: O protocolo seminal de Mahadev (2022) demonstrou que um verificador clássico pode verificar um provador quântico não confiável, mas requer 4 mensagens de interação e baseia-se na suposição de dificuldade quântica do problema Learning-with-Errors (LWE).
• Questão Aberta: É possível reduzir essa complexidade de interação para um esquema não interativo (apenas uma mensagem do provador, após um setup independente da instância) no modelo padrão (sem oráculos aleatórios quânticos), mantendo a segurança baseada em suposições criptográficas padrão?
• Objetivo do Artigo: Investigar se a existência de um protocolo de CVQC não interativo (NI-CVQC) para a classe de complexidade QMA pode ser baseada em suposições falsificáveis.

2. Metodologia e Abordagem Técnica

Os autores utilizam uma técnica de separação por caixa-preta quântica (quantum black-box separation). O objetivo é provar que, sob certas condições, não existe uma redução de caixa-preta quântica que demonstre a segurança (sonoridade) de um NI-CVQC baseada em qualquer suposição falsificável.

A metodologia envolve os seguintes pilares:

A. Definição de Suposições Falsificáveis

Uma suposição é "falsificável" se pode ser formulada como um jogo interativo eficiente entre um desafiador e um adversário, onde o desafiador pode verificar se o adversário venceu. Isso inclui a maioria das suposições padrão (OWFs, RSA, LWE). O NI-CVQC, por si só, é uma suposição não falsificável (pois envolve a existência de um provador quântico que não pode ser simulado eficientemente por um verificador clássico).

B. O Problema de Lacuna QMA-QCMA

O resultado central depende da existência de um Problema de Lacuna QMA-QCMA (QMA-QCMA gap problem).

• Definição: É um problema em QMA onde as instâncias "sim" (com testemunhas quânticas válidas) e as instâncias "não" são indistinguíveis para qualquer adversário que tenha acesso a um oráculo QCMA (que resolve problemas de decisão com testemunhas clássicas).
• Importância: Isso implica que, mesmo com a capacidade de buscar testemunhas clássicas (QCMA), um adversário não consegue distinguir entre casos que exigem testemunhas quânticas (QMA) e casos que não têm solução.

C. A Técnica de Separação (Adaptação de Gentry-Wichs)

O trabalho adapta a separação clássica de Gentry-Wichs (para SNARGs) para o cenário quântico, enfrentando desafios únicos:

1. Lema de Vazamento Modificado (Modified Leakage Lemma): Em esquemas clássicos, o espaço de provas é pequeno, permitindo busca exaustiva. Em NI-CVQC, as provas podem ser exponencialmente longas. Os autores contornam isso equipando o adversário com um oráculo QCMA, permitindo que ele "busque" a informação auxiliar (a prova) sem quebrar a indistinguibilidade do problema QMA subjacente.
2. Indistinguibilidade de Amostra vs. Oráculo: O lema de vazamento garante que amostras clássicas são indistinguíveis. No entanto, para provar a impossibilidade de reduções de caixa-preta quântica, é necessário garantir que o acesso a oráculos quânticos (que simulam o provador honesto) também seja indistinguível.
3. Técnica de Oráculo Comprimido (Compressed Oracle): Para lidar com o fato de que o provador honesto é um algoritmo quântico (e não pode ser simulado apenas por amostras clássicas), os autores utilizam a técnica de oráculo comprimido (de Zhandry) para construir um simulador eficiente que é indistinguível de um oráculo quântico real.

3. Principais Contribuições e Resultados

Teorema Principal (Teorema 1/7)

O artigo prova que, assumindo a existência de um problema de lacuna QMA-QCMA subexponencial:

Não existe nenhuma redução de caixa-preta quântica que demonstre a sonoridade de um protocolo NI-CVQC para QMA baseada em qualquer suposição falsificável.

Isso significa que, se NI-CVQC for possível, ele não pode ser construído a partir de suposições como LWE, RSA ou OWFs usando reduções padrão de caixa-preta.

Corolário Imediato

Assumindo a dificuldade do LWE e a existência do problema de lacuna QMA-QCMA:

Não há redução de caixa-preta quântica que transforme um protocolo CVQC de 4 mensagens (como o de Mahadev) em um protocolo não interativo (NI-CVQC).

Construção de Oráculo (Teorema 2/8)

Para apoiar a premissa de que problemas de lacuna QMA-QCMA existem, os autores apresentam uma construção relativa a um oráculo unitário quântico:

• Eles definem uma linguagem onde as instâncias "sim" estão associadas a estados de Haar aleatórios específicos.
• Um oráculo aplica uma fase (-1) apenas se a entrada corresponder a um desses estados.
• Eles provam que, mesmo com acesso a um oráculo QCMA, um adversário não consegue distinguir entre o oráculo identidade e o oráculo com a fase, estabelecendo a existência do problema de lacuna nesse modelo de oráculo.

4. Significado e Impacto

1. Limites Fundamentais da Criptografia Quântica: O trabalho estabelece um limite teórico forte sobre o que é possível alcançar em verificação de computação quântica. Sugere que a redução da interação para não interatividade (no modelo padrão) pode exigir suposições não falsificáveis ou técnicas que vão além das reduções de caixa-preta.
2. Distinção entre QMA e QCMA: O resultado reforça a complexidade da separação entre QMA e QCMA. A impossibilidade de NI-CVQC está intrinsecamente ligada à dificuldade de distinguir problemas que requerem testemunhas quânticas daqueles que podem ser resolvidos com testemunhas clássicas, mesmo com poder computacional adicional.
3. Direção para Futuras Pesquisas:
   • Indica que a busca por NI-CVQC pode precisar focar em suposições não falsificáveis ou em modelos com oráculos aleatórios quânticos (onde esquemas não interativos já existem).
   • Abre caminho para investigar se a impossibilidade se mantém para a classe BQP (em vez de QMA) sob restrições de verificadores clássicos.
   • Destaca a necessidade de explorar reduções não de caixa-preta ou novos paradigmas de segurança.

Conclusão

O artigo fornece uma barreira teórica significativa, sugerindo que a "mágica" de transformar a verificação quântica interativa em não interativa, mantendo a segurança baseada em problemas computacionais padrão (falsificáveis), é provavelmente impossível dentro do modelo de reduções de caixa-preta. Isso coloca o foco da comunidade em entender melhor a estrutura de QMA versus QCMA e em explorar suposições criptográficas mais exóticas ou modelos de interação alternativos.