SQUWALS: A Szegedy QUantum WALks Simulator
arXiv:2307.14314 · doi:10.1002/qute.202400022
Abstract
Szegedy's quantum walk is an algorithm for quantizing a general Markov chain. It has plenty of applications such as many variants of optimizations. In order to check its properties in an error-free environment, it is important to have a classical simulator. However, the current simulation algorithms require a great deal of memory due to the particular formulation of this quantum walk. In this paper we propose a memory-saving algorithm that scales as with the size of the graph. We provide additional procedures for simulating Szegedy's quantum walk over mixed states and also the Semiclassical Szegedy walk. With these techniques we have built a classical simulator in Python called SQUWALS. We show that our simulator scales as in both time and memory resources. This package provides some high-level applications for algorithms based on Szegedy's quantum walk, as for example the quantum PageRank.
arXiv commentRevTex 4.2, 16 pages, 9 color figures
References in corpus (17)
- Array Programming with NumPy
- Quantum Computation and Decision Trees
- Exponential algorithmic speedup by quantum walk
- Search via Quantum Walk
- Quantum speedup for active learning agents
- Google in a Quantum Network
- Quantum Google in a Complex Network
- The Staggered Quantum Walk Model
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Efficient quantum circuits for Szegedy quantum walks
- Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
- The QWalk Simulator of Quantum Walks
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
- Discrete-time Semiclassical Szegedy Quantum Walks