# Eigenpath traversal by Poisson-distributed phase randomisation

Joseph Cunningham111Centre for Quantum Information and Communication (QuIC),
École polytechnique de Bruxelles, Université libre de Bruxelles Jérémie
Roland11footnotemark: 1

###### Abstract

We present a framework for quantum computation, similar to Adiabatic Quantum
Computation (AQC), that is based on the quantum Zeno effect. By performing
randomised dephasing operations at intervals determined by a Poisson process,
we are able to track the eigenspace associated to a particular eigenvalue.

We derive a simple differential equation for the fidelity, leading to general
theorems bounding the time complexity of a whole class of algorithms. We also
use eigenstate filtering to optimise the scaling of the complexity in the
error tolerance $\epsilon$.

In many cases the bounds given by our general theorems are optimal, giving a
time complexity of $O(1/\Delta_{m})$ with $\Delta_{m}$ the minimum of the gap.
This allows us to prove optimal results using very general features of
problems, minimising the problem-specific insight necessary.

As two applications of our framework, we obtain optimal scaling for the Grover
problem (i.e. $O(\sqrt{N})$ where $N$ is the database size) and the Quantum
Linear System Problem (i.e. $O(\kappa\log(1/\epsilon))$ where $\kappa$ is the
condition number and $\epsilon$ the error tolerance) by direct applications of
our theorems.

##  1 Introduction

It has long been appreciated that the ability to prepare a ground state of a
given Hamiltonian is useful for a large number computational tasks. Many NP-
hard problems, including various types of partitioning, covering, and
satisfiability problems, can be solved by finding the ground state of an Ising
system [1]. There are also many applications in the fields of quantum
chemistry, where finding the ground state of molecules is a common task, and
physics, where knowledge of the ground state helps to understand low-
temperature phenomena such as superconductivity and superfluidity.

For computational problems we have the following strategy: (1) find a physical
system such that the ground state encodes useful information for solving the
problem, (2) prepare the ground state using some physical process and (3) use
the information contained in the ground state to solve the problem. This paper
is about performing the second step of this strategy.

The most famous way to perform the second step is known as Adiabatic Quantum
Computation (AQC) [2]. Suppose $H_{P}$ is the Hamiltonian whose ground state
is of interest. This procedure requires a second Hamiltonian, $H_{0}$, with an
easily preparable ground state. Now consider the following interpolated
Hamiltonian: $H(s)=(1-s)H_{0}+sH_{P}$ and pick a large time $T$. We start with
the system in the ground state of $H_{0}$ and evolve according to the time-
dependent Hamiltonian $H(t/T)$, for time $t\in[0,T]$. The adiabatic theorem
says that if $T$ is large enough, then the resulting state will be close to
the ground state of $H(1)=H_{P}$. See [3] for results detailing how large $T$
has to be. Clearly we want to take $T$ as small as possible, since a larger
$T$ means our computation takes longer.

While AQC is polynomially equivalent to the quantum circuit model [4], it
suffers from a few drawbacks. The most significant one being that it requires
the system to evolve under a very specific time-dependent Hamiltonian. It is
typically very hard to physically implement a system that evolves under
exactly this Hamiltonian. Often the complicated time-dependent dynamics are
approximated by a sequence of simpler evolutions, which introduces
discretisation error. In particular this is necessary when implementing AQC on
a conventional quantum computer. Bounding the discretisation error
analytically is typically hard to do. In contrast, our method only requires
the evolution under a finite number of time-independent Hamiltonians for
finite time and thus has no discretisation cost.

There exist alternatives to AQC that are also based on an interpolation $H(s)$
between a Hamiltonian whose ground state is easy to prepare and one whose
ground state is difficult to prepare. These approaches use alternate ways to
transform the ground state of $H(0)$ into that of $H(1)$, or, more generally
some eigenstate of $H(0)$ into the corresponding eigenstate of $H(1)$. They
often make use of a variant of the quantum Zeno effect. For instance [5] uses
measurement and [6] simulates the quantum Zeno effect by applying Hamiltonian
evolutions for random amounts of time in a procedure known as the
Randomisation Method (RM).

Our framework builds on the RM of [6] in the following way: instead of
performing a fixed sequence of phase randomising steps, we stochastically
choose when to perform phase randomisation, based on a Poisson process with
rate $\lambda(s)$, see algorithm 1. This has a number of advantages. Firstly
it yields a simple differential equation for the state evolution, which fits
in the general framework of non-unitary adiabatic theorems of [7], and greatly
simplifies the analysis. It allows us to obtain general theorems, see in
particular theorems 4 and 5, that in many cases yield optimal results with
minimal extra work or problem-specific insight. Also, we only need very
minimal technical assumptions on $H(s)$: it only needs to be twice
continuously differentiable and we need to know some estimate of the gap
between the eigenvalue of interest and the rest of the spectrum. We do not
assume precise knowledge of the spectrum or gap. We allow the eigenspace of
interest to be degenerate.

Our theorem 4 deals with the case where the rate of the Poisson process
$\lambda$ is taken to be constant. The result we obtain is better than the
corresponding result for AQC with a constant-speed linear interpolation. In
theorem 5 we describe a variable $\lambda(s)$ that can significantly improve
the time complexity, up to $O(1/\Delta_{m})$ in the minimum gap $\Delta_{m}$.
Finally theorem 6 improves the dependence of the time complexity on the error
tolerance. Typically algorithms based on AQC and the RM have a complexity that
scales as $O(1/\epsilon)$ in the error tolerance $\epsilon$. Eigenstate
filtering, introduced in [8], can be used to reduce this to
$O(\log(1/\epsilon))$. This has been used before to RM-inspired algorithms
that use the circuit model, see [8] and [9], but we provide a version native
to our cost model.

From theorem 5, we see that the following property is very useful to obtain
fast algorithms:
$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=O(\Delta_{m}^{1-p})$,
where $\Delta$ is the gap, $\Delta_{m}=\inf_{s\in[0,1]}\Delta$ and $p>1$. This
property seems to be quite generic, in particular it holds for both the Grover
search problem and the Quantum Linear System Problem (QLSP).

In the Grover search problem, [10], the goal is to prepare a specific state in
an $N$-dimensional space with the help of an oracle. It is well-known that
this can be done in $O(\sqrt{N})$ queries to the oracle. When AQC was first
used to tackle this problem, a complexity of $O(N)$ was obtained [2]. The
trick to achieving a complexity of $O(\sqrt{N})$ was to use an adapted
schedule [11], [12]. In our framework, the algorithm using constant $\lambda$
already achieves a scaling of $O\big{(}\sqrt{N}\log(N)\big{)}$ by theorem 4,
which is significantly better than the corresponding case for AQC. Using a
variable $\lambda(s)$, we recover the scaling $O(\sqrt{N})$ by theorem 5. It
is interesting to note that, by the generality of our theorems, we actually
obtain a whole family of schedules, parametrised by some value $0<q<1$, that
solve the problem optimally. This is analogous to the range of adiabatic
schedules considered in [13] and [14]. The original schedule of [11] actually
corresponds to a choice of $q=1$. It seems like the RM can be considered as
the $q=1$ case of a family of methods, at least in the case of linear
interpolation. This falls outside the range of our theorem, but it turns out
that $q=1$ is in fact good enough to give optimality for the Grover problem,
which explains why the RM was already known to be able to perform Grover
search with optimal complexity $O(\sqrt{N})$, [6].

In general, for other problems, $q=1$ does not give optimal scaling. The
Quantum Linear System Problems (QSLP) is an example of a problem where $q=1$
does not work, neither in our framework, nor in AQC [13]. In QLSP, [15], the
goal is to prepare a quantum state $|x\rangle$ that is proportional to the
solution of a system of linear equations $Ax=b$. In [16] the randomisation
method was used to construct an algorithm with complexity
$O\big{(}\kappa\log(\kappa)/\epsilon\big{)}$, where $\kappa$ is the condition
number and $\epsilon$ the error tolerance. This is improved to
$O\big{(}\kappa\log(\kappa/\epsilon)\big{)}$ in [9]. In [14] an algorithm
based on a discrete adiabatic theorem was proposed which scales as
$O\big{(}\kappa\log(1/\epsilon)\big{)}$. This is known to be optimal [15]. We
are able to match this in our framework.

There has actually been some discussion recently on the merits of these two
approaches to QLSP, i.e. the approach based on the RM of [16] and the approach
based on the discrete adiabatic theorem [14]. The approach based on the
discrete adiabatic theorem has the better asymptotic scaling, but it turns out
that the proven complexity for reasonable values of $\kappa$ is very large.
The paper [9] presents an algorithm that is based on the RM and has a better
proven complexity for reasonable values of $\kappa$, but is asymptotically
suboptimal. Finally [17] uses numerical methods to determine the actual
performance of the algorithm based on the discrete adiabatic theorem. They
claim that it works much better than the proven bound and in fact better than
the algorithm based on the RM. We can contribute to this discussion by noting
that our framework gives an algorithm that is based on the RM and has optimal
asymptotic scaling. In addition, since the RM seems to correspond to $q=1$,
which we know to be suboptimal, it is likely that the algorithm of [9] can be
made asymptotically optimal by changing the scheduling.

###  1.1 General setup

We assume we have a physical system and a set of (time-independent)
Hamiltonians, i.e. self-adjoint operators, such that we can evolve the system
under $e^{-itH}$ at a cost of $t$ for any Hamiltonian $H$ in this set.222We
set $\hbar=1$. We call the Hamiltonians in this set admissible. Which
Hamiltonians are admissible will depend on the device or setup, but typically
they will be bounded in norm.

This is not the cost model used by references [14] and [9], which use a query
complexity rather than a time complexity. We discuss a translation of our
results to this model using optimal Hamiltonian simulation in appendix B. The
asymptotic complexities are mostly unaffected, but there are different
constants involved.

For a given instance of a problem, we assume that we have a continuous, twice
differentiable path of admissible Hamiltonians $H(s)$, where $s\in[0,1]$. We
also assume that we can prepare the ground state of $H(0)$.

We are interested in the asymptotic scaling of the time complexity, as
measured by the total length of time we apply unitaries of the form
$e^{-itH}$. We produce theorems that give bounds on the complexity in terms of
the spectral gap and the derivatives $\left\lVert H^{\prime}\right\rVert$ and
$\left\lVert H^{\prime\prime}\right\rVert$.

Our main tool will be the randomised application of unitaries of the form
$e^{-itH}$. Since we are using classical randomness, it will be useful to use
the density matrix formalism. Using this formalism, we can derive differential
equations for these new procedures that share essential features with the
Liouville–von Neumann equation in the adiabatic limit. This allows us to use
many of the same mathematical tricks to study these procedures and we can
derive “generalised” adiabatic theorems in the sense of [7].

####  1.1.1 Cost and error model

It is clear what the cost of one run of the algorithm is: it is just the total
time spent evolving the system under some Hamiltonian. In order to state the
time complexity we have the additional problem that the running time of the
algorithm is not deterministic. That is, even for a fixed input, multiple runs
of the algorithm will take different amounts of time. Our time complexity uses
the expected run time of each input. Thus we say our algorithm has time
complexity $T$ if, for all relevant inputs $I$, the expected time taken by the
algorithm with input $I$ is less than $T$. In other words, we may consider
this a worst-case expected-time complexity.

In order to guarantee that the algorithm does not take too long, we could
abort if the chosen amount of time was too long. This would yield an
additional error, which can be bounded by Markov’s inequality.

Our algorithms are also not guaranteed to give the correct answer, rather we
aim to produce the target state with at least a certain target fidelity.

####  1.1.2 Technical assumptions on the spectrum

We assume the existence of the following objects: a number $\Delta_{m}>0$ and
functions $\omega_{0}:[0,1]\to\mathbb{R}$ and $\Delta:[0,1]\to[0,1]$ such that

  * •

$\omega_{0}$ continuous;

  * •

$\omega_{0}(s)$ is an eigenvalue of $H(s)$ for all $s\in[0,1]$;

  * •

$\Delta(s)\geq\Delta_{m}$ for all $s\in[0,1]$;

  * •

the intersection of $[\omega_{0}(s)-\Delta(s),\omega_{0}(s)+\Delta(s)]$ with
the spectrum of $H(s)$ is exactly $\\{\omega_{0}(s)\\}$.

Let $P(s)$ be the projector on the eigenspace associated to the eigenvalue
$\omega(s)$. We also set $Q(s)=\operatorname{id}-P(s)$.

In order to perform our algorithm, we assume knowledge of $\Delta$, which
bounds the gap. We do not assume more detailed knowledge of the gap,
$\omega_{0}$, or any other part of the spectrum.

##  2 Poisson-distributed phase randomisation

Our algorithms are built using a finite number of steps, where at each step a
Zeno-like dephasing operation is performed. This dephasing operation is given
by the following proposition:

######  Proposition 1 (Phase randomisation [6]).

Let $H$ be a Hamiltonian and $\omega_{0},\Delta,P$ and $Q$ as above. Assume we
can simulate $e^{-itH}$ for any positive or negative time $t$ at a cost of
$|t|$. Then we can construct a stochastic variable $\tau$ such that for all
states $\rho$,

$\langle e^{-i\tau H}\rho e^{i\tau H}\rangle=P\rho P+Q\langle e^{-i\tau H}\rho
e^{i\tau H}\rangle Q,$ (1)

with cost $\langle|\tau|\rangle=t_{0}/\Delta$, where $t_{0}=2.32132$.

The angled brackets mean taking the average over $\tau$. The result is
originally from [6]. The value for $t_{0}$ was obtained in theorem 2 of [9].

The algorithm is now simple to state:

1Pick a Poisson process $N:[0,1]\times(\Omega,\mathcal{A},P)\to\mathbb{N}$
with rate $\lambda(s)$;

2 At each jump point $s$ of the Poisson process, pick an instance $t$ of the
random variable $T$ as defined in proposition 1 and evolve the system under
the Hamiltonian evolution $e^{-itH(s)}$;

Algorithm 1 Poisson-distributed phase randomisation

The density matrix describing the system is a random variable that satisfies
the stochastic differential equation
$\operatorname{d\\!}{\rho}=\big{(}e^{-i\tau(s)H(s)}\rho
e^{i\tau(s)H(s)}-\rho\big{)}\operatorname{d\\!}{N}.$ Averaging over
realisations, we get

$\operatorname{d\\!}{\langle\rho\rangle}=\big{(}P\langle\rho\rangle P+Q\langle
e^{-i\tau H}\rho e^{i\tau H}\rangle
Q-\langle\rho\rangle\big{)}\lambda\operatorname{d\\!}{s}.$ (2)

Note that this should properly be thought of as a “marginalised” density
matrix, rather than an “average” density matrix. This is entirely analoguous
to the situation for classical probability distributions, where integrating
out a variable gives the marginal distribution. In this case we are
marginalising over the choice of Poisson process $N$. In the rest of the
paper, we will use $\rho$ to refer to the marginalised distribution
$\langle\rho\rangle$. This corresponds to the density matrix you would observe
if you were not told which Poisson process $N$ was chosen.

The total time taken by one run of the algorithm is a random variable $T$
satisfying

$\operatorname{d\\!}{T}=\tau\operatorname{d\\!}{N}.$ (3)

In order to find the time complexity, we take the average. This gives
$\operatorname{d\\!}{T}=\Delta^{-1}\lambda\operatorname{d\\!}{s}$, so
$T=\int_{0}^{1}\frac{\lambda}{\Delta}\operatorname{d\\!}{s}$.

###  2.1 Analysis

######  Lemma 2.

Under the assumptions in 1.1.2, the algorithm 1 with rate $\lambda(s)$
produces a state with an infidelity that is bounded by

$\epsilon\leq\left\lVert\lambda(0)^{-1}P^{\prime}(0)\right\rVert+\left\lVert\lambda(1)^{-1}P^{\prime}(1)\right\rVert+\int_{0}^{1}\bigg{(}\left\lVert\frac{P^{\prime\prime}}{\lambda}\right\rVert+\Big{|}\Big{(}\frac{1}{\lambda}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\bigg{)}\operatorname{d\\!}{s}.$ (4)

###### Proof.

The infidelity is given by
$\epsilon=1-\operatorname{Tr}\big{(}P(1)\rho(1)\big{)}=\operatorname{Tr}\big{(}P(0)\rho(0)\big{)}-\operatorname{Tr}\big{(}P(1)\rho(1)\big{)}=\Big{|}\operatorname{Tr}(P\rho)\big{|}_{0}^{1}\Big{|}$,
so it makes sense to track how the fidelity
$\operatorname{Tr}\big{(}P(s)\rho(s)\big{)}$ changes in time.

We construct a differential equation for $\operatorname{Tr}(P\rho)$ by taking
the derivative with respect to $s$,
$\operatorname{Tr}(P\rho)^{\prime}=\operatorname{Tr}(P^{\prime}\rho)+\operatorname{Tr}(P\rho^{\prime})$.
This can be simplified using the fact that $PP^{\prime}P=0$ and
$QP^{\prime}Q=0$.333We have
$P^{\prime}=(PP)^{\prime}=P^{\prime}P+PP^{\prime}$, so
$PP^{\prime}P=2PP^{\prime}P$ and $QP^{\prime}Q=0$. Indeed, we have

$\operatorname{Tr}(P\rho^{\prime})=\lambda\operatorname{Tr}\big{(}P(P\rho
P+Q\langle e^{-i\tau H}\rho e^{i\tau H}\rangle
Q-\rho)\big{)}=\operatorname{Tr}(P\rho P)-\operatorname{Tr}(P\rho)=0$ (5)

and

$\displaystyle\operatorname{Tr}(P^{\prime}\rho)$
$\displaystyle=\operatorname{Tr}\Big{(}P^{\prime}(P\rho P+Q\langle e^{-i\tau
H}\rho e^{i\tau H}\rangle Q-\lambda^{-1}\rho^{\prime})\Big{)}$ (6)
$\displaystyle=\operatorname{Tr}(PP^{\prime}P\rho)+\operatorname{Tr}\big{(}(QP^{\prime}Q)\langle
e^{-i\tau H}\rho e^{i\tau
H}\rangle\big{)}-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime})$ (7)
$\displaystyle=-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime}),$ (8)

so
$\operatorname{Tr}(P\rho)^{\prime}=-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime})$.
Integrating gives

$\displaystyle\operatorname{Tr}(P\rho)\big{|}_{0}^{1}$
$\displaystyle=-\int_{0}^{1}\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime})\operatorname{d\\!}{s}$
(9)
$\displaystyle=-\lambda^{-1}\operatorname{Tr}(P^{\prime}\rho)\big{|}_{0}^{1}+\int_{0}^{1}\bigg{(}\operatorname{Tr}\Big{(}\frac{P^{\prime\prime}}{\lambda}\rho\Big{)}+\operatorname{Tr}\Big{(}\big{(}\tfrac{1}{\lambda}\big{)}^{\prime}P^{\prime}\rho\Big{)}\bigg{)}\operatorname{d\\!}{s},$
(10)

which we can bound by

$\displaystyle\epsilon=\Big{|}\operatorname{Tr}(P\rho)\big{|}_{0}^{1}\Big{|}$
$\displaystyle\leq\Big{|}\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho)\big{|}_{0}^{1}\Big{|}+\int_{0}^{1}\bigg{(}\operatorname{Tr}\Big{(}\big{|}\frac{P^{\prime\prime}}{\lambda}\rho\big{|}\Big{)}+\Big{|}\Big{(}\frac{1}{\lambda}\Big{)}^{\prime}\Big{|}\operatorname{Tr}\Big{(}\big{|}P^{\prime}\rho\big{|}\Big{)}\bigg{)}\operatorname{d\\!}{s}$
(11)
$\displaystyle\leq\Big{(}\left\lVert\lambda(0)^{-1}P^{\prime}(0)\right\rVert+\left\lVert\lambda(1)^{-1}P^{\prime}(1)\right\rVert\Big{)}\operatorname{Tr}(\rho)+\int_{0}^{1}\bigg{(}\left\lVert\frac{P^{\prime\prime}}{\lambda}\right\rVert+\Big{|}\Big{(}\frac{1}{\lambda}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\bigg{)}\operatorname{Tr}(\rho)\operatorname{d\\!}{s}$
(12)
$\displaystyle\leq\left\lVert\lambda(0)^{-1}P^{\prime}(0)\right\rVert+\left\lVert\lambda(1)^{-1}P^{\prime}(1)\right\rVert+\int_{0}^{1}\bigg{(}\left\lVert\frac{P^{\prime\prime}}{\lambda}\right\rVert+\Big{|}\Big{(}\frac{1}{\lambda}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\bigg{)}\operatorname{d\\!}{s}.$ (13)

∎

The next step is to bound $\lVert P^{\prime}\rVert$ and $\lVert
P^{\prime\prime}\rVert$ by more useful quantities. We make use of the
following lemma:

######  Lemma 3.

Under the assumptions stated in 1.1.2, we have

  1. 1.

$\lVert P^{\prime}\rVert\leq 2\frac{\lVert H^{\prime}\rVert}{\Delta}$;

  2. 2.

$\lVert P^{\prime\prime}\rVert\leq 8\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+2\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}$.

This is fairly standard. See for example [18]. A proof is provided in appendix
A. We are now ready to use lemma 2 in two distinct contexts, leading to
theorems 4 and 5.

####  2.1.1 Constant $\lambda$

We first derive a theorem under the assumption that $\lambda$ is constant. In
this case we obtain the following result:

######  Theorem 4.

Under the assumptions in 1.1.2, the algorithm 1 produces the target state with
fidelity of at least $1-\epsilon$ if $\lambda$ is constant and

$\epsilon^{-1}2\Big{(}\frac{\lVert
H^{\prime}(0)\rVert}{\Delta(0)}+\frac{\lVert
H^{\prime}(1)\rVert}{\Delta(1)}+\int_{0}^{1}4\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}\operatorname{d\\!}{s}\Big{)}\leq\lambda.$ (14)

In this case the time complexity of the procedure is given by
$T=\lambda\int_{0}^{1}\frac{1}{\Delta}\operatorname{d\\!}{s}$.

###### Proof.

Let $\epsilon_{0}$ be the actual error of the algorithm. We need
$\epsilon_{0}\leq\epsilon$. We can use lemma 3 to rewrite the inequality in
lemma 2 as

$\displaystyle\epsilon_{0}$ $\displaystyle\leq\lambda^{-1}\big{(}\left\lVert
P^{\prime}(0)\right\rVert+\left\lVert
P^{\prime}(1)\right\rVert\big{)}+\lambda^{-1}\int_{0}^{1}\left\lVert
P^{\prime\prime}\right\rVert\operatorname{d\\!}{s}$ (15)
$\displaystyle\leq\lambda^{-1}\Big{(}2\frac{\lVert
H^{\prime}(0)\rVert}{\Delta(0)}+2\frac{\lVert
H^{\prime}(1)\rVert}{\Delta(1)}+\int_{0}^{1}8\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+2\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}\operatorname{d\\!}{s}\Big{)}.$ (16)

Set $B\coloneqq 2\Big{(}\frac{\lVert
H^{\prime}(0)\rVert}{\Delta(0)}+\frac{\lVert
H^{\prime}(1)\rVert}{\Delta(1)}+\int_{0}^{1}4\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}\operatorname{d\\!}{s}\Big{)}$. Then we have

$\epsilon_{0}\leq\lambda^{-1}B\leq\epsilon B^{-1}B=\epsilon,$ (17)

so the algorithm works. The time complexity is simply given by
$T=\int_{0}^{1}\frac{\lambda}{\Delta}\operatorname{d\\!}{s}=\lambda\int_{0}^{1}\frac{1}{\Delta}\operatorname{d\\!}{s}$.
∎

This result can be compared to theorem 14 in the circuit model.

####  2.1.2 Scaling $\lambda$ with the gap

We know from [11] and [12] that the performance of AQC can be improved with an
adapted schedule, taking more time when the gap is small. Similarly we expect
it to be possible to improve the performance of our procedure by varying
$\lambda$. Indeed this is the case.

######  Theorem 5.

Under the assumptions in 1.1.2, we additionally assume that there exists
$0\leq q\leq 1$ and $B_{1},B_{2}$ such that
$\int_{0}^{1}\frac{1}{\Delta^{1+q}}\operatorname{d\\!}{s}\leq
B_{1}\Delta_{m}^{-q}$ and
$\int_{0}^{1}\frac{1}{\Delta^{2-q}}\operatorname{d\\!}{s}\leq
B_{2}\Delta_{m}^{q-1}$ for all instances of the problem. Then algorithm 1
produces the target state with a fidelity of at least $1-\epsilon$ if

$\lambda=\epsilon^{-1}\frac{C}{\Delta^{q}\Delta_{m}^{1-q}},$ (18)

where $C\coloneqq 2\sup_{s\in[0,1]}\Big{(}2\left\lVert
H^{\prime}(s)\right\rVert+4\left\lVert
H^{\prime}(s)\right\rVert^{2}B_{2}+\left\lVert
H^{\prime\prime}(s)\right\rVert+q|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert B_{2}\Big{)}$.

In this case the time complexity of the procedure is given by

$T\leq\epsilon^{-1}\frac{B_{1}C}{\Delta_{m}}.$

######  Corollary 5.1.

If
$\int_{0}^{1}\frac{1}{\Delta^{p}}\operatorname{d\\!}{s}=O(\Delta_{m}^{1-p})$
holds for all $p>1$, $|\Delta^{\prime}|=O(1)$, $\left\lVert
H^{\prime}\right\rVert=O(1)$ and $\left\lVert
H^{\prime\prime}\right\rVert=O(1)$, then algorithm 1 with the rate defined in
theorem 5 produces the target state with fidelity $1-\epsilon$ and a time
complexity of $O(\Delta_{m}^{-1})$ for all $0<q<1$.

###### Proof of theorem 5.

Let $\epsilon_{0}$ be the actual error of the algorithm, we need
$\epsilon_{0}\leq\epsilon$. In this case the inequality in lemma 2 becomes

$\epsilon_{0}\leq\epsilon
C^{-1}\Delta_{m}^{1-q}\big{(}\Delta(0)^{q}\left\lVert
P^{\prime}(0)\right\rVert+\Delta(1)^{q}\left\lVert
P^{\prime}(1)\right\rVert\big{)}+\epsilon
C^{-1}\int_{0}^{1}\Delta^{q}\Delta_{m}^{1-q}\left\lVert
P^{\prime\prime}\right\rVert+\Big{|}\Big{(}\Delta^{q}\Delta_{m}^{1-q}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\operatorname{d\\!}{s}.$ (19)

We bound the terms separately, using lemma 3. For the first, we have

$\Delta_{m}^{1-q}\Delta^{q}\left\lVert P^{\prime}\right\rVert\leq
2\Delta_{m}^{1-q}\Delta^{q}\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}=2\Delta_{m}^{1-q}\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta^{1-q}}\leq 2\Delta_{m}^{1-q}\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta_{m}^{1-q}}=2\left\lVert
H^{\prime}\right\rVert\leq 2\sup_{s\in[0,1]}\left\lVert
H^{\prime}\right\rVert$ (20)

at both $s=0$ and $s=1$, so we bound the sum by $4\sup_{s\in[0,1]}\left\lVert
H^{\prime}\right\rVert$.

The second term splits into two, since we bound $\left\lVert
P^{\prime\prime}\right\rVert$ by $8\frac{\left\lVert
H^{\prime}\right\rVert^{2}}{\Delta^{2}}+2\frac{\left\lVert
H^{\prime\prime}\right\rVert}{\Delta}$. For the first part we have

$\displaystyle 8\int_{0}^{1}\Delta^{q}\Delta_{m}^{1-q}\frac{\left\lVert
H^{\prime}\right\rVert^{2}}{\Delta^{2}}\operatorname{d\\!}{s}$
$\displaystyle\leq 8\sup_{s\in[0,1]}\left\lVert
H^{\prime}(s)\right\rVert^{2}\Delta_{m}^{1-q}\int_{0}^{1}\frac{1}{\Delta^{2-q}}\operatorname{d\\!}{s}$
(21) $\displaystyle\leq 8\sup_{s\in[0,1]}\left\lVert
H^{\prime}(s)\right\rVert^{2}B_{2}\Delta_{m}^{1-q}\Delta_{m}^{q-1}=8\sup_{s\in[0,1]}\left\lVert
H^{\prime}(s)\right\rVert^{2}B_{2}.$ (22)

The second part gives

$\displaystyle 2\int_{0}^{1}\Delta^{q}\Delta_{m}^{1-q}\frac{\left\lVert
H^{\prime\prime}\right\rVert}{\Delta}\operatorname{d\\!}{s}$
$\displaystyle\leq 2\sup_{s\in[0,1]}\left\lVert
H^{\prime\prime}(s)\right\rVert\Delta_{m}^{1-q}\int_{0}^{1}\frac{1}{\Delta^{1-q}}\operatorname{d\\!}{s}$
(23) $\displaystyle\leq 2\sup_{s\in[0,1]}\left\lVert
H^{\prime\prime}(s)\right\rVert\Delta_{m}^{1-q}\Delta_{m}^{q-1}=2\sup_{s\in[0,1]}\left\lVert
H^{\prime\prime}(s)\right\rVert.$ (24)

Finally, for the third term,

$\displaystyle\int_{0}^{1}\Big{|}\Big{(}\Delta^{q}\Delta_{m}^{1-q}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\operatorname{d\\!}{s}$
$\displaystyle=\int_{0}^{1}q\Delta^{q-1}\Delta_{m}^{1-q}\big{|}\Delta^{\prime}\big{|}\left\lVert
P^{\prime}\right\rVert\operatorname{d\\!}{s}$ (25) $\displaystyle\leq
2q\Delta_{m}^{1-q}\Big{(}\sup_{s\in[0,1]}|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert\Big{)}\int_{0}^{1}\frac{\Delta^{q-1}}{\Delta}\operatorname{d\\!}{s}$
(26)
$\displaystyle=2q\Delta_{m}^{1-q}\Big{(}\sup_{s\in[0,1]}|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert\Big{)}\int_{0}^{1}\frac{1}{\Delta^{2-q}}\operatorname{d\\!}{s}$
(27) $\displaystyle\leq
2q\Big{(}\sup_{s\in[0,1]}|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert\Big{)}\Delta_{m}^{1-q}B_{2}\Delta_{m}^{q-1}$ (28)
$\displaystyle=2qB_{2}\Big{(}\sup_{s\in[0,1]}|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert\Big{)}.$ (29)

Plugging everything back into equation (19), gives

$\displaystyle\epsilon_{0}$ $\displaystyle\leq\epsilon
C^{-1}\sup_{s\in[0,1]}\Big{(}4\left\lVert
H^{\prime}(s)\right\rVert+8\left\lVert
H^{\prime}(s)\right\rVert^{2}B_{2}+2\left\lVert
H^{\prime\prime}(s)\right\rVert+2q|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert B_{2}\Big{)}$ (30) $\displaystyle=\epsilon
C^{-1}C=\epsilon,$ (31)

so the procedure works. We can then calculate the time complexity

$T=\int_{0}^{1}\frac{\lambda}{\Delta}\operatorname{d\\!}{s}=\epsilon^{-1}\int_{0}^{1}\frac{C}{\Delta^{q}\Delta_{m}^{1-q}\Delta}\operatorname{d\\!}{s}=\epsilon^{-1}C\Delta_{m}^{q-1}\int_{0}^{1}\frac{1}{\Delta^{q+1}}\operatorname{d\\!}{s}\leq\epsilon^{-1}C\Delta_{m}^{q-1}B_{1}\Delta_{m}^{-q}=\epsilon^{-1}CB_{1}\Delta_{m}^{-1}.$
(32)

∎

These results can be compared to theorem 15 and corollary 15.1 in the circuit
model.

##  3 Improving the scaling in the error with eigenstate filtering

The use of eigenstate filtering was introduced in [8] to improve scaling in
the error tolerance for algorithms based on adiabatic principles and the
quantum Zeno effect, in particular with application to QLSP.

A similar technique was used in [14] to achieve optimal scaling, but using
Linear Combinations of Unitaries (LCU) instead of Quantum Signal Processing
(QSP). We adapt the technique of [14] to the present situation.

######  Theorem 6.

Let $H$ be a Hamiltonian with $\left\lVert H\right\rVert\leq 1$ and $0$ in the
spectrum of $H$, $\sigma(H)$. Suppose

  * •

$\Delta\geq 0$ is such that $[-\Delta,\Delta]\cap\sigma(H)=\\{0\\}$;

  * •

$P$ is the orthogonal projector on the eigenspace associated to the eigenvalue
$0$, we set $Q\coloneqq\mathbb{1}-P$;

  * •

$\rho$ is a density matrix of the form $P\rho_{0}P+Q\rho_{1}Q$ with
$\operatorname{Tr}(P\rho_{0})>1/2$, that we can prepare at cost $T_{0}$;

  * •

$\epsilon>0$.

Further, suppose

  * •

we can adjoin two ancilla qubits to $\rho$;

  * •

we can can measure and reprepare the ancilla qubits;

  * •

we can evolve the system under $H\otimes R$ and $\mathbb{1}\otimes R$ for time
$t$ for all Hermitian operators $R$ on $\mathbb{C}^{2\times 2}$ with
$\left\lVert R\right\rVert\leq 1$ at a cost of $t$.

Then we can prepare a state $\rho_{2}$ such that
$\operatorname{Tr}(P\rho_{2})\geq 1-\epsilon$ at a cost of
$T=O(T_{0}+\Delta^{-1}\log(1/\epsilon))$.

The idea of the procedure is relatively simple. With these assumptions, we can
apply controlled versions of the unitary $e^{-itH}$, i.e. $e^{itH\otimes\Pi}$
for some projector $\Pi$ on $\mathbb{C}^{2\times 2}$. This means that we can
apply linear combinations of $e^{itH\otimes\Pi}$ using the technique of linear
combinations of unitaries, see lemmas 7 and 8. In particular we can apply a
polynomial that has a large peak at $0$ and is very small everywhere else. We
use this to filter out the part of the state that we do not want.

######  Lemma 7 (LCU with arbitrarily large ancilla register).

Let $f(x)=\sum_{k=-n}^{n}a_{k}x^{k}$ be a rational polynomial with complex
coefficients such that $\sum_{k=-n}^{n}|a_{k}|^{2}=1$. Let $H$ be a
Hamiltonian and $\rho$ the state of the system. Assume we have access to an
ancilla register with orthonormal basis $\\{|k\rangle\;|\;k\in\mathbb{Z}\\}$.
Then, at a cost of $O(nt)$, we can do an operation which either

  * •

succeeds and applies $\sum_{k=-n}^{n}|a_{k}|^{2}e^{-itkH}$ to the system,

  * •

or fails, with a probability of
$1-\operatorname{Tr}\bigg{(}\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{-itkH}\Big{)}\rho\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{itkH}\Big{)}\bigg{)}$.
We can see when this has happened thanks to the measured contents of the
ancilla register.

###### Proof.

The procedure is as follows: we first prepare the ancilla in the state
$|f\rangle\coloneqq\sum_{k=-n}^{n}a_{k}|k\rangle$, then apply
$\sum_{k=-n}^{n}kH\otimes|k\rangle\langle k|$ for time $t$ and finally measure
the state $|f\rangle$. If we measure any other state than $|f\rangle$, the
procedure fails.

The result then follows from the following identity:

$\sum_{k,l=-n}^{n}\Big{(}\mathbb{1}\otimes a_{k}\langle
k|\Big{)}e^{-it\sum_{m=-n}^{n}mH\otimes|m\rangle\langle
m|}\Big{(}\mathbb{1}\otimes\overline{a_{l}}|l\rangle\Big{)}=\sum_{m}|a_{m}|^{2}e^{-itmH}.$
(33)

Defining

$\Pi_{m}^{0}=\mathbb{1}-\sum_{k=0}^{m}|k\rangle\langle
k|\qquad\text{and}\qquad\Pi_{m}^{1}=\mathbb{1}-\sum_{k=-m}^{0}|k\rangle\langle
k|,$ (34)

we can write $e^{-it\sum_{m=-n}^{n}mH\otimes|m\rangle\langle
m|}=\prod_{m=0}^{n-1}e^{-itH\otimes\Pi_{m}^{0}}e^{itH\otimes\Pi_{m}^{1}}$,
which we can clearly apply at a cost of $2nt$.

The cost of ancilla preparation depends on the admissible operations on the
ancilla register, but in a worst-case scenario, each $a_{k}$ needs to be set
separately444This is the case for the procedure used in lemma 8. which means
that the cost is $O(n)$. The total cost is then still $O(nt)$. ∎

######  Lemma 8 (LCU with two ancilla qubits).

We can achieve the results of 7 only using two ancilla qubits at a time.

The construction is identical to the one in [14].

###### Proof of theorem 6.

Let $Q\coloneqq\mathbb{1}-P$ and write $Q=\sum_{j}Q_{j}$, where each $Q_{j}$
is an eigenprojector of $H$ associated to the eigenvalue $\omega_{j}$. Now we
observe

$\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{-ikH}\Big{)}Q_{j}=\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{-ik\omega_{j}}\Big{)}Q_{j}=A(\omega_{j})Q_{j},$
(35)

where $A(\omega)$ is the Fourier transform of the sequence $|a_{k}|^{2}$. Thus

$\displaystyle\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{-ikH}\Big{)}Q\rho
Q\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{ikH}\Big{)}$
$\displaystyle=\sum_{j,l}\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{-ikH}\Big{)}Q_{j}\rho
Q_{l}\Big{(}\sum_{k=-n}^{n}|a_{k}|^{2}e^{ikH}\Big{)}$ (36)
$\displaystyle=\sum_{j,l}A(\omega_{j})A(-\omega_{l})Q_{j}\rho Q_{l}.$ (37)

Taking the trace gives
$\operatorname{Tr}\Big{(}\sum_{j,l}A(\omega_{j})A(-\omega_{l})Q_{j}\rho
Q_{l}\Big{)}\leq\max_{\omega\notin[-\Delta,\Delta]}A(\omega)^{2}\operatorname{Tr}(Q\rho
Q)\leq\max_{\omega\notin[-\Delta,\Delta]}A(\omega)^{2}$. The goal then becomes
to find a sequence and its Fourier transform such that $A(\omega_{0})=1$,
$\max_{\omega\notin[-\Delta,\Delta]}A(\omega)^{2}\leq\epsilon$ and whose
window $n$ is as small as possible. The answer to this optimisation problem is
well-known and is given by the Dolph-Chebyshev window [19]. In this case we
need a window of555We note that we improve the scaling by a factor of two
compared to [14]. This is because we are able to start from a state where
$P\rho Q=0=Q\rho P$.

$\displaystyle
n=\frac{\cosh^{-1}(1/\sqrt{\epsilon})}{\cosh^{-1}\big{(}\sec(\Delta)\big{)}}\leq\frac{1}{2\Delta}\log\Big{(}\frac{4}{\epsilon}\Big{)}.$
(38)

By lemma 7, we can implement this at a cost of $O(n)$. Note that this
procedure terminates succesfully with a probability of at least
$\operatorname{Tr}(P\rho_{0})$ (which is bounded below) and we can check to
see whether the procedure failed. If it failed, we repeat. On average we need
to repeat fewer than $\operatorname{Tr}(P\rho_{0})^{-1}$ times, which is
$O(1)$. ∎

##  4 Applications

###  4.1 Grover search

For the Grover problem, we have an $N$-dimensional vector space we want to
find an element of an $M$-dimensional subspace $\mathcal{M}$. In order to help
us, we assume we have access to an oracle Hamiltonian
$H_{1}=\mathbb{1}-P_{\mathcal{M}}$, where $P_{\mathcal{M}}$ is the orthogonal
projector on $\mathcal{M}$. In other words, we assume $H_{1}$ is admissible.
We also assume $H_{0}=\mathbb{1}-|u\rangle\langle u|$ is admissible, where
$|u\rangle=\frac{1}{\sqrt{N}}\sum_{i=1}^{N}|i\rangle$ is the uniform
superposition. The aim is now to use the interpolation
$H(s)=(1-s)H_{0}+sH_{1}$ to prepare as state in $\mathcal{M}$. For more
details see [2] and [20].

We see that $H(s)$ has four eigenvalues:

$\displaystyle\lambda_{1,2}$
$\displaystyle=\frac{1}{2}\left(1\pm\sqrt{1-4(1-\frac{M}{N})s(1-s)}\right)$
with multiplicity $1$ (39) $\displaystyle\lambda_{3}$ $\displaystyle=1-s$ with
multiplicity $M-1$ (40) $\displaystyle\lambda_{4}$ $\displaystyle=1$ with
multiplicity $N-M-1$. (41)

The eigenvectors corresponding to $\lambda_{3}$ are the eigenvectors in
$\mathcal{M}$ with zero overlap with $|u\rangle$. The eigenvectors
corresponding to $\lambda_{4}$ are the eigenvectors in $\mathcal{M}^{\perp}$
with zero overlap with $|u\rangle$. Since the initial state has zero overlap
with any of these vectors and they are eigenvectors of each $H(s)$, none of
them are prepared by the procedure and everything happens in the two-
dimensional space spanned by the eigenvectors associated to $\lambda_{1}$ and
$\lambda_{2}$.

We have explicitly computed the gap, so we can use this as the bound $\Delta$:

$\Delta(s)=\sqrt{1-4(1-\frac{M}{N})s(1-s)}.$ (42)

We can set $\Delta_{m}=\min_{s\in[0,1]}\Delta(s)=\sqrt{M/N}$. In order to give
bounds on the time-complexity, we use the following result:

######  Lemma 9.

For all $p>1$ and $\Delta$ given by (42), we have

$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=O\big{(}\sqrt{N/M}^{p-1}\big{)}=O\big{(}\Delta_{m}^{1-p}\big{)},$
(43)

and, for $p=1$,

$\int_{0}^{1}\frac{1}{\Delta(s)}\operatorname{d\\!}{s}=O\big{(}\log(N/M)\big{)}.$
(44)

We provide a proof in appendix C.1. For constant $\lambda$, we apply theorem 4
and use the lemma 9 to get a time complexity
$O\big{(}\sqrt{N/M}\log(N/M)\big{)}$.

We are able to take the $q$ in corollary 5.1 to be anywhere in the range
$0<q<1$, since for any such $q$ both $1+q$ and $2-q$ are strictly greater than
$1$. This is related to the range of schedules described in [13]. The time
complexity of the algorithm for any such $q$ is $O(\sqrt{N/M})$, since it is
easy to check that to other conditions hold: $\left\lVert
H^{\prime}\right\rVert=\left\lVert H_{1}-H_{0}\right\rVert$, $\left\lVert
H^{\prime\prime}\right\rVert=0$ and

$\displaystyle|\Delta^{\prime}|$
$\displaystyle=\Big{|}\frac{4(1-\frac{M}{N})(\frac{1}{2}-s)}{\Delta}\Big{|}$
(45)
$\displaystyle\leq\frac{2\sqrt{4(1-\frac{M}{N})(\frac{1}{2}-s)^{2}}}{\Delta}$
(46)
$\displaystyle\leq\frac{2\sqrt{\frac{M}{N}+4(1-\frac{M}{N})(\frac{1}{2}-s)^{2}}}{\Delta}=2\frac{\Delta}{\Delta}=2.$
(47)

###  4.2 Solving linear systems of equations

The Quantum Linear Systems Problem (QLSP) was introduced in [15]. Suppose $A$
is an invertible $N\times N$ matrix $b\in\mathbb{C}^{N}$ a vector. The goal is
to prepare the quantum state $\frac{A^{-1}|b\rangle}{\left\lVert
A^{-1}|b\rangle\right\rVert}$. We express the time complexity of our algorithm
in terms of the condition number $\kappa=\left\lVert
A\right\rVert\,\left\lVert A^{-1}\right\rVert$.

We may restrict ourselves to Hermitian matrices because we can use the
following trick from [15]: If $A$ is not Hermitian, we consider the matrix
$\begin{pmatrix}0&A\\\ A^{*}&0\end{pmatrix}$, which has the same condition
number, and solve the equation $\begin{pmatrix}0&A\\\
A^{*}&0\end{pmatrix}|y\rangle=\begin{pmatrix}|b\rangle\\\ 0\end{pmatrix}$.

First we rescale the matrix $A$ to $\frac{A}{\left\lVert A\right\rVert}$. We
do this because typically admissible matrices need to be uniformly bounded.
This has the effect of shifting the lowest singular value from
$\frac{1}{\left\lVert A^{-1}\right\rVert}$ to $\frac{1}{\left\lVert
A\right\rVert\left\lVert A^{-1}\right\rVert}=\kappa^{-1}$. Now we consider a
path of Hamiltonians that was introduced in [16]. Define
$A(s)\coloneqq(1-s)\sigma_{z}\otimes\mathbb{1}+s\sigma_{x}\otimes A$,
$Q_{b,+}\coloneqq\mathbb{1}-\big{(}|+\rangle|b\rangle\big{)}\big{(}\langle+|\langle
b|\big{)}$ and $\sigma_{\pm}\coloneqq\frac{1}{2}\big{(}\sigma_{x}\pm
i\sigma_{y}\big{)}$. Set
$H(s)=\sigma_{+}\otimes\big{(}A(s)Q_{b,+}\big{)}+\sigma_{-}\otimes\big{(}Q_{b,+}A(s)\big{)}$.
This can be written as a linear interpolation $H(s)=(1-s)H_{0}+sH_{1}$, where

$\displaystyle H_{0}$
$\displaystyle\coloneqq\sigma_{+}\otimes\big{(}(\sigma_{z}\otimes\mathbb{1})Q_{b,+}\big{)}+\sigma_{-}\otimes\big{(}Q_{b,+}(\sigma_{z}\otimes\mathbb{1})\big{)}$
(48) $\displaystyle H_{1}$
$\displaystyle\coloneqq\sigma_{+}\otimes\big{(}(\sigma_{x}\otimes
A)Q_{b,+}\big{)}+\sigma_{-}\otimes\big{(}Q_{b,+}(\sigma_{x}\otimes A)\big{)}.$
(49)

Following the analysis of [16], we see that $H(s)$ has $0$ as an eigenvalue
for all $s\in[0,1]$. The corresponding eigenspace is spanned by
$\\{|0\rangle\otimes|x(s)\rangle,|1\rangle\otimes|+\rangle|b\rangle\\}$, where
$|x(s)\rangle\coloneqq\frac{A(s)^{-1}|b\rangle}{\left\lVert
A(s)^{-1}|b\rangle\right\rVert}$. Since $H(s)$ does not allow transition
between these states, we are sure to not prepare
$|1\rangle\otimes|+\rangle|b\rangle$, so long as we start with
$|0\rangle\otimes|x(0)\rangle$.

In [16] it was also shown that the eigenvalue zero is separated from the rest
of the spectrum by a gap that is at least

$\Delta(s)=\sqrt{(1-s)^{2}+\Big{(}\frac{s}{\kappa}\Big{)}^{2}}.$ (50)

If $\kappa$ is large enough, then we can take
$\Delta_{m}\coloneqq\frac{1}{2\kappa}\leq\sqrt{\frac{1}{\kappa^{2}+1}}=\min_{s\in[0,1]}\Delta(s)$.

In order to give bounds on the time-complexity, we use the following result:

######  Lemma 10.

For all $p>1$, we have

$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=O\big{(}\kappa^{p-1}\big{)}=O\big{(}\Delta_{m}^{1-p}\big{)},$
(51)

and, for $p=1$,

$\int_{0}^{1}\frac{1}{\Delta(s)}\operatorname{d\\!}{s}=O\big{(}\log(\kappa)\big{)}.$
(52)

We provide a proof in appendix C.2.

For constant $\lambda$, we apply theorem 4 and use the lemma 10 to get a time
complexity $O\big{(}\kappa\log(\kappa)\big{)}$. This is also the complexity
that was obtained in [16].

As before, we have a full order reduction for $p>1$ and thus we are able to
take the $q$ in corollary 5.1 to be anywhere in the range $0<q<1$, since for
any such $q$ both $1+q$ and $2-q$ are strictly greater than $1$. If $q=0$ or
$q=1$, the complexity gains a factor of $\log(\kappa)$. This exactly mirrors
the situation in [13] and is the reason why the algorithms for QLSP based on
the RM have an extra factor of $\log(\kappa)$ in the asymptotic complexity,
see [16] and [9].

We can apply 5.1 since $\left\lVert H^{\prime}\right\rVert=\left\lVert
H_{1}-H_{0}\right\rVert$, $\left\lVert H^{\prime\prime}\right\rVert=0$ and

$\displaystyle|\Delta^{\prime}|$
$\displaystyle=\Big{|}\frac{s-1+s/\kappa^{2}}{\Delta}\Big{|}$ (53)
$\displaystyle=\frac{\sqrt{(s-1+s/\kappa^{2})^{2}}}{\Delta}$ (54)
$\displaystyle=\frac{\sqrt{(1+1/\kappa^{2})^{2}s^{2}-(1+1/\kappa^{2})2s+1}}{\Delta}$
(55)
$\displaystyle\leq\frac{\sqrt{(1+1/\kappa^{2})^{2}s^{2}-(1+1/\kappa^{2})2s+(1+1/\kappa^{2})}}{\Delta}$
(56)
$\displaystyle=\sqrt{1+1/\kappa^{2}}\frac{\Delta}{\Delta}=\sqrt{1+1/\kappa^{2}}=O(1).$
(57)

This yields a time complexity of $O(\kappa)$ for fixed error tolerance. The
scaling on both condition number and error tolerance is
$O(\epsilon^{-1}\kappa)$. By a straightforward application of theorem 6 at
$s=1$, we get a scaling of $O\big{(}\log(\epsilon^{-1})\kappa\big{)}$. This is
possible, since we know the eigenvalue of interest is $0$.

This result is optimal and matches the complexity reported in [14], where it
was achieved using a very different method.

This work was supported by the Belgian Fonds de la Recherche Scientifique -
FNRS under Grants No. R.8015.21 (QOPT) and O.0013.22 (EoS CHEQS)

## References

  * [1] Andrew Lucas  “Ising formulations of many NP problems”  In _Frontiers in Physics_ 2, 2014  DOI: 10.3389/fphy.2014.00005
  * [2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Michael Sipser  “Quantum Computation by Adiabatic Evolution”, 2000  arXiv:quant-ph/0001106 [quant-ph]
  * [3] Sabine Jansen, Mary-Beth Ruskai and Ruedi Seiler  “Bounds for the adiabatic approximation with applications to quantum computation”  In _Journal of Mathematical Physics_ 48.10 AIP Publishing, 2007  DOI: 10.1063/1.2798382
  * [4] Dorit Aharonov et al.  “Adiabatic quantum computation is equivalent to standard quantum computation”  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , 2004, pp. 42–51  DOI: 10.1109/FOCS.2004.8
  * [5] Andrew M. Childs et al.  “Quantum search by measurement”  In _Physical Review A_ 66.3 American Physical Society (APS), 2002  DOI: 10.1103/physreva.66.032314
  * [6] Sergio Boixo, Emanuel Knill and Rolando Somma  “Eigenpath traversal by phase randomization”  In _Quantum Information and Computation_ 9.9&10, 2009, pp. 833–855  DOI: 10.26421/QIC9.9-10-7
  * [7] Joseph E. Avron, Martin Fraas, Gian M. Graf and Philip Grech  “Adiabatic Theorems for Generators of Contracting Evolutions”  In _Communications in Mathematical Physics_ 314.1 Springer ScienceBusiness Media LLC, 2012, pp. 163–191  DOI: 10.1007/s00220-012-1504-1
  * [8] Lin Lin and Yu Tong  “Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems”  In _Quantum_ 4 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2020, pp. 361  DOI: 10.22331/q-2020-11-11-361
  * [9] David Jennings et al.  “Efficient quantum linear solver algorithm with detailed running costs”, 2023  arXiv:2305.11352 [quant-ph]
  * [10] Lov K. Grover  “A fast quantum mechanical algorithm for database search”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219  DOI: 10.1145/237814.237866
  * [11] Jérémie Roland and Nicolas J. Cerf  “Quantum search by local adiabatic evolution”  In _Physical Review A_ 65.4 American Physical Society (APS), 2002  DOI: 10.1103/physreva.65.042308
  * [12] Wim Dam, Michele Mosca and Umesh Vazirani  “How powerful is adiabatic quantum computation?”  In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ IEEE, 2001  DOI: 10.1109/sfcs.2001.959902
  * [13] Dong An and Lin Lin  “Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm”  In _ACM Transactions on Quantum Computing_ 3.2 Association for Computing Machinery (ACM), 2022, pp. 1–28  DOI: 10.1145/3498331
  * [14] Pedro C.S. Costa et al.  “Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem”  In _PRX Quantum_ 3 American Physical Society, 2022, pp. 040303  DOI: 10.1103/PRXQuantum.3.040303
  * [15] Aram W. Harrow, Avinatan Hassidim and Seth Lloyd  “Quantum Algorithm for Linear Systems of Equations”  In _Physical Review Letters_ 103.15 American Physical Society (APS), 2009  DOI: 10.1103/physrevlett.103.150502
  * [16] Yiğit Subaşı, Rolando D. Somma and Davide Orsucci  “Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing”  In _Physical Review Letters_ 122.6 American Physical Society (APS), 2019  DOI: 10.1103/physrevlett.122.060504
  * [17] Pedro C.. Costa, Dong An, Ryan Babbush and Dominic Berry  “The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver”, 2023  arXiv:2312.07690 [quant-ph]
  * [18] Ben W. Reichardt  “The quantum adiabatic optimization algorithm and local minima”  In _Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing_ , STOC ’04  Chicago, IL, USA: Association for Computing Machinery, 2004, pp. 502–510  DOI: 10.1145/1007352.1007428
  * [19] Peter Lynch  “The Dolph–Chebyshev Window: A Simple Optimal Filter”  In _Monthly Weather Review_ 125.4 Boston MA, USA: American Meteorological Society, 1997, pp. 655–660  DOI: 10.1175/1520-0493(1997)125¡0655:TDCWAS¿2.0.CO;2
  * [20] Jérémie Roland and Nicolas J. Cerf  “Quantum-circuit model of Hamiltonian search algorithms”  In _Physical Review A_ 68.6 American Physical Society (APS), 2003  DOI: 10.1103/physreva.68.062311

##  Appendix A Bounds on derivatives of projectors

We provide a proof of lemma 3

######  Lemma.

Under the assumptions stated in 1.1.2, we have

  1. 1.

$\lVert P^{\prime}\rVert\leq 2\frac{\lVert H^{\prime}\rVert}{\Delta}$;

  2. 2.

$\lVert P^{\prime\prime}\rVert\leq 8\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+2\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}$.

###### Proof.

Let $\Gamma$ be a circle in the complex plane, centred at the ground energy
with radius $\Delta/2$. Then we have the Riesz form of the projector

$P=\frac{1}{2\pi i}\oint_{\Gamma}R_{H}(z)\operatorname{d\\!}{z},$

where $R_{H}(z)=\big{(}z\operatorname{id}-H\big{)}^{-1}$ is the resolvent of
$H$ at $z$. Then $R_{H}(z)^{\prime}=R_{H}(z)H^{\prime}R_{H}(z)$ (the
derivative is with respect to $s$, not $z$). As $H$ is a normal operator, the
norm $\lVert R_{H}(z)\rVert$ is equal to the inverse of the distance from $z$
to the spectrum $\sigma(H)$. On the circle $\Gamma$ this is equal to
$(\Delta/2)^{-1}$ everywhere. We can then approximate

$\displaystyle\lVert P^{\prime}\rVert$
$\displaystyle=\Big{\lVert}\frac{1}{2\pi
i}\oint_{\Gamma}R_{H}(z)^{\prime}\operatorname{d\\!}{z}\Big{\rVert}$
$\displaystyle\leq\frac{1}{2\pi}\oint_{\Gamma}\lVert
R_{H}(z)^{\prime}\lVert\operatorname{d\\!}{z}$
$\displaystyle\leq\frac{1}{2\pi}\oint_{\Gamma}\lVert R_{H}(z)\rVert\cdot\lVert
H^{\prime}\rVert\cdot\lVert R_{H}(z)\rVert\operatorname{d\\!}{z}$
$\displaystyle=\frac{1}{2\pi}\Big{(}\frac{2}{\Delta}\Big{)}^{2}\lVert
H^{\prime}\rVert\oint_{\Gamma}\operatorname{d\\!}{z}$
$\displaystyle=\frac{1}{2\pi}\Big{(}\frac{2}{\Delta}\Big{)}^{2}2\pi\frac{\Delta}{2}\lVert
H^{\prime}\rVert$ $\displaystyle=2\frac{\lVert H^{\prime}\rVert}{\Delta}.$

Similarly, we can write

$P^{\prime\prime}=\frac{1}{2\pi
i}\oint_{\Gamma}2R_{H}(z)H^{\prime}R_{H}(z)H^{\prime}R_{H}(z)+R_{H}(z)H^{\prime\prime}R_{H}(z)\operatorname{d\\!}{z}.$

Estimating this in the same way as before yields

$\lVert P^{\prime\prime}\rVert\leq 8\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+2\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}.$

∎

##  Appendix B Comparison with the circuit model

So far we have assumed access to a device that can evolve a system under a
given Hamiltonian in real time, i.e. it takes time $t$ to apply $e^{-itH}$.
This is the typical setting of AQC and is also the setting of [6] and [16].

Many papers use a slightly different setup. In [14] and [9] the setting is a
standard quantum computer which is given access to block encodings of $H(s)$
for all $s\in[0,1]$. In this case the complexity is given by the number of
times such a block-encoded Hamiltonian is used. In other words, the complexity
is a query complexity rather than a time complexity.

Given access to only a block encoding of a Hamiltonian $H$, it is generally
not possible to simulate $e^{-itH}$ exactly. Instead, we can use proposition
11, which is taken from [9].

######  Proposition 11 (Theorem 4 from [9]).

Given access to an $(\alpha,m,0)$–block-encoding $U_{H}$ of a Hermitian
operator $H$ with $\left\lVert H\right\rVert\leq 1$, we can realise a
$(1,m+2,\delta)$–block-encoding of $e^{-itH}$ for $t\in\mathbb{R}$ with

$3\Big{\lceil}\frac{e}{2}\alpha|t|+\log\big{(}\frac{2c}{\delta}\big{)}\Big{\rceil}$

calls to $U_{H},U_{H}^{*}$ with $c=4(\sqrt{2\pi}e^{\frac{1}{13}})^{-1}\approx
1.47762$.

In this proposition $\delta$ gives the error of the block encoding, i.e. if
$U$ is the block encoding, then $\left\lVert
U-e^{-itH}\right\rVert\leq\delta$.

This motivates replacing the algorithm 1 by the algorithm 2, which now depends
on both a rate $\lambda(s)$ and an allowable simulation error $\delta(s)$.

1Pick a Poisson process $N:[0,1]\times(\Omega,\mathcal{A},P)\to\mathbb{N}$
with rate $\lambda(s)$;

2 At each jump point $s$ of the Poisson process, pick an instance $t$ of the
random variable $T$ as defined in proposition 1 and use proposition 11 to
simulate the evolution under the time-independent Hamiltonian $H(s)$ for a
time $t$ with error at most $\delta(s)$;

Algorithm 2 Poisson-distributed phase randomisation with imperfect time
evolution

In this case the number of queries is bounded by a quantity $Q$ is a random
variable with stochastic differential equation
$\operatorname{d\\!}{Q}=3\Big{(}\frac{e}{2}\alpha|\tau|+\log\big{(}\frac{2c}{\delta}\big{)}+1\Big{)}\operatorname{d\\!}{N}$.
Taking the average yields $Q=3\int_{0}^{1}\Big{(}\frac{e\alpha
t_{0}}{2\Delta}+\log\big{(}\frac{2c}{\delta}\big{)}+1\Big{)}\lambda\operatorname{d\\!}{s}$.

To analyse algorithm 2, we prove lemma 12, which is analogous to lemma 2.

######  Lemma 12.

Given the assumptions in 1.1.2 and that for all $s\in[0,1]$ and
$t\in[0,\infty[$, we can apply an operation $A(s,t)$ such that $\left\lVert
e^{-itH(s)}-A(s,t)\right\rVert\leq\delta(s)$, the algorithm 1 with rate
$\lambda(s)$ has an error that is bounded by

$\epsilon\leq\int_{0}^{1}(2\delta+\delta^{2})\Big{(}2\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}+\lambda(s)\Big{)}\operatorname{d\\!}{s}+\left\lVert\lambda(0)^{-1}P^{\prime}(0)\right\rVert+\left\lVert\lambda(1)^{-1}P^{\prime}(1)\right\rVert+\int_{0}^{1}\bigg{(}\left\lVert\frac{P^{\prime\prime}}{\lambda}\right\rVert+\Big{|}\Big{(}\frac{1}{\lambda}\Big{)}^{\prime}\Big{|}\left\lVert
P^{\prime}\right\rVert\bigg{)}\operatorname{d\\!}{s}.$ (58)

###### Proof.

The differential equation (2) is then

$\rho^{\prime}=\lambda\Big{(}P\rho P+Q\langle e^{-i\tau H}\rho e^{i\tau
H}\rangle Q-\rho\Big{)}+\lambda\Big{(}A(s,t)\rho A(s,t)^{*}-e^{-i\tau H}\rho
e^{i\tau H}\Big{)}.$ (59)

We set $E\coloneqq A(s,t)\rho A(s,t)^{*}-e^{-i\tau H}\rho e^{i\tau H}$. Then
equations (5) and (8) become
$\operatorname{Tr}(P\rho^{\prime})=\lambda\operatorname{Tr}(E)$ and
$\operatorname{Tr}(P^{\prime}\rho)=\operatorname{Tr}(P^{\prime}E)-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime})$,
so

$\operatorname{Tr}(P\rho)^{\prime}=\operatorname{Tr}(P\rho^{\prime})+\operatorname{Tr}(P^{\prime}\rho)=\lambda\operatorname{Tr}(E)+\operatorname{Tr}(P^{\prime}E)-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime}).$
(60)

The integral of $-\operatorname{Tr}(\lambda^{-1}P^{\prime}\rho^{\prime})$ was
bounded in the proof of lemma 2.

Using lemma 13, we bound $\operatorname{Tr}(|E|)\leq 2\delta+\delta^{2}$.
Together with the bound $\left\lVert P^{\prime}\right\rVert\leq
2\frac{\left\lVert H^{\prime}\right\rVert}{\Delta}$, this yields the result. ∎

In this proof we have made use of the following lemma:

######  Lemma 13 (Lemma 9 from [9]).

Suppose $A,B$ are operators such that $\left\lVert A-B\right\rVert\leq\delta$.
Then, for each density operators $\rho$, we have

$\operatorname{Tr}(|A\rho A^{*}-B\rho B^{*}|)\leq 2\delta\left\lVert
A\right\rVert+\delta^{2}.$ (61)

######  Theorem 14.

Under the assumptions in 1.1.2, the algorithm 2 produces the target state with
fidelity of at least $1-\epsilon$ if $\lambda$ is constant,
$\delta=\frac{4\epsilon}{27\lambda}$ and

$\epsilon^{-1}4\Big{(}\frac{\lVert
H^{\prime}(0)\rVert}{\Delta(0)}+\frac{\lVert
H^{\prime}(1)\rVert}{\Delta(1)}+\int_{0}^{1}4\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}\operatorname{d\\!}{s}\Big{)}\leq\lambda.$ (62)

Using the Hamiltonian simulation of proposition 11, this gives a query
complexity of

$Q=\lambda\Big{(}e\alpha
t_{0}\frac{3}{2}\int_{0}^{1}\frac{1}{\Delta}\operatorname{d\\!}{s}+3\log\big{(}\frac{27c}{2\epsilon}\big{)}+\log(\lambda)+1\Big{)}.$

###### Proof.

Let $\epsilon_{0}$ be the actual error of the algorithm. We need
$\epsilon_{0}\leq\epsilon$. As in the proof of 4, rewrite the inequality in
lemma 12 as

$\epsilon_{0}\leq(2\delta+\delta^{2})\Big{(}\int_{0}^{1}2\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}\operatorname{d\\!}{s}+\lambda\Big{)}+\lambda^{-1}\Big{(}2\frac{\lVert
H^{\prime}(0)\rVert}{\Delta(0)}+2\frac{\lVert
H^{\prime}(1)\rVert}{\Delta(1)}+\int_{0}^{1}8\frac{\lVert
H^{\prime}\rVert^{2}}{\Delta^{2}}+2\frac{\lVert
H^{\prime\prime}\rVert}{\Delta}\operatorname{d\\!}{s}\Big{)}.$ (63)

As in the proof of 4, the second term is bounded by $\epsilon/2$. Since all
the terms of equation (62) are positive, we have
$\int_{0}^{1}2\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}\operatorname{d\\!}{s}\leq\frac{\epsilon\lambda}{8}$.
Then we bound

$\displaystyle(2\delta+\delta^{2})\Big{(}\int_{0}^{1}2\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}\operatorname{d\\!}{s}+\lambda\Big{)}$
$\displaystyle\leq 3\delta\big{(}\frac{\epsilon\lambda}{8}+\lambda\big{)}$
(64)
$\displaystyle\leq\frac{27}{8}\delta\lambda(\epsilon+1)\leq\frac{27}{8}\delta\lambda\leq\frac{\epsilon}{2}.$
(65)

Finally we consider the query complexity and calculate

$\displaystyle Q$ $\displaystyle=3\int_{0}^{1}\Big{(}\frac{e\alpha
t_{0}}{2\Delta}+\log\big{(}\frac{2c}{\delta}\big{)}+1\Big{)}\lambda\operatorname{d\\!}{s}$
(66) $\displaystyle\leq\lambda\Big{(}e\alpha
t_{0}\frac{3}{2}\int_{0}^{1}\frac{1}{\Delta}\operatorname{d\\!}{s}+3\log\big{(}\frac{27c}{2\epsilon}\big{)}+\log(\lambda)+1\Big{)}.$
(67)

∎

######  Theorem 15.

Under the assumptions in 1.1.2, we additionally assume that there exists
$0\leq q\leq 1$ and $B_{1},B_{2}$ such that
$\int_{0}^{1}\frac{1}{\Delta^{1+q}}\operatorname{d\\!}{s}\leq
B_{1}\Delta_{m}^{-q}$ and
$\int_{0}^{1}\frac{1}{\Delta^{2-q}}\operatorname{d\\!}{s}\leq
B_{2}\Delta_{m}^{q-1}$ for all instances of the problem. Then algorithm 2
produces the target state with a fidelity of at least $1-\epsilon$ if

$\displaystyle\lambda$
$\displaystyle=\epsilon^{-1}\frac{2C}{\Delta^{q}\Delta_{m}^{1-q}}$ (68)
$\displaystyle\delta$ $\displaystyle=\frac{2\epsilon}{15\lambda}$ (69)

where $C\coloneqq 2\sup_{s\in[0,1]}\Big{(}2\left\lVert
H^{\prime}(s)\right\rVert+4\left\lVert
H^{\prime}(s)\right\rVert^{2}B_{2}+\left\lVert
H^{\prime\prime}(s)\right\rVert+q|\Delta^{\prime}(s)|\,\left\lVert
H^{\prime}(s)\right\rVert B_{2}\Big{)}$.

If, in addition, there exists a constant $B_{3}$ such that
$\int_{0}^{1}\frac{1}{\Delta^{2q}}\operatorname{d\\!}{s}\leq
B_{3}\Delta_{m}^{1-2q}$ and the Hamiltonian simulation of 11 is used, this
gives a query complexity of

$Q\leq\frac{1}{\epsilon\Delta_{m}}\Big{(}12C\log(\epsilon^{-1})+3e\alpha
t_{0}CB_{1}+6\log(15c)C+12C^{2}B_{3}\Big{)}.$

###### Proof.

As before, we need to bound the inequality in lemma 12. Everything except the
first term has already been bounded in the proof of theorem 5 to be less than
$\epsilon/2$. (Notice that we are taking $\lambda$ to be twice the rate
specified in theorem 5.)

We now need to show that the first term in the inequality in lemma 12 can be
bounded by $\epsilon/2$. Indeed, we calculate

$\displaystyle\int_{0}^{1}(2\delta+\delta^{2})\Big{(}2\frac{\left\lVert
H^{\prime}\right\rVert}{\Delta}+\lambda(s)\Big{)}\operatorname{d\\!}{s}$
$\displaystyle\leq\int_{0}^{1}3\delta\Big{(}\frac{C}{2\Delta}+\lambda\Big{)}\operatorname{d\\!}{s}$
(70)
$\displaystyle=\int_{0}^{1}\frac{2\epsilon}{5\lambda}\Big{(}\frac{C}{2\Delta}+\lambda\Big{)}\operatorname{d\\!}{s}$
(71)
$\displaystyle=\frac{2\epsilon}{5}\Big{(}1+\int_{0}^{1}\epsilon\frac{\Delta_{m}^{q-1}}{4\Delta^{q-1}}\operatorname{d\\!}{s}\Big{)}$
(72)
$\displaystyle\leq\frac{2\epsilon}{5}\Big{(}1+\frac{\epsilon}{4}\Big{)}\leq\frac{\epsilon}{2}.$
(73)

Finally we consider the query complexity and calculate, using the fact that
$\log(x)+1\leq x$ for all positive $x$,

$\displaystyle Q$ $\displaystyle=3\int_{0}^{1}\Big{(}\frac{e\alpha
t_{0}}{2\Delta}+\log\big{(}\frac{2c}{\delta}\big{)}+1\Big{)}\lambda\operatorname{d\\!}{s}$
(74) $\displaystyle=3\int_{0}^{1}\Big{(}\frac{e\alpha
t_{0}}{2\Delta}+\log\big{(}\frac{15c}{\epsilon}\big{)}+\log(\epsilon\lambda)+1\Big{)}\lambda\operatorname{d\\!}{s}$
(75) $\displaystyle\leq 3\int_{0}^{1}\Big{(}\frac{e\alpha
t_{0}}{2\Delta}\lambda+\log\big{(}\frac{15c}{\epsilon^{2}}\big{)}\lambda+\epsilon\lambda^{2}\Big{)}\operatorname{d\\!}{s}.$
(76)

We bound each term separately. First

$\displaystyle 3\int_{0}^{1}\frac{e\alpha
t_{0}}{2\Delta}\lambda\operatorname{d\\!}{s}$ $\displaystyle=\frac{3e\alpha
t_{0}C}{\epsilon\Delta_{m}^{1-q}}\int_{0}^{1}\frac{1}{\Delta^{q+1}}\lambda\operatorname{d\\!}{s}$
(77) $\displaystyle\leq\frac{3e\alpha
t_{0}C}{\epsilon\Delta_{m}^{1-q}}B_{1}\Delta_{m}^{-q}=\frac{3e\alpha
t_{0}CB_{1}}{\epsilon\Delta_{m}}.$ (78)

Next

$\displaystyle
3\int_{0}^{1}\log\big{(}\frac{15c}{\epsilon^{2}}\big{)}\lambda\operatorname{d\\!}{s}$
$\displaystyle=3\log\big{(}\frac{15c}{\epsilon^{2}}\big{)}\epsilon^{-1}\int_{0}^{1}\frac{2C}{\Delta^{q}\Delta_{m}^{1-q}}\operatorname{d\\!}{s}$
(79)
$\displaystyle\leq\log\big{(}\frac{15c}{\epsilon^{2}}\big{)}\epsilon^{-1}\frac{6C}{\Delta_{m}}.$
(80)

Finally

$\displaystyle 3\int_{0}^{1}\epsilon\lambda^{2}\operatorname{d\\!}{s}$
$\displaystyle=\frac{12C^{2}}{\epsilon\Delta_{m}^{2-2q}}\int_{0}^{1}\frac{1}{\Delta^{2q}}\operatorname{d\\!}{s}$
(81)
$\displaystyle\leq\frac{12C^{2}B_{3}}{\epsilon\Delta_{m}^{2-2q}}\Delta_{m}^{1-2q}=\frac{12C^{2}B_{3}}{\epsilon\Delta_{m}}.$
(82)

Putting everything together yields the query complexity. ∎

######  Corollary 15.1.

If
$\int_{0}^{1}\frac{1}{\Delta^{p}}\operatorname{d\\!}{s}=O(\Delta_{m}^{1-p})$
holds for all $p>1$, $|\Delta^{\prime}|=O(1)$, $\left\lVert
H^{\prime}\right\rVert=O(1)$ and $\left\lVert
H^{\prime\prime}\right\rVert=O(1)$, then algorithm 2 with the Hamiltonian
simulation of 11 and the parameters of 15 for some $1/2<q<1$, produces a state
with fidelity larger than $1-\epsilon$ using a number of queries that scales
as $O\big{(}\Delta_{m}^{-1}\epsilon^{-1}\log(\epsilon^{-1})\big{)}$.

The asymptotic scaling in the error $\epsilon$ is slightly worse here, since
there is an extra logarithmic factor, but this is not an issue if we want to
apply eigenstate filtering. With eigenstate filtering the scaling in the error
is still $O(\log(1/\epsilon))$.

##  Appendix C Gap properties

###  C.1 The gap in the Grover problem

For the Grover problem we have the following gap:

$\Delta(s)=\sqrt{1-4(1-\frac{M}{N})s(1-s)}.$ (83)

We can set $\Delta_{m}=\min_{s\in[0,1]}\Delta(s)=\sqrt{M/N}$. We provide a
proof of lemma 9.

######  Lemma.

For all $p>1$ and $\Delta$ given by (83), we have

$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=O\big{(}\sqrt{N/M}^{p-1}\big{)}=O\big{(}\Delta_{m}^{1-p}\big{)},$
(84)

and, for $p=1$,

$\int_{0}^{1}\frac{1}{\Delta(s)}\operatorname{d\\!}{s}=O\big{(}\log(N/M)\big{)}.$
(85)

###### Proof.

We note that $\Delta(s)$ is symmetric about $s=1/2$. It is also strictly
decreasing on $[0,1/2]$, going from $1$ to a minimum of $\sqrt{M/N}$. So we
can write

$\displaystyle\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}$
$\displaystyle=2\int_{0}^{1/2}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}$
(86)
$\displaystyle=2\Big{(}\int_{0}^{1/2-\sqrt{M/N}}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}+\int_{1/2-\sqrt{M/N}}^{1/2}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}\Big{)}.$
(87)

Since $\Delta$ has a minimum of $\sqrt{M/N}$, we can bound the second integral
by

$\int_{1/2-\sqrt{M/N}}^{1/2}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}\leq\sqrt{\frac{M}{N}}\Big{(}\frac{1}{\min_{s\in[0,1]}\Delta(s)}\Big{)}^{p}=\frac{\sqrt{M/N}}{\sqrt{M/N}^{p}}=\sqrt{N/M}^{p-1}.$

For the first integral, we write

$\displaystyle\int_{0}^{1/2-\sqrt{M/N}}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}$
$\displaystyle=\int_{1}^{\Delta\big{(}1/2-\sqrt{M/N}\big{)}}\frac{1}{\Delta^{p}}\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\operatorname{d\\!}{\Delta}$
(88)
$\displaystyle=\int_{\Delta\big{(}1/2-\sqrt{M/N}\big{)}}^{1}\frac{1}{\Delta^{p}}\Big{(}-\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\Big{)}\operatorname{d\\!}{\Delta}.$
(89)

We can invert (42) to obtain
$s=\frac{1}{2}-\frac{1}{2}\sqrt{1-\frac{1-\Delta^{2}}{1-N/M}}$. Then we have

$-\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}=\frac{\Delta}{2\sqrt{(1-M/N)(\Delta^{2}-M/N)}}.$
(90)

We now calculate

$\Delta\Big{(}\frac{1}{2}-\sqrt{\frac{M}{N}}\Big{)}=\sqrt{\frac{M}{N}}\sqrt{5-4\frac{M}{N}}\geq
2\sqrt{\frac{M}{N}},$

assuming $M/N\leq 1/4$. So

$\displaystyle\int_{0}^{1/2-\sqrt{M/N}}\frac{1}{\Delta^{p}}\operatorname{d\\!}{s}$
$\displaystyle\leq\int_{2\sqrt{\frac{M}{N}}}^{1}\frac{1}{\Delta^{p}}\Big{(}-\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\Big{)}\operatorname{d\\!}{\Delta}$
(91)
$\displaystyle=\int_{2\sqrt{\frac{M}{N}}}^{1}\frac{1}{\Delta^{p}}\frac{\Delta}{2\sqrt{(1-M/N)(\Delta^{2}-M/N)}}\operatorname{d\\!}{\Delta}$
(92)
$\displaystyle\leq\int_{2\sqrt{\frac{M}{N}}}^{1}\frac{1}{\Delta^{p}}\frac{\Delta}{2\sqrt{(1-M/N)(\Delta^{2}-\Delta^{2}/4)}}\operatorname{d\\!}{\Delta}$
(93)
$\displaystyle=\frac{1}{\sqrt{3(1-M/N)}}\int_{2\sqrt{\frac{M}{N}}}^{1}\frac{1}{\Delta^{p}}\operatorname{d\\!}{\Delta}.$
(94)

Now $\frac{1}{\sqrt{3(1-M/N)}}$ is $O(1)$ and
$\int_{2\sqrt{\frac{M}{N}}}^{1}\frac{1}{\Delta^{p}}\operatorname{d\\!}{\Delta}=\Big{[}\frac{1}{(p-1)\Delta^{p-1}}\Big{]}_{2\sqrt{M/N}}^{1}$
is $O\big{(}\sqrt{N/M}^{p-1}\big{)}$, if $p>1$. If $p=1$, then it is
$O\big{(}\log\sqrt{N/M}\big{)}$. ∎

###  C.2 The gap in QLSP

For the quantum linear system problem we have the following bound on the gap:

$\Delta(s)=\sqrt{(1-s)^{2}+\Big{(}\frac{s}{\kappa}\Big{)}^{2}}.$ (95)

If $\kappa$ is large enough, then we can take
$\Delta_{m}\coloneqq\frac{1}{2\kappa}\leq\sqrt{\frac{1}{\kappa^{2}+1}}=\min_{s\in[0,1]}\Delta(s)$.
We provide a proof of lemma 10.

######  Lemma.

For all $p>1$, we have

$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=O\big{(}\kappa^{p-1}\big{)}=O\big{(}\Delta_{m}^{1-p}\big{)},$
(96)

and, for $p=1$,

$\int_{0}^{1}\frac{1}{\Delta(s)}\operatorname{d\\!}{s}=O\big{(}\log(\kappa)\big{)}.$
(97)

###### Proof.

We note that $\Delta(s)$ is strictly decreasing on
$\Big{[}0,1-\frac{1}{\kappa^{2}+1}\Big{]}$, going from $1$ to a minimum of
$\sqrt{\frac{1}{\kappa^{2}+1}}$. So we can write

$\int_{0}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}=\int_{0}^{1-\frac{1}{\kappa^{2}+1}}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}+\int_{1-\frac{1}{\kappa^{2}+1}}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}.$

Since $\Delta$ has a minimum of $\sqrt{\frac{1}{\kappa^{2}+1}}$, we can bound
the second integral by

$\int_{1-\frac{1}{\kappa^{2}+1}}^{1}\frac{1}{\Delta(s)^{p}}\operatorname{d\\!}{s}\leq\frac{1}{\kappa^{2}+1}\Big{(}\frac{1}{\min_{s\in[0,1]}\Delta(s)}\Big{)}^{p}=\frac{1}{\kappa^{2}+1}\big{(}\kappa^{2}+1\big{)}^{p/2}=\big{(}\kappa^{2}+1\big{)}^{p/2-1}.$

For the first integral, we write

$\displaystyle\int_{0}^{1-\frac{1}{\kappa^{2}+1}}\frac{1}{\Delta^{p}}\operatorname{d\\!}{s}$
$\displaystyle=\int_{1}^{\Delta\big{(}1-\frac{1}{\kappa^{2}+1}\big{)}}\frac{1}{\Delta^{p}}\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\operatorname{d\\!}{\Delta}$
(98)
$\displaystyle=\int_{\Delta\big{(}1-\frac{1}{\kappa^{2}+1}\big{)}}^{1}\frac{1}{\Delta^{p}}\Big{(}-\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\Big{)}\operatorname{d\\!}{\Delta}$
(99)
$\displaystyle=\int_{\sqrt{\frac{1}{\kappa^{2}+1}}}^{1}\frac{1}{\Delta^{p}}\Big{(}-\mathinner{\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}}\Big{)}\operatorname{d\\!}{\Delta}.$
(100)

We can invert (95) on $\Big{[}0,1-\frac{1}{\kappa^{2}+1}\Big{]}$ to obtain
$s=\frac{\kappa^{2}}{\kappa^{2}+1}(1-\Delta)$. Then we have

$-\dfrac{\operatorname{d\\!}{}s}{\operatorname{d\\!}{{\Delta}}}=\frac{\kappa^{2}}{\kappa^{2}+1},$
(101)

so

$\displaystyle\int_{0}^{1-\frac{1}{\kappa^{2}+1}}\frac{1}{\Delta^{p}}\operatorname{d\\!}{s}$
$\displaystyle=\int_{\sqrt{\frac{1}{\kappa^{2}+1}}}^{1}\frac{1}{\Delta^{p}}\frac{\kappa^{2}}{\kappa^{2}+1}\operatorname{d\\!}{\Delta}$
(102)
$\displaystyle=\frac{\kappa^{2}}{\kappa^{2}+1}\Big{(}\frac{1}{(p-1)\Delta^{p-1}}\Big{)}\Big{|}^{\Delta=\sqrt{\frac{1}{\kappa^{2}+1}}}_{\Delta=1}$
(103) $\displaystyle=O(\kappa^{p-1}).$ (104)

If $p=1$, then the integral is $O\big{(}\log(\kappa)\big{)}$. ∎