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.
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.
Na primeira parte deste trabalho seguimos os estudos de Hirota e colaboradores e definimos quatro estados quase-Bell baseados em estados coerentes comprimidos da luz. Dois desses estados sao maximamente emaranhados, enquanto o emaranhamento dos outros dois depende apenas da sobreposicao entre os estados coerentes comprimidos que os compoem. A partir destes estados quase-Bell, definimos novos estados interpolados cujo emaranhamento e tambem governado por um parâmetro de interpolacao adicional e estudamos algumas das propriedades destes estados (emaranhamento e eficiencia energetica). Por fim, usamos estes estados e definimos alguns estados de Werner, com os quais analisamos de forma simples uma possivel influencia de um ambiente dissipativo parametrizado pela probabilidade de o estado de Werner estar em sua forma emaranhada ou misturada. Para esta analise usamos os conceitos de separabilidade e emaranhamento. Na segunda parte estudamos a estimativa de fase quântica usando estados gaussianos puros (estados coerentes comprimidos). Iniciamos com a estimativa da fase introduzida por um operador unitario em cujo hamiltoniano esta presente uma perturbacao linear nos operadores de criacao e aniquilacao, alem do operador de numero de fotons responsavel pela evolucao de fase (perturbacao linear unitaria). Obtemos quais sao os estados gaussianos otimos para a estimativa desta fase e analisamos a optimalidade da deteccao homodina. A seguir, consideramos o parâmetro de perturbacao como uma variavel aleatoria que obedece a uma distribuicao gaussiana de probabilidades (perturbacao linear aleatoria) e novamente obtemos os estados de sonda otimos e analisamos a optimalidade da deteccao homodina. Por fim, estudamos a estimativa de fase com perturbacao linear unitaria utilizando os estados quase-Bell interpolados definidos na primeira parte deste trabalho e verificamos que a utilizacao de emaranhamento permite uma melhor estimativa de fase para uma mesma energia disponivel
Abstract
[pt] A superioridade de desempenho dos algoritmos quânticos, em alguns problemas específicos, reside no uso direto de fenômenos da mecânica quântica para realizar operações com dados em computadores quânticos. Esta característica fez surgir uma nova abordagem, denominada Computação com Inspiração Quântica, cujo objetivo é criar algoritmos clássicos (executados em computadores clássicos) que tirem proveito de princípios da mecânica quântica para melhorar seu desempenho. Neste sentido, alguns algoritmos evolutivos com inspiração quântica tem sido propostos e aplicados com sucesso em problemas de otimização combinatória e numérica, apresentando desempenho superior àquele dos algoritmos evolutivos convencionais, quanto à melhoria da qualidade das soluções e à redução do número de avaliações necessárias para alcançá-las. Até o presente momento, no entanto, este novo paradigma de inspiração quântica ainda não havia sido aplicado à Programação Genética (PG), uma classe de algoritmos evolutivos que visa à síntese automática de programas de computador. Esta tese propõe, desenvolve e testa um novo modelo de algoritmo evolutivo com inspiração quântica, denominado Programação Genética Linear com Inspiração Quântica (PGLIQ), para a evolução de programas em código de máquina. A Programação Genética Linear é assim denominada porque cada um dos seus indivíduos é representado por uma lista de instruções (estruturas lineares), as quais são executadas sequencialmente. As contribuições deste trabalho são o estudo e a formulação inédita do uso do paradigma da inspiração quântica na síntese evolutiva de programas de computador. Uma das motivações para a opção pela evolução de programas em código de máquina é que esta é a abordagem de PG que, por oferecer a maior velocidade de execução, viabiliza experimentos em larga escala. O modelo proposto é inspirado em sistemas quânticos multiníveis e utiliza o qudit como unidade básica de informação quântica, o qual representa a superposição dos estados de um sistema deste tipo. O funcionamento do modelo se baseia em indivíduos quânticos, que representam a superposição de todos os programas do espaço de busca, cuja observação gera indivíduos clássicos e os programas (soluções). Nos testes são utilizados problemas de regressão simbólica e de classificação binária para se avaliar o desempenho da PGLIQ e compará-lo com o do modelo AIMGP (Automatic Induction of Machine Code by Genetic Programming), considerado atualmente o modelo de PG mais eficiente na evolução de código de máquina, conforme citado em inúmeras referências bibliográficas na área. Os resultados mostram que a Programação Genética Linear com Inspiração Quântica (PGLIQ) apresenta desempenho geral superior nestas classes de problemas, ao encontrar melhores soluções (menores erros) a partir de um número menor de avaliações, com a vantagem adicional de utilizar um número menor de parâmetros e operadores que o modelo de referência. Nos testes comparativos, o modelo mostra desempenho médio superior ao do modelo de referência para todos os estudos de caso, obtendo erros de 3 a 31% menores nos problemas de regressão simbólica, e de 36 a 39% nos problemas de classificação binária. Esta pesquisa conclui que o paradigma da inspiração quântica pode ser uma abordagem competitiva para se evoluir programas eficientemente, encorajando o aprimoramento e a extensão do modelo aqui apresentado, assim como a criação de outros modelos de programação genética com inspiração quântica.
Passeios quânticos em tempo contínuo é uma das áreas de pesquisa em teoria algébrica de grafos e computação quântica. Uma das suas sub-áreas de pesquisa é a de transferência de estados entre vértices de um grafo. Transferências de estados são importantes, pois permitem avaliar em quais casos uma rede com comunicação feita através de estados modelados por um grafo permitem que esses estados sejam transmitidos com o máximo possível de probabilidade de maneira eficiente. Em geral, trabalhos sobre transferência de estados lidam com transferências perfeitas ou quase perfeitas entre dois vértices. Transferências perfeitas de estado possuem caracterizações para as matrizes de Adjacência e Laplaciana. Além disso, foi mostrado ser possível verificar transferências perfeitas de estado em um grafo com um algoritmo polinomial. Em relação a transferências quase perfeitas, embora existam caracterizações para sua ocorrência, tais caracterizações demandam um certo trabalho para sua verificação em grafos e nenhum algoritmo exato é conhecido para validar sua existência. Alguns artigos mostram que, devido às restrições que as transferências perfeitas impõem nos autoespaços do grafo, tais transferências são relativamente raras em classes comuns de grafos. Portanto, é natural tentar verificar a ocorrência de transferências quase perfeitas de estados. Nessa dissertação, apresenta-se o primeiro algoritmo exato para conferir a ocorrência de transferências quase perfeita de estados em grafos. Além disso, aplicou-se resultados conhecidos nas matrizes de adjacência e Laplaciana de transferências perfeita e quase perfeita de estados na matriz Normalizada Laplaciana, considerando sua relação com passeios clássicos em grafos.
O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.
Neste trabalho, apresentamos o uso de computadores quânticos para implementar, ini- cialmente, passeios quânticos em tempo discreto. Para esse propósito, empregamos o modelo de passeios quânticos escalonados (SQW, na sigla em inglês) em ciclos de 8 e 16 vértices, visando alcançar taxas com a maior fidelidade possível. Além disso, demonstramos resultados para um problema de busca espacial e para uma malha bidimensional. Exibimos resultados para passeios quânticos a tempo discreto. Ademais, a decomposição de portas multicontroladas em portas elementares de qubits demonstra uma estratégia pragmática para a mitigação de erros, contribuindo significativamente para a confiabilidade e reprodu- tibilidade de nossos resultados em computação quântica. Essa abordagem meticulosa é crucial, especialmente ao lidar com algoritmos quânticos complexos nos quais a precisão é fundamental. Utilizando metodologia semelhante, também implementamos passeios quânticos em tempo contínuo para três casos: grafo completo, grafo bipartido completo e hipercubo. Além disso, realizamos uma comparação entre os resultados obtidos pelo simulador quântico e pelo computador quântico em todos os casos. Nosso estudo não apenas contribui para o crescente corpo de pesquisa em algoritmos quânticos, mas também destaca a importância da otimização cuidadosa em nível de portas para a computação quântica prática. À medida que as tecnologias quânticas continuam a avançar, essas descobertas abrem caminho para o desenvolvimento de algoritmos quânticos mais robustos e eficientes com aplicações no mundo real.
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.