Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms
Abstract
Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N2) complexity for dense graphs with N nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
Versions
Related
- Towards large-scale ab initio Molecular Dynamics Simulation with Efficient Sampling-based Quantum Computing Algorithms
- Resource-efficient formulations of the Knapsack problem for quantum computing
- Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations
- Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters
- Fermionic non-Gaussianity via Bell sampling: monotones and efficient quantum algorithms
BibTeX
@misc{ortega2026efficient,
title = {{Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms}},
author = {Sergio A. Ortega and Daniel K. Park},
howpublished = {arXiv},
year = {2026},
month = jun,
doi = {10.48550/arxiv.2606.14226},
eprint = {2606.14226},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.14226},
}
RIS
TY - UNPB
TI - Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms
AU - Sergio A. Ortega
AU - Daniel K. Park
PY - 2026
DA - 2026/06/12
PB - arXiv
DO - 10.48550/arxiv.2606.14226
UR - https://arxiv.org/abs/2606.14226
AB - Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N^2) complexity for dense graphs with N nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
ER -