Pesquisadora resolve antigo problema de verificação quântica
Uma das perguntas mais básicas da computação quântica é: como saber se a máquina realmente seguiu suas instruções? Em outras palavras, uma vez que um computador quântico pode realizar cálculos que um computador clássico não consegue, como saberemos se eles foram feitos corretamente?
Se você desconfiar de um computador comum, você pode, em teoria, examinar cada passo de seus cálculos por si mesmo.
Já os sistemas quânticos são fundamentalmente resistentes a esse tipo de verificação. Por um lado, seu funcionamento interno é incrivelmente complexo: escrever uma descrição do estado interno de um computador com apenas algumas centenas de bits quânticos (ou “qubits”) exigiria um disco rígido maior do que todo o universo visível.
E mesmo que, de alguma forma, você tivesse espaço suficiente para escrever essa descrição, não haveria maneira de entendê-la. O estado interno de um computador quântico é geralmente uma superposição de muitos estados “clássicos” não quânticos diferentes (como o gato de Schrödinger, que está simultaneamente morto e vivo).
Assim que você mede um estado quântico, ele colapsa em apenas um desses estados clássicos. Espie dentro de um computador quântico de 300 qubits, e essencialmente tudo o que você verá são 300 bits clássicos – zeros e uns – sorrindo para você.
E agora, José?
Esse problema de pesquisa atormentou Urmila Mahadev, estudante de pós-graduação da Universidade da Califórnia em Berkeley (EUA), por oito anos: é possível para um computador quântico fornecer qualquer garantia de que realmente tenha feito o que afirmou?
Agora, Mahadev finalmente conseguiu a resposta. Ela criou um protocolo interativo pelo qual usuários sem poderes quânticos podem empregar criptografia a um computador quântico e ter certeza de que ele está seguindo suas ordens.
Thomas Vidick, cientista da computação do Instituto de Tecnologia da Califórnia (EUA) que colaborou com Mahadev no passado, chamou seu resultado de “uma das ideias mais notáveis surgidas na interface da computação quântica e da ciência da computação teórica nos últimos anos”.
Pesquisadores de computação quântica ficaram animados não apenas com o protocolo em si, mas também com a abordagem radicalmente nova que Mahadev usou para resolver o problema. Usar a criptografia clássica no reino quântico foi uma aposta ousada.
A origem do problema de verificação
Se um computador quântico resolve um problema que um computador clássico não pode, isso não significa automaticamente que a solução será difícil de ser verificada.
Tomemos, por exemplo, o problema de fatorar grandes números, uma tarefa que um grande computador quântico poderia resolver eficientemente, mas que se acredita estar além do alcance de qualquer computador clássico.
Mesmo se um computador clássico não puder fatorar um número, ele pode facilmente verificar se a fatoração de um computador quântico está correta – basta multiplicar os fatores e ver se eles produzem a resposta correta.
No entanto, muitos dos problemas que um computador quântico poderia resolver não têm essa característica. Em outras palavras, um computador clássico não apenas não pode resolvê-los, como também não pode reconhecer se uma solução proposta está correta.
Anteriormente, estudos obtiveram uma resposta parcial a esse problema. Por exemplo, duas equipes diferentes mostraram que um computador quântico pode provar seus cálculos para um verificador que tem acesso a um computador quântico muito pequeno, mas não para um verificador puramente clássico.
Em 2012, uma equipe de pesquisadores descobriu que um verificador completamente clássico poderia checar cálculos quânticos se eles fossem executados por um par de computadores quânticos que não podem se comunicar entre si. Como a abordagem foi adaptada para um cenário específico, o problema parecia ter chegado a um beco sem saída.
O avanço de Mahadev
Foi nessa época que Mahadev se deparou com tal problema de verificação. No início, ela tentou chegar a um resultado “incondicional”, que não faz suposições sobre o que um computador quântico pode ou não resolver.
Depois de ter trabalhado no problema sem progresso por um tempo, seu orientador Umesh Vazirani propôs a possibilidade de usar criptografia “pós-quântica” – isto é, criptografia que os pesquisadores acreditam estar além da capacidade de até mesmo um computador quântico, embora não tenham certeza disso.
Em 2016, enquanto trabalhavam em um problema diferente, Mahadev e Vazirani fizeram um avanço que mais tarde seria crucial. Em colaboração com Paul Christiano, um cientista da computação da OpenAI, uma empresa em São Francisco, eles desenvolveram uma maneira de usar a criptografia para fazer um computador quântico construir o que chamaremos de “estado secreto” – um estado cuja descrição é conhecida pelo verificador clássico, mas não para o próprio computador quântico.
O procedimento depende do que é chamado de função “alçapão” – uma tarefa fácil de executar, mas difícil de reverter, a menos que você possua uma chave criptográfica secreta.
Estado secreto + função alçapão + LWE
Em 2017, Mahadev descobriu como construir tal função no núcleo do método do estado secreto usando um tipo de criptografia chamado Learning With Errors (LWE).
A partir disso, ela foi capaz de criar uma versão quântica de “computação cega”, pela qual usuários de computação quântica podem mascarar seus dados para que o computador quântico não possa lê-los, mesmo enquanto estiver computando.
Logo depois, Mahadev, Vazirani e Christiano se juntaram a Vidick e Zvika Brakerski (do Instituto Weizmann de Ciência em Israel) para refinar ainda mais essas funções, usando o método do estado secreto para desenvolver uma maneira infalível de um computador quântico gerar números comprovadamente aleatórios.
O progresso era surpreendente, mas ainda não era um protocolo de verificação. A parte complicada seria fazer com que o computador quântico se comprometesse a medir um estado (lembre-se que computadores quânticos trabalham com superposições) antes de saber qual tipo de medida o verificador pediria – caso contrário, seria fácil para o computador enganar o verificador.
Sucesso
É aí que o método do estado secreto entra em cena: o protocolo de Mahadev exige que o computador quântico primeiro crie um estado secreto e, em seguida, o aplique ao estado que deveria medir.
Só então o computador descobre que tipo de medição deve realizar. Como o computador não sabe a composição do estado secreto, mas o verificador sim, é impossível que o erre sem deixar vestígios de sua duplicidade.
Dependência da LWE
O protocolo de verificação de Mahadev – junto com o gerador de números aleatórios e o método de criptografia cego – depende da suposição de que computadores quânticos não podem decifrar a criptografia LWE.
Atualmente, a LWE é considerada uma das principais candidatas à criptografia pós-quântica, e pode ser adotada em breve pelo Instituto Nacional de Padrões e Tecnologia dos EUA como seu novo padrão criptográfico, para substituir os que um computador quântico poderia quebrar.
A única maneira de um computador quântico enganar o protocolo é se alguém no mundo da computação quântica descobrir como decifrar a LWE, o que seria uma conquista notável em si.
Próximos passos
O protocolo de Mahadev provavelmente não será implementado em um computador quântico real em breve, no entanto. Por enquanto, requer muito poder de computação para ser prático.
Mas isso pode mudar nos próximos anos, à medida que os computadores quânticos se tornam maiores e os pesquisadores otimizam o método.
Dada a rapidez com que o campo está se movendo, esse estágio pode chegar mais cedo ou mais tarde.
No geral, cientistas da computação teóricos veem a unificação da computação quântica e da criptografia de Mahadev não tanto como o fim de um problema, mas como o começo de uma exploração que deve produzir muitos frutos. [Quanta]
