Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/15246
Title: | Algoritmos e complexidade no modelo de computação quântica |
Author: | Pereira, António Ferreira |
Advisor: | Rodrigues, Maria Rosália Dinis |
Keywords: | Matemática Computação matemática Complexidade computacional Algoritmos |
Defense Date: | 2007 |
Publisher: | Universidade de Aveiro |
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. |
Description: | Doutoramento em Matemática |
URI: | http://hdl.handle.net/10773/15246 |
Appears in Collections: | UA - Teses de doutoramento DMat - Teses de doutoramento |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.