Search

Dissertação de mestrado integrado em Engenharia Física, 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., Finally, this dissertation was financed by the ERDF – European Regional Development Fund through the Operational Programme for Competitiveness and Internationalization - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project POCI- 01-0145-FEDER-030947.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES The quantum walks, besides being naturally used in the modeling of systems of this scale, has been widely used in the building quantum algorithms. In the last, both its formulation in continuous and discrete time, in some cases, presents better performance when compared to algorithms that use classical random walk. Among these formulations, the literature has highlighted the use of quantum walk in discrete time, in particular, its applicability in complex networks. The small world network is part of this type of structure. In this work, the discrete time quantum walk on this network is presented, analyzing the behavior of the probability distribution with the variation of the parameters q, which determines the topology of the network, and k, which defines the neighborhood closest to the vertex. A formalism is defined that describes this dynamic, allowing to numerically simulate the walk. The evolution of the probability distributions versus parameters reveals its tendency to spread, towards uniformity. Between this transition, there is a regime different from the characteristic ballistic behavior in a circular network. There is an attempt to determine a law of scale to describe this evolution, working only for a small range of parameters. O caminho aleatório quântico, além de ser naturalmente utilizado na modelagem de sistemas desta escala, tem sido amplamente empregado na construção de algorítimos quânticos. Neste último, tanto sua formulação em tempo contínuo quanto em discreto, em alguns casos apresentam melhor desempenho quando comparados a algoritmos que usam caminho aleatório clássico. Dentre essas formulações, a literatura tem dado destaque ao uso da caminhada quântica em tempo discreto, em especial, sua aplicabilidade em redes complexas. A rede pequeno mundo faz parte desse tipo de estrutura. Neste trabalho, é apresentado a caminhada quântica em tempo discreto sobre esta rede, analisando o comportamento da distribuição de probabilidade com a variação dos parâmetros q, que determina a topologia da rede, e k, que define a vizinhança mais próxima do vértice. É definido um formalismo que descreve esta dinâmica, permitindo simular numericamente a caminhada. A evolução das distribuições de probabilidade em função dos parâmetros revelam sua tendência de espalhamento, em direção a uniformidade. Entre essa transição, encontra-se um regime diferentemente do característico comportamento balístico em uma rede circular. Há uma tentativa de determinar uma lei de escala para descrever essa evolução, funcionando apenas para um pequeno intervalo dos parâmetros. São Cristóvão

Submitted by Maria Cristina (library@lncc.br) on 2017-12-12T11:56:42Z No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-12-12T11:57:36Z (GMT) No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) Made available in DSpace on 2017-12-12T11:57:45Z (GMT). No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) Previous issue date: 2017-09-13 Quantum walks play an important role in the development of quantum algorithms, they can be used to solve efficiently problems such as: elements distinct, boolean formulas evaluation, matrix product verification and group commutativity, and especially, spatial search problems. Falk exemplified a quantum walk model for two-dimensional lattice, that does not require an additional space to the coin, and the evolution operator can be obtained via a tessellation process. However, it was not explicit the definition of the model for generic graphs and nor proven its efficiency. The idea presented by Falk inspired the creation of Staggered Quantum Walk model (SQW). Therefore, the goal of this work is: (1) define the stepped model for generic graphs, (2) demonstrate that an important quantum walk already known and explored in the literature, the Szegedy model, is a particular case of the SQW, (3) show the efficiency of SQW in the search problem in the two-dimensional lattice. Os passeios quânticos desempenham um papel importante no desenvolvimento de novos algoritmos quânticos, e podem ser usados para resolver eficientemente problemas como: distinção de elementos, avaliação de fórmulas booleanas, verificação de produto de matrizes e comutatividade de grupos e, em especial, problemas de busca espacial em grafos. Falk exemplificou um modelo de passeios quânticos para malha bidimensional, que não necessita de um espaço adicional para representar a moeda, no qual o operador de evolução pode ser obtido via um processo de tesselação. Porém, não foi explicitada a definição do modelo para grafos genéricos e nem comprovada a sua eficiência. A ideia apresentada por Falk inspirou a criação do Passeio Quântico Escalonado (SQW). Sendo assim, as contribuições deste trabalho são (1) definir o modelo escalonado para grafos genéricos, (2) demonstrar que um importante passeio quântico já conhecido e explorado na literatura, o modelo de Szegedy, é um caso particular do modelo escalonado e (3) mostrar a eficiência do passeio quântico escalonado no problema de busca na malha bidimensional.

Submitted by Maria Cristina (library@lncc.br) on 2015-11-25T13:28:47Z No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-11-25T13:29:04Z (GMT) No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) Made available in DSpace on 2015-11-25T13:29:13Z (GMT). No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) Previous issue date: 2015-11-04 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) The development of quantum algorithms is not a easy task. Elements such as entanglement and quantum paralelism, intrinsics to quantum computation, difficult this task. Quantum walks are crucial tools for development of algorithms, mainly search algorithms. There are many types of quantum walks: with coin toss, Szegedy's, using tessellation (grouping of vertices) and the continuous-time quantum walk. To extract statistics data of a quantum walk, we need to perform its simulation. In this work, we develped the simulator Hiperwalk, a new simulator of quantum walks in graphs of one and two dimension for the quantum walk with a coin toss and coinless using tessellation. The Hiperwalk allows the user to perform simulations of quantum walks in graphs using high performance computing (HPC), even though the user does not knowing parallel programming. The user can employ the parallel devices such as CPU, GPGPU and accelerators cards to speedup the overall process of the walk. 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.