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.
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.
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.
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.
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), which is the smallest number of tessellations required in a total tessellation cover of G. We highlight two of these lower bounds Tt(G)≥ω(G) and Tt(G)≥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 Tt(G)=ω(G) or Tt(G)=is(G)+1. The k-total tessellability problem aims to decide whether a given graph G has Tt(G)≤k. We show that k-total tessellability is in P for good total tessellable graphs. We establish the 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.
Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gilyén, Jeffery, and Kokainis' algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs.
Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.
Studies on Quantum Computing have been developed since the 1980s, motivating researches on quantum algorithms better than any classical algorithm possible. An example of such algorithms is Grover's algorithm, capable of finding k (marked) elements in an unordered database with N elements using O(N/k) steps. Grover's algorithm can be interpreted as a quantum walk in a complete graph (with loops) containing N vertices from which k are marked. This interpretation motivated search algorithms in other graphs -- complete bipartite graph, grid, and hypercube. Using Grover's algorithm's linear operator, the quantum counting algorithm estimates the value of k with an error of O(k) using O(N) steps. This work tackles the problem of using the quantum counting algorithm for estimating the value k of marked elements in other graphs; more specifically, the complete bipartite graph. It is concluded that for a particular case, running the proposed algorithm at most t times wields an estimation of k with an error of O(k) using O(tN) steps and success probability of at least (1−2−t)8/π2.