Em Ciência da Computação, os caminhos aleatórios são utilizados em algoritmos randômicos, especialmente em algoritmos de busca, quando desejamos encontrar um estado marcado numa cadeia de Markov. Nesse tipo de algoritmo é interessante estudar o Tempo de Alcance, que está associado a sua complexidade computacional. Nesse contexto, descrevemos a teoria clássica de cadeias de Markov e caminhos aleatórios, assim como o seu análogo quântico. Dessa forma, definimos o Tempo de Alcance sob o escopo das cadeias de Markov quânticas. Além disso, expressões analíticas calculadas para o tempo de Alcance quântico e para a probabilidade de encontrarmos um elemento marcado num grafo completo são apresentadas como os novos resultados dessa dissertação. / In Computer Science, random walks are used in randomized algorithms, specially in search algorithms, where we desire to find a marked state in a Markov chain.In this type of algorithm,it is interesting to study the Hitting Time, which is associated to its computational complexity. In this context, we describe the classical theory of Markov chains and random walks,as well as their quantum analogue.In this way,we define the Hitting Time under the scope of quantum Markov chains. Moreover, analytical expressions calculated for the quantum Hitting Time and for the probability of finding a marked element on the complete graph are presented as the new results of this dissertation.
| Identifer | oai:union.ndltd.org:IBICT/oai:agregador.ibict.br.BDTD_LNCC:oai:lncc.br:89 |
| Date | 05 March 2010 |
| Creators | Raqueline Azevedo Medeiros Santos |
| Contributors | Marcelo Dutra Fragoso, Celina Miraglia Herrera de Figueiredo, Renato Portugal |
| Publisher | Laboratório Nacional de Computação Científica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações do LNCC, instname:Laboratório Nacional de Computação Científica, instacron:LNCC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds