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.
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.
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.
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.
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 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.
Estudamos o transporte quântico, via caminhadas quânticas de tempo contı́nuo (CTQWs), sobre diferentes redes complexas. Neste modelo, o transporte quântico pode ser completamente resolvido após determinados seus autovalores e autovetores associados à matriz de conectividade da rede. Para fins de comparação, também investigamos o transporte clássico através das caminhadas aleatórias de tempo contı́nuo (CTRWs). A técnica das caminhadas quânticas (QWs) é uma ferramenta poderosa na análise de fenômenos de transporte. Uma maneira de monitorar a eficiência do transporte quântico é através das probabilidades médias e exatas de retorno. Inicialmente, empregamos o modelo CTQW sobre estruturas multicamadas do tipo dendrímero (RMTDs). Para contornar efeitos de localização, decidimos empilhar várias redes dendrímero, umas sobre as outras, conectando-as através de ligações entre vértices vizinhos. Através do parâmetro de probabilidade p, adicionamos novas ligações (intraligações) entre vértices de mesma geração. Com probabilidade 1 − q, retiramos ligações (interligações) entre vértices de camadas vizinhas. O transporte quântico então é investigado através das combinações numéricas desses dois parâmetros. Para essas redes, uma escolha apropriada desses parâmetros fornece, em várias ordens de grandeza, uma eficiência maior. Encontramos algo interessante: a melhor eficiência do transporte é obtida para os seguintes valores: q ≈ 0.9 e p ≈ 0.9. Ou seja, o melhor transporte é obtido quando há a ausência de uma intra- e interligação. Na sequência, utilizamos o modelo CTQW sobre redes livres de escala generalizadas (GSFNs). Tais estruturas são uma mistura não trivial entre segmentos lineares e redes do tipo estrela. Enquanto ao transporte quântico sobre GSFNs, observamos uma alternância entre fortes efeitos de localização, devido aos segmentos de estrelas, e um bom espalhamento, devido aos segmentos lineares. Mostramos que o transporte quântico sobre GSFNs pode ser melhorado através da variação de dois parâmetros de modularidade: o grau máximo e o grau mı́nimo permitidos a todos os nós da rede. Identificamos a mesma eficiência quântica para diferentes combinações dos parâmetros de construção das redes, que estão relacionados à diferentes topologias.
O desenvolvimento de algoritmos quânticos não é uma tarefa trivial. Elementos como emaranhamento e paralelismo quântico, intrínsecos à computação quântica, dificultam esta tarefa. As caminhadas quânticas são ferramentas cruciais para o desenvolvimento de algoritmos, principalmente algoritmos de busca. Existem na literatura vários tipos de caminhadas: com lançamento de moeda, de Szegedy, utilizando tesselagem (agrupamento de vértices) e a caminhada a tempo contínuo. Para extrair dados estatísticos de uma determinada caminhada quântica, necessitamos fazer sua simulação. Neste trabalho, desenvolvemos o simulador Hiperwalk, um novo simulador de caminhadas quânticas, em grafos de uma e duas dimensões para as caminhadas com moeda e sem moeda utilizando tesselagem. O Hiperwalk permite ao usuário efetuar simulações de caminhadas quânticas em grafos utilizando processamento de alto desempenho, mesmo que o usuário não saiba programação paralela. O usuário pode empregar os dispositivos de paralelismo como CPU, GPGPU e co-processadores para acelerar o processo geral da caminhada.