Name
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 consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time of any reversible random walk on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity 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 and the absorbing walk , 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 is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters (the probability of picking a marked vertex from the stationary distribution) and are known. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s00453-015-9979-8 | Algorithmica |
Keywords | Field | DocType |
Quantum algorithms,Quantum walks,Markov chains,Interpolated quantum walks | Discrete mathematics,Quantum,Combinatorics,Open problem,Vertex (geometry),Random walk,Quantum walk,Quantum algorithm,Stationary distribution,Hitting time,Mathematics | Journal |
Volume | Issue | ISSN |
74 | 2 | Algorithmica 74(2), pp. 851-907 (2016) |
Citations | PageRank | References |
13 | 0.89 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hari Krovi | 1 | 57 | 8.29 |
| Frédéric Magniez | 2 | 570 | 44.33 |
| Maris Ozols | 3 | 49 | 7.80 |
| Jeremie Roland | 4 | 46 | 2.91 |