Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Tessellations on Graphs: Theory, Algorithms, and Complexity.

Alexandre Abreu

Published Jan 1, 2020• 0 citations
Publisher

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 \textit{tessellation cover number} $T(G)$ is related to several other parameters present in the literature such as \textit{chromatic number}, \textit{chromatic index}, \textit{total chromatic number}, \textit{independent set number}, and \textit{clique number}. In addition, problems related to $T(G)$, such as \textsc{$t$-tessellability}, \textsc{good tesellable recognition}, and \textsc{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 \textit{total tessellation cover}, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.

DOI
10.7910/dvn/yku2xi

Related papers

Total tessellation cover and quantum walk

Alexandre Abreu, Luís Cunha, Celina M.H. de Figueiredo +3 more

We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on $T_t(G)$, which is the smallest number of tessellations required in a total tessellation cover of $G$. We highlight two of these lower bounds $T_t(G) \geq ω(G)$ and $T_t(G)\geq is(G)+1$, where $ω(G)$ is the size of a maximum clique and $is(G)$ is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either $T_t(G)=ω(G)$ or $T_t(G)=is(G)+1$. The $k$-total tessellability problem aims to decide whether a given graph $G$ has $T_t(G) \leq k$. We show that $k$-total tessellability is in $\mathcal{P}$ for good total tessellable graphs. We establish the $\mathcal{NP}$-completeness of the following problems when restricted to the following classes: ($is(G)+1$)-total tessellability for graphs with $ω(G) = 2$; $ω(G)$-total tessellability for graphs $G$ with $is(G)+1 = 3$; $k$-total tessellability for graphs $G$ with $\max\{ω(G), is(G)+1\}$ far from $k$; and $4$-total tessellability for graphs $G$ with $ω(G) = is(G)+1 = 4$. As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and $(2,1)$-chordal graphs.

arXiv:2002.08992•Feb 20, 2020•0 citations

Staggered quantum walk on hexagonal lattices

Bruno Chagas, Renato Portugal, Stefan Boettcher +1 more

A discrete-time staggered quantum walk was recently introduced as a generalization that allows the unification of other versions, such as the coined and Szegedy's walk. However, it also produces forms of quantum walks not covered by previous versions. To explore their properties, we study here the staggered walk on a hexagonal lattice. Such a walk is defined using a set of overlapping tessellations that cover the graph edges, and each tessellation is a partition of the node set into cliques. The hexagonal lattice requires at least three tessellations. Each tessellation is associated with a local unitary operator and the product of the local operators defines the evolution operator of the staggered walk on the graph. After defining the evolution operator on the hexagonal lattice, we analyze the quantum walk dynamics with the focus on the position standard deviation and localization. We also obtain analytic results for the time complexity of spatial search algorithms with one marked node using cyclic boundary conditions.

arXiv:1806.10249•Physical Review A•Nov 9, 2018•5 citations

Discrete-Time Quantum Walks on Oriented Graphs

Bruno Chagas, Renato Portugal

The interest in quantum walks has been steadily increasing during the last two decades. It is still worth to present new forms of quantum walks that might find practical applications and new physical behaviors. In this work, we define discrete-time quantum walks on arbitrary oriented graphs by partitioning a graph into tessellations, which is a collection of disjoint cliques that cover the vertex set. By using the adjacency matrices associated with the tessellations, we define local unitary operators, whose product is the evolution operator of our quantum walk model. We introduce a parameter, called alpha, that quantifies the amount of orientation. We show that the parameter alpha can be tuned in order to increase the amount of quantum walk-based transport on oriented graphs.

arXiv:2001.04814•Electronic Proceedings in Theoretical Computer Science•Apr 1, 2020•4 citations

The spectra of the unitary marix of a 2-tessellable staggered quantum walk on a graph

Norio Konno, Iwao Sato, Etsuo Segawa

Recently, the staggered quantum walk (SQW) on a graph is discussed as a generalization of coined quantum walks on graphs and Szegedy walks. We present a formula for the time evolution matrix of a 2-tessellable SQW on a graph, and so directly give its spectra. Furthermore, we present a formula for the Szegedy matrix of a bipartite graph by the same method, and so give its spectra. As an application, we present a formula for the characteristic polynomial of the modified Szegedy matrix in the quantum search problem on a graph, and give its spectra.

arXiv:1701.08274•Jan 28, 2017•0 citations

Staggered quantum walks on graphs

Renato Portugal

The staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.

arXiv:1603.02210•Physical Review A•Jun 27, 2016•44 citations

Staggered quantum walk on a line of diamonds

Cauê F. Teixeira da Silva, Daniel Posner, Renato Portugal

The staggered model is a discrete-time quantum walk model, whose evolution operator is obtained from a set of graph tessellations. We use this model to analyze the standard deviation of the probability distribution on a line of diamonds. The results help to understand the dynamics of quantum walks and it can be used as tools for building quantum algorithms.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Dec 19, 2018•0 citations
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 \textit{tessellation cover number} T(G)T(G)T(G) is related to several other parameters present in the literature such as \textit{chromatic number}, \textit{chromatic index}, \textit{total chromatic number}, \textit{independent set number}, and \textit{clique number}. In addition, problems related to T(G)T(G)T(G), such as \textsc{ttt-tessellability}, \textsc{good tesellable recognition}, and \textsc{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)T(G)T(G), and the value of T(G)T(G)T(G) for several graph classes. Furthermore, we present a quantum walk model based on \textit{total tessellation cover}, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.
We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on Tt(G)T_t(G)Tt​(G), which is the smallest number of tessellations required in a total tessellation cover of GGG. We highlight two of these lower bounds Tt(G)≥ω(G)T_t(G) \geq ω(G)Tt​(G)≥ω(G) and Tt(G)≥is(G)+1T_t(G)\geq is(G)+1Tt​(G)≥is(G)+1, where ω(G)ω(G)ω(G) is the size of a maximum clique and is(G)is(G)is(G) is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either Tt(G)=ω(G)T_t(G)=ω(G)Tt​(G)=ω(G) or Tt(G)=is(G)+1T_t(G)=is(G)+1Tt​(G)=is(G)+1. The kkk-total tessellability problem aims to decide whether a given graph GGG has Tt(G)≤kT_t(G) \leq kTt​(G)≤k. We show that kkk-total tessellability is in P\mathcal{P}P for good total tessellable graphs. We establish the NP\mathcal{NP}NP-completeness of the following problems when restricted to the following classes: (is(G)+1is(G)+1is(G)+1)-total tessellability for graphs with ω(G)=2ω(G) = 2ω(G)=2; ω(G)ω(G)ω(G)-total tessellability for graphs GGG with is(G)+1=3is(G)+1 = 3is(G)+1=3; kkk-total tessellability for graphs GGG with max⁡{ω(G),is(G)+1}\max\{ω(G), is(G)+1\}max{ω(G),is(G)+1} far from kkk; and 444-total tessellability for graphs GGG with ω(G)=is(G)+1=4ω(G) = is(G)+1 = 4ω(G)=is(G)+1=4. As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and (2,1)(2,1)(2,1)-chordal graphs.
A discrete-time staggered quantum walk was recently introduced as a generalization that allows the unification of other versions, such as the coined and Szegedy's walk. However, it also produces forms of quantum walks not covered by previous versions. To explore their properties, we study here the staggered walk on a hexagonal lattice. Such a walk is defined using a set of overlapping tessellations that cover the graph edges, and each tessellation is a partition of the node set into cliques. The hexagonal lattice requires at least three tessellations. Each tessellation is associated with a local unitary operator and the product of the local operators defines the evolution operator of the staggered walk on the graph. After defining the evolution operator on the hexagonal lattice, we analyze the quantum walk dynamics with the focus on the position standard deviation and localization. We also obtain analytic results for the time complexity of spatial search algorithms with one marked node using cyclic boundary conditions.
The interest in quantum walks has been steadily increasing during the last two decades. It is still worth to present new forms of quantum walks that might find practical applications and new physical behaviors. In this work, we define discrete-time quantum walks on arbitrary oriented graphs by partitioning a graph into tessellations, which is a collection of disjoint cliques that cover the vertex set. By using the adjacency matrices associated with the tessellations, we define local unitary operators, whose product is the evolution operator of our quantum walk model. We introduce a parameter, called alpha, that quantifies the amount of orientation. We show that the parameter alpha can be tuned in order to increase the amount of quantum walk-based transport on oriented graphs.
Recently, the staggered quantum walk (SQW) on a graph is discussed as a generalization of coined quantum walks on graphs and Szegedy walks. We present a formula for the time evolution matrix of a 2-tessellable SQW on a graph, and so directly give its spectra. Furthermore, we present a formula for the Szegedy matrix of a bipartite graph by the same method, and so give its spectra. As an application, we present a formula for the characteristic polynomial of the modified Szegedy matrix in the quantum search problem on a graph, and give its spectra.
The staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.