Tesselações em grafos e suas aplicações em computação quântica

Abstract

The usage of random walks in classical computing has resulted in good solutions to problems in many areas. Its quantum counterpart has been an efficient tool in the development of quantum algorithms. An example of great theoretical importance using this approach is Ambainis’ algorithm for the Element k-Distinctness problem, which answers if in a list of N elements there are k elements of same value. Ambainis’ approach reduces the problem to finding a marked vertex in a bipartite Johnson graph, requiring O(Nk/k+1) steps, which is better than any known classical approach. This procedure was later generalized by Szegedy in a new model of quantum walks consisting on a walk through the edges of a bipartite graph. Recently, Portugal et al. developed the Staggered model, which includes the Szegedy’s model as a particular case. The Staggered model introduced the concept of graph tessellations, which is important for the definition of the unitary evolution operators. Portugal also proved that all 2-tessellable graphs have a 2-colorable clique graph. It is not possible to state that a graph whose the minimum cover by tessellations T(G) > 2 has a clique graph whose chromatic number is equal T(G). In this work we present the upper bound for the problem of tessellation cover, in addition to families of graphs whose tessellation number is less or equal than this bound. We also present a reformulation of the algorithm for the Element k-Distinctness problem using the Staggered model.