Quantum walks can find a marked element on any graph

DOI10.1007/S00453-015-9979-8zbMATH Open1336.68083arXiv1002.2419OpenAlexW1998539366MaRDI QIDQ262276FDOQ262276

Authors: Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland 

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. In the case when the marked set $M$ consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time $HT(P,M)$ of any reversible random walk $P$ on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity $H{T}^{+}(mathitP,M)$ which we call extended hitting time. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the random walk $P$ and the absorbing walk $P^{\prime }$, whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of this interpolation. Contrary to previous approaches, our results remain valid when the random walk $P$ is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters $p_M$ (the probability of picking a marked vertex from the stationary distribution) and $H{T}^{+}(mathitP,M)$ are known.

Full work available at URL: https://arxiv.org/abs/1002.2419

Recommendations

• Finding Is as Easy as Detecting for Quantum Walks
• On the hitting times of quantum versus random walks
• Efficient quantum walk on the grid with multiple marked elements
• On the hitting times of quantum versus random walks
• Search via Quantum Walk

zbMATH Keywords

Markov chainsinterpolated quantum walksquantum algorithmsquantum walks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Faster quantum-walk algorithm for the two-dimensional spatial search
• Theory of probability and random processes.
• On the hitting times of quantum versus random walks
• Discrete quantum walks hit exponentially faster
• Quantum complexity of testing group commutativity
• Coins make quantum walks faster
• Quantum search of spatial regions
• Spatial search and the Dirac equation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum verification of matrix products
• Finding Is as Easy as Detecting for Quantum Walks
• Quantum algorithms revisited
• Computing with Noisy Information
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness

Cited In (33)

• A quantum searching model finding one of the edges of a subgraph in a complete graph
• On the probability of finding marked connected components using quantum walks
• Spectral approach to quantum searching on the interpolated Markov chains: the complete bipartite graph
• Quantum algorithm design: techniques and applications
• A novel image segmentation algorithm based on continuous-time quantum walk using superpixels
• Efficient quantum walk on the grid with multiple marked elements
• Upperbounds on the probability of finding marked connected components using quantum walks
• Quantum search of matching on signed graphs
• Faster search by lackadaisical quantum walk
• Finding more than one path through a simple maze with a quantum walk
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Periodicity of lively quantum walks on cycles with generalized Grover coin
• Quantum Walks with Multiple or Moving Marked Locations
• Szegedy's quantum walk with queries
• On the hitting times of quantum versus random walks
• On the hitting times of quantum versus random walks
• A note on the search for \(k\) elements via quantum walk
• Adjacent vertices can be hard to find by quantum walks
• Adjacent vertices can be hard to find by quantum walks
• Efficient quantum circuits for Szegedy quantum walks
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Exceptional quantum walk search on the cycle
• The average search probabilities of discrete-time quantum walks
• Topological classification of time-asymmetry in unitary quantum processes
• Improvement of quantum walks search algorithm in single-marked vertex graph
• Optimal deterministic quantum algorithm for the promised element distinctness problem
• Quantum mixing of Markov chains for special distributions
• Finding Is as Easy as Detecting for Quantum Walks
• Circuit implementation of discrete-time quantum walks via the shunt decomposition method
• Title not available (Why is that?)
• Quantum-walk speedup of backtracking algorithms
• Quantum walks and search algorithms

This page was built for publication: Quantum walks can find a marked element on any graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262276)