OLIVEIRA, J. L. de. Ferramentas algébricas para o estudo do entrelaçamento quântico. 2012. 161 f. Tese (Doutorado em Engenharia de Teleinformática) - Centro de Tecnologia, Universidade Federal do Ceará, Fortaleza, 2012. / Submitted by Marlene Sousa (mmarlene@ufc.br) on 2012-09-17T18:15:06Z No. of bitstreams: 1 2012_tese_jloliveira.pdf: 3295719 bytes, checksum: 9042d05fda7d62b4a69031eeb251a49c (MD5) / Approved for entry into archive by Marlene Sousa(mmarlene@ufc.br) on 2012-09-25T19:23:18Z (GMT) No. of bitstreams: 1 2012_tese_jloliveira.pdf: 3295719 bytes, checksum: 9042d05fda7d62b4a69031eeb251a49c (MD5) / Made available in DSpace on 2012-09-25T19:23:18Z (GMT). No. of bitstreams: 1 2012_tese_jloliveira.pdf: 3295719 bytes, checksum: 9042d05fda7d62b4a69031eeb251a49c (MD5) Previous issue date: 2012-03 / This thesis presents some results about two important subjects of the quantum information theory: quantum entanglement and quantum algorithms. Regarding the entanglement, a relationship between negativity and minors principals of Hermitian matrices was stablished, allowing the analysis of the entanglement of two qubits states, three and four qubits pure states, using the minors principals. It was also proposed a new measure, using negativity, for calculating the entanglement of pure states of six qubits. Finally, with respect to quantum algorithms it was proposed a quantum search algorithm able to finding the minimum of a function by performing only one measurement. The algorithm is described and an example of its usage in the calculation of the period of a periodic function is presented. / Esta tese apresenta alguns resultados sobre dois temas importantes para a teoria da informação quântica: entrelaçamento quântico e algoritmos quânticos. Com respeito ao entrelaçamento, é estabelecida uma relação entre a negatividade e os menores principais de matrizes Hermitianas, o que permite analisar o entrelaçamento para estados de dois qubits e estados puros de três e quatro qubits, usando os menores principais. Foi proposta também uma nova medida para o cálculo do entrelaçamento de estados puros de seis qubits, usando a negatividade. Para ambos os casos, o cálculo da variação do entrelaçamento de estados parametrizados foi realizado através de fórmulas analíticas e simulações numéricas. Por fim, com relação aos algoritmos quânticos é proposto um algoritmo de busca capaz de achar o mínimo de uma função realizando apenas uma medição ao final do algoritmo. O algoritmo é descrito e um exemplo de utilização do mesmo no cálculo do período de uma função periódica é apresentado.

Made available in DSpace on 2015-03-04T18:50:39Z (GMT). No. of bitstreams: 1 Apresentacao.pdf: 66215 bytes, checksum: 0f29cb361f1c311758185ca4e078e552 (MD5) Previous issue date: 2006-10-26 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / Descrevemos a transformada de Fourier em grupos não abelianos motivado por suas aplicações em algoritmos quânticos para a computação quântica. A transformada de Fourier em grupos é descrita em termos das representações irredutíveis da teoria da representação de grupos finitos. Essa teoria é a peça chave para atacar o famoso Problema do Subgrupo Escondido (PSE), que consiste na determinação de geradores de um subgrupo, uma vez dado um oráculo que diz se um elemento pertence ou não a esse subgrupo. Neste trabalho, nós apresentamos um algoritmo quântico para o PSE Diedral (DN). A complexidade de tempo do nosso algoritmo é O( N log2 N ). Ele é baseado no método padrão de solução: a transformada de Fourier de um estado quântico |ψ é calculada e medida. O objetivo do nosso algoritmo é reconstruir o subgrupo H de DN gerado por uma reflexão, uma vez dado uma função f em DN, constante nas classes laterais de H e distinta em cada classe lateral.

Made available in DSpace on 2015-03-04T18:50:13Z (GMT). No. of bitstreams: 1 Apresentacao.pdf: 108219 bytes, checksum: 5d45885c1cb3a3bd5830f6b0e8711721 (MD5) Previous issue date: 2006-03-23 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Main memory limitations can lower the performance of segmentation applications for large images or even make it undoable. In this work we integrate the T-Surfaces model and Out-of-Core isosurface generation methods in a general framework for segmentation of large image volumes. T-Surfaces is a parametric deformable model based on a triangulation of the image domain, a discrete surface model and an image threshold. Isosurface generation techniques have been implemented through an Out-of-Core method that uses a kd-tree structure, called Meta-Cell technique. By using the Meta-Cell framework, we present an Out-of-Core version of a segmentation method based on T-Surfaces and isosurface extraction. The Gradient Vector Flow (GVF) is an approach based on Partial Differential Equations. This method has been applied together with snake models for image segmentation through boundary extraction. The key idea is to use a diffusion-reaction PDE in order to generate a new external force field that makes snake models less sensitivity to initialization as well as improves the snakes ability to move into boundary concavities. In this work, we firstly review basic results about global optimization conditions of the GVF and numerical considerations of usual GVF schemes. Besides, we present an analytical analysis of the GVF and a frequency domain analysis, which gives elements to discuss the dependency from the parameter values. Also, we discuss the numerical solution of the GVF based in a SOR method. We observe that the model can be used for Multiply Connected Domains and applied an image processing approach in order to increase the GVF efficiency. / Limitações de memória principal podem diminuir a performance de aplicativos de segmentação de imagens para grandes volumes ou mesmo impedir seu funcionamento. Nesse trabalho nós integramos o modelo das T-Superfícies com um método de extração de iso-superfícies Out-of-Core formando um esquema de segmentação para imagens de grande volume. A T-Superficie é um modelo deformável paramétrico baseado em uma triangulação do domínio da imagem, um modelo discreto de superfície e um threshold da imagem. Técnicas de extração de isso-superfícies foram implementadas usando o método Out-of-Core que usa estruturas kd-tree, chamadas técnicas de Meta-Células. Usando essas técnicas, apresentamos uma versão Out-of-Core de um método de segmentação baseado nas T-Superfícies e em iso-superfícies. O fluxo do Vetor Gradiente (GVF) é um campo vetorial baseado em equações diferenciais parciais. Esse método é aplicado em conjunto com o modelo das Snakes para segmentação de imagens através de extração de contorno. A idéia principal é usar uma equação de difusão-reação para gerar um novo campo de força externa que deixa o modelo menos sensível a inicialização e melhora a habilidade das Snakes para extrair bordas com concavidades acentuadas. Nesse trabalho, primeiramente serão revistos resultados sobre condições de otimização global do GVF e feitas algumas considerações numéricas. Além disso, serão apresentadas uma análise analítica do GVF e uma análise no domínio da frequência, as quais oferecem elementos para discutir a dependência dos parâmetros do modelo. Ainda, será discutida a solução numérica do GVF baseada no método de SOR. Observamos também que o modelo pode ser estendido para Domínios Multiplamente Conexos e aplicamos uma metodologia de pré-processamento que pode tornar mais eficiente o método.

A Computação Quântica é uma área de pesquisa científica onde a teoria da Mecânica Quântica é usada para descrever um conceito mais geral que o da Máquina Universal de Turing clássica. esta abordagem permite o desenvolvimento de algoritmos que podem ser consideravelmente mais rápidos que suas contrapartidas clássicas. Todos os algoritmos quânticos conhecidos até hoje que são exponencialmente mais rápidos que seus correspondentes clássicos utilizam a transformada de Fourier Quântica (QFT) em alguma parte. Nesta dissertação, as versões exata e aproximada da QFT são construídas usando uma abordagem que generaliza o resultado fundamental de Coppersmith. O processo inicia com a representação matricial genérica da Transformada de Fourier Rápida (FFT) clássica, como descrita por Knuth, seguida por sua decomposição em termos de operadores quânticos universais. Tal decomposição também é alcançada por meio de uma abordagem recursiva. A simulação de computadores quânticos também é discutida. Experimentos computacionais são realizados com o objetivo de simular a QFT Aproximada sobre estados da base computacional e gatos de Schrödinger, e com diferentes níveis de aproximação. A qualidade das soluções e a complexidade computacional são estudadas, levando a resultados consistentes com a teoria.

Descrevemos a transformada de Fourier em grupos não abelianos motivado por suas aplicações em algoritmos quânticos para a computação quântica. A transformada de Fourier em grupos é descrita em termos das representações irredutíveis da teoria da representação de grupos finitos. Essa teoria é a peça chave para atacar o famoso Problema do Subgrupo Escondido (PSE), que consiste na determinação de geradores de um subgrupo, uma vez dado um oráculo que diz se um elemento pertence ou não a esse subgrupo. Neste trabalho, nós apresentamos um algoritmo quântico para o PSE Diedral (DN). A complexidade de tempo do nosso algoritmo é O( N log2 N ). Ele é baseado no método padrão de solução: a transformada de Fourier de um estado quântico |ψ é calculada e medida. O objetivo do nosso algoritmo é reconstruir o subgrupo H de DN gerado por uma reflexão, uma vez dado uma função f em DN, constante nas classes laterais de H e distinta em cada classe lateral.

Caminhos aleatórios clássicos são essenciais para a Física, a Matemática, a Ciência da Computação e muitas outras áreas. Há uma grande expectativa que a sua versão quântica seja ainda mais poderosa, uma vez que o caminhante quântico se espalha quadraticamente mais rápido que o seu análogo clássico. Neste trabalho, estudamos o comportamento do caminhante quântico em uma e duas dimensões, além de generalizarmos o formalismo de ligações interrompidas para duas ou mais dimensões. Em uma dimensão, analisamos o comportamento do caminhante quântico, que além das duas possibilidades de deslocamento usuais, direita e esquerda, também permanece na posição atual. Em duas dimensões, apresentamos um estudo detalhado do comportamento do caminhante no plano e quando há descoerência gerada pela quebra aleatória das ligações para as posições vizinhas com uma certa probabilidade para cada uma das direções. Quando essa probabilidade de quebra é diferente nas duas direções encontramos um resultado não trivial que representa uma transição do caso 2-D descorente para o caso 1-D coerente. Também utilizamos o formalismo de ligações interrompidas para modelar o comportamento de um caminhante quântico que passa por uma e por duas fendas. Realizamos simulações com com as principais moedas e observamos conclusivamente os padrões de interferência e difração.

Computadores quânticos prometem resolver certos problemas assintoticamente mais rápido do que os computadores clássicos. Algoritmos quânticos, como o algoritmo de Shor, podem ser considerados casos particulares do chamado Problema do Subgrupo Oculto(PSO). O PSO consiste em encontrar um subgrupo H de um grupo G por meio de avaliações de uma função f que é constante em classes laterais de H e distinta em classes laterais diferentes. O PSO em grupos abelianos é resolvido eficientemente em um computador quântico, mas será que os computadores quânticos podem resolver o PSO em grupos não abelianos? Esta questão tem sido discutida regularmente pela comunidade científica devido a importantes aplicações, como é o caso do problema de isomorfismo de grafos e do problema do menor vetor em um reticulado. Nesta dissertação é feita uma revisão do trabalho de Ivanyos et al. (2007a), o qual apresenta uma solução para o PSO em grupos nilpotentes de classe 2. Com esta finalidade, é elaborada uma breve revisão sobre a Computação Quântica; são mostradas algumas características dos grupos nilpotentes e dos grupos solúveis, dando uma atenção especial aos grupos nilpotentes de classe 2; é exposto o método padrão de solução do PSO em grupos abelianos; também são exibidas as principais características de sequencias policıclicas e reduçõesde grupos nilpotentes usando as propriedades de sequencias policıclicas / Quantum computers may solve certain problems asymptotically faster than the classical computers. Quantum algorithms, such as Shors algorithm, may be considered as a particular case of the Hidden Subgroup Problem (HSP). The HSP consists in finding a subgroup H of a group G by evaluating a function f, which is constant in cosets of H and distinct for each coset. The HSP for Abelian groups is efficiently solved in a quantum computer, but is quantum computers can solve the HSP in non-Abelian groups efficiently? This question has been regularly discussed by the scientific community due to the importance of some applications, such as the graph isomorphism problem and the short vector in a lattice. In this dissertation we review the Ivanyos et al. (2007a) that address HSP in nilpotent groups of class 2. We make a brief review on Quantum Computing; we address some characteristics of nilpotent groups and solvable groups, with special attention to nilpotent groups of class 2; we discuss the standard method of solution of the HSP in Abelian groups; we present the main characteristics of the polycyclic sequences and important reductions of the HSP in classes of nilpotent groups using the properties of polycyclic sequences. Finally, we present an efficient algorithm to solve the HSP in nilpotent groups of class 2.

Made available in DSpace on 2015-03-04T18:50:52Z (GMT). No. of bitstreams: 1 thesis.pdf: 6097890 bytes, checksum: 7eea019378a8126c37befefac84557cb (MD5) Previous issue date: 2007-06-15 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Caminhos aleatórios clássicos são essenciais para a Física, a Matemática, a Ciência da Computação e muitas outras áreas. Há uma grande expectativa que a sua versão quântica seja ainda mais poderosa, uma vez que o caminhante quântico se espalha quadraticamente mais rápido que o seu análogo clássico. Neste trabalho, estudamos o comportamento do caminhante quântico em uma e duas dimensões, além de generalizarmos o formalismo de ligações interrompidas para duas ou mais dimensões. Em uma dimensão, analisamos o comportamento do caminhante quântico, que além das duas possibilidades de deslocamento usuais, direita e esquerda, também permanece na posição atual. Em duas dimensões, apresentamos um estudo detalhado do comportamento do caminhante no plano e quando há descoerência gerada pela quebra aleatória das ligações para as posições vizinhas com uma certa probabilidade para cada uma das direções. Quando essa probabilidade de quebra é diferente nas duas direções encontramos um resultado não trivial que representa uma transição do caso 2-D descorente para o caso 1-D coerente. Também utilizamos o formalismo de ligações interrompidas para modelar o comportamento de um caminhante quântico que passa por uma e por duas fendas. Realizamos simulações com com as principais moedas e observamos conclusivamente os padrões de interferência e difração.

Made available in DSpace on 2015-03-04T18:50:59Z (GMT). No. of bitstreams: 1 thesis.pdf: 520664 bytes, checksum: a8423486c7ffd3a3ceff9cb2b60761ce (MD5) Previous issue date: 2008-03-14 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs. / O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.

Made available in DSpace on 2015-03-04T18:50:59Z (GMT). No. of bitstreams: 1 Thesis_Tharso_Dominisini_Fernandes_2008.pdf: 433414 bytes, checksum: 974d6b0bd3b829341f4f36f9c8d29a72 (MD5) Previous issue date: 2008-03-13 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Quantum computers may solve certain problems asymptotically faster than the classical computers. Quantum algorithms, such as Shor s algorithm, may be considered as a particular case of the Hidden Subgroup Problem (HSP). The HSP consists in finding a subgroup H of a group G by evaluating a function f, which is constant in cosets of H and distinct for each coset. The HSP for Abelian groups is efficiently solved in a quantum computer, but is quantum computers can solve the HSP in non-Abelian groups efficiently? This question has been regularly discussed by the scientific community due to the importance of some applications, such as the graph isomorphism problem and the short vector in a lattice. In this dissertation we review the Ivanyos et al. (2007a) that address HSP in nilpotent groups of class 2. We make a brief review on Quantum Computing; we address some characteristics of nilpotent groups and solvable groups, with special attention to nilpotent groups of class 2; we discuss the standard method of solution of the HSP in Abelian groups; we present the main characteristics of the polycyclic sequences and important reductions of the HSP in classes of nilpotent groups using the properties of polycyclic sequences. Finally, we present an efficient algorithm to solve the HSP in nilpotent groups of class 2. / Computadores quânticos prometem resolver certos problemas assintoticamente mais rápido do que os computadores clássicos. Algoritmos quânticos, como o algoritmo de Shor, podem ser considerados casos particulares do chamado Problema do Subgrupo Oculto(PSO). O PSO consiste em encontrar um subgrupo H de um grupo G por meio de avaliações de uma função f que é constante em classes laterais de H e distinta em classes laterais diferentes. O PSO em grupos abelianos é resolvido eficientemente em um computador quântico, mas será que os computadores quânticos podem resolver o PSO em grupos não abelianos? Esta questão tem sido discutida regularmente pela comunidade científica devido a importantes aplicações, como é o caso do problema de isomorfismo de grafos e do problema do menor vetor em um reticulado. Nesta dissertação é feita uma revisão do trabalho de Ivanyos et al. (2007a), o qual apresenta uma solução para o PSO em grupos nilpotentes de classe 2. Com esta finalidade, é elaborada uma breve revisão sobre a Computação Quântica; são mostradas algumas características dos grupos nilpotentes e dos grupos solúveis, dando uma atenção especial aos grupos nilpotentes de classe 2; é exposto o método padrão de solução do PSO em grupos abelianos; também são exibidas as principais características de sequencias policıclicas e reduções¸de grupos nilpotentes usando as propriedades de sequencias policıclicas