The role of tessellation intersection in staggered quantum walks

DOI10.1007/S11047-019-09758-2MaRDI QIDQ6151197zbMATH OpenOpenAlexWikidataFDO

Authors R. A. M. Santos

Publication date 9 February 2024

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.02387

zbMATH Keywords

quantum walksstaggered modeltessellation intersection

Mathematics Subject Classification ID

Quantum computation (81P68) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random walks on graphs (05C81) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

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.

Recommendations

• The staggered quantum walk model
• The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
• The spectra of the unitary matrix of an n-tessellable staggered quantum walk on a graph
• The spectra of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
• 有限偶圈图上的 2-嵌入交错量子游荡

Cites work

• Coins make quantum walks faster
• Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
• Element distinctness revisited
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Quantum Walk Algorithm for Element Distinctness
• Quantum walks on graphs
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• The staggered quantum walk model

This page was built for publication: The role of tessellation intersection in staggered quantum walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151197)