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

arXiv:1701.08274

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

Norio Konno, Iwao Sato, Etsuo Segawa

Published Jan 28, 2017• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1701.08274

Related papers

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

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•46 citations

Tessellations on Graphs: Theory, Algorithms, and Complexity.

Alexandre Abreu

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.

•Jan 1, 2020•0 citations

Quantum Search on Bipartite Multigraphs

Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal

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.

arXiv:2504.12586•Apr 17, 2025•0 citations

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

Norio Konno, Iwao Sato, Etsuko Segawa

•Jan 1, 2016•2 citations

The spectra of the unitary matrix of an N-tessellable staggered quantum walk on a graph

Norio Konno, Yusuke Ide, Iwao Sato

Linear Algebra and its Applications•Oct 27, 2020•0 citations
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.
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 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.
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.
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.