Tesselações em Grafos e Suas Aplicações em Computação Quântica

O uso de passeios aleatórios na computação clássica tem resultado em boas soluções para problemas em diversas áreas. Seu correspondente quântico tem sido uma ferramenta eficiente no desenvolvimento de algoritmos quânticos. Um exemplo de grande importância teórica usando tal artifício é o algoritmo de Ambainis para o problema de Element k-Distinctness, que responde se em uma lista de N elementos existem k elementos de mesmo valor. A abordagem de Ambainis reduz o problema a encontrar um vértice marcado em um grafo de Johnson, bipartido, requerendo O (N elevado k/k+1) passos e sendo melhor do que qualquer abordagem clássica já desenvolvida. Esse procedimento foi mais tarde generalizado por Szegedy em um novo modelo de passeios quânticos que consiste em executar um passeio através das arestas de um grafo bipartido. Recentemente, Portugal et al. desenvolveram o modelo Escalonado, que inclui o modelo de Szegedy como um caso particular. Junto a este modelo, surgiu o conceito de tesselações em grafos, importante para a geração dos operadores de evolução unitários para o modelo Escalonado. Portugal ainda mostrou que todos os grafos 2-tesseláveis possuem grafos clique 2-coloríveis. Não é possível afirmar que um grafo cuja cobertura mínima por tesselações T(G) > 2 possui um grafo clique cujo numero cromático seja igual a T(G). Neste trabalho apresentamos o limite superior para o problema de cobertura mínima por tesselações, além de famílias de grafos cujo número de tesselações é menor ou igual a este limite. Apresentamos também uma reformulação do algoritmo para o problema de Element k-Distinctness, utilizando o modelo Escalonado.