Urmila Mahadev passou oito anos na magistratura em busca de uma resposta para uma das questões mais básicas da computação quântica: como sabemos que um computador quântico fez pelo menos alguma coisa no nível quântico?
Na primavera de 2017, Urmila Mahadev estava em uma boa posição, do ponto de vista da maioria dos estudantes de pós-graduação. Ela acabou de resolver o problema crucial da computação quântica - o campo da ciência da computação, tirando suas capacidades das estranhas leis da física quântica. Juntamente com seus trabalhos anteriores, um novo resultado de Mahadev descrevendo o chamado "A computação cega" tornou "óbvio que ela é uma estrela em ascensão", disse
Scott Aaronson , especialista em TI da Universidade do Texas em Austin.
Mahadev, que na época tinha 28 anos, já estava no sétimo ano na escola de pós-graduação da Universidade da Califórnia em Berkeley - muito mais do que o tempo que leva para a maioria dos estudantes perder a paciência e querer terminar a escola. E, finalmente, ela conseguiu escrever uma "excelente dissertação de doutorado", disse
Umesh Vazirani , seu curador em Berkeley.
Mas Mahadev não terminou de estudar naquele ano. Ela nem considera esse assunto. Ela ainda não terminou.
Por mais de cinco anos, ela trabalhou em outra tarefa de pesquisa, que Aaronson chamou de "uma das perguntas mais básicas que podem ser feitas no campo da computação quântica". Nomeadamente: se você pede a um computador quântico que faça um cálculo para você, como você sabe se ele segue suas instruções e, de fato, ele faz algo no nível quântico?
Essa questão pode em breve deixar de ser puramente acadêmica. Os pesquisadores esperam que não se passem muitos anos e os computadores quânticos poderão oferecer aceleração exponencial na solução de muitos problemas, desde a modelagem de uma situação perto de um buraco negro até a simulação do dobramento de grandes proteínas.
Mas, assim que um computador quântico pode executar cálculos dos quais o clássico não é capaz, como sabemos que ele os conduz corretamente? Se você não acredita em um computador comum, em teoria você pode estudar cuidadosamente cada etapa de seus cálculos. Mas os computadores quânticos resistem inerentemente a essas verificações. Para começar, o trabalho deles é extremamente complicado: para registrar uma descrição do estado interno de um computador, consistindo em apenas algumas centenas de bits quânticos, ou qubits, você precisará de um disco rígido maior que o Universo observado.
E mesmo se você tivesse um lugar para escrever essa descrição, ela não poderia ser desmontada. O estado interno de um computador quântico é geralmente uma superposição de muitos estados não quânticos, mas clássicos (como o gato de Schrödinger, que está vivo e morto). Mas assim que você mede um estado quântico, ele imediatamente se desintegra em um dos clássicos. Dê uma olhada dentro de um computador quântico com 300 qubits - e você verá apenas 300 bits, zeros e uns clássicos, educadamente sorrindo para você em troca.
"Um computador quântico é poderoso, mas misterioso", disse Vazirani.
Dadas essas limitações, os cientistas da computação há muito pensam se um computador quântico pode oferecer uma garantia absolutamente confiável de que realmente fez o que afirma ser. "A interação entre os mundos quântico e clássico será forte o suficiente para tornar possível esse diálogo?" Perguntou
Dorit Akharonova , cientista da computação da Universidade Hebraica de Jerusalém.
No segundo ano da magistratura, Mahadev foi capturada por essa tarefa, e ela nem sequer entende completamente o porquê. Nos anos seguintes, ela tentou usar uma abordagem para ela, depois outra. "Tive muitos momentos em que me pareceu que estava fazendo tudo certo, e então tudo quebrou - muito rapidamente ou depois de um ano", disse ela.
Mas ela se recusou a desistir. Mahadev mostrou um nível tão imutável de determinação que Vazirani não havia encontrado antes. "Nesse sentido, Urmila é absolutamente extraordinário", disse ele.
E agora, após oito anos de estudos de pós-graduação, Mahadev conseguiu. Ela criou um protocolo interativo com o qual um usuário que não possui recursos quânticos pode, no entanto, usar uma criptografia para restringir um computador quântico e direcioná-lo para qualquer lugar, com total confiança de que o computador quântico obedece às ordens. A abordagem de Mahadev, disse Vazirani, oferece ao usuário "uma alavanca de pressão da qual o computador não consegue se livrar".
"É absolutamente espantoso" que um estudante de graduação possa alcançar esse resultado sozinho, disse Aaronson.
Mahadev, agora um pós-doutorado em Berkeley, apresentou seu protocolo em outubro de 2018 no
Simpósio anual
de Ciência da Computação , uma das maiores conferências de computação realizadas este ano em Paris. A platéia concedeu seu trabalho com os prêmios "melhor trabalho" e "melhor trabalho para estudantes" - um prêmio raro para um especialista em ciência da computação teórica.
Em um post no blog,
Thomas Widick , especialista em TI do Instituto de Tecnologia da Califórnia, que havia trabalhado com Mahadev no passado, descreveu seu resultado como "uma das idéias mais destacadas que surgiram na interseção entre computação quântica e informática teórica nos últimos anos".
Pesquisadores do campo da ciência da computação ficam encantados não apenas com o que o protocolo Mahadev é capaz, mas também com uma abordagem radicalmente nova que ajuda a lidar com esse problema. O uso da criptografia clássica no campo quântico é "uma ideia verdadeiramente inovadora", escreveu Vidik. "Eu acho que muitos outros resultados crescerão com essas idéias."
Longo caminho
Mahadev cresceu em Los Angeles, em uma família de médicos, e estudou na Universidade do Sul da Califórnia, onde se mudou de uma área para outra, inicialmente convencida apenas de que ela mesma não queria ser médica. Então, ela ficou muito interessada no curso de ciência da computação teórica, ensinado por Leonard Aidleman, um dos criadores do famoso algoritmo de criptografia RSA. Ela entrou na faculdade em Berkeley, indicando em uma nota explicativa que estava interessada em todos os aspectos da ciência da computação teórica - exceto na computação quântica.
"Era algo completamente estranho do qual eu tinha a menor idéia", disse ela.
Mas, uma vez em Berkeley, ela logo mudou de idéia sob a influência das explicações disponíveis de Wazirani. Ele a apresentou à busca de um protocolo para confirmar a computação quântica, e essa tarefa "realmente fez sua imaginação funcionar", disse Vazirani.
"Os protocolos são como quebra-cabeças", explicou Mahadev. "É mais fácil para mim do que com outras perguntas, porque aqui você pode começar imediatamente a pensar nos protocolos, dividi-los em pedaços e observar como eles funcionam". Ela escolheu essa tarefa para o doutorado, embarcando em um "caminho muito longo", como Vazirani disse.
Se um computador quântico puder resolver um problema do qual o clássico não é capaz, isso não significa automaticamente que a solução será difícil de verificar. Tomemos, por exemplo, o problema de fatorar grandes números - acredita-se que um grande computador quântico possa resolvê-lo com eficiência, mas, ao mesmo tempo, permanece além das capacidades de qualquer computador clássico. Mas mesmo que um computador clássico não consiga fatorar o número, ele pode facilmente verificar se o resultado quântico está correto - ele só precisa multiplicar todos os fatores e verificar se eles dão a resposta correta.
No entanto, os cientistas da computação acreditam (e recentemente deram um passo no sentido de provar) que muitas tarefas que um computador quântico poderia resolver são desprovidas dessa característica. Em outras palavras, um computador clássico não apenas não pode resolvê-los, nem mesmo reconhece se a solução proposta estará correta. Como resultado, em 2004,
Daniel Gottsman , físico teórico do Instituto Waterloo Perimeter, perguntou se era possível criar algum protocolo que permitisse a um computador quântico provar a um observador não quântico que ele realmente havia conseguido o que estava reivindicando.
Durante quatro anos, os pesquisadores da computação quântica encontraram uma resposta parcial. Duas equipes diferentes
mostraram que um computador quântico pode provar seus cálculos, mas não para um verificador puramente clássico, mas para um que tem acesso a outro computador quântico muito pequeno. Mais tarde, os pesquisadores aprimoraram essa abordagem, mostrando que o testador precisava apenas da capacidade de medir o estado de um qubit por vez.
E em 2012, uma equipe de pesquisadores, que incluiu Vazirani, mostrou que um verificador totalmente clássico pode verificar cálculos quânticos se eles foram realizados por um par de computadores quânticos que não se comunicavam. No entanto, sua abordagem foi projetada especificamente para esse cenário, e a tarefa parecia chegar a um beco sem saída, disse Gottsman. "Acho que provavelmente havia pessoas que pensavam que não havia como ir mais longe."
Nessa época, Mahadev se deparou com o problema da confirmação. A princípio, ela tentou produzir um resultado "incondicional", sem especificar o que um computador quântico pode ou não fazer. Mas, depois que ela trabalhou na tarefa por algum tempo sem sucesso, Vazirani propôs a possibilidade de usar criptografia "pós-quântica" - isto é, criptografia, cuja quebra, segundo os pesquisadores, está além das capacidades dos computadores quânticos, embora com certeza eles não sabem. (Métodos como o algoritmo RSA usado para criptografar transferências on-line não são pós-quantum - um computador quântico grande pode decifrá-los, porque sua segurança se baseia na dificuldade de fatorar grandes números).
Em 2016, enquanto trabalhavam em uma tarefa diferente, Mahadev e Vazirani fizeram um avanço, que será decisivo no futuro. Juntamente com
Paul Cristiano , especialista em TI da OpenAI, empresa de São Francisco, eles criaram uma maneira de usar criptografia para fazer um computador quântico entrar em um "estado secreto" - um estado que é descrito por um verificador clássico, mas não pelo próprio computador quântico .
O procedimento deles é baseado em uma função “trap” - fácil de executar, mas difícil de reverter, a menos que você tenha uma chave criptográfica secreta. (Naquele momento, os pesquisadores ainda não sabiam como fazer uma armadilha adequada - isso veio depois). A função também deve ter a propriedade "dois em um", o que significa que para cada conjunto de dados de saída há dois conjuntos diferentes de dados de entrada. Por exemplo, podemos imaginar uma função ao quadrado dos números - além do número 0, para cada resultado (por exemplo, 9), existem dois números de entrada correspondentes (3 e -3).
Armado com uma função semelhante, você pode fazer um computador quântico entrar em um estado secreto da seguinte maneira. Primeiro, você pede ao computador a tarefa de construir uma superposição de todos os possíveis dados de entrada da função (isso pode parecer uma tarefa difícil para o computador, mas na verdade é simples). Em seguida, você diz ao computador para aplicar a função a essa superposição gigantesca, criando um novo estado que é uma superposição de toda a saída possível da função. As superposições de entrada e saída serão confusas, o que significa que medir uma delas afetará instantaneamente a outra.
Em seguida, você solicita ao computador para medir o estado final e relatar o resultado. Uma medição reduz o estado para um dos conjuntos possíveis de dados de saída e o estado de entrada diminui para corresponder a ele, porque eles são confusos - por exemplo, se usarmos a função square, se o estado de saída for 9, a entrada entrará em colapso para a superposição 3 e -3.
Mas lembre-se de que usamos uma função trap. Temos uma chave secreta para a armadilha, para que possamos descobrir facilmente os dois estados que compõem a superposição de entrada. Um computador quântico não pode. E ele não pode simplesmente medir a superposição de entrada para descobrir em que consiste, uma vez que tal medida a reduzirá ainda mais, deixando o computador uma das duas opções, sem a capacidade de calcular a outra.
Em 2017, Mahadev entendeu como criar as funções de interceptação nas quais o método do estado secreto se baseia usando criptografia chamada
Aprendizado com Erros (LWE). Usando essas funções de interceptação, ela conseguiu criar uma versão quântica da computação "cega", com a qual os usuários dos sistemas de computação em nuvem podem ocultar seus dados para que os computadores em nuvem não possam lê-los, mesmo que façam cálculos com eles. Logo depois, Mahadev, Wazirani e Cristiano se uniram a Vidik e
Zwika Brackerski (do Instituto Weizmann em Israel) para melhorar ainda mais a qualidade dessas funções e usam o método do estado secreto para desenvolver uma maneira garantida de que um computador quântico possa gerar
números comprovadamente aleatórios .
Mahadev poderia ter obtido o diploma já com base nesses resultados, mas pretendia continuar trabalhando até resolver o problema de confirmação. "Nunca pensei em um lançamento porque meu objetivo não era um lançamento", disse ela.
Às vezes, a incerteza na capacidade de resolver esse problema a pressiona. Mas ela disse: "Passei um tempo aprendendo coisas que me interessavam, portanto esse passatempo não pode ser chamado de desperdício".
Esculpido em pedra
Mahadev tentou usar abordagens diferentes para o método do estado secreto para organizar um protocolo de confirmação, mas por algum tempo isso não levou a nada. E então surgiu uma idéia: os pesquisadores já haviam mostrado que o testador pode verificar um computador quântico se ele tiver a capacidade de medir bits quânticos. Por definição, o verificador clássico não tem essa oportunidade. Mas e se um testador clássico pudesse de alguma forma fazer um computador quântico fazer medições por conta própria e honestamente relatar seus resultados?
A dificuldade será como Mahadev entendeu fazer com que o computador quântico prometesse fazer qualquer medida específica antes de descobrir qual medida o inspetor solicitaria - caso contrário, será muito simples para o computador enganá-lo. É aqui que o método do estado secreto entra em ação. O protocolo Mahadev exige que um computador quântico crie primeiro um estado secreto e depois o confunda com o estado que deve ser medido. E só então o computador sabe que medidas precisam ser feitas.
Como o computador não conhece os detalhes internos do estado secreto conhecido pelo inspetor, Mahadev mostrou que o computador quântico não podia enganar de maneira alguma, sem deixar dúvidas. De fato, Vidik escreveu, os qubits que um computador precisa medir são "esculpidos em uma pedra criptográfica". Portanto, se os resultados da medição parecerem uma prova correta, o inspetor poderá ter certeza de que está.
“Essa é uma ideia maravilhosa! - escreveu Vidik. "Ela me golpeia toda vez que Urmila a explica."
O protocolo de confirmação de Mahadev - junto com um gerador de números aleatórios e criptografia cega - depende da suposição de que os computadores quânticos não podem decifrar o LWE. Até agora, o LWE é amplamente considerado o principal candidato à criptografia pós-quântica e, em breve, o Instituto Nacional de Padrões e Tecnologia pode aprová-lo como um novo padrão criptográfico, para substituir aqueles que são propensos a quebrar com um computador quântico. Mas isso não garante que seja realmente seguro contra computadores quânticos, alertou Gottsman. "Mas até agora tudo está claro", diz ele. "Ninguém ainda encontrou evidências da possibilidade de quebrá-lo."
De qualquer forma, a confiança do protocolo no LWE faz do Mahadev um trabalho vencedor em qualquer caso, escreveu Vidik. A única maneira de um computador quântico enganar o protocolo é se alguém do mundo da computação quântica descobrir como invadir o LWE, o que por si só será uma conquista notável.
É improvável que o protocolo Mahadev seja implementado em um computador quântico real em um futuro próximo. Até agora, ele precisa de muito poder computacional do ponto de vista prático. Porém, no futuro, isso poderá mudar à medida que os computadores quânticos crescerem, e os pesquisadores aperfeiçoarão esse protocolo.
É improvável que o protocolo apareça nos próximos cinco anos, por exemplo, mas "não é uma ficção científica", disse Aaronson. "Sobre esse assunto, já será possível começar a pensar, se tudo correr como deveria, no próximo estágio no desenvolvimento de computadores quânticos."
E, dada a rapidez com que essa área está se desenvolvendo, esse estágio pode começar mais cedo do que o esperado. Afinal, apenas cinco anos atrás, disse Vidik, os pesquisadores acreditavam que até computadores quânticos não conseguirem resolver nenhum problema que os computadores clássicos não sejam capazes, isso levará muitos anos. "E agora", disse ele, "as pessoas acreditam que isso acontecerá em um ano ou dois".
Makhadev, tendo resolvido seu problema favorito, permaneceu em um estado um tanto confuso. Mahadev diz que gostaria de entender o que exatamente tornou esse problema tão adequado para ela.
"Agora preciso procurar outra pergunta, por isso seria bom descobrir." Mas especialistas em informática teórica consideram a combinação de computação quântica e criptografia, que Mahadev conseguiu, não o fim da história, mas apenas o começo do estudo do que pode se tornar uma rica fonte de novas idéias."Parece-me que muitas idéias derivadas se seguirão", disse Aaronson. "Estou ansioso por novos resultados de Urmila."