Defesa de Tese de Doutorado: Caminhando em vértices e arestas com o passeio quântico contínuo no tempo

Orientadores:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC

Banca Examinadora:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC (presidente)
Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC
Franklin de Lima Marquezino - COPPE/UFRJ - UFRJ
Marcelo de Oliveira Terra Cunha - UNICAMP

Suplentes:
Jauvane Cavalcante de Oliveira - Laboratório Nacional de Computação Científica - LNCC
Celina Miraglia Herrera de Figueiredo - COPPE/UFRJ - COPPE/UFRJ

Resumo:

A dinâmica de passeios quânticos obedece as leis da mecânica quântica com uma restrição extra de localidade, a qual demanda que o operador de evolução seja local, no sentido que o caminhante deve visitar locais vizinhos antes de locais distantes. Normalmente, o Hamiltoniano é obtido das matrizes de adjacência ou laplaciana do grafo e o caminhante pula de um vértice para vértices vizinhos. Neste trabalho, definimos uma versão do passeio quântico a tempo contínuo que permite o caminhante pular de vértice para aresta. Como uma aplicação, analisamos o algoritmo de busca espacial no grafo bipartido completo através de uma modificação na nova versão do Hamiltoniano com um termo extra que depende da localização do vértice marcado ou da aresta marcada, de forma similar ao que é feito no modelo de passeio quântico a tempo contínuo. Nós mostramos que o tempo de execução ótimo para achar ou um vértice ou uma aresta é O(√Ne) com probabilidade de sucesso 1 + o(1), onde Ne é o número de arestas do grafo bipartido completo.