Otimizando o Algoritmo Quântico de Fatoração do Shor com Uso de Reticulado 

Será defendida no dia 6 de julho de 2026, às 11:00 horas, na sala 213 do Instituto de Computação e por videoconferência, a Tese de Doutorado intitulada “Otimizando o Algoritmo Quântico de Fatoração do Shor com Uso de Reticulado”, do candidato ao título de Doutor em Computação – Fábio Gomes dos Santos.

Link para defesa: https://calendar.app.google/q6QQU9hBAJB8XW127

Resumo:

Os algoritmos de Shor representam um dos principais avanços da computação quântica ao demonstrar que a fatoração de inteiros e o cálculo de logaritmos discretos podem ser realizados em tempo polinomial, ameaçando a segurança de sistemas criptográficos amplamente utilizados, como RSA e ECDSA. Apesar de seu impacto teórico, a execução prática do algoritmo em larga escala ainda é inviável, principalmente devido às limitações do hardware quântico atual, incluindo ruído, necessidade de correção de erros e elevado custo em número de qubits. Além disso, a simulação clássica do algoritmo enfrenta desafios significativos relacionados ao consumo exponencial de memória e processamento.

Neste trabalho, investigamos melhorias no algoritmo de Shor com foco na redução dos requisitos de hardware, particularmente no número de qubits necessários. Propomos uma abordagem baseada em técnicas de reticulados no pós-processamento, permitindo a recuperação da ordem a partir de múltiplas execuções da versão original do algoritmo. Essa estratégia estabelece um trade-off entre a redução de recursos quânticos e o aumento

no número de execuções.

Adicionalmente, desenvolvemos um simulador para o problema da fatoração, possibilitando a análise do comportamento do algoritmo em diferentes cenários e a validação das otimizações propostas. Os resultados obtidos indicam que é possível reduzir significativamente os requisitos de hardware sem comprometer a corretude do algoritmo, contribuindo para aproximar sua implementação prática em dispositivos quânticos reais.

Abstract:

Shor’s algorithm represents a major breakthrough in quantum computing by demonstrating that integer factorization and discrete logarithms can be solved in polynomial time, thereby threatening widely used cryptographic systems such as RSA and ECDSA. Despite its theoretical impact, the practical execution of the algorithm at scale remains infeasible, primarily due to limitations of current quantum hardware, including noise, the need for error correction, and the high cost in terms of qubit resources. Additionally, classical simulation of the algorithm faces significant challenges related to exponential memory and computational requirements.

In this work, we investigate improvements to Shor’s algorithm with a focus on reducing hardware requirements, particularly the number of qubits. We propose an approach based on lattice techniques in the post-processing stage, enabling order recovery from multiple executions of the original version of the algorithm. This strategy introduces a trade-off between reduced quantum resources and an increased number of executions.

Furthermore, we develop a simulator for the integer factorization problem, allowing us to analyze the behavior of the algorithm under different scenarios and to validate the proposed optimizations. The results indicate that it is possible to significantly reduce hardware requirements without compromising correctness, contributing toward the practical realization of quantum factoring on real devices.

Banca  examinadora:

Prof. Luis Antonio Brasil Kowada, UFF – Presidente

Prof. Luís Felipe Ignácio Cunha, UFF

Profa. Celina Miraglia Herrera de Figueiredo, UFRJ

Prof. Franklin de Lima Marquezino, UFRJ 

Prof. Daniel Chicayban Bastos, UFRJ