Authors:

Autores

Person role Person
6860
2882,2733,257
6861
2882,2733,257
6862
2882,2733,257

Informations:

Pesc publication

Title
Tessellations On Graphs: Theory, Algorithms and Complexity
Research area
Algorithms and Combinatorics
Publication type
Doctoral Thesis
Identification Number
Date
3/30/2020
Resumo

Devido ao avanço tecnológico recente, a computação quântica tem ganhado notoriedade. Neste paradigma, o conceito de passeio quântico é fundamental para o desenvolvimento de algoritmos para computadores quânticos. Dentre os modelos de passeios quânticos existentes, destaca-se o modelo escalonado, proposto por Portugal et al., que inclui o modelo de Szegedy como um caso particular, além de parte do modelo com moeda. O modelo escalonado utiliza o conceito de tesselações em grafos para gerar os operadores quânticos de evolução que regem os movimentos do caminhante sobre o grafo. Tesselações em grafos possuem ainda um interessante valor para teoria de grafos visto que o parâmetro tessellation cover number T(G) se relaciona com diversos outros parâmetros presentes na literatura tais como chromatic number, chromatic index, total chromatic number, independent set number, e clique number. Além disso, os problemas que se relacionam com T(G), tais como t-tessellability, good tesellable recognition, e total good tessellable recognition têm relações profundas com problemas clássicos em teoria dos grafos que envolvem coloração de grafos. Neste trabalho apresentamos resultados em teoria de grafos para os problemas relacionados com tesselações em grafos citados acima, tais como complexidade computacional destes problemas para várias classes de grafos, limites inferior e superior para T(G), e o valor de T(G) para diversas classes de grafos. Além disso, apresentamos um modelo de passeio quântico baseado em total tessellation cover, sendo este pioneiro no uso de vértices e arestas como localidades possíveis para o caminhante, simultaneamente.

Abstract

Due to recent technological advances, quantum computing has gained notoriety. In this paradigm, the concept of quantum walk is fundamental for the development of algorithms for quantum computers. Among the existing quantum walk models, the staggered model, proposed by Portugal et al. stands out, since it includes the Szegedy model as a particular case, and part of the coined model. The staggered model uses the concept of tessellations on graphs to generate the quantum evolution operators that perform the walker’s movements on the graph. Tessellations on graphs also have an interesting value for graph theory, since the parameter tessellation cover number T(G) is related to several other parameters present in the literature such as chromatic number, chromatic index, total chromatic number, independent set number, and clique number. In addition, problems related to T(G), such as t-tessellability, good tesellable recognition, and total good tessellable recognition have deep relations with classic problems in graph theory involving graph coloring. In this work we present results in graph theory for the problems related to tessellations on graphs mentioned above, such as computational complexity, lower and upper bounds for T(G), and the value of T(G) for several graph classes. Furthermore, we present a quantum walk model based on total tessellation cover, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.

JSN_TPLFW_GOTO_TOP