Eu tenho visto muito mais alvoroço sobre computadores quânticos no X recentemente, então pensei em fazer um post longo sobre eles. Resumo executivo: Eu não acredito que a computação quântica esteja chegando tão cedo. Eu penso isso porque não houve progresso em muitos anos no problema mais simples para o qual os computadores quânticos podem ser usados, que é a fatoração. O recorde de fatoração quântica está em torno do número 15 (sim, 15, 3 x 5!) há uma década, e nenhum progresso óbvio aconteceu recentemente. Minha razão está abaixo. Vou explicar as coisas para pessoas que não sabem muito de matemática ou ciência da computação, mas isso ainda pode assustar pessoas com fobias matemáticas. A fatoração de números grandes é de interesse porque vários algoritmos criptográficos importantes dependem do fato de que leva muito tempo para fatorar um número suficientemente grande em seus fatores primos usando computadores convencionais. Você pode fatorar um número pequeno (digamos 21) à mão muito rapidamente, basta tentar dividi-lo pelos números começando com 2, depois 3 e assim por diante, e você rapidamente descobrirá que 21 é 3 x 7. No entanto, isso não funciona para números realmente grandes porque o espaço de todos os números que você precisaria tentar fica muito grande. Se você pudesse fatorar números com cerca de 1200 dígitos decimais de comprimento (não o número 1200, que tem quatro dígitos, números com 1200 dígitos!) você poderia quebrar muitos sistemas criptográficos que as pessoas se importam, mas ninguém sabe como fazer isso rápido o suficiente em um computador normal. (Rápido o suficiente significa "antes que todas as estrelas no céu se apaguem.") Alguns anos atrás, Peter Shor mostrou que você poderia (pelo menos em teoria) fatorar números muito rapidamente usando computadores quânticos. A fatoração usando o Algoritmo de Shor é, na minha opinião, o benchmark mais óbvio e difícil de falsificar para a computação quântica. Em 2016, o número 15 (não um número de 15 dígitos, o número 15!) foi pela primeira vez fatorado (obviamente em 3 x 5) em uma demonstração limpa e não manipulada do Algoritmo de Shor. Este é um número pequeno, mas foi um começo. (Há alguma discussão sobre se o número 21 também foi fatorado em uma demonstração não manipulada do algoritmo de Shor ou não.) Mas novamente, 15 é um número de dois dígitos. Queremos fatorar números com milhares de dígitos para poder quebrar sistemas criptográficos. No entanto, desde 2016, nenhum número maior foi fatorado em demonstrações limpas do algoritmo de Shor. (Algumas pessoas afirmaram que fatoraram números maiores usando o Algoritmo de Shor, mas sempre usaram truques que exigiam que já soubessem os fatores para fazê-lo e configuraram o computador quântico com o que equivale a um pré-conhecimento da resposta, o que realmente não é o ponto. Estou procurando demonstrações *não manipuladas*.) Estamos esperando há muito tempo que alguém demonstre a fatoração de um número um pouco maior que 15. Você esperaria que pudesse haver um progresso constante nisso, com alguém fatorando (digamos) um número como 77 (7 x 11), e então um como 323 (17 x 19), depois algo na casa dos milhares, e assim por diante. No entanto, ninguém demonstrou uma máquina que possa fazer algo melhor que o número 15 (que uma criança pode fatorar em sua cabeça em 3 e 5 em momentos) e esse recorde se manteve por muito tempo. Portanto, neste problema pelo menos, um realmente básico que é fácil de explicar, não houve progresso constante na computação quântica. Tivemos muito alvoroço, muitas pessoas exibindo computadores quânticos supostamente executando algoritmos que não são exatamente demonstrações tão limpas, mas não vimos nada há muito tempo sobre fatoração. Eu acreditarei que houve progresso real na computação quântica quando começarmos a ver números maiores sendo fatorados em demonstrações limpas e não manipuladas do Algoritmo de Shor. Eu acreditarei que fizemos progresso real quando pudermos fazer números de quatro dígitos decimais, ou seja, números na casa dos milhares. Mesmo uma demonstração de algo que pudesse fazer um número de dois dígitos muito maior que 15 seria bem-vinda. No entanto, nenhuma máquina que possa fazer isso está realmente no horizonte a curto prazo. Agora, ser capaz de quebrar códigos requer máquinas que possam lidar com números com *milhares* de dígitos, mas ainda não temos números de três dígitos à vista (ou mesmo a maioria dos números de dois dígitos). Portanto, meu benchmark pessoal é ver até mesmo um pouco de progresso nisso. Me ligue de volta quando tivermos computadores quânticos que possam fatorar (digamos) 323 com sucesso, em uma demonstração limpa e não manipulada do Algoritmo de Shor que lidaria com qualquer número composto de tamanho semelhante. Até lá, não acho que haja muito de interessante acontecendo, pelo menos não para mim.

(A propósito, não quero dar a impressão de que acho que a computação quântica é impossível ou algo assim. Estou apenas a dizer que, do meu ponto de vista, o progresso recente não tem sido óbvio e ainda estamos longe de resolver problemas simples como a fatoração de números com isso.)

A propósito, isso também não significa que empresas como o Google sejam tolas por perseguirem pesquisas puras em computação quântica. Eu acho que vale a pena trabalhar nisso. Não é apenas uma aplicação prática iminente. Pode também ser que a NSA ou outras organizações semelhantes tenham feito progressos mais significativos no problema do que o mundo da pesquisa aberta, mas, obviamente, essa não é uma informação à qual eu teria acesso. Por último, isso não significa que a pesquisa em algoritmos criptográficos pós-quânticos seja uma má ideia.

No meu post original no topo, evitei mencionar quão difíceis são os problemas de escalabilidade. Principalmente, concentrei-me no fato de que nenhuma das escalas realmente aconteceu. E para ter certeza, em algum momento, é muito possível que as questões de correção de erros comecem a aparecer. Mas, escalar para fatorar números sérios não vai acontecer no dia seguinte a isso.

@defendtheworld Então, de qualquer forma, novamente: começarei a acreditar quando ver a tecnologia avançar além da fatoração de 15. E sim, isso significa que uma enorme quantidade de trabalho já terá sido feita, mas também deixará uma enorme quantidade de trabalho ainda por fazer.