Quantum walks can find a marked element on any graph

DOI10.1007/S00453-015-9979-8MaRDI QIDQ262276zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1002.2419, https://dipot.ulb.ac.be/dspace/bitstream/2013/198724/3/Krovi2016_Article_QuantumWalksCanFindAMarkedElem.pdf

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)

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.

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

Cites work

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

Cited in

(33)

• Quantum walks and search algorithms
• 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
• Quantum algorithm design: techniques and applications
• Spectral approach to quantum searching on the interpolated Markov chains: the complete bipartite graph
• 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
• Szegedy's quantum walk with queries
• Quantum Walks with Multiple or Moving Marked Locations
• 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
• Exceptional quantum walk search on the cycle
• The average search probabilities of discrete-time quantum walks
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• 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
• Finding Is as Easy as Detecting for Quantum Walks
• Quantum mixing of Markov chains for special distributions
• Circuit implementation of discrete-time quantum walks via the shunt decomposition method
• Quantum-walk speedup of backtracking algorithms
• scientific article; zbMATH DE number 7525446 (Why is no real title available?)

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)