Construção de algoritmos reversíveis e quânticos - Kowada, Luis Antonio Brasil. (UFRJ, 2006)
[PT]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 operando em superposição. Em particular, são propostas versões reversíveis do algoritmo de multiplicação Karatsuba [18], 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 POT. ½' 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 [12], realiza a mesma tarefa com 22,5 'N POT. ½' chamadas do oráculo. Além do mais, o nosso algoritmo Medida-Linear necessita de Θ(n) medições em contraposição às Θ(n²) medições do DH96, onde n é a quantidade de bits necessária para representar o tamanho da lista. Propomos também um operador quânticoque permite adaptar o DH96 [12] 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.[EN]In this work, we propose reversible arithmetic algorithms and quantun algorithms for combinatorial optimization problems. Both types of algorithms can be used in the design of other circuits and algorithms. We show some reversible circuits for non-negative integer operations with both operands in state superposition. We propose reversible circuits for integer multiplication and division. Besides the naive circuit for integer multiplication, we develop some versions for Karatsuba algorithm [18]. We propose a quantum algorithm, denoted Medida-Linear, that makes 8.27 'N POT. ½' oracle calls for finding the smallest (or largest) value with 50% sucess in an unsorted list with N elements. The DH96 algorithm [12] is nowadays the most efficient quantum algorithm for solving this problem. It needs 22.5 'N POT. ½' oracle calls. Another difference is the number of measurements: Medida-Linear makes Θ(n) measurements and DH96 makes Θ(n²), where n is the number of bits needed to represent the list size. We simulated the above algorithms to find the smallest element of a list. A comparison was made considering the number of oracle calls in the list and the number of measurements. In all simulations, the performance of Medida-Linear was better than DH96. The simulations confirmed the linear complexity of measurements of Medida-Linear and the quadratic complexity of DH96.