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 em uma lista não-ordenada. Para uma lista com N elementos, são feitas 8,27 N^0,5 chamadas do oráculo, a fim de obter pelo menos 50% de chance de sucesso. O algoritmo quântico mais eficiente que existe atualmente, DH96, realiza a mesma tarefa com 22,5 N^0,5 chamadas do oráculo. Além do mais, o nosso algoritmo Medida-Linear necessita de O(n) medições em contraposição às O(n^2) medições do DH96, onde n é a quantidade de bits necessária para representar o tamanho da lista. Propomos também um operador quântico que permite adaptar o DH96 e o algoritmo Medida-Linear para resolver problemas de otimização combinatória.

Foram realizadas simulações comparando os algoritmos acima descritos para encontrar o menor elemento de uma lista ou retornado por uma função. A comparação foi feita principalmente sobre o número de consultas à lista e a quantidade de medições realizadas. Em todas as simulações, o algoritmo Medida-Linear teve desempenho superior ao DH96, confirmando também a análise teórica de que o algoritmo Medida-Linear necessita de uma quantidade linear de medições dos resultados parciais enquanto que o algoritmo DH96 necessita de uma quantidade quadrática destas medições.