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.
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.
A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação.Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável.Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências.Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação.Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema.Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica.Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo.Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial.Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas.Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos.Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas.
Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p \rtimes Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(\sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é \Omega(\sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m \rtimes Z_p, com m, N inteiros positivos e N fatorado de forma especial.
Este trabalho apresenta alguns problemas matemáticos ligados à Mecânica Quântica e à Teoria de Números; mais precisamente, este trabalho apresenta três problemas: dois deles no contexto da Mecânica Quântica e o terceiro no âmbito da Teoria de Números. O primeiro problema, dentro do contexto da Mecânica Quântica, trata de determinar a geometria dos estados da esfera de Bloch que representem estados fisicamente realizáveis. Tal geometria herda uma simetria que é preservada por transformacões isoespectrais que compõem um grupo abeliano; nesse sentido, obtivemos os mesmos resultados de Mendas, em [14], e Kimura, em [10] e [11], mas por um método diferente. Em [10] e [11] o problema é abordado inteiramente em coordenadas esféricas, o que conduz a uma formulação ligeiramente diferente na obtenção dos autolavores do operador densidade. Em [14], a mesma ideia de [10] e [11] é abordada mas em dimensão d = 4. Em ambas as referências o ponto principal foi tomar interseção da esfera de Bloch com hiperplanos especiais do espaço, isso permitiu aos autores utilizar métodos computacionais e ilustrar regiões de interesse na tentativa de compreender melhor a geometria do problema. Já o segundo problema trata de descobrir propriedades de sistemas dinâmicos quânticos, como convergência e velocidade de convergência de produto de matrizes unitárias sorteadas aleatoriamente para emaranhadores universais. Conseguimos um resultado interessante que garante a convergência com velocidade exponencial, mesmo sob condições relativamente gerais. Tal resultado é importante devido ao interesse da comunidade acadêmica em entender melhor emaranhadores universais e usá-los em aplicações da computação quântica. Mais especificamente, nosso resultado garante que dado um número finito de elementos u1, ... un ∈... U (n) escolhidos ao acaso, então o produto de elementos aleatoriamente sorteados na vizinhança dos elementos u1, ..., un converge fraco-estrela para um emaranhador universal na medida de Haar em U(n). Tal resultado pode auxiliar no entendimento de propriedades de emaranhadores universais e em aplicações da computação quântica, tópicos que vêm sendo bastante estudados pela comunidade acadêmica. Finalmente, o terceiro problema, pertencente à área de Teoria de Números. É uma conjectura que encontra-se sem solução desde 1932, quando foi formulada por Derrick Henry Lehmer. Uma nova abordagem na tentativa de resolver este problema é apresentada.
A teoria dos algoritmos quânticos promete benefícios sem precedentes ao utilizar as leis da mecânica quântica para resolver certos problemas computacionais. Entretanto, alguns desafios impedem que tais vantagens se apliquem a todos os algoritmos quânticos. Entre esses desafios está o desenvolvimento de uma codificação eficiente de dados clássicos em um estado quântico. Em aplicações práticas, o custo para carregar a informação clássica em um dispositivo quân- tico pode dominar o custo computacional assintótico do algoritmo. Foram propostos diversos métodos baseados em circuitos para codificar dados clássicos nas amplitudes de probabilidade de um estado quântico. Entretanto, esses métodos produzem circuitos com complexidade que cresce linearmente com o tamanho do dado, anulando o benefício da aplicação quântica. O objetivo principal deste trabalho é reduzir a complexidade computacional dos circuitos para a inicialização de estados quânticos. As duas estratégias utilizadas para alcançar tal objetivo exploram a troca de complexidade temporal por espacial ou a transferência de complexidade computacional para um computador clássico. A primeira estratégia reinterpreta métodos al- gébricos para a decomposição de estados quânticos como caminhadas ao longo de árvores binárias. A segunda investiga o grau de emaranhamento de bipartições do estado quântico através da decomposição de Schmidt. Os métodos baseados em árvore alcançam uma redução exponencial na profundidade dos circuitos, em comparação às abordagens existentes. Os base- ados na decomposição de Schmidt produzem circuitos de complexidade variável, proporcional ao emaranhamento do estado. A perspectiva é que o resultado desta tese auxilie os profissionais da computação quântica durante a era dos dispositivos ruidosos de escala intermediária.
resumo A computação quântica possibilita a resolução eficiente de problemas complexos, superando métodos clássicos em diversas aplicações. Em 2009, Harrow, Hassidim e Lloyd propuseram um algoritmo para solução de sistemas lineares, demonstrando aceleração exponencial (em condições ideais) com complexidade p o l y ( log N ), em contraste com abordagens clássicas que, no caso geral, apresentam complexidade da ordem de O ( N 3 ), ainda que possam atingir O ( N ) em casos específicos com matrizes esparsas. Esse algoritmo tem potencial para avanços em aprendizado de máquina, equações diferenciais, regressão linear e ataques a criptossistemas. No entanto, sua estrutura é complexa e há poucos materiais detalhados disponíveis na literatura. Neste contexto, este artigo pretende apresentar um tutorial abordando os fundamentos físicos e matemáticos do algoritmo HHL, direcionado para estudantes de graduação, explicando sua construção teórica e implementação para a resolução de sistemas de equações lineares. Após a discussão dos conceitos matemáticos e físicos subjacentes, apresentamos exemplos numéricos ilustrando a evolução do circuito quântico. Por fim, analisamos sua complexidade, limitações e perspectivas futuras. Os exemplos abordados são comparados com suas simulações clássicas, permitindo uma avaliação operacional da performance do algoritmo.
Dado um grafo qualquer é possível definir um operador que representa a evolução de estados respeitando a localidade do grafo. A busca quântica, representada por uma pequena perturbação em alguns nós nesse operador de evolução para marcá-los, se baseia em evoluir o estado quântico por um determinado número de passos até que a probabilidade de encontrar um dos nós marcados seja máxima. Encontrar o número de passos e a probabilidade de sucesso final em grafos de interesse com um número qualquer de marcados é o principal objetivo deste trabalho. Para tal, desenvolvemos um método analítico que obtém uma expressão assintótica no número de nós para as quantidades desejadas a partir da análise de dois autovetores principais da matriz de evolução. O método foi desenvolvido para o caso de passeios discretos e contínuos, com exemplos na malha bidimensional e em grafos de Johnson, respectivamente e ambos com dois elementos marcados. Para um exemplo ainda mais geral é apresentada a análise de passeios contínuos em t-designs, uma abstração matemática que nos gera diferentes grafos bipartidos. Neste último caso obtemos expressões analíticas dependendo não apenas dos parâmetros do grafo, como também do número de marcados. Os exemplos estudados são casos onde não há uma teoria tão precisa a respeito da probabilidade de sucesso e tempo ótimo de passeios quânticos e também mostram o potencial do método desenvolvido para lidar com problemas mais gerais.