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.
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.
3 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.
4 O algoritmo de Shor, ao vivo
Escolha um número e aperte rodar. O circuito prepara todos os expoentes ao mesmo tempo, calcula ax mod N de uma só vez, e a QFT⁻¹ faz os caminhos errados se cancelarem — sobra o período, e do período saem os fatores. A simulação é exata e mede sozinha quantas vezes precisar.
ver como tabela
5 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.
E um circuito sem atalhos? Afoga — nós testamos
Os três circuitos acima são compilados: usam a estrutura de cada N para caber no hardware de hoje — como toda "fatoração quântica" já demonstrada. Para medir o tamanho dessa concessão, rodamos como controle o circuito genérico de Beauregard para o mesmo N=15, o que uma fatoração cega exigiria: 14 qubits e 12.428 portas de 2 qubits.
Cada porta acerta ~99,7% das vezes, e fidelidades se multiplicam: com 83 portas (0,99783 ≈ 78%) os picos ficam de pé; com 12.428 (0,99712428 ≈ 10−17) sobra ruído puro. Foi o que o hardware devolveu: 14% dos shots em k "bom", contra 13% do chute cego — um histograma chapado que não sabe que 15 = 3 × 5 (job da2jovuaa69c739hjfeg, ibm_fez). É 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.
6 "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 experimento de controle 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.