Trinta anos depois, um aumento na velocidade do factoring quântico | Revista Quanta

Peter Shor não pretendia quebrar a internet. Mas um algoritmo que ele desenvolveu em meados da década de 1990 ameaçava fazer exatamente isso. Em um papel de referência, Shor mostrou como um computador hipotético que explorasse as peculiaridades da física quântica poderia decompor grandes números em seus fatores primos muito mais rápido do que qualquer máquina clássica comum.

O resultado teve implicações muito além da matemática. Na época, um componente vital da segurança da Internet chamado criptografia de chave pública baseou-se na suposição de que fatorar números grandes é tão difícil computacionalmente que é efetivamente impossível. Essa suposição ainda sustenta alguns protocolos críticos hoje. O algoritmo de Shor mostrou que falharia espetacularmente em um mundo com poderosos computadores quânticos.

Nos últimos 30 anos, os cientistas da computação simplificaram o algoritmo de Shor em preparação para o dia em que a tecnologia quântica amadurecer o suficiente para executá-lo. Mas uma nova variante, do cientista da computação da Universidade de Nova York Oded Regev, é mais rápido em um sentido fundamentalmente novo. É o primeiro a melhorar a relação entre o tamanho do número que está sendo fatorado e o número de operações quânticas necessárias para fatorá-lo.

“É realmente notável que alguém aparentemente tenha conseguido melhorar a complexidade deste resultado muitos, muitos anos depois”, disse Ashley Montanaro, pesquisador de computação quântica da Universidade de Bristol. “Isso é realmente emocionante.”

Martin Ekerå, criptógrafo da Autoridade Nacional de Segurança das Comunicações da Suécia, concordou que o artigo de Regev é interessante, mas alertou que superar o estado da arte na prática exigirá maior otimização. “Os algoritmos originais de Shor já são surpreendentemente eficientes, por isso não é trivial fazer grandes melhorias”, escreveu ele por e-mail.

Regev desenvolveu seu novo algoritmo aumentando o algoritmo de Shor com técnicas de um ramo da criptografia que lida com geometria de alta dimensão.

“Eu teria pensado que qualquer algoritmo que funcionasse com esse esquema básico estaria condenado”, disse Shor, um matemático aplicado atualmente no Instituto de Tecnologia de Massachusetts. "Mas eu estava errado."

Encontrando Fatores

Os computadores quânticos derivam seu poder da maneira peculiar como processam informações. Os computadores clássicos usam bits, cada um dos quais deve estar sempre em um de dois estados, rotulados como 0 e 1. Os bits quânticos, ou “qubits”, também podem estar em combinações de seus estados 0 e 1 – um fenômeno chamado superposição. Também é possível persuadir vários qubits a um estado de superposição coletiva: uma superposição de dois qubits tem quatro componentes que podem realizar diferentes cálculos simultaneamente, e o número de tais componentes cresce exponencialmente à medida que o número de qubits aumenta. Isso permite que os computadores quânticos executem efetivamente muitos cálculos diferentes em paralelo.

BUT há um problema: A leitura do resultado de um cálculo realizado em superposição revela apenas a resposta para a parte calculada por um componente aleatório. Para colher os benefícios da computação em superposição, você deve de alguma forma mapear o resultado final em um estado mais simples onde seja seguro ler o resultado. Isso não é possível na maioria dos casos e, a princípio, ninguém sabia como fazê-lo funcionar para qualquer problema. “Havia muito poucas pessoas que tiveram a coragem de pensar em computação quântica”, disse Regev.

Então, em 1994, Shor leu um papel pelo cientista da computação Daniel Simon que mostrou como explorar a superposição quântica para resolver um problema inventado. Shor descobriu como estender o resultado de Simon a um problema mais geral e prático chamado determinação de período. Diz-se que uma função matemática é periódica quando sua saída percorre repetidamente os mesmos valores à medida que a entrada aumenta; a duração de um único ciclo é conhecida como período da função.

Para encontrar o período de uma determinada função usando um computador quântico, comece configurando uma superposição muito grande na qual cada componente calcula a saída da função para uma entrada diferente. Em seguida, use o método de Shor para converter essa grande superposição em um estado mais simples e leia o resultado. Nesse ponto, um computador clássico pode assumir e concluir o cálculo rapidamente. No geral, o algoritmo de determinação de período de Shor é executado exponencialmente mais rápido do que qualquer alternativa clássica porque calcula diferentes saídas da função periódica simultaneamente usando superposição.

Enquanto Shor procurava aplicações para seu algoritmo quântico de determinação de período, ele redescobriu um teorema matemático anteriormente conhecido, mas obscuro: para cada número, existe uma função periódica cujos períodos estão relacionados aos fatores primos do número. Portanto, se houver um número que você deseja fatorar, você pode calcular a função correspondente e então resolver o problema usando a descoberta do período – “exatamente no que os computadores quânticos são tão bons”, disse Regev.

Em um computador clássico, essa seria uma forma dolorosamente lenta de fatorar um grande número – mais lenta ainda do que tentar todos os fatores possíveis. Mas o método de Shor acelera o processo exponencialmente, fazendo com que a descoberta do período seja uma maneira ideal de construir um algoritmo de fatoração quântica rápido.

O algoritmo de Shor foi um dos poucos resultados iniciais importantes que transformaram a computação quântica de um subcampo obscuro da ciência da computação teórica no rolo compressor que é hoje. Mas colocar o algoritmo em prática é uma tarefa difícil, porque os computadores quânticos são notoriamente suscetíveis a erros: além dos qubits necessários para realizar seus cálculos, eles precisam de muitos outros para fazer isso. trabalho extra para evitar que eles falhem. A artigo recente por Ekerå e o pesquisador do Google Craig Gidney estima que usar o algoritmo de Shor para fatorar um número padrão de segurança de 2,048 bits (cerca de 600 dígitos) exigiria um computador quântico com 20 milhões de qubits. As máquinas de última geração de hoje têm no máximo algumas centenas.

É por isso que alguns protocolos críticos da Internet ainda dependem da dificuldade de fatorar grandes números, mas os pesquisadores não querem ser muito complacentes. teórico e as inovações tecnológicas poderiam reduzir ainda mais a contagem de qubits necessária, e não há provas de que o algoritmo de Shor seja ideal - pode haver um algoritmo de fatoração quântica melhor por aí que ninguém descobriu.

Se assim for, disse Regev, “deveríamos saber o mais cedo possível, antes que seja tarde demais”.

Perdido nas árvores

Regev iniciou sua carreira acadêmica no final da década de 1990, quando criptógrafos procuravam uma nova forma de criptografia de chave pública que não fosse vulnerável ao algoritmo de Shor. A abordagem mais promissora, chamada criptografia baseada em treliça, baseia-se na aparente dificuldade de problemas computacionais envolvendo matrizes de pontos ou redes de alta dimensão. Um desses problemas é semelhante à tarefa de localizar a árvore mais próxima de um ponto aleatório em uma floresta.

“Se for uma floresta de cem dimensões, então será muito mais complicado do que se for uma floresta bidimensional”, disse Greg Kuperberg, um matemático da Universidade da Califórnia, Davis.

Regev começou a estudar criptografia baseada em rede como pós-doutorado, inicialmente como um invasor – ele queria testar a nova abordagem, encontrando pontos fracos que um computador quântico poderia explorar. Mas ele não conseguiu fazer nenhum progresso e logo se perguntou se haveria uma razão mais profunda para isso. Em 2005, ele encontrou uma maneira de transformar esses ataques fracassados ​​em uma forma de criptografia baseada em rede superior a todas as outras variantes.

“Oded é absolutamente brilhante com redes”, disse Kuperberg.

Ao longo dos anos, à medida que Regev ensinava o algoritmo de Shor a sucessivas gerações de estudantes, ele se perguntou se as técnicas que havia usado para atacar a criptografia baseada em rede poderiam realmente ser úteis na fatoração de algoritmos. Isso ocorre porque uma etapa no estágio final clássico do algoritmo de Shor equivale a encontrar o ponto mais próximo em uma rede unidimensional. Esse problema unidimensional é trivialmente fácil, mas a semelhança com o problema análogo em centenas de dimensões cuja dureza sustenta a criptografia baseada em rede era inconfundível.

“Se você é alguém que faz treliças como eu, você pensa: 'OK, há alguma treliça acontecendo aqui'”, disse Regev. “Mas não estava claro para mim como fazer uso disso.” Durante anos ele brincou com outras ideias para novos algoritmos de fatoração quântica, mas nunca chegou a lugar nenhum. Então, no inverno passado, ele voltou ao problema e resolveu estabelecer a tentadora conexão entre fatoração e criptografia baseada em rede. Desta vez, ele encontrou o sucesso.

Dimensões extras

Regev sabia que precisava começar generalizando a função periódica no centro do algoritmo de Shor de uma dimensão para muitas dimensões. No algoritmo de Shor, essa função envolve a multiplicação repetida de um número aleatório, denominado g, consigo mesmo. Mas o período desta função — o número de vezes que você deve multiplicar por g antes que a saída da função comece a se repetir — pode ser muito grande, e isso significa que um computador quântico deve multiplicar grandes números em alguns componentes da superposição que usa para calcular a função periódica. Essas grandes multiplicações são a parte computacionalmente mais cara do algoritmo de Shor.

A função bidimensional análoga usa um par de números, g₁ e g₂. Envolve multiplicar g₁ consigo mesmo muitas vezes e depois multiplicando repetidamente por g₂. O período desta função também é bidimensional — é definido pelo número de g₁ multiplicações e g₂ multiplicações que juntas fazem com que a saída da função comece a se repetir. Existem muitas combinações diferentes de g₁ e g₂ multiplicações que resolverão o problema.

Regev trabalhou nos detalhes técnicos para generalizar o algoritmo para um número arbitrário de dimensões, não apenas duas, mas seus resultados iniciais não foram encorajadores. Para calcular a função periódica em muitas dimensões, o computador quântico ainda teria que multiplicar muitos números. Cada número não precisaria ser multiplicado tantas vezes como no caso unidimensional, mas havia mais números distintos para multiplicar. A coisa toda parecia um fracasso.

“Você pensa: 'Ótimo, fiz tudo em grandes dimensões e tem exatamente o mesmo tempo de execução do Shor'”, disse Regev. “Fiquei preso nisso por um tempo.” Então ele percebeu que poderia contornar o problema alterando a ordem das multiplicações. Em vez de acrescentar repetidamente números a um único produto que cresceria progressivamente ao longo da computação quântica, ele começou com pares de números pequenos, multiplicou os produtos resultantes e prosseguiu para cima. O número total de multiplicações não mudou muito, mas agora quase todas envolvem números relativamente pequenos, tornando o cálculo mais rápido.

“Isso faz toda a diferença no mundo”, disse Vinod Vaikuntathan, um criptógrafo do MIT.

A princípio, parecia que Regev tinha acabado de substituir um problema por outro. Ele acelerou o cálculo quântico da função periódica aumentando o número de dimensões, mas o cálculo clássico subsequente necessário para extrair o período era agora semelhante à localização do ponto da rede mais próximo em um espaço de alta dimensão - uma tarefa amplamente considerada ser dificil. A analogia com a criptografia baseada em rede que motivou sua nova abordagem parecia condená-la ao fracasso.

Numa manhã fria de março, antes de uma viagem para um seminário na Universidade de Princeton, Regev se viu esperando pelo colega com quem estava viajando de carona. “Cheguei cedo e ele se atrasou para pegar o carro”, disse ele. Enquanto ele estava sentado esperando, a última peça do quebra-cabeça de repente veio à sua mente. “Esse foi o momento em que as coisas se encaixaram, mas já estava assando há um tempo.”

Tudo se resumia ao número certo de dimensões. Quando a dimensão da rede era muito baixa, seu algoritmo não conseguia aproveitar ao máximo a aceleração da multiplicação de números menores. Quando era muito alto, a computação quântica era rápida, mas a parte clássica exigia a resolução de um problema de rede proibitivamente difícil. Regev sabia desde o início que, para ter alguma esperança de sucesso, teria que trabalhar em algum ponto intermediário, mas não estava claro se existia um ponto ideal. Naquela manhã de março, ele percebeu como poderia ajustar os detalhes do algoritmo para fazê-lo funcionar rapidamente em algumas dezenas de dimensões.

Escrevendo na areia

A melhoria foi profunda. O número de etapas lógicas elementares na parte quântica do algoritmo de Regev é proporcional a n^1.5 ao fatorar um nnúmero de bits, em vez de n² como no algoritmo de Shor. O algoritmo repete essa parte quântica algumas dezenas de vezes e combina os resultados para mapear uma rede de alta dimensão, a partir da qual pode deduzir o período e fatorar o número. Portanto, o algoritmo como um todo pode não funcionar mais rápido, mas acelerar a parte quântica reduzindo o número de etapas necessárias poderia facilitar sua colocação em prática.

É claro que o tempo necessário para executar um algoritmo quântico é apenas uma das várias considerações. Igualmente importante é o número de qubits necessários, que é análogo à memória necessária para armazenar valores intermediários durante um cálculo clássico comum. O número de qubits que o algoritmo de Shor requer para fatorar um n-número de bits é proporcional a n, enquanto o algoritmo de Regev em sua forma original requer um número de qubits proporcional a n^1.5 – uma grande diferença para números de 2,048 bits.

Na computação clássica, a velocidade é geralmente uma consideração mais importante do que a memória, porque os bits clássicos são extremamente robustos: você pode salvar um arquivo no seu computador e não se preocupar com a possibilidade de ele mudar aleatoriamente quando você abri-lo novamente mais tarde. Os pesquisadores da computação quântica nem sempre têm tanta sorte.

“Nossos qubits estão constantemente tentando desmoronar e estamos tentando impedi-los de desmoronar”, disse Gidney. “É como se você estivesse tentando escrever na areia e o vento soprasse para longe.” Isso significa que os qubits extras exigidos pelo algoritmo de Regev podem ser uma grande desvantagem.

Mas o artigo de Regev não é o fim da história. Duas semanas atrás, Vaikuntanathan e seu aluno Seyoon Ragavan encontraram uma maneira de reduzir o uso de memória do algoritmo. Sua variante do algoritmo de Regev, como o algoritmo original de Shor, requer um número de qubits proporcional a n em vez de n^1.5. Ekerå escreveu por e-mail que o trabalho “nos aproxima muito de uma implementação que seria mais eficiente na prática”.

A lição mais ampla do novo algoritmo de Regev, para além das implicações para o factoring, é que os investigadores da computação quântica devem estar sempre abertos a surpresas, mesmo em problemas que têm sido estudados há décadas.

“Essa variante do meu algoritmo não foi descoberta por 30 anos e surgiu do nada”, disse Shor. “Provavelmente ainda existem muitos outros algoritmos quânticos a serem encontrados.”

Nota do editor: Oded Regev recebe financiamento do Fundação Simons, que também financia esta revista editorialmente independente. As decisões de financiamento da Fundação Simons não têm influência em nossa cobertura. Mais detalhes são disponíveis aqui.

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de ciência da computação e você estará inscrito para ganhar de graça Quanta mercadoria.