1 Introduction

Quantum walks (QWs) are being used with many flavors with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Research in QWs started with the coined discrete-time QW [1] proposed with the goal of displaying a quantum system with features strikingly different from classical systems. From a different viewpoint, Meyer [2] proposed a non-trivial example of a quantum cellular automata which can be somehow considered the starting point of staggered QWs. By quantizing continuous classical Markov chains, Farhi and Gutmann [3] proposed a continuous-time version of QWs, with clear implications to the area of quantum computing. Inspired by classical discrete Markov chains, Szegedy [4] proposed a coinless discrete-time QW model and was able to provide us with a natural definition of quantum hitting time.

Szegedy’s QWs are obtained by quantizing classical discrete Markov chains described by some transition matrix. Szegedy [4] also developed QW-based search algorithms inspired by a previous known coined-based search algorithm [5]. On ergodic Markov chains, it is possible to detect the presence of a marked vertex at a hitting time that is quadratically smaller than the classical average hitting time [6]. Szegedy’s model was also used for the searching problem [6, 7], which aims to find the location of a marked vertex, and for searching triangles [8]. Some references highlighted the power of the method, for instance Ref. [9], and some proposed generalizations without the assumption of bipartiteness, for instance Ref. [10]. The fact that Szegedy’s model is a QW on the edges of a bipartite graph rather than on the vertices is emphasized in [6, 11]. In this paper, we investigate this idea by employing the line graph of the bipartite graph.

Meyer [2] circumvented the triviality of quantum cellular automata by relaxing the homogeneity condition. He proposed an one-dimensional quantum cellular automata driven by staggered unitary operators, which can be transposed as a coinless QW on the line or cycle. The connection of this model with the staggered lattice fermion formalism was analyzed in [12] for the two-dimensional case and applied for spatial searching in [13]. The staggered model was rediscovered by Falk [14], who suggested a simple method of obtaining the evolution operator by splitting the vertices of the graph into disjoint polygons that tessellate the two-dimensional lattice. Falk also proposed a searching method, which was used by [15] to prove analytically that the staggered model finds a marked vertex in time \(O(\sqrt{N\log N})\) for a two-dimensional lattice with N vertices matching the performance achieved by other forms of QWs on this graph. The detailed dynamics of the one-dimensional staggered model was analyzed in [16], and the moments of the probability distribution function in [17]. The connection between the coined and the staggered one-dimensional QWs was analyzed in [16, 18, 19]. Further analysis on this connection is an important research topic.

In this paper, we formally define the staggered QW model on graphs by using tessellations so that each tessellation covers all vertices with non-overlapping polygons and the tessellation union covers all edges. The maximal cliques play an essential role in building the tessellation because adjacent vertices are reachable for the walker’s hopping. If two or more maximal cliques share a common vertex, each clique must be inside a different tessellation. The evolution operator is a product of orthogonal reflections that have a one-to-one correspondence with the tessellations producing a diffusion through the maximal cliques in a staggered way. After the action of the evolution operator with a localized initial condition, the wave function spreads to all vertices reachable by the graph structure, which is the clique with the starting location and the adjacent maximal cliques for the case with two reflections. We also discuss a generalized form of staggered QW using partial tessellations which can be used for spatial search algorithms in the sense that the walker will search for the vertices inside the missing polygons. The complete dynamics is obtained by applying the evolution operator recursively starting with some initial state and by performing a measurement at the end.

After formally defining the staggered model, we show that Szegedy’s QWs on a bipartite graph \(\Gamma \) are staggered QWs on the line graph of \(\Gamma \) with a restricted form of tessellation. The restriction is: The polygons must share only one vertex. The converse is also true. Any staggered QW with tessellations that share one vertex in the polygon intersections can be cast into an extended version of Szegedy’s model with complex amplitudes. This result sheds light on the structure of Szegedy’s model and explains the meaning of the fact that a Szegedy’s QW is a hopping on the edges of the bipartite graph rather than on the vertices. We also show that there are generalized staggered QWs that reproduce the searching model proposed by Szegedy. In this case, we need to use partial tessellations and the walker looks for vertices inside missing polygons, which are the ones returned by the measurement. On the other hand, if we allow two or more vertices in at least one polygon intersection, we define instances of staggered QWs that cannot be cast into Szegedy’s framework. We give special attention to those instances.

Falk [14] proposed an evolution operator for a searching model on the two-dimensional lattice by interlacing a reflection around the marked vertices with the orthogonal reflections generated by the tessellations. We use this searching model to define the hitting time on staggered QWs on finite graphs by generalizing Szegedy’s definition, and we describe how to obtain the eigenvalues and eigenvectors of the evolution operator using the discriminant matrix generated by the inner product of the polygons of the tessellations. We show that the evolution operator with marked vertices can be written as a product of two orthogonal reflections, and if an entire polygon is marked, the walker is not able to find it.

The structure of the paper is as follows. In Sect. 2, we define the staggered QW model and discuss generalizations that are useful for searching algorithms. In Sect. 3, we review Szegedy’s QW model with the goal of finding the connection with the staggered QW model. In Sect. 4, we show that Szegedy’s model is a restricted form of staggered QWs and we characterize when staggered walks cannot be cast into Szegedy’s framework. In Sect. 5, we define the hitting time on the staggered model using reflection operators around the marked vertices. In Sect. 6, we analyze the eigenvalues and eigenvectors of the evolution operator for spatial search algorithms based on reflections around the marked vertices. In Sect. 7, we draw our conclusions.

Fig. 1
figure 1

Examples of tessellations for the 10-cycle and a glued triangle tree with 22 vertices: a depicts tessellations with polygons of size 2 for the cycle and b depicts tessellations with polygons of size 3 (except for two vertices) for the glued triangle tree. \(U_0\) is associated with the blue tessellation (solid line), and \(U_1\) is associated with the red tessellation (dashed line). a Cycle with 2-site polygons, b glued triangle tree (Color figure online)

Full size image

2 Staggered quantum walks

Inspired by Falk’s paper [14], we define the staggered quantum walk on a graph \(\Gamma \) with N verticesFootnote 1 by using two (or more) independent graph tessellations. Each tessellation uses non-overlapping (non-planar) polygons of adjacent vertices which need not to have the same shape, and a polygon may contain only one vertex. The set of polygons of each tessellation need to cover all vertices of the graph, and the tessellation union must cover all edges. Two polygons in different tessellations necessarily overlap, and some (or all) intersections may contain more than one vertex. Each polygon defines a unit vector in the Hilbert space \({\mathcal {H}}^{N}\) by superposing the vertices in the polygon with nonzero amplitudes. Examples of tessellations are depicted in Figs. 1 and 2.

The staggered quantum walk with two tessellations called \(\alpha \) and \(\beta \) is defined by the evolution operator

$$\begin{aligned} U \,=\, U_1 U_0, \end{aligned}$$
(1)

where

$$\begin{aligned} U_0= & {} 2\sum _{k=0}^{m-1} \big | \alpha _k \big \rangle \big \langle \alpha _k \big | - I, \end{aligned}$$
(2)
$$\begin{aligned} U_1= & {} 2\sum _{k=0}^{n-1} \big | \beta _k \big \rangle \big \langle \beta _k \big | - I, \end{aligned}$$
(3)

and m and n are the number of polygons in each tessellation, and

$$\begin{aligned} \big | \alpha _k \big \rangle= & {} \sum _{k'\in \alpha _k} a_{k,k'} \big | k' \big \rangle , \end{aligned}$$
(4)
$$\begin{aligned} \big | \beta _k \big \rangle= & {} \sum _{k'\in \beta _k} b_{k,k'} \big | k' \big \rangle , \end{aligned}$$
(5)

where \(a_{k,k'}\) and \(b_{k,k'}\) are nonzero complex amplitudes of the unit vectors \(\big | \alpha _k \big \rangle \) and \(\big | \beta _k \big \rangle \) in \({\mathcal {H}}^{N}\) and \(\big | k' \big \rangle \) belongs to the computation basis of \({\mathcal {H}}^{N}\) and \(k'\in V\). Operators \(U_0\) and \(U_1\) are unitary and Hermitian \(\big (U_{0,1}^2=I\big )\) because each set of polygons is non-overlapping \(\big (\big \langle \alpha _k \big | \alpha _{k'} \big \rangle =\big \langle \beta _k \big | \beta _{k'} \big \rangle =\delta _{k k'}\big )\). It is straightforward to show that

$$\begin{aligned} U\big | k \big \rangle = 4 \sum _{k',k''} D^*_{k'k''} a^*_{k'k}\big | \beta _{k''} \big \rangle - 2\sum _{k''}b^*_{k''k}\big | \beta _{k''} \big \rangle - 2\sum _{k'}a^*_{k'k}\big | \alpha _{k'} \big \rangle + \big | k \big \rangle , \end{aligned}$$
(6)

where \(D_{k'k''}=\big \langle \alpha _{k'} \big | \beta _{k''} \big \rangle \), \(k'\) runs from 0 to \(m-1\), \(k''\) from 0 to \(n-1\), and k from 0 to \(N-1\).

Since the concept of tessellation plays a key role in the definition of staggered QWs, we give a precise definition of this concept. Define tessellations \(\alpha =\bigoplus _{k=0}^{m-1} A_k\) and \(\beta =\bigoplus _{k'=0}^{n-1} B_{k'}\) of graph \(\Gamma (V,E)\) by imposing the following conditions:

  1. 1.

    \(\bigoplus _{k=0}^{m-1} V(A_k)\,=\,\bigoplus _{k'=0}^{n-1} V(B_{k'})\,=\,V(\Gamma )\).

  2. 2.

    \(\bigoplus _{k=0}^{m-1} E(A_k)\,\cup \,\bigoplus _{k'=0}^{n-1} E(B_{k'})\,=\,E(\Gamma )\).

  3. 3.

    For any \(V(A_k)\), there exists a \(V(B_{k'})\) such that \(V(A_k)\cap V(B_{k'})\ne \emptyset \) and vice-versa.

  4. 4.

    For any k and \(k'\), \(A_k\) and \(B_{k'}\) are cliques.

The Hilbert space is spanned by the computational basis associated with the vertices, that is, \({\mathcal {H}}=\text {span}\{\big | k \big \rangle :\,k\in V(\Gamma )\}\). Let \({\mathcal {A}}_{k}=\text {span}\{\big | k' \big \rangle :\,k'\in V(A_{k})\}\) and \({\mathcal {B}}_{k'}=\text {span}\{\big | k \big \rangle :\,k\in V(B_{k'})\}\) be vector spaces and choose normalized vectors \(\big | \alpha _k \big \rangle \in {\mathcal {A}}_{k}\) and \(\big | \beta _{k'} \big \rangle \in {\mathcal {B}}_{k'}\) for every k and \(k'\). After choosing those vectors, define operators \(U_0\) and \(U_1\) via Eqs. (2) and (3). The evolution operator of the staggered QW is \(U_1 U_0\).

Fig. 2
figure 2

Example of tessellations with polygons of size 4 on a non-planar regular graph of degree 6. \(U_0\) is associated with the blue tessellation (solid line), and \(U_1\) is associated with the red tessellation (dashed line) (Color figure online)

Full size image

In order to give an alternative form of the definition of staggered QWs, let us define the notion of orthogonal reflection of a graph.

Definition 2.1

A unitary and Hermitian operator U is called an orthogonal reflection of a graph if the eigenvectors of U associated with eigenvalue 1 have non-overlapping nonzero entries and the sum of those eigenvectors has no zero entries in the orthonormal basis associated with the vertices of the graph.

This definition is basis independent because a basis change keeps the orthogonal reflection invariant and changes the orthonormal basis associated with the graph. A staggered QW on a graph \(\Gamma \) can be alternatively defined by a unitary evolution operator that is a product of orthogonal reflections of \(\Gamma \) that covers the edges of the graph. Given an orthogonal reflection in the basis of \({\mathcal {H}}^N\) associated with the vertices of \(\Gamma \), it is possible to build a disconnected N-graph as a disjoint union of cliques, where each clique is associated with an eigenvector with eigenvalue 1 and the clique is formed with the vertices that have nonzero amplitudes. Each clique defines a polygon, and the set of polygons is the tessellation associated with this orthogonal reflection. The product of orthogonal reflections defines the final graph after the union (and merging) of the edges of all cliques. This final graph must be equal to \(\Gamma \). The union of the tessellations does not have disposable edges in the sense that every edge is inside a polygon of some tessellation.

It is tempting to remove the requirement that the polygons must be cliques. The removal of this requirement is troublesome because after one application of the unitary operator \(U_0\) (or \(U_1\)) with non-clique polygons, the walker can go to non-adjacent vertices. In quantum walk models, we expect that the walker only hops to adjacent vertices, and successive applications of shift operators move the walker to distant locations. Our definition does not permit the tessellations used by Falk in Ref. [14], which were also used by Ambainis et al. in Ref. [15] and Patel et al. in Refs. [12, 13]. Those papers go against the requirement described in Ref. [20], which states that a general form of quantum walks must respect the structure of the graph. The tessellations used in those references in fact refer to the graph depicted in Fig. 2. For the two-dimensional lattice (with degree 4), it is necessary to use at least four tessellations because every vertex belongs to four maximum cliques of size two.

It is also tempting to remove the requirement that all edges must be inside of a polygon. The removal of this requirement is troublesome because it generates a logical indeterminacy, similar to one in the discussion about the use of non-clique polygons in the previous paragraph. If an edge is not inside a polygon, it means that it can be removed generating no change in the dynamics. In this case, non-isomorphic graphs would have exactly the same dynamics and would lead to confusion and logical problems.

2.1 Generalized staggered quantum walks

Usually quantum walk models are defined with no marked vertices. In this case, the dynamics has no special vertex and the amplitude associated with some specific vertex will not increase above average unless the initial condition is a special one. For instance, the coined model defined in Ref. [20] has those characteristics. The standard definition must be changed in order to mark a vertex. In the coined case, the coins for the marked vertices are different from the coins for non-marked vertices [21].

We can extend the staggered quantum walk definition by removing the requirement that each tessellation must cover the entire graph. It is allowed to use partial tessellations so that the partial-tessellation union covers all vertices (not necessarily all edges). The vertices that are not inside all tessellations are the marked ones. An equivalent way of obtaining the same extension is by allowing zero amplitudes in the entries of polygons \(\alpha _k\) and \(\beta _k\). The goal of this generalization is to define search algorithms. For example, Grover’s algorithm [22] can be seen as a generalized staggered quantum walk on the complete graph in the following way: Tessellation \(\alpha \) has polygons of size one for each non-marked vertex, and tessellation \(\beta \) has only one polygon with all vertices. The vertices that do not belong to tessellation \(\alpha \) are the marked ones. The evolution operator of this generalized staggered model is equal to the one used in Grover’s algorithm.

3 Szegedy’s quantum walks

In this section, we review Szegedy’s QW model with the goal of finding the connection with the staggered QW model. Consider a connected bipartite graph \(\Gamma (X,Y,E)\), where X, Y are disjoint sets of vertices and E is the set of non-directed edges. Let

$$\begin{aligned} \left( \begin{array}{cc} 0 &{} A \\ A^T &{} 0 \end{array}\right) \end{aligned}$$
(7)

be the biadjacency matrix of \(\Gamma (X,Y,E)\). Using A, define P as a probabilistic map from X to Y. Using \(A^T\), define Q as a probabilistic map from Y to X. If P is an \(m\times n\) matrix, Q will be an \(n\times m\) matrix, both are right-stochastic with the property that each row sums to 1.

To define a quantum walk on the bipartite graph, we associate it with a Hilbert space \({\mathcal {H}}^{m n} = {\mathcal {H}}^{m}\otimes {\mathcal {H}}^{n} \), where \( m = | X |\) and \(n = | Y | \), the computational basis of which is \( \big \{\big | x, y \big \rangle : x \in X, y \in Y \big \} \). Szegedy’s quantum walk is defined by the evolution operator

$$\begin{aligned} W \,=\, R_1 \, R_0, \end{aligned}$$
(8)

where

$$\begin{aligned} R_0= & {} 2\sum _x \big | \phi _x \big \rangle \big \langle \phi _x \big | - I, \end{aligned}$$
(9)
$$\begin{aligned} R_1= & {} 2\sum _y\big | \psi _y \big \rangle \big \langle \psi _y \big | - I, \end{aligned}$$
(10)

and

$$\begin{aligned} \big | \phi _x \big \rangle= & {} \sum _{y\in Y} \sqrt{p_{x y}} \, \big | x,y \big \rangle , \end{aligned}$$
(11)
$$\begin{aligned} \big | \psi _y \big \rangle= & {} \sum _{x\in X} \sqrt{q_{y x}} \, \big | x,y \big \rangle . \end{aligned}$$
(12)

It is straightforward to show that

$$\begin{aligned} W \big | x,y \big \rangle= & {} 4 \sqrt{p_{x y}}\sum _{y'\in Y} C_{y'x} \big | \psi _{y'} \big \rangle - 2\sqrt{q_{y x}}\big | \psi _{y} \big \rangle - 2 \sqrt{p_{x y}}\big | \phi _{x} \big \rangle + \big | x,y \big \rangle , \end{aligned}$$
(13)

where \(C_{yx}=\big \langle \psi _y \big | \phi _x \big \rangle \). For a detailed review see [23].

4 Equivalence between Szegedy’s and staggered QWs

In this section, we show that any instance of Szegedy’s model is equivalent to a staggered quantum walk version. The converse is not true. We show that some instances of the staggered quantum walk model are equivalent to Szegedy’s model, and we characterize when staggered walks cannot be cast into Szegedy’s framework.

4.1 Szegedy’s walks are staggered walks!

Although Szegedy’s model is defined on the Hilbert space \({\mathcal {H}}^{mn}\) associated with a bipartite graph \(\Gamma (X,Y,E)\), the dynamics takes place in the subspace spanned by the edges of \(\Gamma \). W acts trivially on vectors \(\big | x,y \big \rangle \) that do not belong to the bipartite graph and the initial condition does not include those edges. In this section, we show how to define a staggered QW based on generic stochastic matrices P and Q equivalent to Szegedy’s QW.

Let N be the number of edges of \(\Gamma \). Define two sets of polygons in the line graph \(L(\Gamma )\) by

$$\begin{aligned} \big | \alpha _x \big \rangle= & {} \sum _{y\in Y} \sqrt{p_{x y}} \, \big | f(x,y) \big \rangle , \end{aligned}$$
(14)
$$\begin{aligned} \big | \beta _y \big \rangle= & {} \sum _{x\in X} \sqrt{q_{y x}} \, \big | f(x,y) \big \rangle , \end{aligned}$$
(15)

where f is a bijection between the edge set E of \(\Gamma \) and the labels k of \(L(\Gamma )\), which has associated the Hilbert space \({\mathcal {H}}^{N}\) with the computational basis \(\big \{\big | k \big \rangle \), \(k=0,...,N-1\big \}\). Each polygon \({\alpha _x}\) is a clique, and the union of polygons \(\alpha _x\) tessellates \(L(\Gamma )\). The same is true for polygons \({\beta _y}\).

Suppose that \(f(x,y)=k\), where \(\{x,y\}\in E\). Then

$$\begin{aligned} U\big | k \big \rangle =\left( 2\sum _{y'=0}^{n-1} \big | \beta _{y'} \big \rangle \big \langle \beta _{y'} \big | - I\right) \left( 2\sum _{x'=0}^{m-1} \big | \alpha _{x'} \big \rangle \big \langle \alpha _{x'} \big | - I\right) \big | f(x,y) \big \rangle . \end{aligned}$$
(16)

Using that \(\big \langle \alpha _{x'} \big | f(x,y) \big \rangle =\sqrt{p_{xy}}\delta _{xx'}\) and \(\big \langle \alpha _{y'} \big | f(x,y) \big \rangle =\sqrt{q_{yx}}\delta _{yy'}\), we obtain

$$\begin{aligned} U\big | k \big \rangle = 4 \sqrt{p_{x y}}\sum _{y'} \big \langle \beta _{y'} \big | \alpha _x \big \rangle \big | \beta _{y'} \big \rangle - 2\sqrt{q_{y x}}\big | \beta _{y} \big \rangle - 2 \sqrt{p_{x y}}\big | \alpha _{x} \big \rangle + \big | f(x,y) \big \rangle . \end{aligned}$$
(17)

Eqs. (17) and (13) are essentially the same results if we apply bijection f to the labels (x, y) of the kets \(\big | x,y \big \rangle \) of Eq. (13). This proves

Proposition 4.1

Any instance of Szegedy’s quantum walk model on a bipartite graph \(\Gamma \) is equivalent to a staggered quantum walk version on the line graph of \(\Gamma \).

Notice that U and W are identical only when \(\Gamma \) is the complete bipartite graph. For all other bipartite graphs, the non-edges between X and Y span a subspace that plays no role in Szegedy’s model except to increase the dimension of W.

4.2 Which staggered QWs are instances of Szegedy’s model?

Consider a staggered quantum walk on a N-graph \(\Gamma '\) with the following restriction: The intersections of polygons belonging to different tessellations contain one vertex. If polygons \(\alpha _{k}\) and \(\beta _{k'}\) share one vertex, the ket label of this vertex in Szegedy’s model will be \(\big | k,k' \big \rangle \). Because all vertices must be in both tessellations, this labeling method establishes a bijection \(f'\) between the computational basis of \({\mathcal {H}}^{N}\) used in the staggered model and the set of labels of the form \(\big | k,k' \big \rangle \), that will be used to build an instance of Szegedy’s model on a bipartite graph \(\Gamma \), the line graph of which is \(\Gamma '\).Footnote 2 By construction, the set of labels of the form \(\big | k,k' \big \rangle \) belonging to polygon \(\alpha _{k}\) shares the same value of k with different values of \(k'\). After applying the bijection \(f'\) to the kets of polygon \(\alpha _{k}\), we obtain a vector \(\big | \tilde{\alpha }_k \big \rangle \) in \({\mathcal {H}}^{m n}\) (m, n are the number of polygons in tessellations \(\alpha ,\beta \)) given by

$$\begin{aligned} \big | \tilde{\alpha }_k \big \rangle= & {} \sum _{k'} a_{k,k'} \big | k,k' \big \rangle , \end{aligned}$$
(18)

with the same amplitudes of the original polygon \(\alpha _{k}\), where \(k'\) runs over the subindices of polygons \(\beta _{k'}\) that have overlap with \(\alpha _{k}\), that is, \(\beta _{k'}\cap \alpha _k\ne \emptyset \). Analogously, after applying the bijection \(f'\) to the kets of polygon \(\beta _{k'}\), we obtain a vector \(\big | \tilde{\beta }_{k'} \big \rangle \) in \({\mathcal {H}}^{m n}\) which has same value of \(k'\) as in the second slot of the kets, and it is given by

$$\begin{aligned} \big | \tilde{\beta }_{k'} \big \rangle= & {} \sum _{k} b_{k',k} \big | k,k' \big \rangle , \end{aligned}$$
(19)

where k runs over the subindices of polygons \(\alpha _{k}\) that have overlap with \(\beta _{k'}\), that is, \(\alpha _k\cap \beta _{k'}\ne \emptyset \).

We must consider a second restriction regarding the amplitudes \(a_{k,k'}\) and \(b_{k',k}\) of the staggered model. We assume that \(a_{k,k'} \) and \(b_{k',k}\) are nonnegative real numbers obeying the constraints \(\sum _{k'} a_{k,k'}^2 = 1\) and \(\sum _{k} b_{k',k}^2=1\), that is, \(\big | \tilde{\alpha }_{k} \big \rangle \) and \(\big | \tilde{\beta }_{k'} \big \rangle \) are real unit vectors. After imposing this restriction, such instances of the staggered quantum walk model can be put into the standard Szegedy’s framework. In fact, the evolution driven by U, which is defined using \(\big | \alpha _{k} \big \rangle \) and \(\big | \beta _{k} \big \rangle \) with the restricted version of the amplitudes, is equivalent to the evolution driven by W using \(\big | \tilde{\alpha }_{k} \big \rangle \) and \(\big | \tilde{\beta }_{k'} \big \rangle \) instead of \(\big | \phi _{x} \big \rangle \) and \(\big | \psi _{y} \big \rangle \). The equivalence is brought out by applying bijection \(f'\) to the labels of the kets of \(U\big | k \big \rangle \) given by Eq. (6) and comparing with \(W\big | f'(k) \big \rangle \). The second restriction (real amplitudes) can be eliminated by a straightforward extension of Szegedy’s model, which is addressed in the next section.

The instances of the staggered quantum walk models that cannot be cast into Szegedy’s framework with the above method are those that have at least one overlapping polygons of tessellations \(\alpha \) and \(\beta \) with more than one vertex. To prove this fact, let \(\big | j_1 \big \rangle \) and \(\big | j_2 \big \rangle \) be kets associated with two vertices in the overlap between polygons \(\alpha _{k}\) and \(\beta _{k'}\). There is a contradiction because \(\big | j_1 \big \rangle \) and \(\big | j_2 \big \rangle \) must be mapped to kets of the form \(\big | k,k' \big \rangle \) both sharing the same label k and \(k'\). In fact, in order to build bijection \(f'\), we need to map \(\big | j_1 \big \rangle \) to \(\big | k,k'_1 \big \rangle \in {\mathcal {H}}^{m n}\) and \(\big | j_2 \big \rangle \) to \(\big | k,k'_2 \big \rangle \in {\mathcal {H}}^{m n}\) sharing the same k because both belong to polygon \(\alpha _{k}\). We have to take \(k'_1\ne k'_2\) because different vertices must have different labels. Besides, \(\big | j_1 \big \rangle \) and \(\big | j_2 \big \rangle \) belong also to polygon \(\beta _{k'}\), then labels \(k'_1\) and \(k'_2\) must be the same, which is a contradiction. Therefore, there is no bijection between the computational basis of \({\mathcal {H}}^{N}\) and the set of kets of the form \(\big | k,k' \big \rangle \) with the property of sharing the same k for polygons of tessellation \(\alpha \) and simultaneously sharing the same \(k'\) for polygons of tessellation \(\beta \).

The simplest non-trivial examples of staggered QWs that cannot be cast into Szegedy’s framework are obtained on the graph with only two connected vertices (\(N=2\)). Take tessellations \(\big | \alpha \big \rangle =\big (\big | 0 \big \rangle +\big | 1 \big \rangle \big )/\sqrt{2}\) and \(\big | \beta \big \rangle =\big | \psi \big \rangle \), where

$$\begin{aligned} \big | \psi \big \rangle =\cos \frac{\theta }{2}\,\big | 0 \big \rangle +\sin \frac{\theta }{2}\,\big | 1 \big \rangle , \end{aligned}$$

for some angle \(\theta \) that is not a rational multiple of \(\pi \). The evolution operator is

$$\begin{aligned} U=\left[ \begin{array}{cc} \sin \theta &{}\cos \theta \\ -\cos \theta &{}\sin \theta \end{array} \right] , \end{aligned}$$

which is non-trivial because there is no integer r such that \(U^r=I\). On the other hand, any Szegedy’s quantum walk W on any graph with two edges is trivial because \(W^2=I\). Notice that we do not need to go back to Szegedy’s framework to prove this result because we can use the equivalent staggered versions. This proves

Proposition 4.2

There are instances of the staggered quantum walk model with two tessellations that cannot be cast into Szegedy’s quantum walk framework. Those instances have at least one polygon intersection with at least two vertices in common.

For example, the glued triangle tree of Fig. 1 cannot be cast into Szegedy’s framework because it is not a line graph. Even if it was the line graph of a bipartite graph, it would not be possible to obtain an equivalent Szegedy’s QW because there are polygons intersections with two vertices in common.

An alternative proof of the above proposition in terms of graph theory [25] is as follows. If the quantum walk graph \(\Gamma \) is not a line graph, by inspection we verify that the nine forbidden Beineke induced subgraphs [26] require either tessellations with two vertices in common or at least three tessellations. If graph \(\Gamma \) is a line graph, then it has a Krausz partition [27]. If the Krausz partition is two-colorable, \(\Gamma \) is a line graph of a bipartite graph and can be reduced to Szegedy’s framework by using Eqs. (18) and (19). If the Krausz partition is not two-colorable, \(\Gamma \) requires either tessellations with two vertices in common or at least three tessellations.

4.3 Extension of Szegedy’s model

Szegedy’s model can be easily extended by allowing phases in vectors

$$\begin{aligned} \big | \phi _x \big \rangle= & {} \sum _{y\in Y} \sqrt{p_{x y}}\,\text {e}^{i\theta _{xy}} \, \big | x,y \big \rangle , \end{aligned}$$
(20)
$$\begin{aligned} \big | \psi _y \big \rangle= & {} \sum _{x\in X} \sqrt{q_{y x}}\,\text {e}^{i\theta '_{xy}} \, \big | x,y \big \rangle . \end{aligned}$$
(21)

Entries \(p_{x y},q_{y x}\) are nonnegative real numbers obeying the constraints \(\sum _y p_{x y}=\sum _x q_{y x}=1\), as in the original model. It is straightforward to show that W is unitary in the extended case. Using the same algorithm of Sect. 4.2, we conclude that any staggered quantum walk with the property that the intersections of polygons belonging to different tessellations contain one vertex is equivalent to an instance of the extended version of Szegedy’s model. This proves

Proposition 4.3

Any instance of the staggered quantum walk model with two tessellations which has only one vertex in common in each polygon intersection can be cast into the extended version of Szegedy’s quantum walk framework.

Notice that a staggered quantum walk model on a graph \(\Gamma \) with two tessellations which have only one vertex in common in each polygon intersection has a two-colorable Krauz partition. Therefore \(\Gamma \) is a line graph of a bipartite graph.

4.4 Searching in Szegedy’s model

Szegedy’s model can be used to search for a vertex in a set of marked vertices in some graph \(\Gamma \). The strategy is an extension of the classical method, which uses random walks on the same graph. The key concept in the classical case is the hitting time, which is the average time to hit a marked vertex for the first time using a random walk with stochastic (or transition) matrix P after specifying some initial condition. There is a clever way to find the classical hitting time using the following idea: Convert the original graph \(\Gamma \) into a new directed graph \(\Gamma '\) (with a new stochastic matrix \(P'\)) by removing the edges that leave the marked vertices. Marked vertices are converted into sinks. The hitting time obtained using \(P'\) is the same using P because as soon as the walker hits a marked vertex using some edge that comes from a non-marked vertex, the walker needs not to go ahead. The advantage of using \(P'\) is that it does not have eigenvectors associated with eigenvalue 1 (the spectral norm is smaller than 1), that is, \(I-P'\) is an invertible matrix. We need to invert \(I-P'\) to find the hitting time if we want to avoid the calculation of the limiting probability distribution.

Szegedy proposed a quantum version of this procedure. Let \(\Gamma (X,E)\) be the original graph, where X is the set of vertices and E the set of edges. Define \(\Gamma (X,X',E')\) as a bipartite graph obtained from \(\Gamma (X,E)\) by duplicating X and by converting edges \(\{x_i,x_j\}\in E\) into \(\{x_i,x'_j\}\in E'\). Until this point, no vertex has been marked and the quantum walk described in Sect. 3 can be used taking \(P=Q\). As before, define \(\Gamma '(X,X',E')\) as a directed bipartite graph by removing the edges of \(\Gamma (X,X',E')\) that leaves the marked vertices of X and \(X'\). Add new non-directed edges connecting a marked x with its corresponding copy \(x'\) for all marked vertices. The quantum walk described in Sect. 3 can be used taking \(P'=Q'\), where \(P'\) and \(Q'\) are the new stochastic matrices of \(\Gamma '(X,X',E')\). With this framework and taking

$$\begin{aligned} \big | \psi _0 \big \rangle =\frac{1}{\sqrt{n}}\sum _{x y} \sqrt{p_{x y}} \big | x,y \big \rangle \end{aligned}$$
(22)

as initial condition in \({\mathcal {H}}^{n}\otimes {\mathcal {H}}^{n}\), Szegedy showed that the detection problem on \(\Gamma '(X,X',E')\) can be solved with a quadratic speedup compared to the time complexity of the same problem using random walks with symmetric and ergodic stochastic matrix P in \(\Gamma (X,E)\) [4].

The method of converting Szegedy’s QWs into staggered QWs described in Sect. 4.1 can be used in the searching context after some minor modifications. Let \(L(\Gamma )\) be the line graph of \(\Gamma (X,X',E')\) and define polygons \(\alpha _x\) and \(\beta _y\) as the ones in Eqs. (14) and (15) for all x and y that do not belong to the set of marked vertices. Those sets of polygons define partial tessellations of \(L(\Gamma )\) which is used to define a generalized staggered QW equivalent to Szegedy’s QW on \(\Gamma '(X,X',E')\). The initial condition in \({\mathcal {H}}^{N}\) must be

$$\begin{aligned} \big | \psi _0 \big \rangle =\frac{1}{\sqrt{n}}\sum _{x y} \sqrt{p_{x y}} \big | f(x,y) \big \rangle , \end{aligned}$$
(23)

where f is the bijection from the E to the labels of \(L(\Gamma )\).

The last ingredient in Szegedy’s QW is the measurement, which is performed in the computational basis of X. At this moment, the copy \(X'\) is traced out. If the measurement is performed at the right time, which is the quantum hitting time, the probability of finding a marked vertex will be high enough. The version using generalized staggered QWs is obtained as follows. For \(x\in X\) define projectors

$$\begin{aligned} \Pi _x=\sum _{x'\in \alpha _x}\big | x' \big \rangle \big \langle x' \big |. \end{aligned}$$
(24)

Notice that \(\sum _x \Pi _x=I\). By measuring observable

$$\begin{aligned} {\mathcal {O}}=\sum _{x\in X} x \Pi _x, \end{aligned}$$
(25)

we obtain some value \(x_0\in X\), which is expected to be one of the marked vertices if the measurement is performed at the hitting time. In the staggered version, we are looking for the missing polygons of the (partial) \(\alpha \)-tessellation. This proves

Proposition 4.4

Szegedy’s searching framework on a bipartite graph \(\Gamma \) can be simulated by instances of generalized staggered quantum walks on the line graph of \(\Gamma \).

5 Hitting time on staggered walks

We have showed that any instance of the extended Szegedy’s model can be cast into an equivalent staggered quantum walk. The converse statement is not true. There are instances of staggered walks that are not equivalent to any instance of the extended version of Szegedy’s model. We take advantage of the similarity of both models to define a notion of hitting time on the staggered model, which is specially useful on those staggered walks that cannot be cast into Szegedy’s framework.

Let M be the set of marked vertices. Inspired again by Falk’s paper [14], the evolution operator \(U_M\) for searching a marked vertex is defined by

$$\begin{aligned} U_M = R_M U_1 R_M U_0, \end{aligned}$$
(26)

where

$$\begin{aligned} R_M = 2\sum _{m\in M} \big | m \big \rangle \big \langle m \big | - I. \end{aligned}$$
(27)

\(R_M\) is an orthogonal reflection and flips non-marked vertices.

Definition 5.1

The quantum hitting time \(H_M\) of a staggered quantum walk starting from the initial condition \(\big | \psi (0) \big \rangle \) is the smallest number of steps T such that

$$\begin{aligned} \frac{1}{T+1}\sum _{t=0}^{T}\left\| \, \big | \psi (t) \big \rangle -\big | \psi (0) \big \rangle \, \right\| ^2\ge 1-\frac{|M|}{N}, \end{aligned}$$
(28)

where \(\big | \psi (t) \big \rangle =(U_M)^t\big | \psi (0) \big \rangle \) and N is the number of vertices.

The hitting time depends on the initial condition. An important one in this context is the uniform distribution because the value \(1-|M|/N\) is the distance between the uniform distribution over all vertices and the uniform distribution over the marked vertices.

6 Searching using staggered walks

\(R_M\) can be interpreted as an operator associated with a partial tessellation with |M| polygons each one with one marked vertex. There is a simpler way to analyze the evolution operator (26) by using the fact that \(R_M U_1 R_M\) is an orthogonal reflection.

Proposition 6.1

The evolution operator \(U_M\) for searching a marked vertex using a staggered quantum walk is a product of two orthogonal reflections.

Proof

Define \(U'_1=R_M U_1 R_M\). Using Eq. (3), we obtain

$$\begin{aligned} U'_1= 2\sum _{k=0}^{n-1} \big | \beta '_k \big \rangle \big \langle \beta '_k \big | - I, \end{aligned}$$
(29)

where \(\big | \beta '_k \big \rangle =R_M\big | \beta _k \big \rangle \). Using Eq. (5), we obtain

$$\begin{aligned} \big | \beta '_k \big \rangle = {\left\{ \begin{array}{ll} -\big | \beta _k \big \rangle ,&{} \text {if } \beta _k \cap M = \emptyset \\ {\sum }_{k'=0}^{n-1} (-1)^{f(k')} b_{k k'}\big | k' \big \rangle ,&{} \text {otherwise}, \end{array}\right. } \end{aligned}$$
(30)

where \(f(k)=0\) if \(k\in M\) and \(f(k)=1\) otherwise. Therefore \(U_M=U'_1 \, U_0\), and using Eqs. (29) and (30) it is straightforward to verify that \(U'_1\) is an orthogonal reflection. \(\square \)

Next proposition shows that if we mark all vertices inside some polygons of tessellation \(\alpha \) or \(\beta \), the walker is not able to find a marked polygon.

Proposition 6.2

If the set of marked vertices is a union of polygons of tessellation \(\beta \), then \(U_M=U\). If the set of marked vertices is a union of polygons of tessellation \(\alpha \), then \(U_M\) is similar to U.

Proof

If the set of marked vertices is a union of polygons of tessellation \(\beta \), Eq. (30) reduces to

$$\begin{aligned} \big | \beta '_k \big \rangle = {\left\{ \begin{array}{ll} -\big | \beta _k \big \rangle ,&{} \text {if } \beta _k \cap M = \emptyset \\ \big | \beta _k \big \rangle ,&{} \text {otherwise}. \end{array}\right. } \end{aligned}$$
(31)

Substituting into Eq. (29), we obtain that \(U'_1=U_1\). Therefore \(U_M=U\).

The proof of the second statement is analogous. Define \(U'_0=R_M U_0 R_M\). Using Eq. (2), we obtain

$$\begin{aligned} U'_0= 2\sum _{k=0}^{m-1} \big | \alpha '_k \big \rangle \big \langle \alpha '_k \big | - I, \end{aligned}$$
(32)

where \(\big | \alpha '_k \big \rangle =R_M\big | \alpha _k \big \rangle \). If the set of marked vertices is a union of polygons of tessellation \(\alpha \), then using Eq. (4) we obtain

$$\begin{aligned} \big | \alpha '_k \big \rangle = {\left\{ \begin{array}{ll} -\big | \alpha _k \big \rangle ,&{} \text {if } \alpha _k \cap M = \emptyset \\ \big | \alpha _k \big \rangle ,&{} \text {otherwise}. \end{array}\right. } \end{aligned}$$
(33)

Therefore \(U'_0=U_0\) and \(U_M=R_M\,U\, R_M\). \(\square \)

Useful properties of the QW dynamics are obtained from the spectrum of \(U_M\). The eigenvalues and eigenvectors can be obtained from the singular values and vectors of the discriminant (or Gram-like) matrix D the entries of which are

$$\begin{aligned} D_{k\,k'}=\big \langle \alpha _{k} \big | \beta '_{k'} \big \rangle , \end{aligned}$$
(34)

where \(\big | \alpha _{k} \big \rangle \) is given by Eq. (4) and \(\big | \beta '_{k'} \big \rangle \) is given by Eq. (30). Let \(\big | \nu _j \big \rangle \) and \(\big | \mu _j \big \rangle \) be the right and left singular vectors of D, respectively, and let \(\cos \theta _j\) be the corresponding singular values obeying \(D\big | \nu _j \big \rangle =\cos \theta _j\big | \mu _j \big \rangle \) and \(D^\dagger \big | \mu _j \big \rangle =\cos \theta _j\big | \nu _j \big \rangle \) and \(0\le \theta _j\le \pi /2\). Suppose that \(\theta _1,...,\theta _s\) are the angles in the open interval \((0,\pi /2)\), where s is the number of singular values of D in the open interval (0, 1). Define

$$\begin{aligned} A= & {} \sum _{k=0}^{m-1} \big | \alpha _k \big \rangle \big \langle k \big |, \end{aligned}$$
(35)
$$\begin{aligned} B= & {} \sum _{k'=0}^{n-1} \big | \beta '_{k'} \big \rangle \big \langle k' \big |. \end{aligned}$$
(36)

Let \({\mathcal {A}},{\mathcal {B}}\) be the vector spaces spanned by vectors \(\big | \alpha _{k} \big \rangle \) and vectors \(\big | \beta '_{k'} \big \rangle \), respectively. We reproduce a theorem from [4] adapted to our context.

Theorem 6.3

The spectrum of \(U_M\) obeys:

  1. 1.

    The eigenvalues of \(U_M\) with nonzero imaginary part are exactly \(\text {e}^{\pm 2i\theta _j}\) for \(j=1,...,s\). The corresponding normalized eigenvectors are

    $$\begin{aligned} \frac{A\big | \mu _j \big \rangle -\text {e}^{\pm i\theta _j}B\big | \nu _j \big \rangle }{\sqrt{2} \sin \theta _j}. \end{aligned}$$
    (37)
  2. 2.

    \({\mathcal {A}}\cap {\mathcal {B}}^\perp \,+\,{\mathcal {A}}^\perp \cap {\mathcal {B}}\) is the \(-1\) eigenspace of \(U_M\). \({\mathcal {A}}\cap {\mathcal {B}}^\perp \) is spanned by the left singular vectors of D with singular value 0. \({\mathcal {A}}^\perp \cap {\mathcal {B}}\) is spanned by the right singular vectors of D with singular value 0.

  3. 3.

    \({\mathcal {A}}\cap {\mathcal {B}}\,+\,{\mathcal {A}}^\perp \cap {\mathcal {B}}^\perp \) is the \(+1\) eigenspace of \(U_M\). \({\mathcal {A}}\cap {\mathcal {B}}\) is spanned by the left (or right) singular vectors of D with singular value 1.

The above theorem can be used to find most eigenvectors of the evolution operator when the singular values and vectors of the discriminant matrix can be explicitly found. The eigenvectors that span \({\mathcal {A}}^\perp \cap {\mathcal {B}}^\perp \) are not described in Theorem 6.3. The staggered Fourier transform is an alternative method to find the spectrum of \(U_M\), but it depends on translation symmetries of the tessellating process. The staggered Fourier transform was used in Refs. [15–17].

7 Conclusions and discussions

In this paper, we have formally defined the staggered QW model on graphs. This model can be obtained by tessellating the graph using polygons obeying locality restrictions. The polygons are cliques and each tessellation covers all vertices. All edges must be inside a polygon of some tessellation. An alternative equivalent definition is based on the notion of orthogonal reflections in the basis associated with the graph, which are unitary and Hermitian operators with the following property: The nonzero amplitudes of the eigenvectors associated with eigenvalue 1 do not have overlap, and the sum of those eigenvectors does not have zero entries. The evolution operator of staggered QWs must be a product of orthogonal reflections that covers all edges of the graph.

We have showed that any instance of Szegedy’s QW model on a bipartite graph \(\Gamma \) is equivalent to an instance of the staggered QW model on the line graph of \(\Gamma \) with a special kind of tessellations: There is only one vertex in each polygon intersection, and the tessellation union is a Krausz partition. On the other hand, there are instances of the staggered model with two tessellations that cannot be cast into Szegedy’s framework, which are the ones with two or more vertices in common in at least one polygon intersection. This characterization shows that Szegedy’s model is a restricted version of QWs, which is defined only on line graphs of bipartite graphs, a subset of perfect graphs. This fact helped researchers to obtain generic results using Szegedy’s model, different from the results about the coined version, which is usually found in specific graphs. One of the main results of Szegedy’s model is that the quantum hitting time is quadratically smaller compared with the classical hitting time on symmetric and ergodic Markov chains. Notice that the classical random walk is defined on a graph \(\Gamma \), while the quantum walk is defined on the line graph of the bipartite graph associated with \(\Gamma \). When the expressions for the hitting time on different graphs are compared, they have the same structure and it is possible to reach the result.

There are two main forms of defining searching algorithms in the staggered model: (1) Searching à la Szegedy is the method that uses partial tessellations in the generalized staggered model. The marked vertices are the ones in the missing polygons. (2) Searching à la Falk uses the standard tessellation procedure but interlaces the orthogonal reflections with a reflection around the marked vertices. In both cases, we can use Szegedy’s spectral theorem to calculate the spectrum of the evolution operator when using two tessellations. We have also defined the quantum hitting time on staggered QWs using reflections around the marked vertices which generalizes Szegedy’s original definition. We have shown that the evolution operator, originally defined as a product of four reflections, can be written as a product of two reflections.

Because all vertices of the two-dimensional lattice belong to the intersection of four maximum cliques, it is necessary to employ at least four tessellations. The case with exactly four tessellations has one vertex in the polygon intersections but cannot be cast into Szegedy’s framework because it employs more than two tessellations. Future works on this issue are important to establish the properties of staggered QWs on two-dimensional lattices, the analysis of which is missing in literature.

An interesting subject is the equivalence between the staggered model and the coined quantum walk model. This has been established for the line and cycle [16, 18]. A systematic analysis on the equivalence of those models on generic graphs is an important issue for future works.