Defesa de Tese de Doutorado de Raphael Bernardino Ferreira Lima – 17/01/2025, 10h30, na sala 310 do Instituto de Computação e por videoconferência

Defesa de Tese de Doutorado de Raphael Bernardino Ferreira Lima – 17/01/2025, 10h30, na sala 310 do Instituto de Computação e por videoconferência

Link para defesa: https://meet.google.com/ico-xpgb-rme

Algoritmo de Pós-Síntese Adaptativo para Circuitos Reversíveis

Resumo:

O avanço acelerado da computação nas últimas décadas gerou diversos problemas como o superaquecimento e ineficiência energética. Esse paradigma tradicional computacional continua sendo utilizado de forma abrangente. Novos paradigmas, como computação reversível, foram criados com o intuito de resolver tais problemas, porém ainda são recentes e demandam que mais pesquisas sejam feitas. Em paralelo à computação convencional, também conhecida como clássica, surgiu a computação quântica que permite, ao menos teoricamente, resolver alguns problemas de forma mais rápida. A computação quântica é inerentemente reversível. O desconhecimento de circuitos quânticos eficientes prejudica a evolução computacional nesses paradigmas. Este trabalho tem como intuito auxiliar no avanço da elaboração e otimização de circuitos reversíveis. Para isso, propomos um algoritmo que, dado um circuito reversível, encontra um circuito melhor e equivalente ao original. O nosso algoritmo consegue minimizar cerca de 60\% das funções apresentadas na literatura e \textit{benchmarks}, como os existentes no RevLib. O algoritmo proposto combina três abordagens: regras de minimização, circuitos exatos, e análise espectral baseada no algoritmo de Reed-Muller. Por fim, adicionamos na literatura uma visão mais aprofundada a respeito da síntese de circuitos utilizando o espectro de Reed-Muller, transformações unitárias, sistemas lineares, e baseados em permutação.

Abstract:

The rapid advancement of computing in recent decades has led to various challenges, such as overheating and energy inefficiency. This classical computational paradigm remains widely used. However, new paradigms, like reversible and quantum computing, have emerged to address these issues, though they are still recent and require further research. The lack of efficient quantum circuit designs hampers progress in these new paradigms. This work aims to contribute in the development and optimization of reversible circuits. We propose an algorithm that finds an improved version of a given reversible circuit. Our algorithm is able to minimize, approximately, 60\% of the functions found in the literature and benchmarks, such as those in RevLib. The proposed algorithm combines three approaches: minimization rules, exact circuits, and spectral analysis based on the Reed-Muller algorithm. Finally, we present a perspective regarding the circuit synthesis using the Reed-Muller spectrum, unitary transformations, linear systems, and permutation-based techniques.

Banca  examinadora:

Prof. Luis Antonio Brasil Kowada, UFF – Presidente

Prof. Fábio Protti, UFF

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

Profa. Celina Miraglia Herrera de Figueiredo, UFRJ

Prof. Franklin de Lima Marquezino, UFRJ