A Caltech Library Service

A Unified Framework of Quantum Walk Search

Apers, Simon and Gilyén, András and Jeffery, Stacey (2021) A Unified Framework of Quantum Walk Search. In: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics. No.187. Dagstuhl Publishing , Wadern, Germany, Art. No. 6. ISBN 9783959771801.

PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© Simon Apers, András Gilyén, and Stacey Jeffery; licensed under Creative Commons License CC-BY 4.0. Date of publication: 10.03.2021. Funding: Simon Apers: Work done while being partially supported by the CWI-Inria International Lab and the Dutch Research Council (NWO) through QuantERA ERA-NET Cofund project QuantAlgo 680-91-034. András Gilyén: Funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, as well as by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). Stacey Jeffery: Supported by an NWO Veni Innovational Research Grant under project number 639.021.752, an NWO WISE Grant, and QuantERA project QuantAlgo 680-91-03. SJ is a CIFAR Fellow in the Quantum Information Science Program.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)680-91-034
Samsung ElectronicsUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)639.021.752
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)680-91-03
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Subject Keywords:Quantum Algorithms, Quantum Walks, Graph Theory
Series Name:Leibniz International Proceedings in Informatics
Issue or Number:187
Record Number:CaltechAUTHORS:20210517-104446034
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109149
Deposited By: Tony Diaz
Deposited On:17 May 2021 17:58
Last Modified:17 May 2021 17:58

Repository Staff Only: item control page