Factoring Fermat-prime Products with Explicit Modular Exponentiation on IBM Quantum
Resumo:
Esta dissertação investiga uma implementação de referência da rotina de busca da ordem do algoritmo de Shor em processadores quânticos supercondutores da IBM disponíveis atualmente, enfrentando o desafio prático imposto pela profundidade e pela sensibilidade ao ruído da exponenciação modular explícita na era NISQ. O trabalho tem como objetivo oferecer uma implementação transparente e reprodutível que preserve a estrutura didática de estimação de fase com leitura da transformada quântica de Fourier inversa, evitando atalhos compilados que codificam implicitamente a resposta. A metodologia implementa a exponenciação modular como uma sequência explícita de multiplicações modulares controladas, explora regularidades aritméticas em uma família estruturada de módulos formada por produtos de primos de Fermat para omitir blocos de identidade e realizar multiplicações simples associadas a potências de dois por meio de permutações controladas de bits e operações multi-controladas, e avalia as saídas experimentais pela comparação entre histogramas medidos no registrador de fase e a execução ideal de determinação de ordem, quantificando a concordância por meio da fidelidade de Hellinger. Como contribuição, a dissertação estabelece um pipeline padronizado de experimentação e uma apresentação de métricas e recursos incluindo profundidade e contagem de portas antes e após a transpilação em diferentes backends, permitindo comparações consistentes sob restrições realistas de compilação. Os resultados para as instâncias 51, 85, 255 e 771 indicam alta concordância em nível de distribuição para os menores módulos e degradação para o maior módulo, em consonância com o aumento da profundidade compilada e do volume de portas, bem como com a variabilidade entre processadores.
Abstract:
This dissertation investigates a baseline implementation of Shor’s order-finding routine on current IBM superconducting quantum hardware, addressing the practical challenge posed by the depth and noise sensitivity of explicit modular exponentiation in the NISQ era. The objective is to provide a transparent and reproducible reference implementation that preserves the textbook structure of phase estimation with inverse quantum Fourier transform readout while avoiding compiled shortcuts that implicitly encode the answer. The methodology implements modular exponentiation explicitly as a sequence of controlled modular multiplications, exploits arithmetic regularities in a structured family of moduli formed by products of Fermat primes to omit identity blocks and realize lightweight power-of-two multipliers through controlled bit permutations and multi-controlled operations, and evaluates experimental outputs by comparing measured phase-register histograms with the ideal analytic order-finding signature using Hellinger fidelity. The dissertation contributes a standardized experimental pipeline and resource reporting framework, including circuit depth and gate counts before and after transpilation across multiple IBM backends, enabling consistent comparison under realistic compilation constraints. The results for the instances 51, 85, 255, and 771 show high distribution-level agreement for the smaller moduli and a degradation for the largest modulus, consistent with the increased compiled depth and gate volume and with variability across backends.
Banca examinadora:
Prof. Luis Antonio Brasil Kowada, UFF
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Franklin de Lima Marquezino, UFRJ