Algoritmos e complexidade no modelo de computação quântica

Abstract

Nesta tese estudam-se as implicações da introdução no modelo de Computação Quântica do conceito de Sistema de Representação Redundante, em particular no que concerne à eficiência de Algoritmos para Aritmética. Têm vindo a ser apresentadas diversas considerações favoráveis sobre a exequibilidade de modelos de Computação Quântica em que a unidade de informação, o qudit, admite mais do que os dois níveis distintos proporcionados pelo qubit. O problema da equivalência, ou não, em termos de Complexidade Computacional entre modelos baseados em qubits e aqueles baseados em qudits encontra-se apenas parcialmente resolvido. A análise da Complexidade Computacional de modelos em que se consideram misturas de diferentes unidades de informação, denominados Sistemas Quânticos Híbridos, é uma área praticamente inexplorada. Assim, propõe-se um modelo formal para Computação Quântica nestes sistemas híbridos, generalizando, por inclusão, os modelos baseados em qubits e qudits. Com base no modelo proposto, desenvolvem-se duas classes de circuitos quânticos, com profundidade constante, para a adição das representações de dois números num qualquer sistema redundante. Estabelecem-se ainda condições para a aplicação de um algoritmo de adição, em tempo constante, de um número polinomial de representações redundantes de números. Como consequência, justifica-se a existência de classes de circuitos quânticos, com profundidade constante, para aproximar a soma de um número polinomial de representações redundantes. Por fim, descrevem-se as principais características de um Simulador Simbólico para Algoritmos em Computação Quântica, seguindo-se uma análise de resultados obtidos em simulações do algoritmo de Grover.

In this thesis we study the effect of merging the concept of Redundant Number Systems with Quantum Computation, manly with respect to Quantum Arithmetic Algorithms. Several favorable opinions have been advanced on the feasibility of Quantum Computation models where the unit of information, the qudit, has more than the two levels provided by the qubit. However, the equivalence between this model and the qubit based one is only partially established. The Computational Complexity analysis of Hybrid Quantum Computation models where mixtures of several, distinct, units of information coexist has just started. We propose a new and general formal model for Quantum Computation with Hybrid Quantum Systems, generalizing, by inclusion, all the above mentioned models. Based on this model, we report two classes of constant depth quantum circuits for the addition of two numbers in redundant number systems. Also, we derive conditions for the feasibility of addition, in constant time, of a polynomial number of numbers (represented in any redundant number system) and justify the existence of constant depth quantum circuits for approximating the sum of a polynomial number of numbers. Finally, we report the development of a Symbolic Quantum Computer Simulator and discuss the time-results of the simulation of Grover’s algorithm.