Fatore um número
com física

Esta página conta o algoritmo de Shor de ponta a ponta — superposição, espaço de Hilbert, interferência, medição — com uma simulação exata rodando aqui no seu navegador. E depois mostra o mesmo circuito executado num processador quântico real da IBM, de 156 qubits, com os dados crus da medição: os acertos e o ruído.

Rodar o algoritmo agora Ver o hardware real

Projeto irmão do Sorteio Quântico — a mesma conta IBM Quantum, o mesmo gosto por provas verificáveis.

1 O qubit: uma seta, não um interruptor

Um bit é um interruptor: 0 ou 1. Um qubit guarda uma amplitude para cada valor — um número complexo, que desenhamos como uma seta com comprimento e direção (a fase). A probabilidade de medir um valor é o comprimento da seta ao quadrado.

A porta H (Hadamard) divide o caminho: leva |0⟩ para (|0⟩ + |1⟩)/√2 — os dois valores ao mesmo tempo, cada um com probabilidade ½.

O teste que separa isso de um sorteio clássico: aplique H duas vezes. Uma moeda jogada duas vezes continua aleatória. O qubit volta certinho para |0⟩ — porque os dois caminhos que levariam a |1⟩ chegam com setas opostas (+½ e −½) e se cancelam. Isso é interferência, e é a alma de tudo que vem a seguir.

|0⟩
Amplitudes do qubit — altura = |amplitude|, cor = fase.

2 O espaço de Hilbert: onde a conta acontece

Com n qubits, o estado é uma lista de 2n amplitudes — uma seta para cada combinação de bits. Esse espaço vetorial gigante é o espaço de Hilbert do sistema, e cresce exponencialmente: cada qubit novo dobra a lista.

O detalhe que todo texto de divulgação erra: ter 2n amplitudes não é o mesmo que testar 2n respostas. Ao medir, você recebe um resultado, sorteado. O truque de um algoritmo quântico não é o paralelismo — é arranjar as fases para que os caminhos errados se cancelem e o certo sobre. Sem isso, superposição é só uma moeda cara.

Cada barra é uma dimensão do espaço de Hilbert — em escala real até a tela acabar.

3 Interferência: setas que se somam ou se engolem

Quando vários caminhos levam ao mesmo resultado, as setas deles se somam cabeça em cauda. Se chegam apontando para o mesmo lado, a resultante é enorme — interferência construtiva. Se cada uma chega girada um pouquinho a mais que a anterior, o caminho se fecha num círculo e a resultante morre — destrutiva.

Arraste o passo de fase e veja as 24 setas alinharem ou se engolirem. É exatamente esta figura que decide, lá na frente, quais valores o computador quântico deixa sobreviver na medição.

As 24 setinhas se somam ponta a ponta; a seta rosa, ao lado do caminho, é o total.

4 Fatorar vira achar um período

A ideia clássica por trás de Shor (e ela é 100% clássica): escolha um número a que não divida N e olhe a sequência a¹, a², a³, … (mod N). Ela sempre entra num ciclo — repete com um período r.

Sabendo r (par, com ar/2 ≢ −1), escreva ar − 1 ≡ 0 (mod N) e fatore a diferença de quadrados: (ar/2−1)(ar/2+1) ≡ 0 (mod N). Os fatores de N se repartem entre os dois parênteses — e o mdc de cada parêntese com N os entrega, em tempo de calculadora.

Todo o problema virou: medir o período de uma função que se repete. E medir períodos é a especialidade da transformada de Fourier — que tem uma versão quântica que roda sobre todas as amplitudes de uma vez.

7x mod 15 = 1, 7, 4, 13, 1, 7, 4, 13, … — período r = 4.

5 O algoritmo de Shor, ao vivo

Simulação exata — seu navegador calcula todas as amplitudes do estado, as mesmas que um simulador porta a porta produziria. Escolha o número e acompanhe as quatro etapas.

6 Agora no hardware de verdade

A simulação acima é o algoritmo em condições ideais. Abaixo, os histogramas crus dos mesmos circuitos executados num processador IBM Quantum da família Heron (156 qubits) — renovados automaticamente, uma rodada por semana, pelo mesmo mecanismo que alimenta o Sorteio Quântico. O eixo x é o k medido, o mesmo do simulador acima; abaixo de cada gráfico, a conta que transforma esses k em fatores.

Por que o circuito genérico afoga — e por que isso importa

Cada porta de 2 qubits do processador acerta ~99,7% das vezes. Parece muito, mas fidelidades se multiplicam: com 83 portas (0,99783 ≈ 78%) os picos sobrevivem; com ~12 400 (0,99712400 ≈ 10−17) o que sai é uniforme — ruído puro, indistinguível de um dado de 16 faces.

E aqui mora uma lição de honestidade científica: quase toda "fatoração quântica" já demonstrada usou circuitos compilados, encolhidos com conhecimento prévio da resposta — como os dois primeiros acima. O circuito genérico, o único que contaria numa fatoração cega, ainda não sobrevive ao ruído nem para N=15. É por isso que a fronteira real da área não é "quantos qubits", e sim correção de erros: transformar milhares de qubits físicos ruidosos em alguns qubits lógicos quase perfeitos.

7 "Então o RSA já era?" — ainda não. Mas o relógio anda.

Uma chave RSA-2048 tem 617 dígitos. Fatorá-la com Shor exige circuitos com bilhões de portas executados sem perder a coerência — as estimativas mais citadas falam em ~20 milhões de qubits físicos ruidosos rodando por ~8 horas, ou alguns milhares de qubits lógicos com correção de erros madura. O processador desta página tem 156 qubits físicos e, como você viu acima, tropeça no circuito genérico para N=15.

Mas a distância é de engenharia, não de princípio — nada na física proíbe. Por isso a criptografia já se mexeu: o NIST padronizou em 2024 os primeiros algoritmos pós-quânticos (ML-KEM, ML-DSA), e a migração começou. O risco real de hoje chama-se harvest now, decrypt later: guardar tráfego cifrado agora para abrir quando o hardware chegar lá.

§ Metodologia

Simulação no navegador. O estado após o oráculo é (1/√M) Σ|x⟩|ax mod N⟩; os valores do registrador de trabalho o partem em r pentes aritméticos, e a QFT⁻¹ de cada pente é uma FFT de tamanho M. O site calcula as amplitudes exatas assim, em O(r·M·log M) — sem aproximações e sem fingir: é a mesma álgebra do circuito, pelo atalho que a estrutura dele permite.

Circuitos no hardware. Construídos e validados com Qiskit contra a distribuição teórica, transpilados offline para as portas nativas do Heron (cz, rz, sx, x) e submetidos por um Cloudflare Worker via API REST da IBM Quantum — plano Open, 10 minutos de QPU por mês, compartilhados com o Sorteio Quântico. O circuito genérico segue S. Beauregard, Circuit for Shor's algorithm using 2n+3 qubits (quant-ph/0205095); o experimento de referência sobre fatorar 15, 21 e 35 em hardware IBM é Amico, Saleem & Kumph (arXiv:1903.00768); a crítica clássica aos circuitos compilados é Smolin, Smith & Vargo, Oversimplifying quantum factoring (arXiv:1301.7007).

Nenhum cookie, nenhum rastreador. Os dados de hardware exibidos são contagens brutas de medição, sem pós-seleção.