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

Quantum Information Processing

Szegedy’s quantum walk with queries

Raqueline A. M. Santos

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

Related papers

Szegedy’s Quantum Walk

Renato Portugal

Quantum science and technology•Jan 1, 2018•0 citations

Equivalence of Szegedy’s and coined quantum walks

Thomas G. Wong

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

Szegedy's quantum walk with queries

Raqueline A. M. Santos

When searching for a marked vertex in a graph, Szegedy's usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy's quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggests that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy's search operator, obtained from the absorbing walk, using the standard query model.

arXiv:1603.05473•Mar 17, 2016•1 citation

Quantum queries

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

Search via Quantum Walk

Jiangfeng Du, Chao Lei, Qin Gan +2 more

Quantum walk

InTech eBooks•Apr 26, 2011•4 citations
When searching for a marked vertex in a graph, Szegedy's usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy's quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggests that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy's search operator, obtained from the absorbing walk, using the standard query model.
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.