Computadores quanticos

O que

São computadores que diferentemente dos tradicionais binários, utilizam estados quânticos para processar algoritmos

Por que

Muito se ouve falar que eles são superiores aos computadores tradicionais porque os 'qubits' estão em superposição e consegue-se calcular todos os resultados em tempo real (paralelismo) mas isso é falso

Como

A vantagem do computador quântico está somente na complexidade temporal, que em teoria é mais rápido comparado ao computador mecânico. Não está na capacidade computacional.

A explicação de como funciona é um tema bem complexo, mas tudo que é complexo pode ser quebrado em etapas menores. Vou tentar anotar o que entendi até o momento

Qubits

O computador tradicional usa a unidade informacional bit. É um conjunto mecânico de transistores que podem estar em dois estados: ligado ou desligado, 0 ou 1.

Já o quântico utiliza unidade informacional o qubit (que ainda não sei como é fisicamente) e seu estado é probabilistico. Para determinar seu estado é preciso fazer uma leitura que vai colapsar o qubit em um estado ligado ou desligado igual o tradicional

Se utiliza essa notação $|0\rangle$ $|1\rangle$ para escrever um estado quântico

Teoria quantica

Difere das leis clássicas drasticamente e ainda existem divergências de definições

A mais utilizada seria a interpretação de Copenhagen que define a mecânica quântica como indeterminável e probabilística.

Para medir e trazer um estado para o mundo real é preciso observar e este ato faz com que as probabilidades se colapsem ou reduzem para um estado clássico

Não entendi ainda bem mas tem uma frase legal

Einstein suddenly stopped, turned to me and asked whether I really believed that the moon exists only when I look at it

Algoritmos

O computador precisa resolver algum problema. Esse problema precisa ser traduzido em um programa ou algoritmo e este, por sua vez, transformado em uma sequencia de operações logic gates

Nenhum problema que não pode ser resolvido no computador clássico também não consegue ser resolvido no quântico

Um dos algoritmos mais famoso:

Grover: Para brute-force ou busca linear. É mais rápido que um computador mecânico na ordem quadrática.

Shor: Achar fator primo de um numero integral

No hardware atual, isso ainda não chega perto de quebrar SHA-256 ou RSA-2048. A importância está no princípio: alguns problemas mudam de escala quando existe um computador quântico grande, confiável e com correção de erros.

O algoritmo de Shor

O algoritmo de Shor é importante porque ele mostra uma vantagem quântica aplicada a um problema real de segurança: fatorar números inteiros grandes. A versão mais conhecida ataca a fatoração, que é a base do RSA. Outras ideias relacionadas também atingem problemas de logaritmo discreto, que aparecem em sistemas como Diffie-Hellman e criptografia de curva elíptica.

O ponto principal não é que o computador quântico testa todos os fatores ao mesmo tempo e depois lê a resposta. Isso não acontece. Shor transforma a fatoração em um problema de período, usa interferência quântica para tornar esse período mensurável e depois usa contas clássicas para recuperar os fatores.

Por que isso importa

Em RSA, a chave pública contém um número N que é o produto de dois primos grandes: N = p × q. Qualquer pessoa consegue multiplicar p e q rapidamente, mas recuperar p e q a partir de N fica impraticável em computadores clássicos quando os primos são grandes.

Se um computador quântico tolerante a falhas conseguir rodar Shor em um N grande, ele pode recuperar p e q. Com esses primos, uma etapa clássica reconstrói a chave privada correspondente. Por isso Shor é uma das razões para a migração para criptografia pós-quântica.

Como ele pode ser usado

O uso ofensivo seria pegar uma chave pública RSA, extrair o módulo N, rodar Shor para fatorar N e usar os fatores para calcular a chave privada. O uso defensivo é entender esse risco e trocar sistemas vulneráveis por algoritmos pós-quânticos antes que exista hardware grande o bastante.

Hoje, o exemplo abaixo usa N = 15 porque ele cabe em poucos qubits e mostra a estrutura do algoritmo. Ele não representa a escala de uma chave real.

O exemplo pequeno: fatorar 15

Imagine que queremos fatorar N = 15. O algoritmo escolhe um número a menor que N, por exemplo a = 2, e verifica se a já compartilha algum divisor com N. Se mdc(a, N) for maior que 1, encontramos um fator sem precisar da parte quântica. Se não for, o algoritmo procura o período de a^x mod N.

O período é o ponto central do algoritmo. Shor não tenta dividir 15 por todos os candidatos. Ele observa a função f(x) = a^x mod N e procura de quanto em quanto tempo os resultados se repetem.

Para N = 15 e a = 2, a sequência fica assim:

2^0 mod 15 = 1
2^1 mod 15 = 2
2^2 mod 15 = 4
2^3 mod 15 = 8
2^4 mod 15 = 1

A sequência voltou para 1 depois de quatro passos. O período é r = 4.

Como o circuito organiza a conta

O circuito usa dois registradores principais. Um registrador é um conjunto de qubits tratado como uma pequena memória: em vez de guardar apenas um número clássico, ele guarda um estado quântico que pode representar muitos valores possíveis antes da medição.

O primeiro registrador guarda o expoente x. O segundo registrador guarda o resultado modular a^x mod N. Separar esses dois espaços ajuda o circuito a relacionar cada valor possível de x com o resultado correspondente da função modular.

Para N = 15, precisamos de n = 4 qubits para representar números de 0 até 15, então o registrador modular usa 4 qubits. Em uma forma didática comum de Shor, o registrador de expoente usa cerca de 2n qubits para medir o período com boa precisão. Neste exemplo, isso dá 8 qubits para x, ou seja, 2^8 = 256 posições possíveis para testar expoentes em superposição.

Assim, o exemplo conceitual usa:

8 qubits  para o registrador de expoente x
4 qubits  para o registrador modular
12 qubits lógicos principais

Circuitos reais ainda precisam de qubits auxiliares para fazer aritmética reversível e correção de erros. Demonstrações pequenas de 15 = 3 × 5 às vezes usam menos qubits porque otimizam o circuito para esse caso específico, mas isso não representa o algoritmo geral.

O preparo começa com o registrador de expoente em |0...0⟩, que significa “todos os qubits começam em zero”. Portas Hadamard colocam esse registrador em uma superposição uniforme de muitos valores de x. Em linguagem menos formal: o circuito prepara uma tabela quântica onde várias entradas de x existem ao mesmo tempo, mas ainda não foram lidas como números clássicos.

Depois, o circuito de exponenciação modular calcula:

|x⟩ |1⟩  →  |x⟩ |2^x mod 15⟩

Esse passo cria correlação entre o expoente e o resultado. Correlação aqui significa que cada possibilidade de x fica ligada ao valor correspondente de 2^x mod 15. A sequência modular tem período 4, mas esse período ainda não aparece como um número clássico legível.

Onde a QFT entra

QFT significa transformada quântica de Fourier. Ela entra exatamente depois da exponenciação modular, quando o período já está escondido nas amplitudes do registrador de expoente.

A QFT é a versão quântica da transformada de Fourier. Em vez de operar sobre uma lista clássica de números, ela opera sobre as amplitudes de um estado quântico.

A ideia intuitiva é simples: Fourier troca “posição” por “frequência”. No exemplo de Shor, “posição” quer dizer o índice x dentro do registrador de expoente. “Frequência” quer dizer o ritmo de repetição escondido nessa sequência.

Quando dizemos que a QFT “muda a base do registrador”, não significa que ela troca os qubits físicos. Ela muda o jeito matemático de descrever e medir o mesmo estado. Antes da QFT, o estado está organizado pelos valores possíveis de x; depois da QFT, ele fica organizado por frequências compatíveis com repetições desses valores.

Se uma sequência repete a cada 4 posições, a QFT concentra mais probabilidade em alguns resultados de medição. Esses resultados não são o período diretamente, mas apontam para frações que permitem recuperar o período na etapa clássica.

No exemplo, o registrador de expoente tem 8 qubits, portanto tem 2^8 = 256 posições possíveis. Um período r = 4 gera picos separados por:

256 / 4 = 64

Por isso a animação mostra picos em 0, 64, 128 e 192. Uma medição útil, como 64 ou 192, aponta para frações próximas de 1/4 ou 3/4. A etapa clássica usa frações contínuas para recuperar o denominador 4, que é o período r.

Nem toda medição serve. O resultado 0 não informa o período, e alguns resultados podem reduzir para uma fração simples demais. Shor repete a parte quântica quando a medição não entrega um período útil.

Animação completa do Shor

A animação abaixo junta as etapas na ordem do circuito: preparar os registradores, calcular 2^x mod 15, aplicar a QFT, medir um pico e usar a etapa clássica para recuperar os fatores.

Como o período vira fatores

Quando o período r é par, o pós-processamento volta a ser clássico. Calculamos:

mdc(a^(r/2) - 1, N)
mdc(a^(r/2) + 1, N)

No exemplo, a = 2, r = 4 e N = 15:

mdc(2^2 - 1, 15) = mdc(3, 15) = 3
mdc(2^2 + 1, 15) = mdc(5, 15) = 5

Portanto, 15 = 3 × 5.