The role of tessellation intersection in staggered quantum walks
- PDF / 1,252,806 Bytes
- 10 Pages / 595.276 x 790.866 pts Page_size
- 18 Downloads / 198 Views
(0123456789().,-volV)(0123456789(). ,- volV)
The role of tessellation intersection in staggered quantum walks Raqueline A. M. Santos1
Ó Springer Nature B.V. 2019
Abstract The staggered quantum walk (SQW) model is defined by partitioning the graph into cliques, which are called polygons. We analyze the role that the size of the polygon intersection plays on the dynamics of SQWs on graphs. We introduce two processes (intersection reduction and intersection expansion), that change the number of vertices in some intersection of polygons, and we compare the behavior of the SQW on the reduced or expanded graph in relation to the SQW on the original graph. We describe how the eigenvectors and eigenvalues of the evolution operators relate to each other. This processes can help to establish the equivalence between SQWs on different graphs and to simplify the analysis of SQWs. We also show an example of a SQW on a graph that is not included in Szegedy’s model, but which is equivalent to an instance of Szegedy’s model after applying the intersection reduction. Keywords Quantum walks Staggered model Tessellation intersection
1 Introduction The staggered quantum walk (SQW) model (Portugal et al. 2015) has been actively studied in the last years and its relation with other quantum walk models has already been established. Portugal et al. (2015) showed that Szegedy’s quantum walk model (Szegedy 2004) is included in the SQW model. Portugal (2016a) showed that many instances of coined QWs (Aharonov et al. 1993, 2001) can be cast into Szegedy’s model and therefore into the SQW model, including the abstract search algorithm scheme (Ambainis et al. 2005). Coutinho and Portugal (2018) showed that the SQW model is able to provide a natural discretization of a continuous time quantum walk (Farhi and Gutmann 1998) for some special class of graphs. In terms of physical implementation, Portugal et al. (2017) presented an extension of the SQW model that can be used for physical implementations in terms of time independent Hamiltonians. And Moqadam et al. (2017) proposed an implementation with superconducting
& Raqueline A. M. Santos [email protected] 1
Center for Quantum Computer Science, Faculty of Computing, University of Latvia, Raina Bulv. 19, Riga 1586, Latvia
microwave resonators. In terms of algorithmic applications, spatial quantum search was analyzed on the two dimensional lattice (Portugal and Fernandes 2017) and on hexagonal lattices (Chagas et al. 2018). The quantum algorithm for element distinctness was analyzed using the SQW model by Portugal (2018) obtaining optimal values for some critical parameters of Ambainis’ quantum algorithm (Ambainis 2004). A SQW on a graph is defined by a graph tessellation cover. A tessellation is a partitioning of the graph into cliques, called polygons. A tessellation cover is a set of tessellations that cover all the edges of the graph. We say that an edge belongs to a tessellation if both of its endpoints belong to the same polygon. See Fig. 1 for an example of a tessellation cover of a gr
Data Loading...
