English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Spatial search by discrete-time quantum walk can find a marked node on anyergodic, reversible Markov chain $P$ quadratically faster than its classicalcounterpart, i.e.\ in a time that is in the square root of the hitting time of$P$. However, in the framework of continuous-time quantum walks, it waspreviously unknown whether such general speed-up is possible. In fact, in thisframework, the widely used quantum algorithm by Childs and Goldstone fails toachieve such a speedup. Furthermore, it is not clear how to apply thisalgorithm for searching any Markov chain $P$. In this article, we aim toreconcile the apparent differences between the running times of spatial searchalgorithms in these two frameworks. We first present a modified version of theChilds and Goldstone algorithm which can search for a marked element for anyergodic, reversible $P$ by performing a quantum walk on its edges. Althoughthis approach improves the algorithmic running time for several instances, itcannot provide a generic quadratic speedup for any $P$. Secondly, using theframework of interpolated Markov chains, we provide a new spatial searchalgorithm by continuous-time quantum walk which can find a marked node on any$P$ in the square root of the classical hitting time. In the scenario wheremultiple nodes are marked, the algorithmic running time scales as the squareroot of a quantity known as the extended hitting time. Our results establish anovel connection between discrete-time and continuous-time quantum walks andcan be used to develop a number of Markov chain-based quantum algorithms.

Finding a marked node on any graph by continuous-time quantum walk