Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.14226

Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms

Sergio A. Ortega, Daniel K. Park

quant-phSubmitted Jun 12, 2026• Announced Jun 15, 2026• 0 citations
arXivHTMLPDF

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(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.

Comments
27 pages, 15 figures (including Supplementary Material)

Related papers

Complex-phase extensions of the Szegedy quantum walk on graphs

Sergio A. Ortega, Miguel Angel Martin-Delgado

This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.

arXiv:2410.22011•Physical Review A•Mar 19, 2025•2 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations

SQUWALS: A Szegedy QUantum WALks Simulator

Sergio A. Ortega, Miguel Angel Martin-Delgado

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, a memory‐saving algorithm is proposed that scales as with the size of the graph. Additional procedures are provided for simulating Szegedy's quantum walk over mixed states and also the Semiclassical Szegedy walk. With these techniques, a classical simulator in Python called SQUWALS (Szegedy QUantum WALks Simulator) has been built. It is shown that the 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:2307.14314•Advanced Quantum Technologies•Apr 14, 2024•5 citations

Quantum Walk-Based Algorithms for Graph Traversal and Optimization

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to graph traversal and optimization problems. Classical graph algorithms often struggle with scalability and efficiency when dealing with large and complex graphs. Quantum walks, utilizing the principles of superposition and interference, offer a potential solution by providing a fundamentally different approach to graph exploration. We present a framework for constructing quantum walk-based algorithms tailored for graph traversal, focusing on algorithms that can efficiently explore the graph space. Furthermore, we explore the integration of these algorithms into graph optimization problems, aiming to achieve speedups compared to traditional classical methods. The core idea is to represent graph nodes and edges as quantum states, enabling parallel exploration of the graph through quantum superposition. We explore the mathematical formulation of these algorithms, highlighting key concepts like Hilbert space representation, transition amplitudes, and interference effects. The results presented demonstrate the potential for quantum walk algorithms to significantly improve the performance of graph-related tasks.

•Sep 5, 2026•0 citations

Discrete-time semiclassical Szegedy quantum walks

Sergio A. Ortega, Miguel Angel Martin-Delgado

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:2303.18202•Physica A Statistical Mechanics and its Applications•Jul 8, 2023•5 citations

Implementation of a continuous-time quantum walk on a sparse graph

Zhaoyang Chen, Guanzhong Li, Lvzhou Li

Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and $A$ corresponds to the adjacency matrix of a graph). Our result is, for a $d$-sparse graph with $N$ vertices and evolution time $t$, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance, $d=O(1)$, we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian $H$ can be represented as the sum of some Hamiltonians ${H}_{j}$, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.

arXiv:2408.10553•Physical Review A•Nov 15, 2024•6 citations
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)O(N^2)O(N2) complexity for dense graphs with NNN nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N)O(N)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.
This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.
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, a memory‐saving algorithm is proposed that scales as with the size of the graph. Additional procedures are provided for simulating Szegedy's quantum walk over mixed states and also the Semiclassical Szegedy walk. With these techniques, a classical simulator in Python called SQUWALS (Szegedy QUantum WALks Simulator) has been built. It is shown that the 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.
This paper investigates the application of quantum walk algorithms to graph traversal and optimization problems. Classical graph algorithms often struggle with scalability and efficiency when dealing with large and complex graphs. Quantum walks, utilizing the principles of superposition and interference, offer a potential solution by providing a fundamentally different approach to graph exploration. We present a framework for constructing quantum walk-based algorithms tailored for graph traversal, focusing on algorithms that can efficiently explore the graph space. Furthermore, we explore the integration of these algorithms into graph optimization problems, aiming to achieve speedups compared to traditional classical methods. The core idea is to represent graph nodes and edges as quantum states, enabling parallel exploration of the graph through quantum superposition. We explore the mathematical formulation of these algorithms, highlighting key concepts like Hilbert space representation, transition amplitudes, and interference effects. The results presented demonstrate the potential for quantum walk algorithms to significantly improve the performance of graph-related tasks.
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.
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and AAA corresponds to the adjacency matrix of a graph). Our result is, for a ddd-sparse graph with NNN vertices and evolution time ttt, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance, d=O(1)d=O(1)d=O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian HHH can be represented as the sum of some Hamiltonians Hj{H}_{j}Hj​, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.