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.
Resumo: 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 são maximamente emaranhados, enquanto o emaranhamento dos outros dois depende apenas da sobreposição entre os estados coerentes comprimidos que os compõem. A partir destes estados quase-Bell, definimos novos estados interpolados cujo emaranhamento é também governado por um parâmetro de interpolação adicional e estudamos algumas das propriedades destes estados (emaranhamento e eficiência energética). Por fim, usamos estes estados e definimos alguns estados de Werner, com os quais analisamos de forma simples uma possível influência de um ambiente dissipativo parametrizado pela probabilidade de o estado de Werner estar em sua forma emaranhada ou misturada. Para esta análise 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 unitário em cujo hamiltoniano está presente uma perturbação linear nos operadores de criação e aniquilação, além do operador de número de fótons responsável pela evolução de fase (perturbação linear unitária). Obtemos quais são os estados gaussianos ótimos para a estimativa desta fase e analisamos a optimalidade da detecção homódina. A seguir, consideramos o parâmetro de perturbação como uma variável aleatória que obedece a uma distribuição gaussiana de probabilidades (perturbação linear aleatória) e novamente obtemos os estados de sonda ótimos e analisamos a optimalidade da detecção homódina. Por fim, estudamos a estimativa de fase com perturbação linear unitária utilizando os estados quase-Bell interpolados definidos na primeira parte deste trabalho e verificamos que a utilização de emaranhamento permite uma melhor estimativa de fase para uma mesma energia disponível
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.
Passeios quânticos surgiram como um proposta de expansão de passeios aleatórios para sistemas exclusivamente quânticos. Esse trabalho tem como objetivo demonstrar como implementar um passeio quânticos em computadores quânticos de maneira mais eficiente para certos tipos de grafos ao utilizar a versão truncada da tranformada de Fourier quântica. Também demonstraremos alguns resultados relacionados com a adição de pesos complexos nas aretas de grafos dentre eles como a dinâmica do passeio se altera para certos grafos como árvores e caminhos. Adicionalmente provaremos a existência de uma família de grafos que possuem vértices no qual é impossível encontrar o caminhante neles para qualquer tempo t do passeio. Provaremos a conexão desse fenômeno nessa família com a degenerescência dos autovalores do Hamiltoniano associado ao grafo o que nos permite trilhar um caminho para uma possível compreensão de uma formato geral para os tipos de grafo que exibem esse fenômeno.
A dinâmica de passeios quânticos obedece às leis da mecânica quântica com uma restrição extra de localidade, a qual demanda que o operador de evolução seja local, no sentido que o caminhante deve visitar locais vizinhos antes de visitar locais distantes. Normalmente, o Hamiltoniano é obtido das matrizes de adjacência ou laplaciana do grafo e o caminhante pula de um vértice para vértices vizinhos. Neste trabalho, definimos uma versão do passeio quântico a tempo contínuo que permite o caminhante pular de vértice para aresta. Como uma aplicação, analisamos o algoritmo de busca espacial no grafo bipartido completo através de uma modificação na nova versão do Hamiltoniano com um termo extra que depende da localização do vértice marcado ou da aresta marcada, de forma similar ao que é feito no modelo de passeio quântico a tempo contínuo. Nós mostramos que o tempo de execução ótimo para achar ou um vértice, ou uma aresta é O(√Ne) com probabilidade de sucesso 1 − o(1), onde Ne é o número de arestas do grafo bipartido completo.