The role of tessellation intersection in staggered quantum walks

DOI10.1007/S11047-019-09758-2zbMATH Open1530.81045arXiv1810.02387OpenAlexW2970890244WikidataQ127311775 ScholiaQ127311775MaRDI QIDQ6151197FDOQ6151197

Authors: R. A. M. Santos 

Publication date: 9 February 2024

Published in: Natural Computing (Search for Journal in Brave)

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.

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

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-嵌入交错量子游荡

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)

Cites Work

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

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)