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.
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.
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.
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.
The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N / M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N / M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically. Published by the American Physical Society 2024
In this paper, we describe a continuous-time quantum walk (CTQW) simulation package for Python 3 , covering their theoretical foundations and practical applications. The software provides both unitary and open system evolution of over general graphs, alongside tools for visualization and exploration of several different aspects of the quantum walk. We go over installation, design and performance of the package, concluding with several examples on how QWAK can be used to explore problems such as search, perfect state transfer, among others. Additionally, we demonstrate how CuPy is utilized to leverage GPU acceleration. Program Summary/New Version Program Summary Program Title: QWAK CPC Library link to program files: https://doi.org/10.17632/wyrm54zc3f.1 Developer's repository link: https://github.com/JaimePSantos/QWAK Licensing provisions: CC By 4.0 Programming language: Python, Javascript, HTML and CSS. Nature of problem: QWAK simulates unitary and stochastic continuous-time quantum walks, focusing on transport property analysis, applications, visualization and ease of use. Solution method: We leverage Python 's vast package resources such as NumPy and NetworkX to implement the desired structures, and then generate the Hamiltonians via spectral decomposition. For the stochastic case, the Lindblad master equations are solved with Qutip . Additional comments including restrictions and unusual features: The GUI provided uses MongoDB to store QWAK objects, which currently limits the size of the graphs since the adjacency matrices are also stored.
This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2
In a seminal paper, Szegedy showed how to construct a quantum walk W(P) for any reversible Markov chain P such that its eigenvector with eigenphase 0 is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of P. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest.