Can PCE solve the factorisation problem via optimisation?

Resumo Técnico: Pode o PCE Resolver o Problema da Fatoração via Otimização?

Enunciado do Problema
A fatoração de inteiros, particularmente de números semiprimos ($N = p \cdot q$), é um problema fundamental na teoria dos números computacional e a base de segurança para a criptografia RSA. Embora o algoritmo de Shor ofereça uma solução quântica de tempo polinomial, o hardware atual de Escala Intermediária com Ruído (NISQ) carece da contagem de qubits e da coerência necessárias para uma implementação prática. Abordagens alternativas, como os Algoritmos Quânticos Variacionais (VQAs) que convertem a fatoração em problemas de otimização binária, enfrentam problemas de escalabilidade, tipicamente exigindo um número de qubits que escala linearmente com o número de variáveis binárias. Essa escala linear torna-os inviáveis para instâncias de grande escala no hardware atual. O artigo investiga se a Codificação de Correlação de Pauli (PCE - Pauli Correlation Encoding), um framework capaz de codificar $m$ variáveis binárias usando um número polinomial de qubits ($n \ll m$), pode ser adaptada para resolver o problema da fatoração via otimização com recursos limitados.

Metodologia
O estudo reformula o problema da fatoração como uma tarefa de otimização binária e aplica o PCE para reduzir os requisitos de qubits. A metodologia envolve:

1. Estratégias de Codificação: Duas abordagens distintas foram desenvolvidas para mapear as restrições de fatoração em uma função de custo:
   • Abordagem Básica: Codifica diretamente as representações binárias dos fatores desconhecidos $p$ e $q$. A função de custo minimiza a distância de Hamming ao quadrado entre o inteiro alvo $N$ e o produto candidato $x_p \cdot x_q$, com penalidades para evitar soluções triviais (ex: $N \cdot 1$).
   • Abordagem da Diferença de Dois Quadrados (DoTS - Difference of Two Squares): Reformula o problema como a busca por inteiros $a$ e $b$ tais que $a^2 \equiv b^2 \pmod N$ (com $a \not\equiv \pm b$). Os fatores são recuperados via $\gcd(a-b, N)$ e $\gcd(a+b, N)$. A função de custo combina um termo que impõe a congruência modular com um termo que verifica a fatoração resultante.
2. Circuito Quântico: Um ansatz "brickwork" eficiente em hardware foi empregado, consistindo em camadas alternadas de rotações de um único qubit ($R_X, R_Y, R_Z$) e portas de emaranhamento ($R_{XX}, R_{YY}, R_{ZZ}$). A ordem de compressão PCE $k$ determina a profundidade do circuito e o número de qubits necessários ($n \approx m/k$).
3. Otimização: Os circuitos quânticos parametrizados foram simulados classicamente usando Qiskit Aer. A otimização foi realizada utilizando três algoritmos livres de gradiente: Evolução Diferencial (DE), Otimização por Enxame de Partículas (PSO) e Otimização por Enxame de Partículas Delta Quântica (QDPSO). A função sinal foi utilizada para aproximar as variáveis binárias, evitando a relaxação de tangente hiperbólica para prevenir soluções reais infinitas.

Principais Contribuições e Resultados

• Redução de Recursos: O estudo demonstra que o PCE pode reduzir drasticamente o número de qubits necessários para a fatoração. Para comprimentos de chave RSA típicos, os qubits necessários permanecem dentro de uma faixa "acessível" para o hardware atual ou de curto prazo, e para ordens de compressão $k > 2$, o problema pode ser resolvido inteiramente em computadores clássicos via emulação de circuito quântico.
• Comparação de Desempenho:
  • DoTS vs. Básica: A abordagem DoTS superou consistentemente a abordagem Básica. A função de custo DoTS, que captura a estrutura aritmética da relação de diferença de quadrados, rendeu taxas de sucesso mais altas e um cenário de otimização mais favorável.
  • Sensibilidade do Otimizador: A Evolução Diferencial (DE) provou ser o otimizador mais robusto, alcançando fatorações bem-sucedidas através de vários comprimentos de bits. Métodos baseados em enxame (PSO, QDPSO) exibiram taxas de sucesso significativamente menores, sugerindo que o cenário de otimização é desafiador para esses algoritmos específicos.
  • Limites de Escalabilidade: O método fatorou com sucesso semiprimos de até 36 bits usando a abordagem DoTS com $k=4$ e DE. As taxas de sucesso declinaram para inteiros maiores que 25–36 bits, indicando limitações intrínsecas nas formulações atuais das funções de custo para instâncias maiores.
• Eficiência de Busca: A análise do número de avaliações da função objetivo mostrou que o algoritmo não depende de exploração por força bruta. O número de avaliações permaneceu várias ordens de magnitude abaixo do tamanho do espaço de busca combinatória ($2^n$), indicando um processo de busca guiada.

Significância e Alegações
O artigo posiciona este trabalho como uma contribuição preliminar e exploratória, em vez de uma solução definitiva ou uma alegação de vantagem computacional sobre algoritmos existentes.

• Viabilidade: O principal achado é que os algoritmos baseados em PCE são um framework plausível para estudar a fatoração como um problema de otimização com recursos quânticos limitados. Oferece uma perspectiva alternativa aos métodos estabelecidos como VQF e QAOA ao desacoplar o número de variáveis do número de qubits.
• Limitações: Os autores declaram explicitamente que as formulações atuais não escalam com sucesso para tamanhos de inteiros criptograficamente relevantes (ex: RSA de 2048 bits). O sucesso do método é fortemente dependente do design da função de custo clássica e da escolha do otimizador.
• Direções Futuras: O estudo sugere que pesquisas futuras devem focar em:
  • Projetar funções de custo mais informativas que capturem melhor a estrutura aritmética da fatoração (potencialmente incorporando variáveis de transporte/carry).
  • Explorar suposições de fatores equilibrados (comuns em RSA) para reduzir a contagem de variáveis.
  • Investigar estratégias de warm-start e arquiteturas de ansatz alternativas.
  • Avaliar o desempenho sob modelos de ruído realistas.

Em conclusão, embora o método não ameace atualmente a segurança do RSA, ele estabelece um framework viável e eficiente em recursos para investigar a fatoração via otimização inspirada em computação quântica, justificando novas pesquisas em design de funções de custo e refinamentos algorítmicos.