| Resumo: | 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.
|
|---|