# Quadratic speedup for spatial search by continuous-time quantum walk

Simon Apers1<EMAIL_ADDRESS>Shantanav Chakraborty2<EMAIL_ADDRESS>Leonardo Novo3<EMAIL_ADDRESS>Jérémie Roland3<EMAIL_ADDRESS>1
IRIF, CNRS, Paris, France  2 CQST and CSTAR, International Institute of
Information Technology Hyderabad, Telangana, India  3 QuIC, Ecole
Polytechnique de Bruxelles, Université libre de Bruxelles, Brussels, Belgium

###### Abstract

Continuous-time quantum walks provide a natural framework to tackle the
fundamental problem of finding a node among a set of marked nodes in a graph,
known as spatial search. Whether spatial search by continuous-time quantum
walk provides a quadratic advantage over classical random walks has been an
outstanding problem. Thus far, this advantage is obtained only for specific
graphs or when a single node of the underlying graph is marked. In this
article, we provide a new continuous-time quantum walk search algorithm that
completely resolves this: our algorithm can find a marked node in any graph
with any number of marked nodes, in a time that is quadratically faster than
classical random walks. The overall algorithm is quite simple, requiring time
evolution of the quantum walk Hamiltonian followed by a projective
measurement. A key component of our algorithm is a purely analog procedure to
perform operations on a state of the form $e^{-tH^{2}}\ket{\psi}$, for a given
Hamiltonian $H$: it only requires evolving $H$ for time scaling as $\sqrt{t}$.
This allows us to quadratically fast-forward the dynamics of a continuous-time
classical random walk. The applications of our work thus go beyond the realm
of quantum walks and can lead to new analog quantum algorithms for preparing
ground states of Hamiltonians or solving optimization problems.

Quantum walks, the quantum analogue of classical random walks, find widespread
applications across quantum information processing. Besides being a universal
model of quantum computation [1], quantum walks have proven to be a useful
primitive in the design of quantum algorithms [2, 3]. A particularly appealing
model is that of continuous-time quantum walks (CTQWs) which provides a
physics-inspired paradigm for quantum algorithm design, based solely on the
evolution of a time-independent Hamiltonian that is related to a graph. One of
the most widely studied algorithmic applications of this framework has been to
tackle the spatial search problem of finding marked nodes on a graph. However,
even though the first spatial search algorithm to tackle this problem was
proposed almost two decades ago [4], it is unknown whether CTQWs can generally
find a node within a marked set of nodes quadratically faster than classical
random walks: a spatial search algorithm by CTQW that offers this general
quadratic speedup has remained elusive. In contrast, in a recent breakthrough
this problem was fully resolved for _discrete-time_ quantum walks [5].
Childs and Goldstone provided the first spatial search algorithm by CTQW which
could find a single marked node in certain graphs (such as the complete graph,
hypercube and lattices of dimension greater than four) quadratically faster
than classical random walks [4]. Since then, a plethora of results have
demonstrated a quadratic speed-up for several specific instances of graphs [6,
7, 8, 9, 10, 11, 12, 13, 14, 15]. The approach by Childs and Goldstone is
appealing because, similar to classical random walks, the state space of the
walk is spanned by the nodes of the graph. However, explicit counterexamples
are known where this approach fails to provide quadratic advantages for
search, even for certain highly-connected graphs [16]. Furthermore, it seems
difficult to analyse this algorithm in the scenario where multiple nodes in
the underlying graph are marked and general results in this setting are
missing.
More recently, Chakraborty et al. developed a CTQW algorithm for spatial
search on any weighted graph (or, equivalently, any ergodic, reversible Markov
chain). This algorithm, which can be seen as a quantum walk on the edges of
the underlying graph, offers a quadratic advantage over classical random walks
only when a single node is marked [17]. For certain instances with multiple
marked nodes, the running time of the algorithm is even slower than its
classical counterpart.
In this article we completely solve the spatial search problem by CTQW. We
provide a CTQW-based algorithm that, starting from a quantum encoding of the
stationary distribution $\pi$, finds a marked node on any graph, with any
number of marked nodes in a time that is (up to a logarithmic factor)
quadratically faster than the corresponding classical random walk. The key
ideas behind this general result are as follows. We show that evolving a state
$\ket{\psi_{0}}$ under a Hamiltonian $H$ for a random time proportional to
$\sqrt{t}$ allows us, in a certain sense, to simulate projective measurements
on the state $e^{-tH^{2}}\ket{\psi_{0}}$. When $H$ corresponds to the CTQW
Hamiltonian on a graph, this procedure allows us to quadratically fast-forward
the dynamics of a continuous-time random walk on $P$, analogous to the results
of Ref. [18]. The expected time required by a classical random walk to solve
the spatial search problem is known as the hitting time $(HT)$. For the
spatial search problem then it suffices to show that if we take $t\propto HT$,
then the resulting state has a large overlap with the marked elements.
Obtaining a generic quadratic advantage for the spatial search problem has
proven to be extremely challenging also in the discrete-time quantum walk
(DTQW) framework and was only recently solved in [5]. However, this does not
imply the existence of a CTQW algorithm with the same performance. In fact,
even though there are general procedures to simulate Hamiltonian evolution
(and hence CTQWs) using DTQWs à la Szegedy [19, 20], there is no known way to
translate DTQW dynamics to the continuous-time setting. The fact that these
two frameworks are not equivalent is also why for the spatial search
algorithm, efforts to prove a general quadratic speedup over classical random
walks were undertaken in parallel.
Apart from being a fundamental contribution in the field of quantum walks, our
work introduces new tools that are of independent interest and could lead to
the development of novel analog quantum algorithms. In particular, our
continuous-time procedure to access the quantum state
$e^{-tH^{2}}\ket{\psi_{0}}$ naturally translates to a quantum algorithm to
prepare the ground states of $H$. This procedure has a running time that
matches the best quantum algorithms in the circuit model but is considerably
simpler. We believe that similar techniques can lead to other analog quantum
algorithms for optimization such as simulated annealing and Gibbs state
preparation.

Imaginary time-evolution – We begin by describing a technique of broader
relevance, which uses a continuous-time procedure to prepare the state
$e^{-tH^{2}}\ket{\psi}$, which can be seen as an imaginary time evolution
under Hamiltonian $H^{2}$ for time $t$. In the spatial search setting, we will
use this result to fast-forward the dynamics of a continuous-time random walk.
Consider a quantum system in state $\ket{\psi_{0}}$ coupled to an ancillary
system in a Gaussian state

$\ket{\psi_{g}}=\int_{-\infty}^{+\infty}\dfrac{dz}{(2\pi)^{1/4}}e^{-z^{2}/4}\ket{z}.$
(1)

Choosing suitable units of mass and frequency, this state can be seen as the
ground state of a one-dimensional quantum harmonic oscillator. The coupling is
done via interaction Hamiltonian $H^{\prime}=H\otimes\hat{z}$, where $\hat{z}$
corresponds to the position operator. Evolving $\ket{\psi_{0}}\ket{\psi_{g}}$,
under $H^{\prime}$ for a time $\sqrt{2t}$ results in the state

$\displaystyle\ket{\eta_{t}}$
$\displaystyle=e^{-i\sqrt{2t}H^{\prime}}\ket{\psi_{0}}\ket{\psi_{g}}$
$\displaystyle=\int_{-\infty}^{+\infty}\dfrac{dz}{(2\pi)^{1/4}}e^{-z^{2}/4}e^{-i\sqrt{2t}Hz}\ket{\psi_{0}}\ket{z}$
(2)
$\displaystyle=\int_{-\infty}^{+\infty}\dfrac{dz}{\sqrt{2\pi}}e^{-z^{2}/2}e^{-i\sqrt{2t}Hz}\ket{\psi_{0}}\ket{\psi_{g}}+\ket{\Phi}^{\perp},$

where $\ket{\Phi}^{\perp}$ is a quantum state where the ancillary system is
orthogonal to $\ket{\psi_{g}}$. Now we can make use of the Hubbard-
Stratonovich transformation which states that, for any $x\in\mathbb{R}$,

$e^{-x^{2}/2}=\int\dfrac{dy}{\sqrt{2\pi}}~{}e^{-y^{2}/2}e^{-ixy}.$

If we choose $x=\sqrt{2t}H$, it allows us to rewrite

$\ket{\eta_{t}}=e^{-tH^{2}}\ket{\psi_{0}}\ket{\psi_{g}}+\ket{\Phi}^{\perp}.$
(3)

By post-selecting on obtaining $\ket{\psi_{g}}$ in the second register (for
example, by measuring the second register in the eigenbasis of the quantum
harmonic oscillator), we are able to prepare a quantum state proportional to
$e^{-tH^{2}}\ket{\psi_{0}}$ in the first register.
This simple analog procedure in itself can have several applications. For
example, consider the problem of preparing the ground state of $H$ (say
$\ket{v_{0}}$). If $\Delta$ is the gap between the ground state and the first
excited state of $H$, then it can be shown that the state
$e^{-tH^{2}}\ket{\psi_{0}}$, for $\sqrt{t}$ scaling as
$\mathcal{O}\left(\frac{1}{\Delta}\log^{1/2}\left(\frac{1}{|\braket{\psi_{0}}{v_{0}}|\varepsilon}\right)\right)$
111We use the Big-Oh notation, i.e. $f(n)\in\mathcal{O}(g(n))$ if there exists
a constant $c$ such that $f(n)\leq cg(n)$. Any $f(n)\in\Omega(g(n))$ if there
exists a constant $c$ such that $f(n)\geq cg(n)$. Finally
$f(n)\in\Theta(g(n))$, if there exists constants $c_{1},c_{2}$ such that
$c_{1}~{}g(n)\leq f(n)\leq c_{2}~{}g(n)$., is $\varepsilon$-close to
$\ket{v_{0}}$ with probability scaling as $|\braket{\psi_{0}}{v_{0}}|^{2}$
(See Appendix for details). The performance matches the best circuit model
algorithms for this problem but is conceptually simpler as unlike in the
discrete-time setting, does not require implementing linear combination of
unitaries or quantum phase estimation [22, 23, 24].
We believe that our approach can also lead to potentially simpler analog
quantum algorithms for preparing Gibbs states, as in [25].

Dropping the ancilla register – For several quantum algorithmic applications,
we are only interested in the projection of the state
$e^{-tH^{2}}\ket{\psi_{0}}$ into some subspace of interest. This is typically
the case for simulated annealing, where we are only interested in finding a
(close to) optimal solution. Similarly it holds for the spatial search
problem, wherein $H$ corresponds to the quantum walk Hamiltonian, and we want
the final state to have a good overlap with the marked nodes. In such
scenarios, we will show that it is possible to get rid of the ancilla register
altogether: it suffices to evolve according to the Hamiltonian $H$ for some
appropriately random time. We formalize this in the following lemma.

######  Lemma 1.

Evolving a quantum state $\ket{\psi_{0}}$ under a Hamiltonian $H$ for time
$\sqrt{2t}z$, where $z\sim\mathcal{N}(0,1)$ is drawn from the standard normal
distribution, results in a mixed state

$\rho_{t}=\int_{-\infty}^{+\infty}\dfrac{dz}{\sqrt{2\pi}}e^{-z^{2}/2}e^{-i\sqrt{2t}Hz}\ket{\psi_{0}}\bra{\psi_{0}}e^{i\sqrt{2t}Hz},$

such that for any projector $\Pi$,

$\operatorname{tr}[\Pi\rho_{t}]\geq\bra{\psi_{0}}e^{-tH^{2}}\Pi
e^{-tH^{2}}\ket{\psi_{0}}.$

###### Proof.

It can be seen that

$\displaystyle\operatorname{tr}[\Pi\rho_{t}]$
$\displaystyle=\operatorname{tr}\left[\left(\Pi\otimes
I\right)\ket{\eta_{t}}\bra{\eta_{t}}\right]$
$\displaystyle=\bra{\psi_{0}}e^{-tH^{2}}\Pi
e^{-tH^{2}}\ket{\psi_{0}}+\bra{\Phi^{\perp}}\Pi\otimes I\ket{\Phi^{\perp}},$

where the first equality follows from Eq. (2) and the second from Eq. (3). The
proof of the Lemma then follows from the fact that the last term in the
expression for $\operatorname{tr}[\Pi\rho_{t}]$ is non-negative. ∎

The expected time required to obtain $\rho_{t}$ is simply
$T=\sqrt{2t}\cdot\langle|z|\rangle$. Since $z\sim\mathcal{N}(0,1)$ this is
$T=2\sqrt{t/\pi}$. We note that this lemma is an analog variant of an
observation in [26, Section 6]. Next we explain how Lemma 1 can be used to
fast-forward continuous-time random walk dynamics - a key ingredient of our
spatial search algorithm.

Fast-forwarding continuous-time random walks – Before explaining the
construction of the Hamiltonian driving the quantum walk, we introduce some
notions about Markov chains and random walks. For details on some of these
concepts, we refer the reader to the Appendix. A Markov chain with a set of
$V$ nodes, such that $|V|=n$, is defined by an $n\times n$ stochastic matrix
$P$, such that $P_{xy}=p_{xy}$, which is the probability of of transitioning
from node $x$ to node $y$. The state of the random walker at any time is given
by a stochastic row vector. A discrete-time random walk proceeds by repeated
applications of $P$, starting from some initial state $v_{0}$: $t$ random walk
steps result in the state $v_{t}=v_{0}P^{t}$.
To any discrete-time chain with transition matrix $P$, we can associate a
continuous-time chain by choosing the _transition kernel_ $Q=P-I$. Starting
from some distribution $v_{0}$, the state of this continuous-time walk after
time $t$ is described by the distribution $v_{t}=v_{0}e^{Qt}$.
We assume that $P$ represents an ergodic and reversible Markov chain, implying
(i) the eigenvalues of $P$ lie between $-1$ and $1$ and (ii) $P$ has a unique
stationary distribution $\pi=(\pi_{1}~{}\pi_{2}~{}\cdots~{}\pi_{n})$, which
obeys the so-called detailed balance condition, $\pi_{x}p_{xy}=\pi_{y}p_{yx}$.
Any reversible $P$ corresponds to a discrete-time random walk on a weighted
graph. A useful matrix associated to $P$ is the discriminant matrix $D$,
defined as an $n\times n$ symmetric matrix with entries
$D_{xy}=\sqrt{p_{xy}p_{yx}}$. The discriminant matrix is symmetric, its
spectrum coincides with that of $P$, and the coherent encoding of the
stationary distribution $\ket{\sqrt{\pi}}=\sum_{j}\sqrt{\pi_{j}}\ket{j}$ is an
eigenstate of $D$ with eigenvalue $1$.
The discriminant matrix provides a framework to deal with cases when $P$ is
not symmetric and the spectral relationship between the two has been
fundamental for designing many quantum walk algorithms. In fact, for symmetric
$P$, $D=P$.
In particular, it is used in a canonical construction of a Hamiltonian
$H_{P}$, associated to a reversible Markov chain $P$, so that $e^{-iH_{P}t}$
corresponds to a quantum walk on the edges of the underlying graph for time
$t$ [27, 17]. A useful property is that the spectra of $H_{P}$ and $P$ are
closely related. To define $H_{P}$, consider the Hilbert space $\mathcal{H}$
spanned by the nodes of $P$ and an additional reference state $\ket{0}$. We
define (i) a unitary $U_{P}$ acting on $\mathcal{H}\otimes\mathcal{H}$ such
that $U_{P}\ket{x,0}=\sum_{y\in V}\sqrt{p_{xy}}\ket{x,y}$, for any $x\in V$,
and (ii) a swap operation $S$ defined by $S\ket{x,y}=\ket{y,x}$. The CTQW
Hamiltonian is then defined as the commutator
$H_{P}=i[U_{P}^{\dagger}SU_{P},\Pi_{0}]$, where
$\Pi_{0}=I\otimes\ket{0}\bra{0}$.
We refer the readers to Refs. [28, 17] wherein the spectral properties of
$H_{P}$ have been analyzed in detail. Here, we shall rely only on an elegant
relationship between $H_{P}$ and the discriminant matrix of the underlying
Markov chain. Specifically, for any quantum state $\ket{\psi}\in\mathcal{H}$
it holds that

$H^{2}_{P}\ket{\psi,0}=I-D^{2}\ket{\psi,0}.$ (4)

We now combine this with Lemma 1. It follows that evolving any state
$\ket{\psi_{0}}=\ket{\psi,0}$ under $H_{P}$ for a time $T=2\sqrt{t}z$, where
$z\sim\mathcal{N}(0,1)$, results in a mixed state $\rho_{t}$ such that

$\operatorname{tr}[\Pi\rho_{t}]\geq\bra{\psi_{0}}e^{t\left(D^{2}-I\right)}\Pi
e^{t\left(D^{2}-I\right)}\ket{\psi_{0}}.$ (5)

Note that $e^{D^{2}-I}$ has the same spectrum as $e^{P^{2}-I}$ which is the
continuous-time random walk transition matrix obtained from $P^{2}$,
corresponding to two steps of the discrete-time random walk. The previous
inequality can be interpreted as follows: if we want to find a marked node by
measuring $e^{t\left(D^{2}-I\right)}\ket{\psi_{0}}$, then we may instead
measure $\rho_{t}$, for which the probability of finding a marked node is at
least as large. As the expected time to prepare $\rho_{t}$ is
$\langle|T|\rangle=2\sqrt{t/\pi}$, this can be seen as a way to fast-forward a
continuous-time random walk, in analogy to the discrete-time quantum fast-
forwarding scheme introduced in Ref [29]. This technique is a crucial
ingredient for the proof of a quadratic speedup for spatial search. We will
show that when $t$ scales as the hitting time of the classical walk, and we
make a suitable choice of $D$, then a marked node is found with large
probability by measuring $\rho_{t}$.

Spatial search by CTQW– In the classical scenario, the problem of searching
marked nodes by random walk can be stated as follows. Given a reversible
Markov chain $P$ with $|V|=n$ nodes, suppose $M\subset V$ corresponds to the
set of marked nodes. Starting from its stationary distribution $\pi$, a random
walk search algorithm repeatedly applies a step of the walk, while checking
whether the new node is marked. The expected time required by the random walk
to find some node $x\in M$ is defined as the hitting time $HT(P,M)$. The
classical algorithm stops as soon as a marked node is reached. As such, it be
seen as the repeated application of the absorbing walk $P^{\prime}$, obtained
from $P$ by replacing all the outgoing edges from nodes in $M$ with self-
loops.
The original approach by Szegedy to obtain speed-ups for spatial search
problems used a quantum walk operator based on from $P^{\prime}$ [30].
However, improvements over this approach made use of the framework of
_interpolated Markov chains_ [28, 31, 5, 16], and we will also use this idea
in our work. For an ergodic reversible Markov chain $P$ and absorbing walk
$P^{\prime}$, the interpolated random walk operator is given by
$P(s)=(1-s)P+sP^{\prime}$, where $s\in[0,1]$. Intuitively, at any timestep the
interpolated random walk first checks whether the current node is marked and
(i) if it is not, the original walk operator $P$ is applied, while (ii) if it
is, then $P$ is applied with probability $(1-s)$ and otherwise $P^{\prime}$ is
applied (i.e., the walk remains at the node). The advantage with using this
framework is that for appropriate choice of $s$, the interpolated walk $P(s)$
demonstrates the useful properties of both the original Markov chain $P$ as
well as the absorbing chain $P^{\prime}$. E.g., Krovi et al. [31] showed that
if $P$ is ergodic and reversible, then so is $P(s)$ for any $s\in[0,1)$. So
$P(s)$ has a unique stationary distribution $\pi(s)$ and its spectrum
coincides with its discriminant matrix $D(s)$.
We now have all the necessary ingredients to introduce our quantum search
algorithm. Similar to prior works, we assume we have a procedure to prepare
the state $\ket{\sqrt{\pi}}$, as well as a procedure to measure if a node is
marked or not. We define $\Pi_{M}$ as the projective measurement onto the set
of marked nodes $M$. The first step of the algorithm is to prepare
$\ket{\sqrt{\pi}}$ and perform a projective measurement associated to
operators $\\{\Pi_{M},I-\Pi_{M}\\}$. Either this returns a marked node, in
which case we are done, or it returns the post-measurement state
$\ket{\sqrt{\pi_{U}}}=\sum_{j\in U}\sqrt{\pi_{j}}\ket{j}$, where $U=V\setminus
M$ denotes the set of nodes that are not marked.
The next step is to evolve $\ket{\sqrt{\pi_{U}}}$ according to the Hamiltonian
$H_{P(s)}$, for some $s\in[0,1)$. More specifically, we use a random time
evolution so as to prepare the state $\rho_{t}$ as in Lemma 1. Using this
Lemma, we obtain that the probability of observing a marked node by measuring
$\rho_{t}$ is $\mathrm{Tr}[(\Pi_{M}\otimes
I)\rho_{t}]\geq\left\lVert\Pi_{M}e^{(D^{2}(s)-I)t}\ket{\sqrt{\pi_{U}}}\right\rVert^{2}$.
Now recall that $\rho_{t}$ can be prepared in $O(\sqrt{t})$ time. Hence, this
results in a quadratic speedup over classical random walks if we can choose
some $t$ scaling as $HT(P,M)$, and some $s\in[0,1)$, so that the success
probability is large. While the optimal choice of $s$ seems hard to determine,
we show that a large success probabilities can be obtained by choosing an
appropriately random $s$, similar to Ref. [5]. This essentially follows from
the following lemma.

######  Lemma 2.

Consider an ergodic, reversible Markov chain $P$ and a set of marked nodes
$M$. If we choose parameters
$s\in\\{1-1/r\mathrel{\mathop{\ordinarycolon}}r=1,2,\cdots,2^{\lceil\log
T\rceil}\\}$ and $T\in\Theta\left(HT(P,M)\right)$ uniformly at random, then
the continuous-time random walk operator $e^{D^{2}(s)-I}$ satisfies

$\mathbb{E}\left[\left\lVert\Pi_{M}e^{(D^{2}(s)-I)T}\ket{\sqrt{\pi_{U}}}\right\rVert^{2}\right]\in\Omega\left(1/\log^{2}T\right).$
(6)

Here, we summarize the main technical steps of the proof, while the details
are provided in the Appendix. First, we show that the probability of finding a
marked state by measuring the (sub-normalized) quantum state
$e^{(D^{2}(s)-I)T}\ket{\sqrt{\pi_{U}}}$ can be lower bounded by a purely
classical quantity. This quantity is the probability of a specific event
happening in a continuous-time random walk with walk operator
$e^{(P^{2}(s)-I)T}$. Then, through some non-trivial reductions, we show that
this probability on its turn can be lower bounded by the probability of the
same event happening in a discrete-time walk with walk operator $P(s)$. This
reduction to a problem involving discrete-time walks allows us to use the
central result of Ref. [5] to finally prove Lemma 2.
The final CTQW search algorithm (Algorithm 1) is described below.

Pick some
$s\in\\{1-1/r\mathrel{\mathop{\ordinarycolon}}r=1,2,\cdots,2^{\lceil\log
T\rceil}\\}$ and $T\in\Theta\left(HT(P,M)\right)$ uniformly at random.

  * 1\.

Prepare the state $\ket{\sqrt{\pi}}\ket{0}$.

* 2\.

Perform a measurement using $\\{\Pi_{M},I-\Pi_{M}\\}$ on the first register.
If the output is marked, measure in the node basis to obtain $x\in M$ and
output $x$. Otherwise we are left with the state
$\ket{\sqrt{\pi_{U}}}\ket{0}$.

* 3\.

Evolve $\ket{\sqrt{\pi_{U}}}\ket{0}$, under $H_{P(s)}$ for time $\sqrt{2T}z$,
where $z\sim\mathcal{N}(0,1)$, to prepare the state $\rho_{t}$.

* 4\.

Perform a measurement on $\rho_{t}$ in the node basis on the first register.

Algorithm 1 Quantum spatial search by CTQW

By combining Lemma 1 and Lemma 2, we see that Algorithm 1 runs in expected
time $\Theta(\sqrt{HT(P,M)})$, and has a success probability of at least
$1/\log^{2}\left(HT(P,M)\right)$. Thus by repeating it
$\log^{2}\left(HT(P,M)\right)$ times, we obtain a marked node $x\in M$ with a
constant probability. This yields an overall expected runtime of

$T=\Theta\left(\sqrt{HT(P,M)}\log^{2}\left(HT(P,M)\right)\right).$

Discussion – We have presented a CTQW search algorithm that achieves a general
quadratic speedup over classical random walks on an arbitrary graph, even when
multiple nodes are marked. This solves a long-standing open problem in the
field. The running time of our algorithm matches that of a recent breakthrough
DTQW algorithm for this problem [5].
This equivalence in performance between DTQWs and CTQWs for the spatial search
problem raises the question of whether more general equivalences can be proven
between these different frameworks. In particular, it is currently unknown if
any DTQW algorithm or, more generally, any dynamics generated by DTQW can be
simulated by a CTQW (although the reverse holds owing to Childs’ reduction
[19]). It would be interesting to explore whether such an equivalence can be
obtained: solving this may bring new insights into the power of simple analog
models of computation and inspire new analog quantum algorithms.
Indeed, the development of our CTQW algorithm for spatial search has led to
the development of tools of independent interest. For any Hamiltonian $H$, we
provide a simple continuous-time procedure to prepare the state
$e^{-tH^{2}}\ket{\psi_{0}}$. This translates to an analog quantum algorithm
for preparing the ground states of $H$ with a running time that matches the
best known quantum algorithms in the circuit model. For several physical
systems, preparing ground states of Hamiltonians is of extreme interest as
they contain information about interesting phases of matter and are also
useful to solve optimization problems [32]. In this regard, our work could
also lead to other simple analog quantum algorithms for optimization such as
quantum simulated annealing [33] and preparation of thermal states [25].

Note: After the completion of this article, we became aware of recent Refs.
[34] and [35]. In [34], the authors have applied a discretized version of the
Hubbard-Stratonovich transform (using linear combination of unitaries) to
prepare the ground state of a Hamiltonian in the circuit model. Ref. [35]
explores ideas similar to ours to develop analog near-term quantum algorithms
for ground state preparation. Neither of these references consider the spatial
search problem.

###### Acknowledgements.

SA acknowledges funding from QuantERA ERA-NET Cofund project QuantAlgo. SC
acknowledges support from the Faculty Seed Grant, IIIT Hyderabad. LN
acknowledges support from F.R.S.- FNRS. JR is supported by the Belgian Fonds
de la Recherche Scientifique - FNRS under grant no R.50.05.18.F (QuantAlgo).

## References

  * [1] Andrew M Childs.  Universal computation by quantum walk.  Physical review letters, 102(18):180501, 2009.
  * [2] Andris Ambainis.  Quantum walks and their algorithmic applications.  International Journal of Quantum Information, 1(04):507–518, 2003\.
  * [3] Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman.  Exponential algorithmic speedup by a quantum walk.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003.
  * [4] Andrew M. Childs and Jeffrey Goldstone.  Spatial search by quantum walk.  Phys. Rev. A, 70:022314, Aug 2004.
  * [5] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis.  Quadratic speedup for finding marked vertices by quantum walks.  In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), pages 412–424. ACM, 2020.
  * [6] Andrew M Childs and Jeffrey Goldstone.  Spatial search and the dirac equation.  Physical Review A, 70(4):042312, 2004.
  * [7] Andrew M Childs and Yimin Ge.  Spatial search by continuous-time quantum walks on crystal lattices.  Physical Review A, 89(5):052337, 2014.
  * [8] Jonatan Janmark, David A Meyer, and Thomas G Wong.  Global symmetry is unnecessary for fast quantum search.  Physical Review Letters, 112(21):210502, 2014.
  * [9] Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Hartmut Neven, and Yasser Omar.  Systematic dimensionality reduction for quantum walks: Optimal spatial search and transport on non-regular graphs.  Scientific reports, 5(1):1–16, 2015.
  * [10] David A Meyer and Thomas G Wong.  Connectivity is a poor indicator of fast quantum search.  Physical review letters, 114(11):110503, 2015.
  * [11] Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, and Yasser Omar.  Spatial search by quantum walk is optimal for almost all graphs.  Physical review letters, 116(10):100501, 2016.
  * [12] Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio, and Yasser Omar.  Optimal quantum spatial search on random temporal networks.  Physical review letters, 119(22):220503, 2017.
  * [13] Thomas G Wong, Konstantin Wünscher, Joshua Lockhart, and Simone Severini.  Quantum walk search on kronecker graphs.  Physical Review A, 98(1):012338, 2018.
  * [14] Tomo Osada, Bruno Coutinho, Yasser Omar, Kaoru Sanaka, William J Munro, and Kae Nemoto.  Continuous-time quantum-walk spatial search on the bollobás scale-free network.  Physical Review A, 101(2):022310, 2020.
  * [15] Dylan Lewis, Asmae Benhemou, Natasha Feinstein, Leonardo Banchi, and Sougato Bose.  Optimal quantum spatial search with one-dimensional long-range interactions.  Physical Review Letters, 126(24):240502, 2021.
  * [16] Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland.  Optimality of spatial search via continuous-time quantum walks.  Physical Review A, 102(3):032214, 2020.
  * [17] Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland.  Finding a marked node on any graph via continuous-time quantum walks.  Physical Review A, 102(2):022227, 2020.
  * [18] Simon Apers and Alain Sarlette.  Quantum fast-forwarding: Markov chains and graph property testing.  Quantum Information & Computation, 19(3-4):181–213, 2019.
  * [19] Andrew M Childs.  On the relationship between continuous-and discrete-time quantum walk.  Communications in Mathematical Physics, 294(2):581–603, 2010.
  * [20] Dominic W Berry, Andrew M Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809. IEEE, 2015.
  * [21] We use the Big-Oh notation, i.e. $f(n)\in\mathcal{O}(g(n))$ if there exists a constant $c$ such that $f(n)\leq cg(n)$. Any $f(n)\in\Omega(g(n))$ if there exists a constant $c$ such that $f(n)\geq cg(n)$. Finally $f(n)\in\Theta(g(n))$, if there exists constants $c_{1},c_{2}$ such that $c_{1}~{}g(n)\leq f(n)\leq c_{2}~{}g(n)$.
  * [22] Daniel S Abrams and Seth Lloyd.  Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.  Physical Review Letters, 83(24):5162, 1999.
  * [23] Yimin Ge, Jordi Tura, and J Ignacio Cirac.  Faster ground state preparation and high-precision ground energy estimation with fewer qubits.  Journal of Mathematical Physics, 60(2):022202, 2019.
  * [24] Lin Lin and Yu Tong.  Near-optimal ground state preparation.  Quantum, 4:372, 2020.
  * [25] Anirban Narayan Chowdhury and Rolando D Somma.  Quantum algorithms for gibbs sampling and hitting-time estimation.  Quantum Information & Computation, 17(1-2):41–64, 2017.
  * [26] Simon Apers, András Gilyén, and Stacey Jeffery.  A unified framework of quantum walk search.  In Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, 2021.
  * [27] RD Somma and G Ortiz.  Quantum approach to classical thermodynamics and optimization.  In Quantum Quenching, Annealing and Computation, pages 1–20. Springer, 2010.
  * [28] Hari Krovi, Maris Ozols, and Jérémie Roland.  Adiabatic condition and the quantum hitting time of markov chains.  Physical Review A, 82(2):022333, 2010.
  * [29] Simon Apers and Alain Sarlette.  Quantum fast-forwarding: Markov chains and graph property testing.  Quantum Information & Computation, 19(3-4):181–213, 2019.
  * [30] Mario Szegedy.  Quantum speed-up of markov chain based algorithms.  In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004.
  * [31] Hari Krovi, Frédéric Magniez, Maris Ozols, and Jérémie Roland.  Quantum walks can find a marked element on any graph.  Algorithmica, 74(2):851–907, 2016.
  * [32] Andrew Lucas.  Ising formulations of many np problems.  Frontiers in physics, 2:5, 2014.
  * [33] Rolando D Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill.  Quantum simulations of classical annealing processes.  Physical review letters, 101(13):130504, 2008.
  * [34] Trevor Keen, Eugene Dumitrescu, and Yan Wang.  Quantum algorithms for ground-state preparation and green’s function calculation.  arXiv preprint arXiv:2112.05731, 2021.
  * [35] Min-Quan He, Dan-Bo Zhang, and ZD Wang.  Quantum gaussian filter for exploring ground-state properties.  arXiv preprint arXiv:2112.06026, 2021.

Appendix for Quadratic speedup for spatial search by continuous-time quantum
walk

Here we elaborate on the proofs of the main article.

##  I Discrete and continuous-time Markov chains

Discrete-time Markov chains: A sequence of random variables
$(Y)=(Y_{j})_{j=0}^{\infty}$, is a (discrete-time) Markov chain if for all
$j>0$,

$\mathrm{Pr}\left[Y_{i}=y_{i}|Y_{0}=y_{0},Y_{1}=y_{1},\cdots,Y_{i-1}=y_{i-1}\right]=\mathrm{Pr}\left[Y_{i}=y_{i}|Y_{i-1}=y_{i-1}\right].$
(S1)

A discrete-time Markov chain over a set of $V$ nodes, such that $|V|=n$, can
be described by a $n\times n$ stochastic matrix $P$. Each entry $p_{xy}$ of
this matrix $P$, known as the transition matrix, represents the probability of
transitioning from state $x$ to state $y$.
A discrete-time random walk on such a chain is defined as follows: Suppose
$v_{0}$ is some distribution over $V$ and $Y_{0}$ is the random variable
distributed according to $v_{0}$. Then $t$ steps of a discrete-time random
walk results in a distribution $v_{t}=v_{0}P^{t}$ such that $Y_{t}$ is a
random variable distributed according to $v_{t}$. Equivalently, $t$-steps of a
discrete-time random walk corresponds to a sequence of random variables
$(Y)=(Y_{1},Y_{2},\cdots,Y_{t})$, such that each $Y_{i}$ is a random variable
from the distribution $v_{i}$.
The probability that, starting from the distribution $v$, a discrete-time
Markov chain $(Y)$ belongs to some subset $M$ of $V$ after $t$-steps will be
denoted as $\mathrm{Pr}_{v}\left[Y_{t}\in M\right]$.

Properties of Markov chains: A Markov chain is irreducible if any state can be
reached from any other state in a finite number of steps. Any irreducible
Markov chain is aperiodic if there exists no integer greater than one that
divides the length of every directed cycle of the graph. A Markov chain is
ergodic if it is both irreducible and aperiodic. By the Perron-Frobenius
Theorem, any ergodic Markov chain $P$ has a unique stationary state $\pi$ such
that $\pi P=\pi$. The stationary state $\pi$ is a stochastic row vector and
has support on all the nodes in $V$. Let us denote it as

$\pi=\left(\pi_{1}~{}~{}\pi_{2}~{}~{}\cdots~{}~{}\pi_{n}\right),$ (S2)

such that $\sum_{j=1}^{n}\pi_{j}=1$. For any ergodic Markov chain, $\pi$ is
the unique eigenvector with eigenvalue $1$. All eigenvalues of $P$ lie between
$-1$ and $1$. We shall concern ourselves with ergodic Markov chains that are
also reversible, i.e. Markov chains which satisfy the detailed balance
condition

$\pi_{x}p_{xy}=\pi_{y}p_{yx},~{}\forall(x,y)\in X.$

This can also be rewritten as

$\text{diag}(\pi)P=P^{T}\text{diag}(\pi),$

where $\text{diag}(\pi)$ is a diagonal matrix with the $j^{\text{th}}$
diagonal entry being $\pi_{j}$. In other words, the reversibility criterion
implies that the matrix $\text{diag}(\pi)P$ is symmetric. Henceforth we shall
only deal with reversible (and hence ergodic) Markov chains.

Discriminant matrix:  The discriminant matrix of $P$ is a symmetric matrix $D$
such that the $(x,y)^{\mathrm{th}}$ entry of $D$ is
$D_{xy}=\sqrt{p_{xy}p_{yx}}$. For any ergodic, reversible Markov chain $P$,

$D=\mathrm{diag}(\sqrt{\pi})P\mathrm{diag}(\sqrt{\pi})^{-1},$ (S3)

where $\sqrt{\pi}$ is a row vector with its $j^{\text{th}}$-entry being
$\sqrt{\pi_{j}}$. From this it is easy to see that $D$ and $P$ have the same
set of eigenvalues. In particular, the eigenstate of $D$ with eigenvalue $1$
is given by

$\ket{\pi}=\sum_{j=1}^{n}\sqrt{\pi_{j}}\ket{j}.$ (S4)

Lazy random walk: Often, it is convenient to add self-loops to every node of
$P$, resulting in what is called the lazy walk. In fact, we shall map
$P\mapsto(I+P)/2$ such that $P_{ii}=1/2$ for $1\leq i\leq n$. This
transformation ensures that for the Markov chain corresponding to the lazy
walk, all its eigenvalues lie between $0$ and $1$. It will be easier to deal
with lazy walks, which do not affect our results. For example, the hitting
time is affected by a factor of two by this transformation.

Interpolated Markov chains: Let $M\subset V$ denote the set of marked nodes of
$P$. For any $P$, we define $P^{\prime}$ as the absorbing Markov chain
obtained from $P$ by replacing all the outgoing edges from $M$ by self-loops.
If we re-arrange the elements of $V$ such that the set of unmarked nodes
$U\mathrel{\mathop{\ordinarycolon}}=V\backslash M$ appear first, then we can
write

$\displaystyle P=\begin{bmatrix}P_{UU}&P_{UM}\\\
P_{MU}&P_{MM}\end{bmatrix},~{}~{}~{}~{}~{}~{}~{}~{}~{}P^{\prime}=\begin{bmatrix}P_{UU}&P_{UM}\\\
0&I\end{bmatrix},$

where $P_{UU}$ and $P_{MM}$ are square matrices of size $(n-|M|)\times(n-|M|)$
and $|M|\times|M|$ respectively. On the other hand $P_{UM}$ and $P_{MU}$ are
matrices of size $(n-|M|)\times|M|$ and $|M|\times(n-|M|)$ respectively.

An interpolated Markov chain, $\left(X^{(s)}\right)$ corresponds to a
transition matrix

$P(s)=(1-s)P+sP^{\prime},$ (S5)

where $s\in[0,1]$. $P(s)$ thus has a block structure

$\displaystyle P=\begin{bmatrix}P_{UU}&P_{UM}\\\
(1-s)P_{MU}&(1-s)P_{MM}+sI\end{bmatrix}.$

Clearly, $P(0)=P$ and $P(1)=P^{\prime}$. Notice that if $P$ is ergodic, so is
$P(s)$ for $s\in[0,1)$. This is because any edge in $P$ is also an edge of
$P(s)$ and so the properties of irreducibility and aperiodicity are preserved.
However when $s=1$, $P(s)$ has outgoing edges from $M$ replaced by self-loops
and as such the states in $U$ are not accessible from $M$, implying that
$P(1)$ is not ergodic.

Now we shall see how the stationary state of $P$ is related to that of $P(s)$.
Since $V=U\cup M$, the stationary state $\pi$ can be written as
$\pi=(\pi_{U}~{}~{}\pi_{M})$, where $\pi_{U}$ and $\pi_{M}$ are row-vectors of
length $n-|M|$ and $|M|$ obtained by projecting the stationary distribution on
to the marked subspace and the unmarked subspace, respectively. As mentioned
previously, $P^{\prime}$ is not ergodic and does not have a unique stationary
state. In fact, any state having support over only the marked set is a
stationary state of $P^{\prime}$. On the other hand $P(s)$ is ergodic for
$s\in[0,1)$. Let $p_{M}=\sum_{x\in M}\pi_{x}$ be the probability of obtaining
a marked node in the stationary state of $P$. Then it is easy to verify that
the unique stationary state of $P(s)$ is

$\pi(s)=\dfrac{1}{1-s(1-p_{M})}\left((1-s)\pi_{U}~{}~{}\pi_{M}\right).$ (S6)

Continuous-time Markov chains: A continuous-time Markov chain is defined by a
continuous sequence of random variables $(X)$. From a discrete-time chain with
transition matrix $P$ we can derive a continuous-time chain by setting
$Q=P-I$. If $P$ has no self-loops then the continuous-time chain simply
follows by replacing every state of the discrete-time chain by an interval of
length distributed according to an exponential random variable with rate $1$.
If $P$ is lazy ($P_{ii}=1/2$ for every $i$) then the rate of the exponential
random variables is $1/2$. This implies that

$\mathrm{Pr}(X_{t}=x\mid X_{0}=y)=(e^{Qt})_{xy},$ (S7)

which corresponds to the $(x,y)^{\text{th}}$-entry of the matrix $e^{tQ}$. We
refer to $Q$ as the transition matrix of the continuous-time random walk on
Markov chain $(X)$. So, a continuous-time random walk for some time $t$,
starting from some distribution $v_{0}$ is simply $v_{t}=v_{0}e^{Qt}$.

Note that the random walk maps a distribution over $V$ to another distribution
over $V$ as $Q$ is a matrix whose rows sum to $0$. Equivalently a continuous-
time random walk on a graph for time $t$, corresponds to a continuous sequence
of random variables over $V$, i.e. $X=(X_{t})$. One can also define
interpolated continuous-time Markov chains (or random walks) by considering
$P(s)$: definitions translate naturally. Like in the discrete-time scenario,
the probability that, starting from the distribution $v$ a continuous-time
Markov chain $(X)$ belongs to some subset $M$ of $V$ after time $t$ will be
denoted as $\mathrm{Pr}_{v}\left[X_{t}\in M\right]$.

Finally, it will be useful for us to consider the continuous-time random walk
with transition matrix $Q=P^{2}-I$. This corresponds to the walk obtained from
two steps of a discrete-time random walk.

##  II Proof of lemma 2

We want to prove the following lemma (also stated in the main article):

Lemma 2.  Consider an ergodic, reversible Markov chain $P$ and a set of marked
nodes $M$. If we choose parameters
$s\in\\{1-1/r\mathrel{\mathop{\ordinarycolon}}r=1,2,\cdots,2^{\lceil\log
T\rceil}\\}$ and $T\in\Theta\left(HT(P,M)\right)$ uniformly at random, then
the continuous-time random walk operator $e^{D^{2}(s)-I}$ satisfies

$\mathbb{E}\left[\left\lVert\Pi_{M}e^{(D^{2}(s)-I)T}\ket{\sqrt{\pi_{U}}}\right\rVert^{2}\right]\in\Omega\left(1/\log^{2}T\right).$
(S8)

We begin by relating the quantity
$\left\lVert\Pi_{M}e^{(D(s)^{2}-I)T}\ket{\pi_{U}}\right\rVert^{2}$ to the
behaviour of the original Markov chain $P(s)$ via the following lemma (which
applies to any reversible Markov chain).

######  Lemma S3.

Consider a continuous-time Markov chain $(X)$ with transition matrix
$P^{2}-I$, where $P$ is a reversible Markov chain transition matrix with
stationary distribution $\pi$ and discriminant matrix $D$. Let $M$ be a set of
marked nodes and $U$ be the set of non-marked nodes of $P$. Then for any
$t,t^{\prime}\geq 0$ we have that

$\|\Pi_{M}e^{t(D^{2}-I)}\ket{\sqrt{\pi_{U}}}\|\geq\mathrm{Pr}_{\pi_{U}}(X_{t}\in
M,X_{t+t^{\prime}}\notin M).$

###### Proof.

The proof is similar to [5, Lemma 8]. Since
$\|\Pi_{M}e^{t^{\prime}(D^{2}-I)}\|\leq 1$ for any $t^{\prime}\geq 0$, we can
bound

$\displaystyle\|\Pi_{M}e^{t(D^{2}-I)}\ket{\sqrt{\pi_{U}}}\|$
$\displaystyle\geq\|\Pi_{M}e^{t(D^{2}-I)}\ket{\sqrt{\pi_{U}}}\|\,\|\Pi_{M}e^{t^{\prime}(D^{2}-I)}\ket{\sqrt{\pi_{U}}}\|$
$\displaystyle\geq\bra{\sqrt{\pi_{U}}}e^{t(D^{2}-I)}\Pi_{M}e^{t^{\prime}(D^{2}-I)}\ket{\sqrt{\pi_{U}}},$

where the second inequality follows from Cauchy-Schwarz. Using that
$D=\mathrm{diag}(\sqrt{\pi})P\mathrm{diag}(\sqrt{\pi})^{-1}$ we can rewrite
this as

$\displaystyle\bra{\sqrt{\pi_{U}}}e^{t(D^{2}-I)}$
$\displaystyle\Pi_{M}e^{t^{\prime}(D^{2}-I)}\ket{\sqrt{\pi_{U}}}$
$\displaystyle=\bra{\sqrt{\pi_{U}}}\mathrm{diag}(\sqrt{\pi})e^{t(P^{2}-I)}\mathrm{diag}(\sqrt{\pi})^{-1}\Pi_{M}\mathrm{diag}(\sqrt{\pi})e^{t^{\prime}(D^{2}-I)}\mathrm{diag}(\sqrt{\pi})^{-1}\ket{\sqrt{\pi_{U}}}$
$\displaystyle=\bra{\pi_{U}}e^{t(P^{2}-I)}\Pi_{M}e^{t^{\prime}(P^{2}-I)}\ket{1_{U}}=\mathrm{Pr}_{\pi_{U}}(X_{t}\in
M,X_{t+t^{\prime}}\notin M),$

where we used the shorthands $\ket{\pi_{U}}=\frac{1}{\pi(U)}\sum_{x\in
U}\pi(x)\ket{x}$ and $\ket{1_{U}}=\sum_{y\in U}\ket{y}$. ∎

Note that as $P(s)=(1-s)P+sP^{\prime}$ is reversible for any $s\in[0,1)$, we
can extend Lemma S3 to any interpolated Markov chain. We shall now be working
with this Markov chain quantity for interpolated Markov chains $(X^{(s)})$
with transition matrix $P^{2}(s)-I=((1-s)P+sP^{\prime})^{2}-I$.
Next, we use a probabilistic argument to show that there exist some (in fact,
many) choices of $t$, $t^{\prime}$ and interpolation parameter $s$ for which
the Markov chain quantity can be lower bounded. Specifically, fix some finite
subset $R\subset[0,1)$ and a range $[0,T]$. If we pick an interpolation
parameter $s\in R$ and times $t,t^{\prime}\in[0,T]$ uniformly at random, then
we can lower bound the success probability by

$\displaystyle\mathbb{E}_{s,t}\left[\|\Pi_{M}e^{t((D{(s)})^{2}-I)}\ket{\sqrt{\pi_{U}}}\|^{2}\right]$
$\displaystyle\geq\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(X^{(s)}_{t}\in
M,X^{(s)}_{t+t^{\prime}}\notin M)^{2}\right]$
$\displaystyle\geq\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(X^{(s)}_{t}\in
M,X^{(s)}_{t+t^{\prime}}\notin M)\right]^{2},$ (S9)

where we used Cauchy-Schwarz in the last inequality. We will lower bound this
by using the central technical lemma from Ref. [5], which is about _discrete-
time_ random walks.

######  Lemma S4 (Discrete-time, [5, Corollaries 11-12]).

Let $P$ be a reversible ergodic discrete-time Markov chain with stationary
distribution $\pi$. Let $(Y^{(s)})$ denote the discrete-time Markov chain with
transition matrix $P(s)$. If $\pi(M)\leq 1/9$ and $T\geq 3\mathrm{HT}(M)$, and
we choose interpolation parameter
$s\in\\{1-1/r\,\mathrel{\mathop{\ordinarycolon}}\,r=1,2,\dots,2^{\lceil\log(12T)\rceil}\\}$
and time $t,t^{\prime}\in[24T]$ uniformly at random, then

$\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(Y^{(s)}_{t}\in
M,Y^{(s)}_{t+t^{\prime}}\notin M)\right]\in\Omega(1/\log(T)).$

Given Eq. (S9) and Lemma S4, we can prove Lemma 2 by showing that

$\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(X^{(s)}_{t}\in
M,X^{(s)}_{t+t^{\prime}}\notin
M)\right]\in\Omega\left(\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(Y^{(s)}_{t}\in
M,Y^{(s)}_{t+t^{\prime}}\notin M)\right]\right),$ (S10)

where $(X^{(s)})$ corresponds to the continuous-time Markov chain with
transition kernel $P(s)^{2}-I$. We arrive at Eq. (S10) with the help of two
lemmas. For the first lemma we prove the following:

######  Lemma S5.

Consider a reversible continous-time Markov chain $(X)$ with transition matrix
$P-I$ and stationary distribution $\pi$. Let $(Y)$ denote the discrete-time
Markov chain with transition matrix $P$. For any $T$ we have that

$\int_{0}^{40T}\int_{0}^{40T}\mathrm{Pr}_{\pi_{U}}(X_{t}\in
M,X_{t+t^{\prime}}\notin
M)\operatorname{d\\!}t\,\operatorname{d\\!}t^{\prime}\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Y_{t}\in
M,Y_{t+t^{\prime}}\notin M)\right).$ (S11)

###### Proof.

By linearity of expectation it suffices to prove that

$\int_{0}^{40T}\int_{0}^{40T}\mathrm{Pr}_{v}(X_{t}\in M,X_{t+t^{\prime}}\notin
M)\operatorname{d\\!}t\,\operatorname{d\\!}t^{\prime}\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{v}(Y_{t}\in
M,Y_{t+t^{\prime}}\notin M)\right)$ (S12)

for any $v\in V$. Denote a single trajectory of the Markov chain $(Y_{t})$ by
the deterministic sequence $({\cal Y}_{t})$, and let $\mathrm{Pr}_{v}(({\cal
Y}_{t}))$ denote the probability of this trajectory, given that ${\cal
Y}_{0}=v$. Then

$\mathrm{Pr}_{v}(Y_{t}\in M,Y_{t+t^{\prime}}\notin M)=\sum_{\\{({\cal
Y}_{t})\\}}\mathrm{Pr}_{v}(({\cal Y}_{t}))I({\cal Y}_{t}\in M,{\cal
Y}_{t+t^{\prime}}\notin M),$ (S13)

with $I(Z)$ the indicator function of event $Z$. We can associate a
continuous-time trajectory to $({\cal Y}_{t})$ by drawing a sequence of
exponentially distributed time intervals $\\{\tau_{t}\\}$ of expected length
1, and replacing state ${\cal Y}_{t}$ by a time interval of length $\tau_{t}$.
For a given sequence $({\cal Y}_{t})$ we denote this trajectory by the random
variable $(X^{{\cal Y}}_{t})$. We can now expand

$\mathrm{Pr}_{v}(X_{t}\in M,X_{t+t^{\prime}}\notin M)=\sum_{\\{({\cal
Y}_{t})\\}}\mathrm{Pr}_{v}(({\cal Y}_{t}))\mathrm{Pr}(X^{\cal Y}_{t}\in
M,X^{\cal Y}_{t+t^{\prime}}\notin M).$ (S14)

Plugging (S14) and (S13) into (S12), it suffices to prove that

$\int_{0}^{40T}\int_{0}^{40T}\mathrm{Pr}_{v}(X^{\cal Y}_{t}\in M,X^{\cal
Y}_{t+t^{\prime}}\notin
M)\operatorname{d\\!}t\operatorname{d\\!}t^{\prime}\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\right),$ (S15)

for a single trajectory $({\cal Y}_{t})$.

To do so, we will prove a union bound on the following two events:

  * •

$Z$ denotes the event that $\sum_{t=1}^{2T}\tau_{t}\leq 40T$, implying that
all states $({\cal Y}_{t})_{t\leq T}$ appear as rescaled intervals in the
relevant $[0,40T]$ interval of the random variable $(X^{\cal Y}_{t})$.

  * •

$W$ denotes the event that
$\left\\{\sum_{t,t^{\prime}=1}^{T}\tau_{t}\tau_{t+t^{\prime}}\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin
M)\geq\frac{1}{2}\sum_{t,t^{\prime}=1}^{T}I({\cal Y}_{t}\in M,{\cal
Y}_{t+t^{\prime}}\notin M)\right\\}$, i.e., the left quantity exceeds $1/2$
times its expectation.

Conditioning on these events we get the wanted bound:

$\displaystyle\int_{0}^{40T}\int_{0}^{40T}\mathrm{Pr}_{v}(X^{\cal Y}_{t}\in
M,X^{\cal Y}_{t+t^{\prime}}\notin M\mid Z\cap
W)\operatorname{d\\!}t\operatorname{d\\!}t^{\prime}$
$\displaystyle=\mathbb{E}\left[\sum_{t,t^{\prime}=1}^{T}\tau_{t}\tau_{t+t^{\prime}}\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\,\bigg{|}\,Z\cap W\right]$
$\displaystyle\geq\frac{1}{2}\sum_{t,t^{\prime}=1}^{T}I({\cal Y}_{t}\in
M,{\cal Y}_{t+t^{\prime}}\notin M).$

It remains to prove that the probability of $Z\cap W$ is large. First,
combining the fact that $\mathbb{E}(\sum_{t=1}^{2T}\tau_{t})=2T$ with Markov’s
inequality we indeed have that $\mathrm{Pr}(Z)\geq 19/20$. Now define the
random variable

$A=\sum_{t,t^{\prime}=1}^{T}\tau_{t}\tau_{t+t^{\prime}}\,I({\cal Y}_{t}\in
M,{\cal Y}_{t+t^{\prime}}\notin M).$ (S16)

We wish to bound $\mathrm{Pr}(W)=\mathrm{Pr}(A\geq\mathbb{E}[A]/2)$. We know
that $\mathbb{E}[A]=\sum_{t,t^{\prime}=1}^{T}I({\cal Y}_{t}\in M,{\cal
Y}_{t+t^{\prime}}\notin M)$ and we can bound

$\displaystyle\mathbb{E}[A^{2}]$
$\displaystyle=\sum_{t,t^{\prime},s,s^{\prime}}\mathbb{E}[\tau_{t}\tau_{t+t^{\prime}}\tau_{s}\tau_{s+s^{\prime}}]\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\,I({\cal Y}_{s}\in M,{\cal
Y}_{s+s^{\prime}}\notin M)$ $\displaystyle\leq
4\left(\sum_{t,t^{\prime}=1}^{T}I({\cal Y}_{t}\in M,{\cal
Y}_{t+t^{\prime}}\notin M)\right)^{2}.$

To see this, notice that
$\mathbb{E}[\tau_{t}\tau_{t+t^{\prime}}\tau_{s}\tau_{s+s^{\prime}}]\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\,I({\cal Y}_{s}\in M,{\cal
Y}_{s+s^{\prime}}\notin M)\neq 0$ only if $t\neq t+t^{\prime}$ and $s\neq
s+s^{\prime}$, and so the “worst correlation” shows up when $t=s\neq
t+t^{\prime}=s+s^{\prime}$, in which case

$\mathbb{E}[\tau_{t}\tau_{t+t^{\prime}}\tau_{s}\tau_{s+s^{\prime}}]\leq\mathbb{E}[\tau_{t}^{2}]\,\mathbb{E}[\tau_{t+t^{\prime}}^{2}]=\left(\int_{\tau_{t}\geq
0}\tau_{t}^{2}e^{-\tau_{t}}\operatorname{d\\!}\tau_{t}\right)^{2}=4,$ (S17)

with the last equality following from partial integration. Now using the
Paley-Zygmund inequality we get that

$\mathrm{Pr}(W)=\mathrm{Pr}(A>\mathbb{E}[A]/2)\geq\frac{1}{4}\frac{\mathbb{E}[A]^{2}}{\mathbb{E}[A^{2}]}\geq\frac{1}{16}.$
(S18)

Finally, by a union bound we get that $\mathrm{Pr}(W\cap Z)\geq
1-\mathrm{Pr}(\bar{W})-\mathrm{Pr}(\bar{Z})\geq 1-15/16-1/20\geq 1/80$, and so

$\displaystyle\mathbb{E}\left[\sum_{t,t^{\prime}=1}^{T}\tau_{t}\tau_{t+t^{\prime}}\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\right]$
$\displaystyle\geq\frac{1}{80}\mathbb{E}\left[\sum_{t,t^{\prime}=1}^{T}\tau_{t}\tau_{t+t^{\prime}}\,I({\cal
Y}_{t}\in M,{\cal Y}_{t+t^{\prime}}\notin M)\,\bigg{|}\,Z\cap W\right]$
$\displaystyle\geq\frac{1}{160}\sum_{t,t^{\prime}=1}^{T}I({\cal Y}_{t}\in
M,{\cal Y}_{t+t^{\prime}}\notin M).\qed$

Note that as Lemma S5 holds for any reversible Markov chain $P$, it immediate
extends to interpolated Markov chains, $P(s)$ for any $s\in[0,1)$.
Furthermore, the lemma also holds if we replace $P$ with $P^{2}$, where $P$ is
any reversible Markov chain. Thus, Lemma S5 already gives us a relation
between continuous-time Markov chains $(X^{(s)})$, with walk operator
$e^{P^{2}(s)-I}$ and the Markov chain quantity of interest discrete-time
Markov chains $(Z^{(s)})$, with walk operator $P^{2}(s)$. That is we obtain,

$\int_{0}^{40T}\int_{0}^{40T}\mathrm{Pr}_{\pi_{U}}(X^{(s)}_{t}\in
M,X^{(s)}_{t+t^{\prime}}\notin
M)\operatorname{d\\!}t\,\operatorname{d\\!}t^{\prime}\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Z^{(s)}_{t}\in
M,Z^{(s)}_{t+t^{\prime}}\notin M)\right).$ (S19)

Now, all that is left is to relate discrete-time Markov chains with transition
matrix $P$ and discrete-time Markov chains with transition matrix $P^{2}$, for
any reversible Markov chain $P$. For this we state the following lemma:

######  Lemma S6.

Consider a reversible discrete-time Markov chain $(Y)$ with lazy transition
matrix $P$ and stationary distribution $\pi$. Let $(Z)$ denote the discrete-
time Markov chain with transition matrix $P^{2}$. For any $T$ we have that

$\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Z_{t}\in
M,Z_{t+t^{\prime}}\notin
M)\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Y_{t}\in
M,Y_{t+t^{\prime}}\notin M)\right).$ (S20)

###### Proof.

First note that for any $t>0$, $Z_{t}$ and $Y_{2t}$ are equally distributed,
which implies that

$\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Z_{t}\in
M,Z_{t+t^{\prime}}\notin
M)=\sum_{t,t^{\prime}=1}^{T}\mathrm{Pr}_{\pi_{U}}(Y_{2t}\in
M,Y_{2t+2t^{\prime}}\notin
M)\eqqcolon\sum_{t,t^{\prime}=1}^{T}A_{2t,2t^{\prime}}.$ (S21)

We would like to show that
$\sum_{t,t^{\prime}=1}^{T}A_{2t,2t^{\prime}}\in\Omega\left(\sum_{t,t^{\prime}=1}^{T}A_{t,t^{\prime}}\right)$.
To this end, recall from Lemma S3 the expression

$A_{2t,2t^{\prime}}=\braket{\pi_{U}}{P^{2t}\Pi_{M}P^{2t^{\prime}}}{1_{U}}.$
(S22)

Since $P$ is a lazy walk, we can rewrite it as $P=I/2+Q/2$ for some other
Markov chain $Q$. This allows us to bound

$A_{2t,2t^{\prime}}=\braket{\pi_{U}}{(I/2+Q/2)P^{2t-1}\Pi_{M}P^{2t^{\prime}}}{1_{U}}\geq\frac{1}{2}\braket{\pi_{U}}{P^{2t-1}\Pi_{M}P^{2t^{\prime}}}{1_{U}}=\frac{1}{2}A_{2t-1,2t^{\prime}}.$
(S23)

By the same argument we have
$A_{2t,2t^{\prime}}\geq\frac{1}{2}A_{2t,2t^{\prime}-1}$ and hence
$A_{2t,2t^{\prime}}\geq\frac{1}{4}A_{2t-1,2t^{\prime}-1}$. Combining these
bounds we see that

$A_{2t,2t^{\prime}}=\frac{A_{2t,2t^{\prime}}+A_{2t,2t^{\prime}}+A_{2t,2t^{\prime}}+A_{2t,2t^{\prime}}}{4}\geq\frac{A_{2t,2t^{\prime}}+A_{2t-1,2t^{\prime}}+A_{2t,2t^{\prime}-1}+A_{2t-1,2t^{\prime}-1}}{16}.$
(S24)

The proof now follows by noting that

$\sum_{t,t^{\prime}=1}^{T}A_{2t,2t^{\prime}}\geq\frac{1}{16}\sum_{t,t^{\prime}=1}^{T}A_{2t,2t^{\prime}}+A_{2t-1,2t^{\prime}}+A_{2t,2t^{\prime}-1}+A_{2t-1,2t^{\prime}-1}\geq\frac{1}{16}\sum_{t,t^{\prime}=1}^{T}A_{t,t^{\prime}}.\qed$
(S25)

Thus, Lemma S5 and Lemma S6, combined lead to the required bound in Eq. (S10).
Finally, equipped with this result, we can use Lemma S4 to obtain:

######  Corollary S1.

Let $P$ be a lazy, reversible ergodic discrete-time Markov chain with
stationary distribution $\pi$. Let $(X^{(s)})$ denote the continuous-time
Markov chain with transition matrix $P^{2}(s)-I$. If $\pi(M)\leq 1/9$ and
$T\geq 3\mathrm{HT}(M)$ then choosing interpolation parameter
$s\in\\{1-1/r\,\mathrel{\mathop{\ordinarycolon}}\,r=1,2,\dots,2^{\lceil\log(12T)\rceil}\\}$
and times $t,t^{\prime}\in[960T]$ uniformly at random gives that

$\mathbb{E}_{s,t,t^{\prime}}\left[\mathrm{Pr}_{\pi_{U}}(X^{(s)}_{t}\in
M,X^{(s)}_{t+t^{\prime}}\notin M)\right]\in\Omega(1/\log(T)).$ (S26)

Thus, Corollary S1 combined with Eq. (S9), results in

$\mathbb{E}\left[\left\lVert\Pi_{M}e^{(D^{2}(s)-I)T}\ket{\pi_{U}}\right\rVert^{2}\right]\in\Omega\left(1/(\log^{2}T\right),$
(S27)

for $T\in\Theta\left(HT(P,M)\right)$, which proves Lemma 2.

##  III Analog procedure to prepare the ground states of a Hamiltonian

In this section, we will show that the analog procedure leading to Eq. (3)
prepares a quantum state that is $\varepsilon$-close to the ground state of
any Hamiltonian.

Assumptions – Suppose we have a Hamiltonian $H$ with ground state
$\ket{v_{0}}$ and ground energy $\lambda_{0}$, and assume that we are given a
lower bound on the gap between the ground state and the first excited state of
$H$, i.e. we are given $\Delta$ such that
$|\lambda_{1}-\lambda_{0}|\geq\Delta$.
For clarity of exposition, we assume that the ground space of $H$ is non-
degenerate. If this is not the case, e.g. if the degeneracy of the ground
space is $d$ and is spanned by mutually orthonormal eigenstates
$\\{\ket{v^{(\ell)}_{0}}\\}_{l=1}^{d}$, then we will be preparing a quantum
state $\ket{v_{0}}$ which is a projection onto the ground space given by

$\ket{v_{0}}=\dfrac{1}{\sqrt{\sum_{\ell=1}^{d}|c^{(\ell)}_{0}|^{2}}}\sum_{\ell=1}^{d}c^{(\ell)}_{0}\ket{v^{(\ell)}_{0}}.$

In addition, suppose we have access to some initial state $\ket{\psi_{0}}$ and
a lower bound on the overlap $|\braket{\psi_{0}}{v_{0}}|=c_{0}\geq\eta$.
Furthermore, for some desired accuracy $\varepsilon\in(0,1)$, we will assume
that we know the value of the ground energy to some precision parameter
$\varepsilon_{g}$ such that
$\varepsilon_{g}\in\mathcal{O}\left(\Delta/\sqrt{\log\frac{1}{\eta\varepsilon}}\right)$.
That is, we know some $E_{0}$ such that

$|\lambda_{0}-E_{0}|\leq\varepsilon_{g}.$ (S28)

By implementing $H-(E_{0}-\varepsilon_{g})I$, we ensure that
$0\leq\lambda_{0}\leq 2\varepsilon_{g}$. This transformation also ensures that
the lower bound for the spectral gap of $H$ remains $\Delta$. If also an upper
bound on the maximum eigenvalue of $H$ is known, then we can actually assume
that the spectrum of $H$ is in $[0,1]$.
Note that these assumptions are standard and apply to quantum algorithms for
this problem designed in the circuit model [23, 24].

Running time and success probability – Now we are in a position to formally
state the ground state preparation algorithm and analyze its complexity, which
we do in the following lemma.

######  Lemma S7.

Suppose $\varepsilon\in(0,1)$ and $\eta\leq 1/\sqrt{2}$. Furthermore suppose
we have a Hamiltonian $H$ with ground state $\ket{v_{0}}$ with $\Delta$ being
a lower bound on the spectral gap. Also, the ground state energy of $H$ is
known up to a precision
$\varepsilon_{g}\in\mathcal{O}\left(\Delta/\sqrt{\log\frac{1}{\eta\varepsilon}}\right)$.
Then, given an initial state $\ket{\psi_{0}}$ satisfying
$|\braket{\psi_{0}}{v_{0}}|\geq\eta$, we output, with probability
$\mathcal{O}(\eta^{2})$, a state $\ket{\phi}$ such that
$\left\lVert\ket{\phi}-\ket{v_{0}}\right\rVert\leq\varepsilon$ by evolving the
Hamiltonian $H^{\prime}=H\otimes\hat{z}$ for time

$T\in\mathcal{O}\left(\dfrac{1}{\Delta}\sqrt{\log\left(\dfrac{1}{\eta\varepsilon}\right)}\right).$

###### Proof.

We shift the overall eigenvalues of $H$ by $-E_{0}+\varepsilon_{g}$ as
explained previously. So now suppose $H$ has a spectral decomposition is
$H=\sum_{j}\lambda_{j}\ket{v_{j}}\bra{v_{j}}$ with eigenvalues
$\lambda_{j}\in(0,1]$ and particularly $0\leq\lambda_{0}\leq
2\varepsilon_{g}$.

Then the input quantum state, when expressed in the eigenbasis of $H$ is
written as $\ket{\psi_{0}}=\sum_{j}c_{j}\ket{v_{j}}$. Without loss of
generality, we assume that $c_{0}$ is real and positive. Then following the
analog procedure outlined in the main article, we obtain from Eq. (3) that

$\ket{\eta_{t}}=e^{-tH^{2}}\ket{\psi_{0}}\ket{\psi_{g}}+\ket{\Phi}^{\perp}.$
(S29)

By post-selecting on obtaining the Gaussian state $\ket{\psi_{g}}$ on the
second register, we are left with the following quantum state in the first
register after a time $\sqrt{2t}$

$\ket{\phi}=\dfrac{e^{-tH^{2}}\ket{\psi_{0}}}{\sqrt{\braket{\psi_{0}}{e^{-2tH^{2}}}{\psi_{0}}}},$
(S30)

with probability
$\|e^{-tH^{2}}\ket{\psi_{0}}\ket{\psi_{g}}\|^{2}=\braket{\psi_{0}}{e^{-2tH^{2}}}{\psi_{0}}$.
Expressing $\ket{\phi}$ in the eigenbasis of $H$, we obtain

$\ket{\phi}=\dfrac{c_{0}e^{-t\lambda^{2}_{0}}}{\sqrt{\braket{\psi_{0}}{e^{-2tH^{2}}}{\psi_{0}}}}\left[\ket{v_{0}}+\sum_{j\geq
1}\dfrac{c_{j}}{c_{0}}e^{-t(\lambda^{2}_{j}-\lambda^{2}_{0})}\ket{v_{j}}\right],$
(S31)

where the normalization factor

$\braket{\psi_{0}}{e^{-2tH^{2}}}{\psi_{0}}=|c_{0}|^{2}e^{-2t\lambda^{2}_{0}}\left[1+\sum_{j\geq
1}\frac{|c_{j}|^{2}}{|c_{0}|^{2}}e^{-2t(\lambda^{2}_{j}-\lambda^{2}_{0})}\right].$
(S32)

Now, we intend to choose a value of $t$, so that $\ket{\phi}$ and the ground
state $\ket{v_{0}}$ are $\varepsilon$-close to each other in $\ell_{2}$-norm.
We have,

$\left\lVert\ket{\phi}-\ket{v_{0}}\right\rVert^{2}=2-2\braket{\phi}{v_{0}},$
(S33)

where we use the fact that $c_{0}\geq 0$ which implies
$\braket{\phi}{v_{0}}>0$. Thus we have,

$\displaystyle\braket{\phi}{v_{0}}$ $\displaystyle=\left[1+\sum_{j\geq
1}\dfrac{|c_{j}|^{2}}{|c_{0}|^{2}}e^{-2t(\lambda_{j}^{2}-\lambda_{0}^{2})}\right]^{-1/2}$
$\displaystyle\geq\left[1+\dfrac{1-\eta^{2}}{\eta^{2}}e^{-2t(\lambda_{1}^{2}-\lambda_{0}^{2})}\right]^{-1/2}$
$\displaystyle\geq
1-\dfrac{1-\eta^{2}}{2\eta^{2}}e^{-2t(\lambda_{1}^{2}-\lambda_{0}^{2})},$

which gives

$\left\lVert\ket{\phi}-\ket{v_{0}}\right\rVert^{2}\leq\dfrac{1-\eta^{2}}{\eta^{2}}e^{-2t(\lambda_{1}^{2}-\lambda_{0}^{2})}\leq\dfrac{1-\eta^{2}}{\eta^{2}}e^{-2t(\lambda_{1}-\lambda_{0})^{2}}.$
(S34)

Thus by choosing any value of $t$ such that

$\displaystyle
t>\dfrac{1}{2\Delta^{2}}\log\left(\dfrac{1-\eta^{2}}{\eta^{2}\varepsilon^{2}}\right),$

we ensure that $\left\lVert\ket{\phi}-\ket{v_{0}}\right\rVert\leq\varepsilon$.
The total evolution time of the interaction Hamiltonian is $T=\sqrt{2t}$,
which is

$T\in\mathcal{O}\left(\dfrac{1}{\Delta}\sqrt{\log\left(\dfrac{1}{\eta\varepsilon}\right)}\right).$
(S35)

Now we have,

$\braket{\psi_{0}}{e^{-2tH^{2}}}{\psi_{0}}=\dfrac{|c_{0}|^{2}e^{-2t\lambda^{2}_{0}}}{|\braket{\phi}{\psi_{0}}|^{2}}\geq|c_{0}|^{2}e^{-2t\lambda^{2}_{0}}.$
(S36)

So the success probability of our algorithm

$\braket{\psi_{0}}{e^{-T^{2}H^{2}}}{\psi_{0}}\geq|c_{0}|^{2}e^{-T^{2}\lambda^{2}_{0}}\geq\mathcal{O}(\eta^{2}),$
(S37)

where we have used the fact that $\lambda_{0}\leq 2\varepsilon_{g}$ and so
$T\lambda_{0}\in\mathcal{O}(1)$. ∎

The running time of this simple analog procedure matches that of the best-
known quantum algorithms for this problem in the circuit model [23, 24].