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

quant-pharXiv:2606.14226Jun 15, 20260 citations

Quantum circuit design for quantum walks

Oon Han Thomas Loke

This thesis focuses on applying analytical and numerical techniques to the problem of designing quantum circuits for quantum walks. We develop efficient quantum circuit implementations of continuous-time quantum walks using diagonalization of the Hamiltonian. Next, for the discrete-time Szegedy quantum walk model, we provide a theoretical framework for the development of efficient quantum circuits, and apply it to a wide variety of graphs. We also investigate the optimisation of numerical techniques to the general problem of implementing a unitary matrix. Lastly, we discuss design principles for the development of efficient quantum circuit implementations of quantum walks of different types.This thesis focuses on applying analytical and numerical techniques to the problem of designing quantum circuits for quantum walks. We develop efficient quantum circuit implementations of continuous-time quantum walks using diagonalization of the Hamiltonian. Next, for the discrete-time Szegedy quantum walk model, we provide a theoretical framework for the development of efficient quantum circuits, and apply it to a wide variety of graphs. We also investigate the optimisation of numerical techniques to the general problem of implementing a unitary matrix. Lastly, we discuss design principles for the development of efficient quantum circuit implementations of quantum walks of different types.

Jan 1, 20171 citation

Efficient Universal Quantum Circuits

Debajyoti Bera, Stephen Fenner, Frederic Green +1 more

Lecture notes in computer scienceJan 1, 20092 citations

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.