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:1603.05473 · Quantum Information Processing

Szegedy’s quantum walk with queries

Raqueline A. M. Santos

Published Aug 26, 2016• 30 citations
arXivHTMLPDF
DOI
10.1007/s11128-016-1427-4

Related papers

Szegedy’s Quantum Walk

Renato Portugal

Quantum science and technology•Jan 1, 2018•1 citation

Equivalence of Szegedy’s and coined quantum walks

Thomas G. Wong

arXiv:1611.02238•Quantum Information Processing•Jul 24, 2017•30 citations

Quantum Algorithm for Commutativity Testing of a Matrix Set

Yuki Kelly Itakura

Suppose we have k matrices of size n by n. We are given an oracle that knows all the entries of k matrices, that is, we can query the oracle an (i,j) entry of the l-th matrix. The goal is to test if each pair of k matrices commute with each other or not with as few queries to the oracle as possible. In order to solve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that relates a hitting time of a classical random walk to that of a quantum walk. We also take a look at another method of quantum walk by Andris Ambainis (quant-ph/0311001). We apply both walks into triangle finding problem (quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to compare the powers of the two different walks. We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem. It turns out Szegedy's algorithm can be generalized to solve similar problems. Therefore we use Szegedy's theorem to analyze the problem of matrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n). We generalize the technique used in coming up with the upper bound to solve a broader range of similar problems. This is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here, k and n.

arXiv:quant-ph/0509206•Sep 29, 2005•3 citations

Quantum queries

Bloomsbury Academic eBooks•Aug 29, 2018•0 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•7 citations

Quaternionic quantum walks of Szegedy type and zeta functions of graphs

Norio Konno, Kaname Matsue, Hideo Mitsuhashi +1 more

We define a quaternionic extension of the Szegedy walk on a graph and study its right spectral properties. The condition for the transition matrix of the quaternionic Szegedy walk on a graph to be quaternionic unitary is given. In order to derive the spectral mapping theorem for the quaternionic Szegedy walk, we derive a quaternionic extension of the determinant expression of the second weighted zeta function of a graph. Our main results determine explicitly all the right eigenvalues of the quaternionic Szegedy walk by using complex right eigenvalues of the corresponding doubly weighted matrix. We also show the way to obtain eigenvectors corresponding to right eigenvalues derived from those of doubly weighted matrix.

arXiv:1703.04969•Quantum Information and Computation•Dec 1, 2017•1 citation
Suppose we have k matrices of size n by n. We are given an oracle that knows all the entries of k matrices, that is, we can query the oracle an (i,j) entry of the l-th matrix. The goal is to test if each pair of k matrices commute with each other or not with as few queries to the oracle as possible. In order to solve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that relates a hitting time of a classical random walk to that of a quantum walk. We also take a look at another method of quantum walk by Andris Ambainis (quant-ph/0311001). We apply both walks into triangle finding problem (quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to compare the powers of the two different walks. We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem. It turns out Szegedy's algorithm can be generalized to solve similar problems. Therefore we use Szegedy's theorem to analyze the problem of matrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n). We generalize the technique used in coming up with the upper bound to solve a broader range of similar problems. This is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here, k and n.
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.
We define a quaternionic extension of the Szegedy walk on a graph and study its right spectral properties. The condition for the transition matrix of the quaternionic Szegedy walk on a graph to be quaternionic unitary is given. In order to derive the spectral mapping theorem for the quaternionic Szegedy walk, we derive a quaternionic extension of the determinant expression of the second weighted zeta function of a graph. Our main results determine explicitly all the right eigenvalues of the quaternionic Szegedy walk by using complex right eigenvalues of the corresponding doubly weighted matrix. We also show the way to obtain eigenvectors corresponding to right eigenvalues derived from those of doubly weighted matrix.