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.
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
O método de Adomian é usado na solução de equações diferenciais não lineares com resíduo, em áreas das engenharias. Nesse trabalho, usaremos o método para transformar a Equação de Schrödinger não linear em um sistema de equações lineares para, então, estudar a construção de um algoritmo quântico de Adomian. Como método, realizamos uma revisão bibliográfica do método de Adomian e utilizamos Matlab para aplicar o método, no caso de um sistema clássico. Já quanto a versão quântica do método, fizemos uma revisão bibliográfica de algoritmos quânticos e identificamos possibilidades de usos de algoritmos quânticos para equações diferenciais lineares que podem ser utilizados, após a aplicação do método de Adomian. Nesse particular, discutimos abordagens que poderão ser úteis em trabalhos futuros. Resultados os resíduos do método de Adomian são muito variáveis em ordem de grandeza, contudo, em certas condições, o método apresenta soluções muito próximas da solução real. A ideia de algoritmo quântico proposto neste trabalho precisa ser aprofundada em estudos futuros para ser testada de forma apropriada, dependendo do sistema que se queira trabalhar.