Como a física quântica leva à descriptografia de algoritmos comuns

A ascensão da computação quântica ea sua implicações para os padrões de criptografia atuais são bem conhecidos. Mas por que exatamente os computadores quânticos deveriam ser especialmente hábeis em quebrar a criptografia? A resposta é um belo malabarismo matemático chamado o algoritmo de Shor. A questão que ainda permanece é: o que esse algoritmo faz para que os computadores quânticos sejam muito melhores em quebrar a criptografia? Em este vídeo, YouTuber minutefísica explica isso em seu estilo tradicional de desenho animado no quadro branco.

“A computação quântica tem o potencial de tornar super fácil o acesso a dados criptografados – como ter um sabre de luz que você pode usar para romper qualquer fechadura ou barreira, não importa quão forte seja”, diz Minutephysics. “O algoritmo de Shor é aquele sabre de luz.”

De acordo com o vídeo, o algoritmo de Shor parte do entendimento de que, para qualquer par de números, eventualmente multiplicar um deles por si mesmo resultará em um fator do outro número mais ou menos 1. Assim, você adivinha o primeiro número e o fatora. somando e subtraindo 1, até chegar ao segundo número. Isso desbloquearia a criptografia (especificamente RSA aqui, mas funciona em alguns outros tipos) porque teríamos então os dois fatores.

Uma razão pela qual este processo aparentemente simples depende do desenvolvimento de computadores quânticos poderosos é que encontrar a potência correta para multiplicar o primeiro número a fim de encontrar um fator do segundo número (N) ± 1 requer uma enorme quantidade de tentativas. A chave de criptografia é um número bastante longo e, portanto, o poder pode variar de 1 a milhões. Mas a força bruta não é a razão pela qual os computadores quânticos funcionam tão bem aqui.

Os superpoderes das superposições

Resumidamente, graças à superposição quântica, um computador quântico pode calcular muitas respostas para uma única entrada. No entanto, o vídeo diz que você obtém apenas uma resposta por vez, com probabilidades anexadas. Para resolver esse problema, o cálculo é configurado de forma que as respostas erradas interfiram umas com as outras, de modo que apenas a resposta correta (ou pelo menos um bom palpite) provavelmente será gerada. Esse cálculo, que se concentra em encontrar a potência certa p, é o algoritmo de Shor.

É tudo extremamente matemático, envolvendo uma assistência de Algoritmo de Euclides, bem como uma transformada quântica de Fourier que transforma uma série de superposições de superposições em ondas senoidais que interferem construtivamente (se somam) ou destrutivamente - ou seja, se cancelam. O vídeo diz que, essencialmente, você pode configurá-lo para que apenas 1/p é salva, com todas as outras respostas interferindo destrutivamente fora da discórdia. Uma vez lá, é um passeio no parque para encontrar p, o que torna muito mais fácil encontrar os dois fatores de criptografia. Assista ao vídeo inteiro para mais detalhes e talvez para se sentir um pouco mais inteligente.

A propósito, Peter Shor é ainda prosperando, e se você estiver interessado em saber mais sobre como ele quebrou a Internet, aqui está outro vídeo onde o próprio homem explica como ele descobriu sua obra-prima homônima.