Discrete-time semiclassical Szegedy quantum walks

DOI10.1016/J.PHYSA.2023.129021arXiv2303.18202OpenAlexW4383645709MaRDI QIDQ6167724FDOQ6167724

Miguel A. Martín-Delgado, Sergio Ortega

Publication date: 7 August 2023

Published in: Physica A (Search for Journal in Brave)

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.

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)

Cites Work

• Optimization by Simulated Annealing
• Monte Carlo sampling methods using Markov chains and their applications
• Equation of State Calculations by Fast Computing Machines
• Title not available (Why is that?)
• Inequalities: theory of majorization and its applications
• The staggered quantum walk model
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum walks and search algorithms
• Title not available (Why is that?)
• Szegedy's quantum walk with queries
• Probability distributions for Markov chain based quantum walks
• Efficient quantum circuits for Szegedy quantum walks
• Implementation of quantum walks on IBM quantum computers
• Parameter estimation of gravitational waves with a quantum metropolis algorithm

Cited In (4)

• Discrete Lorentz covariance for quantum walks and quantum cellular automata
• Crossovers induced by discrete-time quantum walks
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• 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)