{"id":{"repo_id":"brazil-uerj","oai_identifier":"oai:pantheon.ufrj.br:11422/8119"},"canonical_url":"https://search.dev.ndltd.org/etd/brazil-uerj/oai:pantheon.ufrj.br:11422/8119","repository":{"repo_id":"brazil-uerj","name":"Brazil UERJ","base_url":"https://pantheon.ufrj.br/oai/request"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Abreu, Alexandre Santiago de"],"institution":"Universidade Federal do Rio de Janeiro","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Marquezino, Franklin de Lima"],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-03","date_published":"2017-03","updated_at":"2026-07-24T01:16:29Z","subjects":["Engenharia de Sistemas e Computação","Tesselações em grafos","Algoritmo quântico"],"languages":["por"],"rights":["Acesso Aberto"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11422/8119","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Marquezino, Franklin de Lima"]},{"key":"dc:creator","label":"Author","values":["Abreu, Alexandre Santiago de"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-05-22T18:53:26Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-05-16T03:02:57Z"]},{"key":"dc:date.issued","label":"Date","values":["2017-03"]},{"key":"dc:publisher","label":"Institution","values":["Universidade Federal do Rio de Janeiro"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia"]},{"key":"dc:type","label":"Dc Type","values":["Dissertação"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engenharia de Sistemas e Computação","Tesselações em grafos","Algoritmo quântico"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["por"]},{"key":"dc:rights","label":"Dc Rights","values":["Acesso Aberto"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11422/8119"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Tesselações em grafos e suas aplicações em computação quântica"]}]}],"canonical_facts":{"dc:contributor.advisor":["Marquezino, Franklin de Lima"],"dc:creator":["Abreu, Alexandre Santiago de"],"dc:date.accessioned":["2019-05-22T18:53:26Z"],"dc:date.available":["2026-05-16T03:02:57Z"],"dc:date.issued":["2017-03"],"dc:description.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."],"dc:identifier.uri":["http://hdl.handle.net/11422/8119"],"dc:language":["por"],"dc:publisher":["Universidade Federal do Rio de Janeiro"],"dc:publisher.department":["Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia"],"dc:rights":["Acesso Aberto"],"dc:subject":["Engenharia de Sistemas e Computação","Tesselações em grafos","Algoritmo quântico"],"dc:title":["Tesselações em grafos e suas aplicações em computação quântica"],"dc:type":["Dissertação"]},"updated_at":"2026-07-24T01:16:29Z"}