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.