Construção de Algoritmos Reversíveis e Quânticos

Este trabalho consiste na proposta de algoritmos aritméticos reversíveis e algoritmos quânticos para problemas de otimização combinatória. Ambos os tipos podem ser utilizados na construção de outros circuitos e algoritmos. Mostramos como implementar circuitos reversíveis para operações aritméticas, tais como multiplicação e divisão de inteiros não-negativos, que podem ser utilizados para operações quânticas com ambos operandos em superposição. Em particular, são propostas versões reversíveis do algoritmo de multiplicação Karatsuba, com procedimento de limpeza de lixo recursivo. Propomos um algoritmo quântico, denominado Medida-Linear, para encontrar um valor ótimo (máximo ou mínimo) em uma lista não-ordenada.