Análise,Simulações e Aplicações Algorítmicas de Caminhadas Quânticas / Analysis,Simulations and Algorithmic Applications of Quantum Walks
AUTOR(ES)
Franklin de Lima Marquezino
DATA DE PUBLICAÇÃO
2010
RESUMO
Quantum computing is a model of computation based on the laws of quantum mechanics, which can be used to develop faster algorithms. The development of efficient quantum algorithms, however, is a highly challenging task. A recent successful approach is the use of quantum walks. In this work, we have studied the quantum walk on the hypercube, obtaining the exact stationary distribution and analyzing properties of its mixing time both in the ideal and in the noisy set-ups, with noise generated by broken links. We have also studied the walk in a two-dimensional grid, where we have obtained its stationary distribution analytically and have explored the relation between mixing time and the complexity of the search algorithm for this graph. We have developed a computational tool for numerical simulation of quantum walks in one- and two-dimensional grids with several boundary conditions. Finally, we have studied some algorithms for search on graphs and have numerically analyzed the impact of decoherence over their performances.
ASSUNTO(S)
computabilidade e modelos de computacao algorithms (computation) quantum computing computação quântica caminhadas aleatórias algoritmos (computação) random walks computadores quânticos
