Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique

Resumo Técnico: Identificação de Números Primos Demonstrada com Processadores Quânticos Usando uma Nova Técnica de Mitigação de Ruído Baseada em Redimensionamento

Enunciado do Problema
A identificação e classificação de números primos permanecem desafios fundamentais na teoria dos números, com implicações significativas para a criptografia e a complexidade computacional. Embora algoritmos clássicos tenham avançado, abordagens quânticas oferecem métodos alternativos ao codificar propriedades teórico-numéricas em observáveis quânticos. Especificamente, o algoritmo "Identificação de Primos via Dinâmica de Emaranhamento" (PIED), proposto anteriormente em trabalhos teóricos, associa a primalidade de um inteiro a assinaturas específicas no espectro de Fourier da pureza reduzida (emaranhamento) de um sistema quântico bipartite. No entanto, a transição deste algoritmo da simulação clássica para hardware real em dispositivos Quânticos de Escala Intermediária Ruidosa (NISQ) apresenta desafios significativos devido ao ruído experimental, que pode obscurecer as distinções sutis entre números primos e compostos nos modos de Fourier medidos.

Metodologia
Os autores implementaram o algoritmo PIED em processadores quânticos da IBM (especificamente o dispositivo Heron r2 "Aachen") para dimensões de sistema $d = 4, 8,$ e $16$. O protocolo envolve:

1. Configuração do Sistema: Um sistema bipartite $AB$ com subsistemas idênticos de dimensão $d$, evoluído sob um Hamiltoniano diagonal com níveis de energia uniformemente espaçados.
2. Preparação do Estado: O sistema é inicializado em um estado de superposição uniforme (preparado via portas Hadamard) e evoluído sob um operador unitário derivado do Hamiltoniano.
3. Medição: A pureza reduzida $\gamma_A(t)$ do subsistema $A$ é medida ao longo do tempo usando o protocolo de teste SWAP, que requer duas cópias idênticas do sistema e um qubit ancilla.
4. Extração do Sinal: A pureza dependente do tempo é transformada por Fourier para extrair modos $\alpha_n$. Teoricamente, números primos correspondem a valores mínimos desses modos, enquanto números compostos produzem valores maiores.

Para abordar o ruído do hardware, os autores desenvolveram e aplicaram uma técnica de Extrapolação de Fator de Correção (CFE). Este método envolve:

• Calibração: Realização de execuções de circuito para um subconjunto de dimensões de sistema ($d=4, 8, 16$) onde os valores analíticos ideais dos modos de Fourier são conhecidos.
• Otimização: Cálculo de um fator de redimensionamento global ótimo $\Lambda_{opt}(d)$ para cada dimensão, minimizando o desvio entre dados experimentais ruidosos e a referência analítica.
• Extrapolação: Ajuste de uma forma funcional aos valores calculados de $\Lambda_{opt}(d)$ (especificamente $\Lambda_{opt}(d) = \Lambda_0 + \kappa d^\eta$) para prever fatores de correção para outras configurações ou validar a tendência. Isso permite o redimensionamento dos modos de Fourier ruidosos para mitigar viés sistemático sem exigir múltiplas medições de níveis de ruído por instância de circuito (como na Extrapolação de Ruído Zero).

Principais Contribuições

1. Implementação em Hardware: A primeira demonstração do algoritmo PIED em hardware quântico real, transicionando com sucesso da simulação para dispositivos NISQ.
2. Estratégia de Mitigação de Ruído (CFE): A introdução de uma técnica de mitigação de erros baseada em redimensionamento, computacionalmente barata. Diferentemente de métodos tradicionais que exigem execuções repetidas de circuitos em níveis de ruído variados, a CFE aproveita o comportamento analítico conhecido do algoritmo em diferentes dimensões de sistema para construir um fator de correção.
3. Limites Teóricos Refinados: A derivação de um novo limite inferior analítico, $P_n$, para os modos de Fourier de números compostos (especificamente para inteiros da forma $n=k^2$ onde $k$ é primo). Este limite fornece uma separação mais rigorosa entre assinaturas de primos e compostos do que o limite trivial anteriormente conhecido $B_n$. Os autores identificaram rigorosamente que exceções a este limite ocorrem apenas para semiprimos específicos envolvendo fatores 2 e 3 dentro de certos subintervalos, permitindo um framework de classificação mais robusto.
4. Estados Iniciais Alternativos: Simulações numéricas explorando o uso de estados coerentes de spin como condições iniciais. Embora a preparação seja mais complexa, esses estados mostraram potencial para reduzir o número de partições de tempo necessárias para integração de Fourier precisa em comparação com estados de superposição uniforme.

Resultados

• Separação Primo/Composto: As implementações em hardware reproduziram com sucesso a tendência teórica onde números primos correspondem a valores mínimos de modos de Fourier. A aplicação do método CFE melhorou significativamente a concordância entre dados experimentais e previsões analíticas, restaurando efetivamente a separação entre assinaturas de primos e compostos que estava obscurecida pelo ruído nos dados brutos.
• Desempenho da CFE: O fator de correção $\Lambda_{opt}(d)$ mostrou-se aumentar monotonicamente com a dimensão $d$, saturando assintoticamente. Os dados redimensionados apresentaram excelente concordância com o modelo funcional proposto.
• Validação Teórica: O novo limite $P_n$ mostrou-se válido para a maioria dos números compostos. A análise confirmou que apenas semiprimos específicos (da forma $2k$ ou $3k$) poderiam produzir valores abaixo deste limite, necessitando de verificações de divisibilidade específicas nessas regiões.
• Estados Coerentes de Spin: Simulações indicaram que, embora estados coerentes de spin sejam mais difíceis de preparar, eles podem oferecer uma escalabilidade mais favorável para o número de amostras de tempo necessárias para integração de Fourier, potencialmente reduzindo a sobrecarga computacional.

Significado
O artigo afirma que esses resultados representam um passo em direção a aplicações práticas de teoria dos números em dispositivos NISQ. Ao validar o algoritmo PIED sob condições de hardware realistas e demonstrar uma estratégia especializada de mitigação de ruído de baixa sobrecarga (CFE), o trabalho destaca o potencial de combinar insights analíticos com implementações baseadas em hardware. Os autores enfatizam que sua abordagem oferece um caminho viável para extrair informações estruturadas de dinâmicas quânticas ruidosas, sugerindo aplicabilidade mais ampla a outros algoritmos quânticos que dependem de assinaturas espectrais de observáveis físicos. O trabalho não afirma resolver a fatoração de inteiros em grande escala, mas sim demonstra a viabilidade de identificar assinaturas de primos em sistemas quânticos de pequena escala usando dinâmica de emaranhamento.