Discrete-time semiclassical Szegedy quantum walks

DOI10.1016/J.PHYSA.2023.129021MaRDI QIDQ6167724zbMATH OpenOpenAlexFDO

Authors Sergio Ortega, Miguel A. Martín-Delgado

Publication date 7 August 2023

Published in Physica A (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random walkquantum computingquantum walkSzegedy quantum walksemiclassical walk

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Abstract: Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy's quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Efficient quantum circuits for Szegedy quantum walks
• Equation of state calculations by fast computing machines
• Google's PageRank and beyond. The science of search engine rankings
• Implementation of quantum walks on IBM quantum computers
• Inequalities: theory of majorization and its applications
• Monte Carlo sampling methods using Markov chains and their applications
• Optimization by simulated annealing
• Parameter estimation of gravitational waves with a quantum metropolis algorithm
• Probability distributions for Markov chain based quantum walks
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum walks and search algorithms
• Szegedy's quantum walk with queries
• The staggered quantum walk model

Cited in

(4)

• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Crossovers induced by discrete-time quantum walks
• Discrete Lorentz covariance for quantum walks and quantum cellular automata
• Equivalence of Szegedy's and coined quantum walks

This page was built for publication: Discrete-time semiclassical Szegedy quantum walks

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