Discrete-time Semiclassical Szegedy Quantum Walks
arXiv:2303.18202 · doi:10.1016/j.physa.2023.129021
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.
arXiv commentRevTex 4.2, 16 pages, 11 color figures
References in corpus (18)
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Quantum speedup for active learning agents
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Google in a Quantum Network
- Quantum Google in a Complex Network
- The Staggered Quantum Walk Model
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- Efficient quantum circuits for Szegedy quantum walks
- Measurement induced quantum walks on an IBM Quantum Computer
- Measurement induced quantum walks
- Beyond Zeno: Approaching Infinite Temperature upon Repeated Measurements
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
- Probability distributions for Markov chains based quantum walks