NDLI: On the Hitting Times of Quantum Versus Random Walks

Content Provider	Springer Nature Link
Author	Magniez, Frédéric Nayak, Ashwin Richter, Peter C. Santha, Miklos
Copyright Year	2011
Abstract	The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find—a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains.Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.
Starting Page	91
Ending Page	116
Page Count	26
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	63
Issue Number	1-2
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2011-05-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Markov chain Random walk Hitting time Quantum walk Quantum hitting time Algorithms Algorithm Analysis and Problem Complexity Data Structures, Cryptology and Information Theory Mathematics of Computing Theory of Computation Computer Systems Organization and Communication Networks
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quantum Walks Can Find a Marked Element on Any Graph

Search via Quantum Walk

Concentration of First Hitting Times Under Additive Drift

Random Walks, Bisections and Gossiping in Circulant Graphs

Near-Linear Approximation Algorithms for Geometric Hitting Sets

Evolutionary Algorithms for Quantum Computers

Reconstructive Dispersers and Hitting Set Generators

Random Bichromatic Matchings

Quantum Complexity of Testing Group Commutativity

On the Hitting Times of Quantum Versus Random Walks

Similar Documents

Quantum Walks Can Find a Marked Element on Any Graph

Search via Quantum Walk

Concentration of First Hitting Times Under Additive Drift

Random Walks, Bisections and Gossiping in Circulant Graphs

Near-Linear Approximation Algorithms for Geometric Hitting Sets

Evolutionary Algorithms for Quantum Computers

Reconstructive Dispersers and Hitting Set Generators

Random Bichromatic Matchings

Quantum Complexity of Testing Group Commutativity

On the Hitting Times of Quantum Versus Random Walks