Quantum random walks: simulations and physical realizations

Abstract

Quantum computing is an emergent field that brings together Quantum Mechanics, Computer Science and Information Theory, which promises improvements to classical algorithms such as simulation of quantum systems, cryptography, data base searching and many others. Among these algorithms, quantum walks may provide a quadratic speed up when compared to their classical counterparts, allowing improvements to applications such as element distinctness, searching problems, matrix product verification and hitting times in graphs. The present work offers a general theoretical overview, simulation and circuit implementation of the coined, staggered and continuous-time quantum walk models. The first two chapters of this thesis are dedicated to the definition of the theoretical framework, simulation in Python and comparison of the aforementioned quantum walk models for the simple case of the dynamics in a line graph and for the search algorithm in a complete graph. This is then used as a benchmark for the final chapter, devoted to building and testing the circuits corresponding to models mentioned above in IBM’s Qiskit. A main contribution of this dissertation concerns the circulant graph approach to diagonal operators for continuous-time quantum walks.

A computação quântica é uma área emergente, que junta os campos de Mecânica Quântica, Ciências da Computação e Teoria da Informação, com a promessa de melhoramentos a algoritmos clássicos tais como a simulação de sistemas quânticos, criptografia, busca em base de dados, e outros. Entre estes algoritmos, as caminhadas quânticas surgem com um ganho quadrático de complexidade em comparação às caminhadas clássicas, possibilitando melhor desempenho em aplicações como distinção de elementos, problemas de busca, verificação de produtos de matrizes e tempos de alcance em grafos. O trabalho atual oferece uma visão geral de um ponto de vista teórico, de simulação e de implementação de circuitos, relativos aos modelos de caminhadas quânticas com moeda, escalonadas e contínuas no tempo. Os primeiros dois capítulos desta tese são dedicados à definição da estrutura teórica, simulação em Python e comparação dos modelos supracitados, para o caso simples da dinâmica na linha, e para o problema de busca num grafo completo. Isto será então utilizado como referência para o capítulo final, dedicado à construção e teste dos circuitos correspondentes aos modelos supracitados. Uma contribuição principal desta dissertação diz respeito à abordagem de grafos circulantes para realização de caminhadas quânticas continuas no tempo.