Given a graph $G$ and a set of marked vertices $M$, spatial search problem is the problem of finding a marked vertex. A classical approach is to perform a random walk on the graph to find out a marked vertex, for which the required time is the hitting time of the random walk.

For discrete time quantum walk, Krovi et al. [1] have proven that the hitting time is quadratically faster than the classical random walk when only 1 element is marked. For continous time quantum walks, a similar result is proven by Chakraborty et al. [2]. Recently, Ambainis et al. [3] have showed that for discrete time quantum walks, the speedup holds even when there are more than 1 marked vertices.

Are there any special types of graphs for which the spatial search problem can be solved with exponential speedup compared to classical algorithms?

For instance, for certain types of graphs like the hypercube, random walk spreads exponentially faster [4] but as detecting a marked vertex is not the same thing as finding the marked vertex in the quantum setting, I am not sure if this result implies an exponential speedup for finding a marked vertex.

[1] Krovi, H., Magniez, F., Ozols, M., & Roland, J. 2016. “Quantum walks can find a marked element on any graph”, Algorithmica, 74(2), 851-907.

[2] Chakraborty, S., Novo, L., & Roland, J. (2018). Finding a marked node on any graph by continuous-time quantum walk. arXiv preprint arXiv:1807.05957.

[3] Ambainis, Andris, et al. "Quadratic speedup for finding marked vertices by quantum walks." arXiv preprint arXiv:1903.07493 (2019).

[4] Kempe, Julia. "Discrete quantum walks hit exponentially faster." Probability theory and related fields 133.2 (2005): 215-235.

  • $\begingroup$ Welded trees? But that's continuous-time. $\endgroup$
    – Mark S
    Apr 26, 2020 at 17:17
  • $\begingroup$ @MarkS As far as I know, it is not a spatial search proble but it should be one of the first examples where exponential speedup over classical is proven using quantum walks. $\endgroup$
    – usercs
    Apr 26, 2020 at 19:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.