# Improvement of quantum walk-based search algorithms in single marked vertex
graphs

Xinying Li  Institute of Mathematics, Academy of Mathematics and Systems
Science, Chinese Academy of Sciences, Beijing 100190, China  School of
Mathematical Sciences, University of Chinese Academy of Sciences, Beijing
100049, China  Yun Shang<EMAIL_ADDRESS>Institute of Mathematics, Academy
of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing
100190, China  NCMIS, MDIS, Academy of Mathematics and Systems Science,
Chinese Academy of Sciences, Beijing 100190, China

###### Abstract

Quantum walks are powerful tools for building quantum search algorithms or
quantum sampling algorithms named the construction of quantum stationary
state. However, the success probability of those algorithms are all far away
from 1. Amplitude amplification is usually used to amplify success
probability, but the soufflé problems follow. Only stop at the right step can
we achieve a maximum success probability. Otherwise, as the number of steps
increases, the success probability may decrease, which will cause troubles in
practical application of the algorithm when the optimal number of steps is not
known.

In this work, we define generalized interpolated quantum walks, which can both
improve the success probability of search algorithms and avoid the soufflé
problems.

Then we combine generalized interpolation quantum walks with quantum fast-
forwarding. The combination both reduce the times of calling walk operator of
searching algorithm from $\Theta((\varepsilon^{-1})\sqrt{\mathrm{HT}})$ to
$\Theta(\log(\varepsilon^{-1})\sqrt{\mathrm{HT}})$ and reduces the number of
ancilla qubits required from
$\Theta(\log(\varepsilon^{-1})+\log\sqrt{\mathrm{HT}})$ to
$\Theta(\log\log(\varepsilon^{-1})+\log\sqrt{\mathrm{HT}})$, and the souffle
problem is avoided while the success probability is improved, where
$\varepsilon$ denotes the precision and $\mathrm{HT}$ denotes the classical
hitting time.

Besides, we show that our generalized interpolated quantum walks can be used
to improve the construction of quantum states corresponding to stationary
distributions as well.

Finally, we give an application that can be used to construct a slowly
evolving Markov chain sequence by applying generalized interpolated quantum
walks, which is the necessary premise in adiabatic stationary state
preparation.

##  1 Introduction

Algorithms based on quantum walks have been studied widely and speed-up
classical random walk algorithms on many problems, such as element
distinctness [1], triangle finding [2], matrix product verification [3],
especially on searching problems and sampling problems.

In classical random walks, hitting time describes the speed to reach marked
vertex set and mixing time denotes the convergence speed of Markov chain to
approximate stationary distribution. They reflect the algorithm complexity of
classical search problems and sampling

problems and have many applications [4], such as mixing time can be used for
Google’s PageRank algorithm of ranking websites [5].

Since quantum walks have shown their advantages compared with random walks,
the studies in quantum version of hitting time and mixing time is the current
research focus. By quantizing classical discrete Markov chains, a bipartite
quantum walk model was proposed by Szegedy [6], which proved that quantum
algorithms quadraticly speed up classical hitting time in detecting the
existence of marked vertices for symmetric Markov chain. After Szegedy’s
framework, there appeared many new algorithms with better complexity
performance in many variety contexts [7, 8, 9].

By introducing recursive amplitude amplification, Magniez et al. extended
Szegedy’s framework to find marked vertex in reversible ergodic Markov chains
[10]. However, its complexity can not quadratic speed-up the classical
algorithms such as for 2D grid search problem. Then Tulsi proposed a new
technique to solve the open problem [11]. By extending Tulsi’s technique,
Magniez et al. [12] demonstrated the possibility of finding a unique marked
vertex with a square root speed up over the classical hitting time for any
reversible state-transitive single-marked vertex Markov chain. In [13], Krovi
et al. introduced the interpolated quantum walks, the serious restrictions are
relaxed to reversible Markov chain with single-marked vertex. Recently,
Ambainis et al. [14] introduced a search algorithm for any reversible Markov
chain with quadratic speedup, which is more suitable for multi-marked vertices
graphs, but does not perform as well as [13] on single-marked vertex graphs.

Simultaneously, reverse search algorithms and stationary states can be
prepared in $\Theta(\sqrt{\mathrm{HT}}\frac{1}{\varepsilon})$ walk steps for
any reversible Markov chain [13]. Further, the number of walk steps and
ancilla qubits required is improved in [15] by constructing a new reflection
on stationary state and introducing quantum fast-forwarding.

However, all above search algorithms and qsampling algorithms can only achieve
constant success probability or even less, and in order to improve success
probability, amplitude amplification is usually introduced. Unfortunately, the
implementation of amplitude amplification often introduces the soufflé
problems [16], because the largest success probability can be achieved only
when we stop at the right time. Stopping too early or too late will not
maximize the success probability. Since the success probability has only a
lower bound instead of an exact value, which means we do not know the proper
time to stop. When we stop late, the success probability will decrease as the
number of steps increases. Besides, now all search algorithms with constant
success probability are linearly related to $\varepsilon^{-1}$, where
$\varepsilon$ denotes the error of algorithm. Obviously, the dependency on
error is too large. For example, if we want to improve the success probability
from $1/16$ to $1/4$ with error $1/400$, the cost of current algorithm will
become 100 times of the original algorithm cost [13]. When it comes to the
qsampling algorithm, the error required is even smaller, and the number of
calling walk operator will follow with a sharp increase.

To increase success probability, in this work, we introduce generalized
interpolated quantum walks, which will be combined with phase estimation to
construct a new search algorithm instead of amplitude amplification. The
introduction of generalized interpolated quantum walks both amplifies the
success probability and avoids the soufflé problems while maintaining the time
complexity.

Based on reversible Markov chains, quantum fast-forwarding algorithm [17] can
simulate actions of $n$ random walk steps by $\sqrt{n}$ quantum walks steps.
Here we find generalized interpolated quantum walks can be combined with
quantum fast-forwarding. The combination reduces the dependency on error,
which not only reduces the time complexity but also reduces the number of
ancilla qubits required.

Similar to the above search algorithm, for qsampling problems, our generalized
interpolated quantum walks also improve the success probability and avoid the
soufflé problems as well.

Finally, we give an application of generalized interpolated quantum walks. In
adiabatic quantum computing, a quantum state can be prepared by preparing the
ground state of a slowly evolving Hamiltonian sequence, and the ground state
of Hamiltonian can be seen as the stationary state of corresponding Markov
chain. However, it is not easy to prepare the needed Hamiltonian or Markov
chain in adiabatic quantum computing. By applying generalized interpolated
walks, we can construct a series of slowly evolving Markov chains and prepare
quantum stationary state in adiabatic quantum computation.

The paper is organized as follows. Preliminaries is provided in Section 2.1
firstly. Second we define generalized interpolated walks in Section 2.2. Then
to amplify the success probability of search algorithms and qsampling
algorithms, we apply generalized interpolated walks with quantum phase
estimation and quantum fast-forwarding instead of amplitude amplification in
Section 3.1 and Section 3.2. Besides, we apply generalized interpolated walks
to prepare quantum stationary state of Markov chains in adiabatic quantum
computing in Section 3.3. Finally, the paper is concluded in Section 4.

##  2 Methods

###  2.1 Preliminaries

We introduce random walks firstly. Consider a graph $G(V,E)$ consisting of
$N=|V|$ vertices, the transition probability between vertices depends on
Markov chain $P$. For arbitrary vertex $x,y\in V$, $p_{xy}$ denotes the
transition probability from $x$ to $y$. $P=(p_{xy})_{x,y\in V}$ is the
corresponding transition matrix of the Markov chain, and the corresponding
discriminant matrix is

$D(P)\coloneqq\sqrt{P\circ P^{T}},$

where ’$\circ$’ and square root are computed element-wise.

For any Markov chain P, if after enough steps every vertex in it can reach any
other vertex, and the length of each directed cycle has the greatest common
factor of 1, then P is ergodic. Ergodic Markov chain has a unique
$1$-eigenvector, $i.e.$ stationary distribution, which is represented by
$\pi={(\pi_{x})}_{x\in V}$. A chain is reversible if it satisfies
$\pi_{x}p_{xy}=\pi_{y}p_{yx}$, and naturally, there is $D(P)\pi=\pi$.

Assume P is a reversible Markov chain. By introducing lazy walks [13], all
eigenvalues of $P$ lie in $[0,1]$, where $\lambda_{0}$ denotes the eigenvalue
of $P$ that equals to $1$ and the other eigenvalues $\lambda_{j}$ for
$j=1,\dotsc,n-1$ are strictly less than $1$ in non-increasing order. The
eigenvalue gap of $P$ is $\Delta\coloneqq 1-\lambda_{1}$.

For any ergodic reversible Markov chain P on graph $G(V,E)$, the corresponding
quantum walks perform on the extended space $\Lambda_{V}\otimes\Lambda_{V}$,
where $\Lambda_{V}\coloneqq\mathrm{span}\\{|x\rangle,x\in V\\}$. For arbitrary
initial probability distribution $\sigma$ over $V$, the initial state is
defined as $|\sigma\rangle|\bar{0}\rangle$, where “$|\bar{0}\rangle$” in the
second register is some fixed initialization state in $\Lambda_{V}$. The
corresponding quantum walk operator of reversible Markov chain P can be
expressed as

$W(P)\coloneqq V(P)^{\dagger}\cdot S\cdot V(P)\cdot R_{\bar{0}},$

where $V(P)$ is derived from the transition matrix $P$ as

$V(P)|x\rangle|\bar{0}\rangle\coloneqq|x\rangle\sum_{y\in
X}\sqrt{P_{xy}}|y\rangle.$

The unitary swap operator $S$ and reflection operator $R_{\bar{0}}$ are
expressed respectively as

$|x\rangle|y\rangle\mapsto
S|x\rangle|y\rangle\coloneqq\begin{cases}|y\rangle|x\rangle,&\text{if
}(x,y)\in E,\\\ |x\rangle|y\rangle,&\text{otherwise.}\end{cases}$
$|x\rangle|y\rangle\mapsto R_{\bar{0}}|x\rangle|y\rangle\coloneqq
I\otimes\left(2|\bar{0}\rangle\langle\bar{0}|-I\right)|x\rangle|y\rangle.$

For a graph $G$ with a marked subset $M\subseteq V$, the expectation time to
hit any marked vertex in $M$ by a random walk with Markov chain P is called
classical hitting time $\mathrm{HT}(P,M)$, which is defined as

$\mathrm{HT}(P,M)\coloneqq\sum_{k=1}^{n-|M|}\frac{|\langle
v_{k}^{\prime}|\bar{\pi}\rangle|^{2}}{1-\lambda_{k}^{\prime}},$ (1)

where $\lambda_{k}^{\prime}$ and $|v_{k}^{\prime}\rangle$ are eigenvalues and
the corresponding eigenvectors of the discriminant matrix $D(P^{\prime})$
defined by the Markov chain $P^{\prime}$ in nondecreasing order, and
$P^{\prime}$ is the absorbing version of $P$ that all outgoing transformations
from marked vertices are replaced by self-loops. Let
$\mathrm{HT}\coloneqq\max_{x\in V}\mathrm{HT}(P,\\{x\\})$ denote the maximum
hitting time to reach any vertex in $V$.

In order to search a vertex in $M$, Krovi et al. introduced interpolation into
Markov chain firstly [13, 18]. The interpolated Markov chain $P(s)$ can be
expressed as

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

where $0\leq s\leq 1$, and the corresponding $W(s)$ and $D(s)$ are defined as
$W(P(s))$ and $D(P(s))$.

From the construction of $W(s)$, there may be more than one $1$-eigenvectors
for $W(s)$. Here we choose one of them as $|v_{0}(s)\rangle$ to prove the
following theorem. Define $|v_{0}(s)\rangle$ as

$|v_{0}(s)\rangle=\sum_{x}\sqrt{\frac{(1-s)\pi_{x}+s\pi^{\prime}_{x}}{1-s+s\pi_{M}}}|x\rangle,$
(2)

where $\pi^{\prime}$ is a classical vector that all zeros in the unmarked
vertices, and the same as $\pi$ in the marked vertices. It is easy to get

$W(s)|v_{0}(s)\rangle|\bar{0}\rangle=|v_{0}(s)\rangle|\bar{0}\rangle,\
D(s)|v_{0}(s)\rangle=|v_{0}(s)\rangle,\quad\forall s\in\left[0,1\right].$

Similar to the classical random walk algorithm, assume that quantum walks have
access to the following (controlled) unitary operators:

$Setup(\pi)$: generates $|\pi\rangle|\bar{0}\rangle$,
where$|\pi\rangle=\sum_{x}\sqrt{x}$. Complexity $\mathcal{S}$.

$Update(P)$: implements a (controlled) walk operator $W(P)$. Complexity
$\mathcal{U}$.

$Check(M)$: checks whether $x$ is a marked vertex. Complexity $\mathcal{C}$.
Described by the mapping

$\forall x\in
V,b\in{0,1}:|x\rangle|b\rangle\to\left\\{\begin{matrix}|x\rangle|b\rangle\quad\quad\
&if\ x\notin M\\\ |x\rangle|b\oplus 1\rangle&if\ x\in M.\end{matrix}\right.$

We list the search algorithm and related details as below. The search
algorithm proposed by Krovi et al. [13] consists of interpolated walks and
quantum phase estimation and can be expressed as follows:

1\. Use $Setup(\pi)$ to prepare $|\pi\rangle|\bar{0}\rangle$.

2\. Apply $Check(M)$ to check whether the current vertex belongs to $M$.

a. If it is marked, measure and output the current state.

b. Otherwise, apply $U_{qee}(W(s),\lceil\log\sqrt{\mathrm{HT}}\rceil)$.
$U_{qee}(W(s),\lceil\log\sqrt{\mathrm{HT}}\rceil)$ is quantum phase estimation
operator and expressed in the following lemma.

######  Lemma 1 (Phase estimation [19]).

Let $A$ be an arbitrary unitary operator on $n$ qubits and $|\Psi_{k}\rangle$
is any eigenvector of $A$ with eigenvalue $e^{i\phi_{k}}$, where
$0\leq\phi_{k}\leq\frac{\pi}{2}$. It does not need to know the exact value of
$A$ or $|\Psi_{k}\rangle$ or $e^{i\phi_{k}}$. For any precision
$t\in\mathbb{N}$, there exists a phase estimation algorithm $U_{qee}(A,t)$,
which performs controlled-$A$, controlled-$A^{2}$, …,
controlled-$A^{2^{t-1}}$. For $k=0,\cdots,n-1$, the phase estimation algorithm
$U_{qee}(A,t)$ acts on the eigenvector $|\Psi_{k}\rangle$ as

$|\Psi_{k}\rangle|0^{t}\rangle\mapsto
U_{qee}(A,t)|\Psi_{k}\rangle|0^{t}\rangle=|\Psi_{k}\rangle\frac{1}{2^{t}}\sum_{l,m=0}^{2^{t}-1}e^{-\frac{2\pi
ilm}{2^{t}}}e^{i\phi_{k}l}|m\rangle=:|\Psi_{k}\rangle|\xi_{k}\rangle,$

where $|\Psi_{k}\rangle|\xi_{k}\rangle$ satisfies that
$\langle{0^{t}}|{\xi_{k}}\rangle=\frac{1}{2^{t}}\sum_{l=0}^{2^{t}-1}e^{i\phi_{k}l}$.
The algorithm calls $\mathcal{O}(2^{t})$ controlled-$A$ operator and
$\mathcal{O}(t)$ ancilla qubits in total.

For any reversible Markov chain with single-marked vertex $g$, the output
state in above search algorithm has constant overlap with the target state
$|g\rangle$, but the maximum success probability is about $1/4-\varepsilon$.
Amplitude amplification is usually applied to enlarge the success probability.

Qsampling algorithm [15] consists of quantum interpolated walks and quantum
fast-forwarding algorithm and can be expressed as follows:

1\. Use $Setup(g)$ to prepare $|g\rangle$ for any vertex $g\in V$.

2\. Apply $U_{qfs}(W(s),\log\lceil\sqrt{\mathrm{HT}}\rceil)$.
$U_{qfs}(W(s),\log\lceil\sqrt{\mathrm{HT}}\rceil)$ is a unitary operator
composed of the quantum fast-forwarding operator and can be expressed as:

$ccX_{2,4}X_{4}(U_{qff}^{\dagger}(W(s),\log\lceil\sqrt{\mathrm{HT}}\rceil)\otimes
I)ccX_{234,5}(U_{qff}(W(s),\log\lceil\sqrt{\mathrm{HT}}\rceil)\otimes
I)X_{4}ccX_{2,4}.$

Let $\Lambda_{0}\coloneqq\mathrm{span}\\{|0\rangle,|1\rangle\\}$, and the
above operator is applied in five registers as
$\Lambda_{V}\otimes\Lambda_{V}\otimes\Lambda_{0}^{\tau}\otimes\Lambda_{0}\otimes\Lambda_{0}^{r}$.
The symbols above are defined as below: for any operator $A$, $A_{x}$
represents the $x$th register which is applied with $A$; $cA_{x,y}$ represents
the controlled-$A$ gate with control register $x$ and target register $y$,
where $A$ is applied when the $x$th qubit is $|1\rangle$; similarly,
$ccA_{x,y}$ represents that the controlled gate $A$ is applied when the $x$th
qubit is $|0\rangle$.

The state after the unitary operator $U_{qfs}$ has constant overlap with the
target state $|\pi\rangle$, but the maximum possible value is not enough and
amplitude amplification is usually applied to enlarge success probability. In
the following we propose a concept of generalized quantum interpolated walks,
which can improve the success probability of above search algorithm and
qsampling algorithm to at least $4/5$.

###  2.2 Generalized quantum interpolated walks

Here we define generalized interpolated walks as follows.

######  Definition 1 (Generalized quantum interpolated walks).

Let $P$ be a Markov chain with a set of marked vertices $M$, and the
corresponding absorbing walk is $P^{\prime}$. For a series of parameter
$\\{s_{1},s_{2},...,s_{r}:0\leq s_{1},\cdots,s_{r}\leq 1\\}=:S$, an
independent Markov chain $Q$ is defined to express the transition probability
$q_{ij}$ from $s_{i}$ to $s_{j}$. $s_{k_{1}},s_{k_{2}},\cdots$ is a sequence
determined by the Markov chain $Q$, where $s_{k_{i+1}}$ is the next item of
$s_{k_{i}}$ according to $(q_{ij})_{1\leq i,j\leq r}$. Generalized
interpolated Markov chain is defined as
$P(S)\coloneqq\\{P(s_{k_{1}}),P(s_{k_{2}}),\cdots\\}$, where

$P(s_{k_{i}})=(1-s_{k_{i}})P+s_{k_{i}}P^{\prime}.$

All the previous quantum interpolated walks can be seen as special cases of
generalized interpolated walks. We summarize and list them in Table 1 and
apply a special case in following sections.

Figure 1: Relationship between all above interpolated walks. Table 1: The generalized interpolated walks and special cases Quantum interpolated walks frameworks |  $Q$
---|---
Generalized interpolated walks |  $S=\\{s_{1},s_{2},...,s_{r}\\}$, $Q=(q_{ij})_{1\leq i,j\leq r}$
Krovi’s interpolated walks [13] |  $r=1$
Ambainis’s interpolated walks [14] |  $q_{i,j}=1/r,\forall 1\leq i,j\leq r$
Our improved interpolated walks for searching and qsampling |  $q_{i,i+1}=1,\forall 1\leq i\leq r-1$

######  Remark 2 (The relationship between interpolated walk framework).

We list all above interpolated walks as follow, and the relationship between
them is in Figure 1. If $r=1$, generalized quantum interpolated walks
degenerate to Krovi’s interpolated walks [13], which are determined by only
one parameter $s$ chosen by preparing a 1-eigenvector of $W(s)$ that has a
large overlap with both the initial state and the target state.

Ambainis’s interpolated walks [14] can be seen as that each $s_{i}$ in
$S\coloneqq\\{s_{1},s_{2},\cdots,s_{r}:0\leq s_{1},\cdots,s_{r}\leq 1\\}$ is
chosen with equal probability and $W(s_{i})$ acts on the initial state.
Therefore the walk based on Markov chain Q is in complete graph, and the
corresponding distribution keeps
$(\frac{1}{r},\frac{1}{r},\cdots,\frac{1}{r})$. The series of $s_{i}$ can be
constructed as
$\\{1-\frac{1}{r}:r\in\\{1,2,4,\cdots,2^{\lceil\log(2592\mathrm{HT})\rceil}\\}\\}$,
and the corresponding walk operators are applied to the initial state
$|\pi\rangle$ in superimposed form.

Our improved interpolated walks which is applied in following section fixe the
order of each $s_{i}$ in $S\coloneqq\\{s_{1},s_{2},\cdots,s_{r}:0\leq
s_{1},\cdots,s_{r}\leq 1\\}$. By implementing the walk operator corresponding
to each $s_{i}$ one by one, as $i$ increases, the overlap between the
1-eigenvector of the current quantum walk operator and the target state will
become larger.

As far as we know, quantum interpolated walks that applied previously to
search problems or qsampling problems have only one parameter $s$, and the
maximum successful probability corresponding to single implementation is a
small constant [13, 20] or even smaller [14].

##  3 Results

###  3.1 Algorithms based on quantum phase estimation

By applying generalized interpolated walks instead of amplitude amplification,
we will amplify the success probability of the search algorithms and qsampling
algorithms while maintaining the time complexity and avoiding the soufflé
problems.

Figure 2: Soufflé problem.

Since the success probability of existing algorithms is still far from $1$,
generally, amplitude amplification is used to enlarge the success probability,
and then we often face soufflé problem. When the number of search steps is
greater than the steps required, the success probability of these algorithms
may drop dramatically as Figure 2. Here we replace the single parameter $s$
with $S\coloneqq\\{s_{1},s_{2},...,s_{n}\\}$, the set of parameters, and use
this to amplify the success probability instead of amplitude amplification.

######  Theorem 1 (Search marked vertex based on quantum phase estimation).

For an ergodic reversible Markov chain $P$ in $G(V,E)$ with single marked
vertex $g$, Algorithm 1 achieves $|g\rangle$ with success probability more
than $4/5$ from initial state $|\pi\rangle$. The complexity is
$\mathcal{S}+\Theta(\varepsilon^{-1}\sqrt{\mathrm{HT}})(\mathcal{U}+\mathcal{C})$
with $\Theta(\log(\varepsilon^{-1})+\log\sqrt{\mathrm{HT}})$ ancilla qubits,
where $\varepsilon$ is error.

Algorithm 1 The generalized interpolated search algorithm based on quantum
phase estimation

Input: $\Gamma_{1}$, a number satisfies that
$\Gamma_{1}=\frac{r\pi\sqrt{\mathrm{HT}}}{\sqrt{2}\varepsilon}$, where
$\varepsilon$ is the error.
Output: A state that has a constant overlap with the $|g\rangle$.

1: Set $\tau=\lceil\log\Gamma_{1}\rceil$, and prepare the initial state as
$|\pi\rangle|\bar{0}\rangle|0^{\tau}\rangle$ on
$\mathsf{R}_{1}\mathsf{R}_{2}\mathsf{R}_{3}$.

2: Measure $\mathsf{R}_{1}$ and check it whether it is $|g\rangle$ by
$\Pi_{g}=|g\rangle\langle g|$.

3: if the current vertex is marked then

4: return the marked vertex, stop.

5: else

6: for i = 1,2,…,r do

7: Apply $U_{qee}(W(s_{i}),\tau)$ with $s_{i}$ to the current state.

8: end for

9: end if

10: Measure and output the first register.

Intuitively, our quantum algorithm works as Figure 3. We fix the set of
parameters as $\\{s_{1},s_{2},\cdots,s_{r}:0\leq s_{1}\leq\cdots\leq s_{r}\leq
1\\}$. Firstly, we map $|\bar{\pi}\rangle$ to $|v_{0}(s_{1})\rangle$ by
quantum walk operator based on $P(s_{1})$, and then map $|v_{0}(s_{1})\rangle$
to $|v_{0}(s_{2})\rangle$ by quantum walk operator based on $P(s_{2})$, …,
finally, we map $|v_{0}(s_{r-1})\rangle$ to $|v_{0}(s_{r})\rangle$ by quantum
walk operator based on $P(s_{r})$ and measure $|v_{0}(s_{r})\rangle$ in the
standard basis to get the marked vertex.

Figure 3: Our quantum algorithm framework.

We analyze the success probability firstly. For the initial state
$|\pi\rangle$ and target state $|g\rangle$, let $p_{succ}$ denote the success
probability, then we have

$\sqrt{p_{succ}}=\||g\rangle\langle g|_{1}U_{qee}(s_{r})\cdots
U_{qee}(s_{2})U_{qee}(s_{1})(|\bar{\pi}\rangle|\bar{0}0^{\tau}\rangle)\|.$

When $M=\\{g\\}$, define the state after Step. 2 as
$|\bar{\pi}\rangle\coloneqq\frac{1}{\sqrt{1-\pi_{g}}}\sum_{x\notin
g}\sqrt{\pi_{x}}|x\rangle.$ From (2), we have

$|v_{0}(s_{i})\rangle=\cos\theta_{i}|\bar{\pi}\rangle+\sin\theta_{i}|g\rangle,$

where $\cos\theta_{i}\coloneqq\sqrt{\frac{1-s_{i}}{s_{i}}}$,
$\sin\theta_{i}\coloneqq\sqrt{\frac{2s_{i}-1}{s_{i}}}$.

Set $|v_{0}(s_{0})\rangle\coloneqq|\bar{\pi}\rangle$, for $i=1,\cdots,r$,
$k=0,\cdots,n-1$, and $\beta_{k}^{i}\coloneqq\left\langle
v_{k}(s_{i})|v_{0}(s_{i-1})\right\rangle$. Since for any $s\in[0,1]$ we have
$|\bar{\pi}\rangle\in\Lambda_{V}=\mathrm{span}\\{|v_{k}(s)\rangle|k=0,\cdots,n-1\\}$,
then

$\displaystyle|\bar{\pi}\rangle=\sum_{k=0}^{n-1}\left\langle
v_{k}(s_{1})|\bar{\pi}\right\rangle\cdot|v_{k}(s_{1})\rangle=\sum_{k=0}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle.$

Here we give an estimation of the success probability $p_{succ}$ as below.

$\displaystyle\sqrt{p_{succ}}$ $\displaystyle=\||g\rangle\langle
g|_{1}U_{qee}(s_{r})\cdots
U_{qee}(s_{1})(\sum_{k=0}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle)|\bar{0}0^{\tau}\rangle\|$
$\displaystyle\geq\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\Pi_{0^{\tau}}U_{qee}(s_{1})(\sum_{k=0}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle)|\bar{0}0^{\tau}\rangle\|$
where $\Pi_{0^{\tau}}=I\otimes I\otimes|0^{\tau}\rangle\langle 0^{\tau}|$
$\displaystyle\geq\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\Pi_{0^{\tau}}U_{qee}(s_{1})\beta_{0}^{1}|v_{0}(s_{1})\rangle|\bar{0}0^{\tau}\rangle\|-$
$\displaystyle\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\Pi_{0^{\tau}}U_{qee}(s_{1})(\sum_{k=1}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle)|\bar{0}0^{\tau}\rangle\|$
from triangle inequality $\displaystyle=\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\beta_{0}^{1}|v_{0}(s_{1})\rangle|\bar{0}0^{\tau}\rangle\|-A_{1}$
$\displaystyle\geq\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\beta_{0}^{r-1}\cdots\beta_{0}^{1}|v_{0}(s_{r})\rangle|\bar{0}0^{\tau}\rangle\|-A_{1}-\cdots-
A_{r}$
$\displaystyle=\|\beta_{0}^{r}\beta_{0}^{r-1}\cdots\beta_{0}^{1}\left\langle
g|v_{0}(s_{r})\right\rangle\|-A_{1}-\cdots-A_{r},$ (3)

where $A_{i}\coloneqq\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\Pi_{0^{\tau}}U_{qee}(s_{i})(\sum_{k=1}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\bar{0}0^{\tau}\rangle\|$.

To amplify the success probability, we consider the first item of (3) as
follows:

$\displaystyle|\left\langle
g|v_{0}(s_{r})\right\rangle\beta_{0}^{r}\beta_{0}^{r-1}\cdots\beta_{0}^{1}|$
$\displaystyle=$
$\displaystyle|\cos(\pi/2-\theta_{r})\cos(\theta_{r}-\theta_{r-1})\cdots\cos(\theta_{2}-\theta_{1})\cos\theta_{1}|$
$\displaystyle=:$ $\displaystyle G(r).$

Let $\theta_{0}=0$. For $i=0,\cdots,r-1$, define
$\vartheta_{i}\coloneqq\theta_{i+1}-\theta_{i}$ and then

$G(r)=\cos(\pi/2-\vartheta_{r-1}-\cdots-\vartheta_{0})\cos\vartheta_{r-1}\cdots\cos\vartheta_{1}\cos\vartheta_{0}.$

The problem to solve $G(r)$ becomes an optimization problem:

$\left\\{\begin{matrix}X=\\{\vartheta_{0},\vartheta_{1},\cdots,\vartheta_{r}\\}\\\
s.t.\ \sum_{i}\vartheta_{i}=\pi/2,\ \vartheta_{i}\geq 0\quad for\
i\in\\{0,1,\cdots,r\\}\\\ \max G(X,r)\end{matrix}\right.$

For any $i\in\\{0,1,\cdots,r-1\\}$, there is

$\displaystyle\frac{\partial G(X,r)}{\partial\vartheta_{i}}=$
$\displaystyle\frac{\partial[\cos(\pi/2-\vartheta_{r-1}-\cdots-\vartheta_{0})\cos\vartheta_{r-1}\cdots\cos\vartheta_{1}\cos\vartheta_{0}]}{\partial\vartheta_{i}}$
$\displaystyle=$
$\displaystyle[\sin(\pi/2-\vartheta_{r-1}-\cdots-\vartheta_{0})\cos\vartheta_{i}-\cos(\pi/2-\vartheta_{r-1}-\cdots-\vartheta_{0})\sin\vartheta_{i}]\cdot$
$\displaystyle\cos\vartheta_{r-1}\cdots\cos\vartheta_{i+1}\cos\vartheta_{i-1}\cdots\cos\vartheta_{0}$
$\displaystyle=$
$\displaystyle\sin(\pi/2-\vartheta_{r-1}-\cdots-\vartheta_{i+1}-2\vartheta_{i}-\vartheta_{i-1}-\cdots-\vartheta_{0})\cos\vartheta_{r-1}\cdot$
$\displaystyle\cdots\cos\vartheta_{i+1}\cos\vartheta_{i-1}\cdots\cos\vartheta_{0}.$

Define $\vartheta_{r}\coloneqq\pi/2-\sum_{j=0}^{r-1}\vartheta_{j}$. If
$\vartheta_{i}<\vartheta_{r}$, $G(X,r)$ increases as $\vartheta_{i}$
increases; if $\vartheta_{i}>\vartheta_{r}$, $G(X,r)$ decreases as
$\vartheta_{i}$ increases, which means the maximum of $G(X,r)$ is achieved
when $\vartheta_{i}=\vartheta_{r}$. Since $i$ is any number in
$\\{0,1,\cdots,r-1\\}$, we have

$G(X,r)=G(\vartheta_{0},\vartheta_{1},\cdots,\vartheta_{r-1})\leq
G(\vartheta_{r},\vartheta_{r},\cdots,\vartheta_{r}).$
$\pi/2=\sum_{j=0}^{r}\vartheta_{j}=(r+1)\vartheta_{r},$

that is $\vartheta_{i}=\frac{\pi}{2(r+1)}$ for $i\in\\{0,1,\cdots,r-1\\}$.
Then we have

$\max_{X}G(X,r)=\cos^{r+1}(\frac{\pi}{2(r+1)}),$ (4)

which is achieved when

$\theta_{i}=\frac{i\pi}{2(r+1)},\quad for\quad i\in\\{0,1,\cdots,r\\}.$

Now we bound the value of $A_{i}$. Define $\alpha_{k,0}^{i}=\left\langle
v_{k}(s_{i})|\bar{\pi}\right\rangle$, $\alpha_{k,r+1}^{i}=\left\langle
v_{k}(s_{i})|g\right\rangle$, since

$\displaystyle
0=\left\langle{v_{k}(s_{i})}|{v_{0}(s_{i})}\right\rangle=\cos\theta_{i}\left\langle{v_{k}(s_{i})}|\bar{\pi}\right\rangle+\sin\theta_{i}\left\langle{v_{k}(s_{i})}|g\right\rangle=\cos\theta_{i}\alpha_{k,0}^{i}+\sin\theta_{i}\alpha_{k,r+1}^{i},$

for $i=1,\cdots,r$, $k=1,\cdots,n-1$, we have
$\alpha_{k,r+1}^{i}=-\frac{\cos\theta_{i}}{\sin\theta_{i}}\alpha_{k,0}^{i}$,
then

$\displaystyle\beta_{k}^{i}=$ $\displaystyle\left\langle
v_{k}(s_{i})|v_{0}(s_{i-1})\right\rangle$ $\displaystyle=$
$\displaystyle\cos\theta_{i-1}\left\langle
v_{k}(s_{i})|\bar{\pi}\right\rangle+\sin\theta_{i-1}\left\langle
v_{k}(s_{i})|g\right\rangle$ $\displaystyle=$
$\displaystyle\cos\theta_{i-1}\alpha_{k,0}^{i}+\sin\theta_{i-1}\alpha_{k,r+1}^{i}$
$\displaystyle=$
$\displaystyle\cos\theta_{i-1}\alpha_{k,0}^{i}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}\alpha_{k,0}^{i}$
$\displaystyle=$
$\displaystyle[\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}]\alpha_{k,0}^{i}$
$\displaystyle=$
$\displaystyle[\cos(\frac{(i-1)\pi}{2(r+1)})-\sin(\frac{(i-1)\pi}{2(r+1)})\frac{\cos(\frac{i\pi}{2(r+1)})}{\sin(\frac{i\pi}{2(r+1)})}]\alpha_{k,0}^{i},$
(5)

which means

$\lvert\beta_{k}^{i}\rvert\leq\lvert[\cos(\frac{(i-1)\pi}{2(r+1)})-\sin(\frac{(i-1)\pi}{2(r+1)})\frac{\cos(\frac{i\pi}{2(r+1)})}{\sin(\frac{i\pi}{2(r+1)})}]\rvert\cdot\lvert\alpha_{k,0}^{i}\rvert\leq\lvert\alpha_{k,0}^{i}\rvert.$
(6)

To determine the value of $A_{i}$, we introduce the relationship between
$W(s)$ and $D(s)$ as follows:

######  Lemma 2 (Spectrum of $W(s)$ and $D(s)$ [6]).

The eigenvalues and eigenvectors $|v_{k}(s)\rangle$ of $D(s)$ satisfy that

$(D(s)\otimes
I)|v_{k}(s)\rangle|\bar{0}\rangle=cos(\varphi_{k}(s))|v_{k}(s)\rangle|\bar{0}\rangle,$

for $k=0,\dotsc,n-1$, with $\varphi_{0}(s)=0$, the eigenvalues and
eigenvectors of $W(s)$ are:

$W(s)|\Psi_{0}(s)\rangle=|\Psi_{0}(s)\rangle,W(s)|\Psi^{\pm}_{k}(s)\rangle=e^{\pm
i\varphi_{k}(s)}|\Psi^{\pm}_{k}(s)\rangle,$

and the relation between them can be expressed as:

$|\Psi_{0}(s)\rangle:=|v_{0}(s)\rangle|\bar{0}\rangle,|\Psi^{\pm}_{k}(s)\rangle\coloneqq\frac{|v_{k}(s)\rangle|\bar{0}\rangle\pm
i|v_{k}(s)\rangle|\bar{0}^{\perp}\rangle}{\sqrt{2}}.$

Then
$\mathcal{B}_{k}(s)=span\\{|\Psi^{+}_{k}(s)\rangle,|\Psi^{-}_{k}(s)\rangle\\}=\mathrm{span}\\{|v_{k}(s)\rangle|\bar{0}\rangle,|v_{k}(s)\rangle|\bar{0}^{\perp}\rangle\\}$
for $k=1,\dotsc,n-1$ and
$\mathcal{B}_{0}(s)=span\\{|\Psi_{0}(s)\rangle\\}=span\\{|v_{0}(s)\rangle\\}$
are invariant subspace of $W(s)$ and mutually orthogonal. Actually, the walk
space of $W(s)$ is $\bigcup_{k=0}^{n-1}\mathcal{B}_{k}(s)$.

From Lemma 1 and Lemma 2, since $W(s_{i})$ is a real operator,
$U_{qee}(W(s_{i}),\tau)$ acts on the eigenvectors of $W(s_{i})$ as:

$|\Psi_{0}(s_{i})\rangle\mapsto|\Psi_{0}(s_{i})\rangle|0^{\tau}\rangle,\quad|\Psi^{\pm}_{k}(s_{i})\rangle\mapsto|\Psi^{\pm}_{k}(s_{i})\rangle|\xi^{\pm}_{k}(s_{i})\rangle,$

where $|\xi^{\pm}_{k}(s_{i})\rangle$ is a ${\tau}$-qubit state that satisfies
$\left\langle
0^{\tau}|\xi^{\pm}_{k}(s_{i})\right\rangle=\frac{1}{2^{\tau}}\sum_{l=0}^{2^{\tau}-1}e^{\pm
i\varphi_{k}(s_{i})l}=:\delta^{\pm}_{k}(s_{i}).$ Thus, eigenvectors of
$D(s_{i})$ after phase estimation are

$\displaystyle|v_{k}(s_{i})\rangle|\bar{0}0^{\tau}\rangle$
$\displaystyle\mapsto
U_{qee}(s_{i})|v_{k}(s_{i})\rangle|\bar{0}0^{\tau}\rangle$
$\displaystyle=\frac{1}{\sqrt{2}}\sum_{k=1}^{n-1}\bigl{(}|\Psi^{+}_{k}(s_{i})\rangle|\xi^{+}_{k}(s_{i})\rangle+|\Psi^{-}_{k}(s_{i})\rangle|\xi^{-}_{k}(s_{i})\rangle\bigr{)}.$

Now we bound $A_{i}$ as

$\displaystyle A_{i}=$ $\displaystyle\||g\rangle\langle
g|_{1}\Pi_{0^{\tau}}U_{qee}(s_{r})\cdots\Pi_{0^{\tau}}U_{qee}(s_{i})(\sum_{k=1}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\bar{0}0^{\tau}\rangle\|$
$\displaystyle\leq$
$\displaystyle\beta_{0}^{i-1}\cdots\beta_{0}^{1}\|\Pi_{0^{\tau}}U_{qee}(s_{i})(\sum_{k=1}^{n-1}\beta_{k}^{i}|v_{k}(s_{i})\rangle)|\bar{0}0^{\tau}\rangle\|$
$\displaystyle=$
$\displaystyle\beta_{0}^{i-1}\cdots\beta_{0}^{1}\|\Pi_{0^{\tau}}\frac{1}{\sqrt{2}}\sum_{k=1}^{n-1}\beta_{k}^{i}\bigl{(}|\Psi^{+}_{k}(s_{i})\rangle|\xi^{+}_{k}(s_{i})\rangle+|\Psi^{-}_{k}(s_{i})\rangle|\xi^{-}_{k}(s_{i})\rangle\bigr{)}\|$
$\displaystyle=$
$\displaystyle\beta_{0}^{i-1}\cdots\beta_{0}^{1}\|\frac{1}{\sqrt{2}}\sum_{k=1}^{n-1}\beta_{k}^{i}\bigl{(}\delta^{+}_{k}(s_{i})|\Psi^{+}_{k}(s_{i})\rangle+\delta^{-}_{k}(s_{i})|\Psi^{-}_{k}(s_{i})\rangle\bigr{)}\|$
$\displaystyle\leq$
$\displaystyle\beta_{0}^{i-1}\cdots\beta_{0}^{1}\sqrt{\sum_{k=1}^{n-1}\lvert\beta_{k}^{i}\rvert^{2}\delta_{k}^{2}(s_{i})}\leq\sqrt{\sum_{k=1}^{n-1}\lvert\beta_{k}^{i}\rvert^{2}\delta_{k}^{2}(s_{i})}.$
$|\Psi^{\pm}_{1}\rangle,\dotsc,|\Psi^{\pm}_{k}\rangle$ are mutually orthogonal

where
$\delta_{k}(s_{i}):=\lvert\delta^{+}_{k}(s_{i})\rvert=\lvert\delta^{-}_{k}(s_{i})\rvert$,
${\tau}=\lceil\log\Gamma_{1}\rceil$, and satisfies111The detailed construction
can be seen in [13].
$\delta_{k}^{2}(s_{i})\leq\frac{\pi^{2}}{2^{2{\tau}}\varphi^{2}_{k}(s_{i})}\leq\frac{\pi^{2}}{\Gamma_{1}^{2}\varphi^{2}_{k}(s_{i})}$.

Similar to (1), the interpolated hitting time in single-marked vertex graph is

$\mathrm{HT}(s_{i})=\sum_{k=1}^{n-1}\frac{\lvert\langle
v_{k}(s_{i})|\bar{\pi}\rangle\rvert^{2}}{1-\lambda_{k}(s_{i})}=\sum_{k=1}^{n-1}\frac{\lvert\alpha_{k,0}^{i}\rvert^{2}}{1-\cos\varphi_{k}(s_{i})}\geq
2\sum_{k=1}^{n-1}\frac{\lvert\alpha_{k,0}^{i}\rvert^{2}}{\varphi^{2}_{k}(s_{i})}.$
(7)

By combining (6) and (7) we have

$\sqrt{\sum_{k=1}^{n-1}\lvert\beta_{k}^{i}\rvert^{2}\delta_{k}^{2}(s_{i})}\leq\sqrt{\sum_{k=1}^{n-1}\lvert\alpha_{k,0}^{i}\rvert^{2}\delta_{k}^{2}(s_{i})}\leq\frac{\pi}{\Gamma_{1}}\sqrt{\sum_{k=1}^{n-1}\frac{\lvert\alpha_{k,0}^{i}\rvert^{2}}{\varphi^{2}_{k}(s_{i})}}\leq\frac{\pi}{\Gamma_{1}}\sqrt{\frac{\mathrm{HT}(s_{i})}{2}}.$

From theorem 17 in [13], we have $HT(s_{i})\leq HT$ in the single-marked
vertex Markov chain. Thus,
$\frac{\pi}{\Gamma_{1}}\sqrt{\frac{\mathrm{HT}(s_{i})}{2}}\leq\frac{\varepsilon}{r}$
and (3) becomes

$\sqrt{p_{succ}}\geq\cos^{r+1}(\frac{\pi}{2(r+1)})-r\cdot\frac{\varepsilon}{r}\geq\cos^{r+1}(\frac{\pi}{2(r+1)})-\varepsilon,$

that is $p_{succ}\geq(\cos^{r+1}(\frac{\pi}{2(r+1)})-\varepsilon)^{2}$.

We evaluate how the value of $\cos^{r+1}(\frac{\pi}{2(r+1)})$ varies with $r$
as follows. Let $f(r)=\cos^{r}(\frac{\pi}{2r})$ and
$\ln(f(r))=r\ln(\cos(\frac{\pi}{2r}))$, then

$\displaystyle\frac{f^{\prime}(r)}{f(r)}=$
$\displaystyle\ln(\cos(\frac{\pi}{2r}))+\frac{r[-\sin(\frac{\pi}{2r})\frac{\pi}{2}(-\frac{1}{r^{2}})]}{\cos(\frac{\pi}{2r})}$
$\displaystyle=$
$\displaystyle\ln(\cos(\frac{\pi}{2r}))+\frac{\frac{\pi}{2r}\sin(\frac{\pi}{2r})}{\cos(\frac{\pi}{2r})}.$

Since $r\geq 2$, then $0<\frac{\pi}{2r}<\frac{\pi}{2}$ and
$\cos(\frac{\pi}{2r})>0$, which means to determine whether $f^{\prime}(r)$ is
positive or negative, we only need to determine

$\cos(\frac{\pi}{2r})\ln(\cos(\frac{\pi}{2r}))+\frac{\pi}{2r}\sin(\frac{\pi}{2r})=:g(r).$

Let $y\coloneqq\frac{\pi}{2r}$ and
$h(y)\coloneqq\cos(y)\ln(\cos(y))+y\sin(y)=g(r)$, then

$h^{\prime}(y)\coloneqq-\sin(y)\ln(\cos(y))+\cos(y)\frac{-\sin(y)}{\cos(y)}+\sin(y)+y\cos(y).$

Since $r\geq 2$, $y\in(0,1]$, $h^{\prime}(y)\geq 0$ and $h(y)$ is an
increasing function, which means for any $r\geq 2$, $g(r)=h(y)\geq h(0)=0$,
that is $f^{\prime}(r)\geq 0$, $f(r)$ is an increasing function.

From the definition of $f(r)$, the success probability increases and tends to
$1$ as the number of steps $r$ increases, which means our method will never
face the soufflé problems. When $r\geq 10$ and $\varepsilon$ is small, we have
$p_{succ}\geq 4/5$, and the success probability increases as $r$ increases.

###  3.2 Algorithms based on quantum fast-forwarding

In the previous section, a new search algorithm based on generalized
interpolated walks and phase estimation improves the success probability to
nearly 1. However, it relies on $\varepsilon^{-1}$ too heavily that when the
value of $\varepsilon$ is small, the algorithm complexity also increases
rapidly. Quantum fast-forwarding as a quantum version of random walk with
acceleration can be used here to reduce the dependence on $\varepsilon$. In
this section, we combine the generalized interpolated walks with quantum fast-
forwarding, which both reduces the times of calling walk operators and the
number of ancilla qubits.

We introduce quantum fast-forwarding algorithm firstly.

######  Lemma 3 (Quantum fast-forwarding [17]).

For any reversible Markov chain and corresponding walk operator $W(P)$ on
state space $\Lambda_{V}\otimes\Lambda_{V}$ and any
$|\psi\rangle\in\Lambda_{V}$, quantum fast-forwarding algorithm
$U_{qff}(W,\tau)$ acting on $|\psi\rangle|\bar{0}0^{\tau}\rangle$ will output
a state $\varepsilon$-close to
$D^{t}|\psi\rangle|00^{\tau}\rangle+|\chi\rangle|{00}^{\perp}\rangle$, where
$|{00}^{\perp}\rangle$ satisfies $\langle 00^{\tau}|00^{\perp}\rangle=0$. The
algorithm invokes controlled-$W$ operator
$\Gamma\coloneqq\Theta(\sqrt{t\log(\varepsilon^{-1})})$ times and requires
$\tau=\lceil\log\Gamma\rceil$ ancilla qubits.

The dynamics of discriminant matrix $D$ are simulated by the unitary operator
$U_{qff}(W,\tau)$, which acts as follows:

$\left\|\Pi_{\bar{0}0}U_{qff}(W,\tau)|\psi\rangle|\bar{0}0^{\tau}\rangle-(D^{t}|\psi\rangle)|\bar{0}0^{\tau}\rangle\right\|\leq\varepsilon_{1},$
(8)

where
$\Pi_{\bar{0}0}=I\otimes(|\bar{0}\rangle\langle\bar{0}|)\otimes(|0^{\tau}\rangle\langle
0^{\tau}|)$. The detailed construction of
$U_{qff}(W,\tau)=V_{q}^{\dagger}W_{ctrl}V_{q}$ can be described as:
$V_{q}|\psi,\bar{0}\rangle|0^{\tau}\rangle=\sum_{l=0}^{2^{\tau}-1}\sqrt{\frac{p_{l}}{1-(\sum_{x={2^{\tau}}}^{t}p_{x})}}|\psi,\bar{0}\rangle|l\rangle,W_{ctrl}=\sum_{l=0}^{2^{\tau}-1}W^{l}\otimes|l\rangle\langle
l|$, where $p_{l}$ is the probability of uniform random walk with a distance
$l$ from the origin point at time $t$, the detailed description of $p_{l}$ can
be found in Equation (6) of [17].

Then the new algorithm for searching is described as follows.

######  Theorem 2 (Search marked vertex based on quantum fast-forwarding).

For an ergodic reversible Markov chain $P$ in $G(V,E)$ with single marked
vertex $g$, Algorithm 2 achieves $|g\rangle$ with success probability more
than $4/5$ from initial state $|\pi\rangle$. The complexity is
$\mathcal{S}+\Theta(\log(\varepsilon^{-1})\sqrt{\mathrm{HT}})(\mathcal{U}+\mathcal{C})$
with $\Theta(\log\log(\varepsilon^{-1})+\log\sqrt{\mathrm{HT}})$ ancilla
qubits, where $\varepsilon$ is the error.

###### Proof.

Algorithm 2 The generalized interpolated search algorithms based on quantum
fast-forwarding

Input: $\Gamma_{2}$, a number satisfies that
$\Gamma_{2}=\Theta(\log(\varepsilon^{-1})\sqrt{\mathrm{HT}})$, where
$\varepsilon$ is the error; $S=\\{s_{1},s_{2},...,s_{r}\\}$.
Output: $|\psi_{r}\rangle$, the state that has a constant overlap with the
$|g\rangle$.

1: Set $\tau=\lceil\log\Gamma_{2}\rceil$, prepare the initial state as
$|\pi\rangle|\bar{0}\rangle|0^{\tau}\rangle|0\rangle|0^{r}\rangle$ on
$\mathsf{R}_{1}\mathsf{R}_{2}\mathsf{R}_{3}\mathsf{R}_{4}\mathsf{R}_{5}$,
where the five registers are the same as registers in [15].

2: Measure $\mathsf{R}_{1}$ and check whether it is $|g\rangle$.

3: if the current vertex is marked then

4: return the marked vertex, stop.

5: else

6: for i = 1,2,…,r do

7: Apply $U_{qfs}(W(s_{i}),\tau)$ with $s_{i}$ to the current state.

8: end for

9: end if

10: Measure and output the first register.

We analyze the success probability firstly. For initial state
$|\bar{\pi}\rangle$ and target state $|g\rangle$, let $p_{succ}$ denote the
success probability, then we have

$\displaystyle\sqrt{p_{succ}}$ $\displaystyle=\||g\rangle\langle
g|_{1}U_{qfs}(s_{r})\cdots
U_{qfs}(s_{1})(|\bar{\pi}\rangle|\bar{0}0^{\tau}00^{r}\rangle)\|$
$\displaystyle=\||g\rangle\langle g|_{1}U_{qfs}(s_{r})\cdots
U_{qfs}(s_{1})(\sum_{k=0}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle)|\bar{0}0^{\tau}00^{r}\rangle\|$
$\displaystyle\geq\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qfs}(s_{r})\cdots
U_{qfs}(s_{1})\beta_{0}^{1}|v_{0}(s_{1})\rangle|\bar{0}0^{\tau}0\rangle|0^{r}\rangle\|$
$\displaystyle-\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qfs}(s_{r})\cdots
U_{qfs}(s_{1})(\sum_{k=1}^{n-1}\beta_{k}^{1}|v_{k}(s_{1})\rangle)|\omega_{0}\rangle\|$
where $\Pi_{g}=|g\rangle\langle g|_{1}$,
$|\omega_{i}\rangle=|\bar{0}0^{\tau}0\rangle|1^{i}0^{r-i}\rangle$
$\displaystyle\geq\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qfs}(s_{r})\cdots\beta_{0}^{1}|v_{0}(s_{1})\rangle|\omega_{1}\rangle\|-B_{1}$
$\displaystyle\geq\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qfs}(s_{r})\beta_{0}^{r-1}\cdots\beta_{0}^{1}|v_{0}(s_{r})\rangle|\omega_{r-1}\rangle\|-B_{1}-\cdots-
B_{r}$ $\displaystyle=|\left\langle
g|v_{0}(s_{r})\right\rangle\beta_{0}^{r}\beta_{0}^{r-1}\cdots\beta_{0}^{1}|-B_{1}-\cdots-
B_{r},$

where $B_{i}=\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qff}(s_{r})\cdots
U_{qff}(s_{i})(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$.
Since the $i$th qubit in the fifth register changes from $|0\rangle$ to
$|1\rangle$ only if the state before $ccX_{234,\gamma_{i}}$ is expressed as
$|\cdots\rangle|\bar{0}0^{\tau}0\rangle|1^{i-1}0^{r-i+1}\rangle$, we have

$\displaystyle B_{i}=$ $\displaystyle\||g\rangle\langle g|_{1}|1\rangle\langle
1|_{\gamma_{1}\cdots\gamma_{r}}U_{qfs}(s_{r})\cdots
U_{qfs}(s_{i})(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle\leq$ $\displaystyle\|(|1\rangle\langle
1|_{\gamma_{i}})U_{qfs}(s_{r})\cdots
U_{qfs}(s_{i})(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$ $\displaystyle\|U_{qfs}(s_{r})\cdots(|1\rangle\langle
1|_{\gamma_{i}})U_{qfs}(s_{i})(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$ $\displaystyle\||1\rangle\langle
1|_{\gamma_{i}}U_{qfs}(s_{i})(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$ $\displaystyle\||1\rangle\langle
1|_{\gamma_{i}}ccX_{2,4}X_{4}(U_{qff}^{\dagger}(W(s_{i}),\tau)\otimes
I)ccX_{234,\gamma_{i}}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$
$\displaystyle\|ccX_{2,4}X_{4}(U_{qff}^{\dagger}(W(s_{i}),\tau)\otimes
I)|1\rangle\langle
1|_{\gamma_{i}}ccX_{234,\gamma_{i}}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$ $\displaystyle\||1\rangle\langle
1|_{\gamma_{i}}ccX_{234,\gamma_{i}}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle=$
$\displaystyle\||\bar{0}\rangle\langle\bar{0}|_{2}|0^{\tau}\rangle\langle
0^{\tau}|_{3}|0^{\tau}\rangle\langle 0|_{4}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=0}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|$
$\displaystyle\leq$
$\displaystyle\|\Pi_{\bar{0}0}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=1}^{n-1}\beta_{k}^{i}\beta_{0}^{i-1}\cdots\beta_{0}^{1}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|.$

From (5) we have the above equation satisfies

$B_{i}=|\beta_{0}^{i-1}\cdots\beta_{0}^{1}|\cdot|\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}|\cdot\|\Pi_{\bar{0}0}(U_{qff}(W(s_{i}),\tau)\otimes
I)(\sum_{k=1}^{n-1}\alpha_{k,0}^{i}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|,$

then from triangle equality, we have

$\displaystyle
B_{i}\leq|\beta_{0}^{i-1}\cdots\beta_{0}^{1}|\cdot|\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}|\cdot(\|\sum_{k=1}^{n-1}(D^{t}\alpha_{k,0}^{i}|v_{k}(s)\rangle)|\omega_{i-1}\rangle\|+$
$\displaystyle\|\Pi_{\bar{0}0}(U_{qff}(W(s_{i}),\tau)\otimes
I)|\omega_{i-1}\rangle\sum_{k=1}^{n-1}\alpha_{k,0}^{i}|v_{k}(s_{i})\rangle|\omega_{i-1}\rangle-\sum_{k=1}^{n-1}(D^{t}\alpha_{k,0}^{i}|v_{k}(s_{i})\rangle)|\omega_{i-1}\rangle\|).$

From Lemma 2 we have

$\|D^{t}|v_{k}(s)\rangle\|=\cos^{t}\varphi_{k}\leq\cos^{t}\varphi_{1}=(1-\Delta(s))^{t}=e^{-t\log(\frac{1}{1-\Delta(s)})}.$

Let $t=\log(\frac{2r}{\varepsilon})\frac{2}{\Delta(s)}$, where $\Delta(s)$
denotes the eigenvalue gap of $P(s)$, then

$\|D^{t}|v_{k}(s)\rangle\|=\left[e^{-\log(\frac{2r}{\varepsilon})}\right]^{\frac{2}{\Delta(s)}\log(\frac{1}{1-\Delta(s)})}=(\frac{\varepsilon}{2r})^{\frac{2}{\Delta(s)}\log(\frac{1}{1-\Delta(s)})}\leq\frac{\varepsilon}{2r}.$

Combine with (8) and $\varepsilon_{1}=\frac{\varepsilon}{2r}$, the above
equation can be expressed as

$\displaystyle|\beta_{0}^{i-1}\cdots\beta_{0}^{1}|\cdot|\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}|\cdot(2|\sum_{k=1}^{n-1}\cos^{t}(\varphi_{k})\alpha_{k,0}^{i}|+\frac{\varepsilon}{2r})$
$\displaystyle\leq$
$\displaystyle|\beta_{0}^{i-1}\cdots\beta_{0}^{1}|\cdot|\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}|\cdot(\frac{\varepsilon}{2r}|\sum_{k=1}^{n-1}\alpha_{k,0}^{i}|+\frac{\varepsilon}{2r})$
$\displaystyle\leq$
$\displaystyle|\beta_{0}^{i-1}\cdots\beta_{0}^{1}|\cdot|\cos\theta_{i-1}-\sin\theta_{i-1}\frac{\cos\theta_{i}}{\sin\theta_{i}}|\cdot\frac{\varepsilon}{r}\leq\varepsilon.$

From (4) we have

$\displaystyle\sqrt{p_{succ}}$ $\displaystyle=|\left\langle
g|v_{0}(s_{r})\right\rangle\beta_{0}^{r}\beta_{0}^{r-1}\cdots\beta_{0}^{1}|-B_{1}-B_{2}-\cdots-
B_{r}$ $\displaystyle\geq\cos^{k+1}(\frac{\pi}{2(k+1)})-\varepsilon.$

From the definition of $f(r)$ in proof of Theorem 1, success probability
increases with the number of steps $r$ increases, so the algorithm avoids the
soufflé problems that amplitude amplification will bring. Compared with the
result in Theorem 1, we achieve a faster search algorithm with less ancilla
qubits. ∎

In general, for a reversible Markov chain, if we reverse a search algorithm,
we can obtain a qsamping algorithm. Reversing the above algorithm results, we
get a qsampling algorithm as shown below.

######  Theorem 3 (Qsampling based on generalized interpolated walks).

For an ergodic reversible Markov chain P in $G(V,E)$, there exists an
algorithm that outputs $|\pi\rangle$ with success probability more than
$\frac{4}{5}$ from initial state $|g\rangle$ for any $g\in V$. The complexity
is
$\Theta(\mathcal{S}(g)+\log(\varepsilon^{-1})\sqrt{\mathrm{HT}}(\mathcal{U}+\mathcal{C}))$,
with $\Theta(\log\log(\varepsilon^{-1})+\log\sqrt{\mathrm{HT}})$ ancilla
qubits, where $\varepsilon$ is the error.

###  3.3 Application

In this section, we give an application of generalized interpolated walks.
Adiabatic quantum computing is an important quantum computing model that is
equivalent to standard quantum circuit model [21]. We apply generalized
interpolated walks to prepare quantum stationary state of Markov chains for
adiabatic quantum computing. In adiabatic quantum computing, the state
preparation is the premise of algorithm and is always expressed as a ground
state of the target Hamiltonian which can be obtained by a series of slowly
changing Hamiltonian.

However, the slowly evolving Hamiltonian sequence is not always easy to
prepare. For those Hamiltonian that corresponds the reversible Markov chains,
the corresponding ground state can be equivalent to the stationary state [21],
and the construction of slowly evolving Hamiltonian sequences are reduced to
construct a series of slowly evolving Markov chains with their stationary
states [8], where the algorithm to prepare Boltzmann-Gibbs distribution has
been constructed. However, the construction of general slowly evolving Markov
chain sequence is not given in [8], although it is necessary when we want to
prepare stationary state of any reversible Markov chain.

By applying generalized interpolated walks, we give the detailed construction
of slowly evolving Markov chains to approach any reversible Markov chain P as
follows.

Let $Q=(q_{i,j})_{1\leq i,j\leq r}$ satisfy

$q_{i,j}=\left\\{\begin{matrix}1\quad if\quad j=i+1,1\leq i\leq r-1\\\
0\quad\quad\quad\quad\quad\quad\quad\ \quad otherwise\end{matrix}\right.$

We define a series of Markov chains as:

$P(s_{0}),P(s_{1}),P(s_{2}),\cdots,P(s_{i}),\cdots,P(s_{r}).$

The walk operator can be defined as

$P(s_{i})\coloneqq(1-s_{i})P+s_{i}P^{\prime},\ W(s_{i})\coloneqq
V(s_{i})^{\dagger}\cdot S\cdot V(s_{i})\cdot R_{\bar{0}},$

and the corresponding details can be seen in Section 2.1. Let
$\pi(s_{i})=\frac{(1-s_{i})\pi+s_{i}\pi^{\prime}}{1-s_{i}+s_{i}\pi_{0}}$. From
proposition 11 in [13], for every $s\in[0,1)$, $P(s_{i})$ is a reversible
Markov chain and $\pi(s_{i})$ is the only stationary distribution of
$P(s_{i})$. Define the corresponding quantum state as
$|\pi(s_{i})\rangle=\sum_{x}\sqrt{\frac{(1-s_{i})\pi_{x}+s_{i}\pi^{\prime}_{x}}{1-s_{i}+s_{i}\pi_{0}}}|x\rangle$,
we have

$\displaystyle W(s_{i})|\pi(s_{i})\rangle|\bar{0}\rangle=$ $\displaystyle
V(s_{i})^{\dagger}\cdot S\cdot V(s_{i})\cdot
R_{\bar{0}}(\sum_{x,y}\sqrt{\pi(s_{i})_{x}}|x\rangle|\bar{0}\rangle)$
$\displaystyle=$ $\displaystyle V(s_{i})^{\dagger}\cdot
S(\sum_{y}\sqrt{\pi(s_{i})_{y}}(\sum_{x}\sqrt{P(s_{i})_{y,x}}|x\rangle)|y\rangle)$
$\displaystyle=$ $\displaystyle
V(s_{i})^{\dagger}(\sum_{y}\sqrt{\pi(s_{i})_{y}}|y\rangle(\sum_{x}\sqrt{P(s_{i})_{y,x}}|x\rangle))$
$\displaystyle=$ $\displaystyle
V(s_{i})^{\dagger}V(\sum_{y}\sqrt{\pi(s_{i})_{y}}|y\rangle|\bar{0}\rangle)=|\pi(s_{i})\rangle|\bar{0}\rangle,$

that is for any $s\in[0,1)$, $|\pi(s_{i})\rangle|\bar{0}\rangle$ is
1-eigenvector of $W(s_{i})$.

According to the construction of $|\pi(s_{i})\rangle$ we know:

$|\pi(s_{i})\rangle=\sqrt{\frac{(1-s_{i})(1-\pi_{0})}{1-s(1-\pi_{0})}}|\bar{\pi}\rangle+\sqrt{\frac{\pi_{0}}{1-s(1-\pi_{0})}}|0\rangle.$
(9)

For any $i\in\\{0,1,\cdots,r\\}$, let

$s_{i}=\frac{1-\pi_{0}/\sin^{2}\theta_{i}}{1-\pi_{0}}=\frac{1-\pi_{0}/\sin^{2}(\frac{i\pi}{2(r+1)})}{1-\pi_{0}},i\in\\{0,1,\cdots,r\\},$

and we have
$|v_{0}(s_{i})\rangle=\cos\theta_{i}|\bar{\pi}\rangle+\sin\theta_{i}|0\rangle=\cos(\frac{i\pi}{2(r+1)})|\bar{\pi}\rangle+\sin(\frac{i\pi}{2(r+1)})|0\rangle$.

Now we prove that all above Markov chains satisfies varying slowing condition,
which means that for any two adjacent Markov chains, there exists $q$ such
that the inner product of their quantum stationary state is greater than $q$.

Select the initial quantum stationary state to be
$|0\rangle\in\mathrm{span}\\{|0\rangle,|1\rangle,\cdots,|n-1\rangle\\}$, which
is easy to prepare. Since we have $\left\langle\bar{\pi}|0\right\rangle=0$,
which means

$\displaystyle\left\langle\pi_{i}|\pi_{i+1}\right\rangle=$
$\displaystyle(\cos\theta_{i}\langle\bar{\pi}|+\sin\theta_{i}\langle
0|)(\cos\theta_{i+1}|\bar{\pi}\rangle+\sin\theta_{i+1}|0\rangle)$
$\displaystyle=$
$\displaystyle\cos\theta_{i}\cos\theta_{i+1}+\sin\theta_{i}\sin\theta_{i+1}=\cos(\frac{\pi}{2(r+1)}).$

If $r\geq\frac{\pi}{2\arccos q}-1$, then $\cos(\frac{\pi}{2(r+1)})\geq q$, and
the slowing evolving condition $\left\langle\pi_{i}|\pi_{i+1}\right\rangle\geq
q$ is satisfied for $i\in\\{0,1,\cdots,r\\}$, where the quantum stationary
state of the first Markov chain is easy to prepare and the quantum stationary
state of the last Markov chain approximates target state.

##  4 Discussion

In this work, by defining and applying generalized interpolated walks instead
of amplitude amplification, we both improve the success probability of search
algorithm to nearly 1, and avoid the soufflé problems that amplitude
amplification will bring. By introducing quantum fast-forwarding our new
algorithms not only reduce the dependency on error but also reduce the number
of ancilla qubits required. In this process, we find the relationship between
the phase estimation and quantum fast-forwarding, as well as the relationship
between the generalized interpolated walks and amplitude amplification. We
think there is something that deserves to be explored in the future.

Besides, we use generalized interpolated walks to improve the success
probability of qsampling algorithm as well. Finally, by applying generalized
interpolated walks to adiabatic quantum computing, we construct a series of
slowing evolving Markov chains, which satisfy that the first stationary state
is easy to prepare and the final stationary state is the target state. The
process is fundamental in adiabatic stationary state preparation and we give
the detailed construction.

## Acknowledgements

We thank the support of National Natural Science Foundation of China (Grant
No.61872352), and Program for Creative Research Group of National Natural
Science Foundation of China (Grant No. 61621003).

## References

  * [1] Ambainis A.. Quantum walk algorithm for element distinctness. In: 45th Annual IEEE Symposium on Foundations of Computer Science (SFCS ’04), Italy, 2004. 22-31.
  * [2] Magniez F., Santha M., Szegedy M.. Quantum algorithms for the triangle problem. In: Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’05), Canada, 2005. 1109–1117.
  * [3] Buhrman H., Spalek R. Quantum verification of matrix products. In: Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’06), US, 2006. 880–889.
  * [4] Sheng Y., Zhang Z Z.. Low-Mean Hitting Time for Random Walks on Heterogeneous Networks. IEEE Trans., 2019, 65: 6898-6910.
  * [5] Page L., Brin S., Motwan R., et al.. The PageRank Citation Ranking : Bringing Order to the Web. Stanford InfoLab, 1999, 66.
  * [6] Szegedy M.. Quantum speed-up of Markov chain based algorithms. In: 45th Annual IEEE Symposium on Foundations of Computer Science (SFCS ’04), Italy, 2004. 32-41.
  * [7] Szegedy M.. Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule. arXiv, 2004, quant-ph/0401053.
  * [8] Wocjan P., Abeyesinghe A.. Speedup via quantum sampling. Phys. Rev. A, 2008, 78: 042336.
  * [9] Yung M., Aspuru‐Guzik A.. A quantum–quantum Metropolis algorithm. PProc. Natl. Acad. Sci. U. S. A., 2012, 109: 754 - 759.
  * [10] Magniez F., Nayak A., Roland J., et al.. Search via quantum walk. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingJune 2007 (STOC ’07), USA, 2007. 575-584.
  * [11] Tulsi A.. Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A, 2008, 78: 012310.
  * [12] Magniez F., Nayak A., Richter P. C., et al.. On the Hitting Times of Quantum Versus Random Walks. Algorithmica, 2012, 63: 91–116.
  * [13] Krovi H., Magniez F., Ozols M., et al.. Quantum walks can find a marked element on any graph. Algorithmica, 2015, 74: 851-907.
  * [14] Ambainis A., Gilyén A, Jeffery S., et al.. Quadratic Speedup for Finding Marked Vertices by Quantum Walks. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingJune 2020 (STOC ’20), USA, 2020. 412–424.
  * [15] Li X., Shang Y.. Faster quantum mixing of Markov chains in non-regular graph with fewer qubits. arXiv, 2022, quant-ph/2205.06099.
  * [16] Brassard G.. Searching a quantum phone book. Science, 1997, 275: 627–628.
  * [17] Apers S., Sarlette A.. Quantum fast-forwarding: Markov chains and graph property testing. Quantum Inf. Comput., 2018, 19: 181-213.
  * [18] Krovi H., Ozols M., Roland J.. Adiabatic condition and the quantum hitting time of markov chains. Phys. Rev. A, 2010, 82: 022333.
  * [19] Cleve R., Ekert A., Macchiavello C., ea al. Quantum algorithms revisited. Proc. R. Soc. Lond. A., 1998, 454: 339–354.
  * [20] Dohotaru C., Høyer P.. Controlled quantum amplification. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Poland, 2017. 18: 1-13.
  * [21] Aharonov D., Ta-Shma A.. Adiabatic quantum state generation and statistical zero knowledge. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingJune 2003 (STOC ’03) ,USA, 2003. 20–29.