Quantum walks can find a marked element on any graph

DOI10.1007/S00453-015-9979-8MaRDI QIDQ262276zbMATHOpenAlexFDO

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

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)

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

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)