2016/03/31 by Renato Portugal · 52 citations
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Computer science #Discrete mathematics #Formalism (music) #Graph #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum mechanics #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Statistics #math.CO #quant-ph
paper · pdf · doi:10.1103/physreva.93.062335
published in Physical Review A 93(6) (American Physical Society) · 14 pages, 9 figs
arxiv created 2016/06/04 · openalex publication_date 2016/06/27 · arxiv updated 2016/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.