Succinct Arguments for QMA from Collapsing Hash Functions

No mundo da criptografia, existe uma tensão constante entre segurança e eficiência. De um lado, temos a necessidade de verificar se um cálculo complexo foi realizado corretamente sem ter que refazer todo o cálculo nós mesmos. Este é o domínio dos argumentos sucintos, um método que permite a um verificador checar uma prova usando muito menos recursos do que o tempo que levou para criá-la. Por décadas, esta tecnologia tem sido um pilar da confiança digital, permitindo tudo, desde a verificação de blockchain até a computação em nuvem segura. No entanto, uma lacuna significativa existia entre o mundo clássico dos computadores padrão e o mundo emergente dos computadores quânticos. Embora saibamos como criar essas provas eficientes para problemas clássicos usando apenas ferramentas matemáticas básicas e não estruturadas, fazer o mesmo para problemas quânticos parecia exigir maquinários criptográficos muito mais pesados e complexos. A crença predominante era que a verificação de provas quânticas sempre exigiria o tipo de sistemas de criptografia de chave pública avançados, que são muito mais custosos computacionalmente e estruturalmente complexos do que as ferramentas simples usadas para a verificação clássica.

Este artigo altera esse cenário ao demonstrar que a verificação eficiente de provas quânticas é possível usando apenas as suposições criptográficas mais simples e fundamentais. Os pesquisadores construíram um protocolo que permite a um cliente verificar um cálculo quântico com alta confiança, baseando-se unicamente na existência de "funções de hash colapsáveis". Estas funções são a versão quântica de uma ferramenta básica usada para garantir a integridade dos dados, representando o nível mais fraco de segurança criptográfica necessário para esta tarefa. Ao provar que tal sistema pode ser construído sem a necessidade da maquinaria pesada da criptografia de chave pública, os autores mostram que a capacidade de verificar cálculos quânticos reside em um nível de criptografia muito mais simples e acessível do que se pensava anteriormente. Esta conquista une uma divisão crítica, sugerindo que as ferramentas necessárias para assegurar o futuro quântico já estão ao nosso alcance, fundamentadas nos mesmos princípios básicos que asseguram o nosso mundo digital atual.

O cerne desta descoberta reside num novo método para gerar um tipo específico de correlação quântica conhecido como "estado de garra" (claw state). Para entender a significância, imagine um cenário onde um servidor poderoso quer provar que realizou um cálculo complexo, mas um cliente mais fraco quer checar o trabalho sem realizar o cálculo em si. O cliente precisa estabelecer uma conexão secreta e compartilhada com o servidor que prove que o servidor está seguindo as regras, sem revelar o segredo em si. Em tentativas anteriores, criar estas conexões exigia que o cliente realizasse um trabalho quântico massivo ou dependesse de sistemas complexos de chave pública. Os autores perceberam que o cliente não precisa ser inteiramente clássico; ele pode realizar uma pequena quantidade fixa de operações quânticas e ainda assim atingir o objetivo. Esta percepção permitiu-lhes projetar um protocolo onde o cliente prepara uma série de mensagens quânticas cuidadosamente preparadas com antecedência, antes de qualquer interação começar. O servidor então processa estas mensagens para gerar milhares destas conexões de "garra" secretas, tudo isso enquanto o cliente realiza apenas um trabalho quântico ínfimo.

O protocolo funciona fazendo com que o cliente envie uma superposição de muitas possibilidades de uma só vez durante cada rodada de interação. O servidor, usando apenas comunicação clássica e seu próprio poder de computação, é capaz de "colapsar" esta superposição em um conjunto de estados quânticos específicos e verificados. A parte inteligente do design é que o servidor pode gerar um vasto número destes estados, mas não consegue descobrir os rótulos secretos específicos associados a eles. Se o servidor tentar adivinhar os rótulos, o protocolo é desenhado de modo que a probabilidade de adivinhar corretamente caia drasticamente. Para tornar esta segurança robusta, os pesquisadores executam este processo várias vezes consecutivas, enviando múltiplas mensagens quânticas sequencialmente. Eles então utilizam uma técnica para "colar" os resultados destas execuções separadas, criando um único estado quântico altamente seguro. Este processo de amplificação garante que, mesmo que o servidor tenha uma pequena chance de desviar em uma instância, a chance de desvio em todas as instâncias se torne ínfima, tornando o sistema efetivamente seguro contra qualquer ataque realista.

Este novo método para gerar correlações quânticas serve como o motor para um sistema maior chamado "delegação cega" (blind delegation). Neste cenário, um cliente pode delegar um cálculo quântico complexo a um servidor sem que o servidor aprenda qualquer coisa sobre o que é o cálculo ou como os dados de entrada se parecem. O cliente fornece ao servidor os recursos quânticos necessários, e o servidor realiza o cálculo, retornando um resultado que o cliente pode verificar. Como o novo protocolo é tão eficiente e exige recursos quânticos mínimos do cliente, ele se encaixa perfeitamente em uma estrutura que comprime a comunicação entre as duas partes. Ao combinar este método de delegação eficiente com um compilador que encolhe a quantidade de dados trocados, os pesquisadores criaram um sistema completo de argumentos sucintos para problemas quânticos. O resultado final é um protocolo onde a quantidade total de dados enviados e recebidos é pequena, e o tempo que o cliente leva para verificar o resultado depende apenas do tamanho do enunciado do problema, não de quanto tempo o cálculo levou para rodar. É importante notar, contudo, que este protocolo exige que o verificador seja quântico e utilize comunicação quântica, o que é uma limitação central da abordagem atual.

A significância deste trabalho estende-se para além dos detalhes técnicos do protocolo. Ele resolve uma questão de longa data sobre os requisitos fundamentais para a verificação quântica. Durante anos, não estava claro se a verificação de provas quânticas exigiria as ferramentas pesadas e complexas da criptografia de chave pública ou se poderiam ser construídas a partir das ferramentas mais leves e simples usadas para a verificação clássica. Os autores provaram que a segunda opção é a verdadeira. Eles mostraram que a existência destes sistemas de verificação quântica eficientes é garantida pelas mesmas suposições básicas que sustentam a internet hoje. Isto coloca a capacidade de verificar cálculos quânticos numa categoria de criptografia conhecida como "Minicrypt", um reino definido por suposições simples e não estruturadas, em vez do reino mais complexo "Cryptomania" que se pensava ser necessário. Esta descoberta sugere que a infraestrutura para um futuro quântico seguro pode ser mais simples e robusta do que o antecipado, baseando-se nos mesmos blocos fundamentais que têm protegido o nosso mundo digital há décadas.