Characterizing the Inherent Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks on Finite Graphs

Passeios quânticos em grafos são ubíquos na Computação Quântica, possuindo uma miríade de aplicações importantes. De forma similar, passeios aleatórios em grafos são fundamentais na descrição de muitos algoritmos com diversas aplicações. Ainda que a relação entre passeios quânticos e passeios aleatórios tenha sido explorada em trabalhos recentes, esta dissertação estabelece uma equivalência entre os dois passeios em grafos finitos, sobre condições gerais dos operadores quânticos e do passeio aleatório. Tal equivalência demanda empoderar passeios aleatórios com heterogeneidade no tempo, de forma que as probabilidades de transição sejam não-uniformes e dependam do instante de tempo. Essa equivalência é obtida ao se igualar, a cada instante e para todos os vértices do grafo, a probabilidade do caminhante clássico estar no vértice com a probabilidade desse mesmo vértice ser resultado da medição do passeio quântico. O resultado apresentado possui duas vertentes similares. A primeira aparece sob a forma de um procedimento para construir a sequência de matrizes estocásticas capaz de gerar um passeio aleatório com a mesma evolução de probabilidade de um dado passeio quântico qualquer, incluindo o cenário de múltiplos caminhantes quânticos que interagem entre si. A segunda vertente apresenta um procedimento na direção oposta, partindo de um aleatório e construindo um passeio quântico equivalente. Nesse contexto, a sequência de matrizes obtida pelo primeiro procedimento permite uma abordagem inédita para a simulação de passeios quânticos onde as amostras da posição do caminhante respeitam a vizinhança dos vértices dando origens a trajetórias quânticas. A convergência da simulação é garantida através da lei dos grandes números, permitindo a amostragem eficiente (em tempo polinomial) de trajetórias quânticas do grafo. Em complemento, a complexidade computacional do procedimento de construção dessas matrizes é discutida para o caso geral.