only depends on their difference $\Delta_{t}$. While the values
$a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}$ may vary randomly in the
algorithm, $\Delta_{t}$ is always exactly $0.9^{t}$. Since the total number of
polynomials we sample from is also independent of
$a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}$, to total degree of all
polynomials $\mathbf{D}$ is deterministic. This makes asymptotic claims on
$\mathbf{D}$ well defined.

At the $t$’th iteration of step 2, we sample from a polynomial of degree $\in
O(\Delta_{t}^{-1}0.1^{-1})=O(0.9^{-t})=O(b^{t})$ a total of $m_{t}$ times.
Then, in step 4, we sample from a polynomial of degree $\in
O(\Delta_{t}^{-1}\eta^{-1})\subseteq O(\varepsilon^{-1}\eta^{-1})$ once. So
the total degree is:

$\displaystyle\mathbf{D}\in
O\left(\sum_{t=0}^{T-1}\frac{m_{t}}{0.9^{t}}+\frac{1}{\eta\varepsilon}\right)$
$\displaystyle\leq
O\left(\sum_{t=0}^{T-1}\frac{1}{0.9^{t}}\ln\left(\frac{1}{\delta_{t}}\right)+\frac{1}{\eta\varepsilon}\right)$
(113) $\displaystyle\leq
O\left(\sum_{t=0}^{T-1}\frac{1}{0.9^{t}}\ln\left(\frac{0.9^{t}}{\varepsilon\delta}\right)+\frac{1}{\eta\varepsilon}\right)$
(114) $\displaystyle\leq
O\left(\frac{1}{\varepsilon}\ln\left(\frac{1}{\delta}\right)+\frac{1}{\eta\varepsilon}\right)+O\left(\sum_{t=0}^{T-1}b^{t}\left[\ln\left(\frac{1}{\varepsilon}\right)-t\ln(b)\right]\right)$
(115)

The first term is the desired bound, so all that remains to show is that the
second term is dominated by the first term. Indeed, a somewhat cumbersome
calculation in equations (38-44) of [AR19] demonstrates that the second term
is $\leq O(\varepsilon^{-1})$ (albeit with $T+1$ instead of $T$, which is a
stronger result).

Finally, we prove the fact that makes this construction unique: that
$\left|\mathbb{E}[\mathbf{\hat{a}}]-a\right|\leq\varepsilon\eta+\delta$. To do
so, we interpret the dynamics of the algorithm as a binary decision tree: at
each node we can either proceed to the left child where we increase
$a_{\text{min}}$ or the right child where we decrease $a_{\text{max}}$. At the
$t$’th iteration of step 2 we are at the $t$’th layer of the tree, and we can
think of step 4 as the $T$’th layer containing all the leaves. See Figure 9.

We can label each node in the $t$’th layer of the tree with a bit string
$\vec{x}\in\\{0,1\\}^{t}$, where the bits encode the choices made to get to
that node. We say a node $\vec{x}$ is ‘good’ if the corresponding interval
$[a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}]$ contains $a$, otherwise we say
$\vec{x}$ is ‘bad’. Each node is associated with a random variable
$\mathbf{\hat{a}}_{\vec{x}}$, denoting the output of the algorithm assuming we
were at the $\vec{x}$ node at iteration $t=\text{dim}(\vec{x})$.
Correspondingly, at the root of the tree $\mathbf{\hat{a}}$ equals
$\mathbf{\hat{a}}_{\vec{x}}$ where $\vec{x}$ is the ‘empty’ bit string with
dimension 0.

We establish
$\left|\mathbb{E}[\mathbf{\hat{a}}]-a\right|\leq\varepsilon\eta+\delta$ by
proving the following fact. For all $t\in[0,1,...,T]$ and for all good
$\vec{x}\in\\{0,1\\}^{t}$:

$\displaystyle\left|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]-a\right|\leq\varepsilon\eta+\sum_{k=t}^{T-1}\delta_{k}$
(116)

Then $\left|\mathbb{E}[\mathbf{\hat{a}}]-a\right|\leq\varepsilon\eta+\delta$
follows by plugging in $t=0$ and noting that
$\sum_{k=0}^{T-1}\delta_{k}\leq\delta$ as shown above.

We prove the statement recursively, starting with the leaves and working our
way to the root. For a leaf, $t=T$ so the sum $\sum_{k=T}^{T-1}\delta_{k}$
vanishes. We have:

$\displaystyle\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]$
$\displaystyle=|P^{(T)}_{\eta}(a)|^{2}\cdot
a_{\text{max}}-(1-|P^{(T)}_{\eta}(a)|^{2})\cdot a_{\text{min}}$ (117)
$\displaystyle=|P^{(T)}_{\eta}(a)|^{2}\cdot\Delta_{T}+a_{\text{min}}$ (118)

By Lemma 22, we have
$||P^{(T)}_{\eta}(a)|^{2}-(a-a^{(T)}_{\text{min}})/\Delta_{T}|\leq\eta$. So:

$\displaystyle\eta\Delta_{T}$
$\displaystyle\geq\left||P^{(T)}_{\eta}(a)|^{2}-(a-a^{(T)}_{\text{min}})/\Delta_{T}\right|\cdot\Delta_{T}$
(119)
$\displaystyle=\left|\left(|P_{\eta}(a)|^{2}\cdot\Delta_{T}+a^{(T)}_{\text{min}}\right)-a\right|=\left|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]-a\right|$
(120)

At step 4 we have $\Delta_{T}\leq\varepsilon$, so we have established
$\left|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]-a\right|\leq\varepsilon\eta$ as
desired.

Now we recursively show the statement for $t$ and all good
$\vec{x}\in\\{0,1\\}^{t}$, assuming it holds for all good $\vec{x}y$ at $t+1$,
with $y\in\\{0,1\\}$. There are two cases: either $\vec{x}y$ is good for both
$y\in\\{0,1\\}$, or it is only good for one of them. It cannot be bad for both
$y$, because then $a$ would need to be both $\leq
a^{(t)}_{\text{min}}+0.1\Delta_{t}$ and $\geq
a^{(t)}_{\text{min}}+0.9\Delta_{t}$.

If $\vec{x}y$ is good for both $y$ (like $\vec{x}=01$ in Figure 9), then by
assumption
$|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}y}]-a|\leq\varepsilon\eta+\sum_{k=t+1}^{T}\delta_{k}$.
For some probability $p$ we have:

$\displaystyle\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]$
$\displaystyle=p\cdot\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}0}]+(1-p)\cdot\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}1}]$
(121) $\displaystyle|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]-a|$
$\displaystyle\leq
p\cdot|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}0}]-a|+(1-p)\cdot|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}1}]-a|$
(122)
$\displaystyle\leq\varepsilon\eta+\sum_{k=t+1}^{T}\delta_{k}\leq\varepsilon\eta+\sum_{k=t}^{T}\delta_{k}$
(123)

Now assume without loss of generality that $\vec{x}0$ is bad, and $\vec{x}1$
is good (like $\vec{x}=0$ in Figure 9). Now the assumption says nothing about
$|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}0}]-a|$, but we at least know that
$|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}0}]-a|\leq 1$. Furthermore, we know that
the probability $p$ with which we proceed down the $\vec{x}0$ path is at most
$\delta_{t}$. So:

$\displaystyle|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}}]-a|$
$\displaystyle\leq\delta_{t}\cdot|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}0}]-a|+|\mathbb{E}[\mathbf{\hat{a}}_{\vec{x}1}]-a|$
(124)
$\displaystyle\leq\varepsilon\eta+\delta_{t}+\sum_{k=t+1}^{T}\delta_{k}=\varepsilon\eta+\sum_{k=t}^{T}\delta_{k}.$
(125)

∎

Figure 9:  Sketch of the intervals considered in the proof of Theorem 23,
labeled by the string $\vec{x}\in\\{0,1\\}^{t}$. At each iteration, we cut off
either the right or left side of the interval which corresponds to adding
either a $0$ or $1$ to $\vec{x}$. ‘Bad’ intervals not containing the true
amplitude $a=0.4$ are marked with dashed lines, and their children are not
shown. The algorithm describes shrinking the interval by a factor of 0.9 with
every step, but for visual clarity we use a factor of 0.55 here.

##  5 Hybrid Classical-Quantum Estimation

In the future, we may have access to quantum computers that are capable of
running Grover’s algorithm but are still limited in the overall circuit depth.
Amplitude estimation algorithms may become useful earlier if they can still
accelerate estimation to accuracy $\varepsilon$ without requiring depth
$O(1/\varepsilon)$. This can be achieved by mixing classical and quantum
resources.

In particular, [GKLPZ20] consider the following version of this problem: for
any $0\leq\beta<1$ they show that there exists an amplitude estimation
algorithm that runs in time $O(1/\varepsilon^{1+\beta})$, but requires a
maximum depth of only $O(1/\varepsilon^{1-\beta})$. When $\beta=0$ this
reproduces the ‘fully quantum’ performance of other algorithms, and when
$\beta\to 1$ this algorithm has the same asymptotic complexity as classical
probability estimation.

We consider the construction of such hybrid algorithms a fascinating
theoretical problem. [GKLPZ20] give two methods for achieving this: a ‘Power
law’ algorithm relying on maximum likelihood estimation, and a ‘QoPrime’
algorithm relying on the Chinese remainder theorem. In this section we give
another method for solving this problem based on quantum signal processing.
Depending on the reader’s background this new method may be more intuitive.

However, we remark that we consider it questionable if any of these methods
are actually useful in practice. In particular, constructing the algorithms to
achieve the nice theoretical scaling of $O(1/\varepsilon^{1\pm\beta})$
undercuts the simplicity of the underlying situation. A depth-limited quantum
computer will be able to run some fixed number of Grover rotations $r$. A
practical version of hybrid estimation would take as input such an $r$, and
use that to extract as much information about $a$ as possible. In the context
of quantum signal processing, this $r$ corresponds to some fixed ‘degree
budget’. We could then use machine learning to find whatever polynomial of
degree $\leq r$ gives the most information about $a$. That is not to say that
[GKLPZ20] does not consider practicality: they perform a noise analysis, and
even implement their algorithm in hardware [Guirgica-Tiron&21] albeit with a
trivial oracle. We merely invite the possibility of simpler algorithms with
less elegant theoretical properties.

There is a reason to be skeptical of the $\beta\to 1$ limit in particular: we
expect early quantum computers to have significantly slower clock speeds than
classical computers. Thus, classical oracle evaluation is likely much faster
than quantum oracle evaluation. So if one is going to put in all the effort of
running the oracle on the quantum computer, one might as well do so as many
times as possible. A perhaps more reasonable notation of hybrid quantum-
classical is discussed by [Rosmanis22]: we have two different types of
queries, quantum and classical, each with different cost. Unfortunately,
[Rosmanis22] shows that there is no speedup for Grover’s search in this
setting. Is the same true for estimation?

Despite these observations, we consider the task of varying the complexity
with $\beta$ an excellent opportunity to display the power of the polynomial
sampling framework. We now discuss the new algorithm for achieving depth
$\mathbf{d}\in O(1/\varepsilon^{1-\beta})$ and overall complexity
$\mathbf{D}\in O(1/\varepsilon^{1+\beta})$ based on quantum signal processing.
The final result is presented in Theorem 31. While the polynomial
constructions require cumbersome error analysis as usual, the core idea is
quite simple. In light of the above discussion, we do not attempt a constant-
factor performance analysis on this algorithm.

We take the same approach as in Theorem 23: we maintain an interval
$[a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}]$ containing $a$ with high
probability, and shrink the interval with every iteration depending on what
side of the interval $a$ is on. Letting
$\Delta_{t}:=a^{(t)}_{\text{max}}-a^{(t)}_{\text{min}}$, we test this by
finding a polynomial $P(a)$ that is $\leq\frac{1}{2}-\gamma$ when $a$ is $\leq
a^{(t)}_{\text{min}}+0.1\Delta_{t}$, and is $\geq\frac{1}{2}+\gamma$ when $a$
is $\geq a^{(t)}_{\text{max}}-0.1\Delta_{t}$. This can be achieved by making
$P(a)$ approximate a line with slope $\propto\gamma/\Delta_{t}$, and the
degree is largely determined by the slope. Then, $\propto 1/\gamma^{2}$
samples from the polynomial suffice to distinguish the two cases.

In the previous section we selected $\gamma$ to be constant, so the degree is
$\propto 1/\Delta_{t}$. This makes the depth and the total number of queries
$\propto 1/\Delta_{t}$. To achieve hybrid estimation, we simply select
$\gamma\propto\Delta_{t}^{\beta}$. Then the depth is
$\propto\Delta_{t}^{\beta}/\Delta_{t}=1/\Delta_{t}^{1-\beta}$. But, since we
need to take $\propto 1/\gamma^{2}\propto 1/\Delta_{t}^{2\beta}$ samples from
the polynomial, the total complexity is $1/\Delta_{t}^{1+\beta}$. The runtime
is dominated by the final iterations where $\Delta_{t}\propto\varepsilon$, so
the final depth is $\propto 1/\varepsilon^{1-\beta}$ and the final complexity
is $\propto 1/\varepsilon^{1+\beta}$ as desired.

Letting $a^{(t)}_{\text{mid}}:=a^{(t)}_{\text{min}}+0.5\Delta_{t}$, we require
a polynomial that approximates a line passing through
$(a^{(t)}_{\text{mid}},1/2)$ with whatever slope we want. Once such a
polynomial has been constructed the remainder of the analysis is extremely
simple as shown above. However, such a polynomial is unfortunately not so easy
to build because of two complications:

  * •

Jackson’s theorem (Theorem 21) is not precise enough. The line that we desire
to approximate only creates a gap $\gamma\propto\Delta^{\beta}\in o(1)$. The
approximation error better be be smaller than $\gamma$, but Jackson’s theorem
requires an additional factor of $1/\gamma$ in the degree to achieve this.
This is too slow, so we need a more accurate polynomial approximation of a
line. Fortunately, [LC17] constructed an extremely accurate approximation of
$\text{erf}(kx)\approx kx$ via the Jacobi-Anger expansion.

  * •

Semi-Pellian polynomials have fixed parity, so even though $\text{erf}(kx)$ is
odd, the shifted version $\text{erf}(k(a-a_{\text{mid}}))$ has mixed parity.
We can fix this by instead approximating the even function
$\text{erf}(k(a-a_{\text{mid}}))+\text{erf}(-k(a+a_{\text{mid}}))+1$, which is
very similar to $\text{erf}(k(a-a_{\text{mid}}))$ for $a\geq 0$. But this only
works when $a_{\text{mid}}$ is not too close to the origin - otherwise the two
erf functions interfere. This forces us to adopt special behavior for small
$a_{\text{mid}}$, causing $O(a^{-1})$ terms in the final runtime. [GKLPZ20]
treat $a$ and $\beta$ as constants in their analysis, so if we are allowed to
do the same then we still reproduce their complexities.

######  Remark 24.

As pointed out by [MML22], it is sometimes possible to construct oracles for a
shifted amplitude $\frac{a+1}{2}$. For some state $\ket{0}$ say we have a
unitary $U$ satisfying $U\ket{0}=\ket{\Psi}$ and another unitary $V$ such that
$\Pi=V\ket{0}\bra{0}V^{\dagger}$. Then redefine:

$\displaystyle\ket{\bar{\Psi}}:=(I\oplus V^{\dagger}U)\ket{+}\ket{0}$ (126)
$\displaystyle\bar{\Pi}:=\ket{+}\bra{+}\otimes\ket{0}\bra{0}$ (127)

Observe that $|\bra{0}V^{\dagger}U\ket{0}|=|\Pi\ket{\Psi}|=a$, but suppose
furthermore that $\bra{0}V^{\dagger}U\ket{0}=a$. Then, we see that:

$\displaystyle|\bar{\Pi}\ket{\bar{\Psi}}|$
$\displaystyle=\left|\bra{0}\cdot(\bra{+}\otimes I)(I\oplus
V^{\dagger}U)(\ket{+}\otimes I)\cdot\ket{0}\right|$ (128)
$\displaystyle=\left|\bra{0}\cdot\frac{I+V^{\dagger}U}{2}\cdot\ket{0}\right|=\frac{1+a}{2}$
(129)

If we use this oracle in our algorithm instead, then we have $a\geq 1/2$ so
all the $O(a^{-1})$ terms in Theorem 31 become constant.

We begin by discussing the approximation of $\text{erf}(kx)$.

######  Lemma 25.

([LC17] Corollary 4). For all $k,\eta>0$ there exists an odd polynomial
$P_{\text{erf},k,\eta}$ such that for all $x\in[-2,2]$:

$\displaystyle\left|P_{\text{erf},k,\eta}(x)-\text{erf}(kx)\right|\leq\eta.$
(130)

Furthermore $\text{deg}(P_{\text{erf},k,\eta})\in
O(\sqrt{(k^{2}+\log(1/\eta))\log(1/\eta)})$.

The construction in [LC17] actually obtains an approximation for $x\in[-1,1]$,
but this is easily expanded to $x\in[-2,2]$ by dividing the input by two and
then doubling $k$.

Now we leverage that $\text{erf}(kx)$ can be used to approximate the line
$kx$, and is close to $-1$ or $1$ when far from the origin. These properties
are listed in the two facts below and also plotted in Figure 10. Note that the
kind of approximation $\text{erf}(kx)\approx kx$ we achieve here is sufficient
for interval reduction, but not sufficient for the sampling performed for the
unbiased estimation algorithm from the previous section. If this had been the
case, we could have exponentially improved the accuracy of the unbiased
estimation algorithm.

######  Fact 26.

For $x\in[-1,0]$ we have $\text{erf}(x)\leq 0.8x$. For $x\in[0,1]$ we have
$0.8x\leq\text{erf}(x)$.

######  Fact 27.

For any $\tau>0$, let $\kappa(\tau):=\frac{1}{2}\sqrt{2\ln(2/(\pi\tau^{2}))}$.
Then:

$\displaystyle x\leq-\kappa\hskip 14.22636pt$ $\displaystyle\to\hskip
14.22636pt-1\leq\text{erf}(x)\leq-(1-\tau)$ (131) $\displaystyle\kappa\leq
x\hskip 14.22636pt$ $\displaystyle\to\hskip
14.22636pt1-\tau\leq\text{erf}(x)\leq 1$ (132)

Figure 10:  Sketch of the properties of $\text{erf}(x)$ stated in Facts 26 and
27. Here we selected $\tau=0.1$, making $\kappa(\tau)\approx 1.44$. Fact 26
asserts that $\text{erf}(x)$ is either strictly above or below the dashed line
$0.8x$ depending on the sign. Fact 27 asserts that $\text{erf}(x)$ is within
$\tau$ of $\pm 1$ when $x$ is $\kappa$-far from the origin. These bounds
correspond to the gray regions.

Now we discuss the trick we explained earlier that lets us approximate the
mixed-parity function $\text{erf}(k(a-a_{\text{mid}}))$ with an even function
on the interval $a\in[0,1]$. Think of
$f(a)\approx\text{erf}(k(a-a_{\text{mid}}))+1$, so that $f(a)$ jumps from 0 to
1 on the interval $[a_{\text{min}},a_{\text{max}}]$. Then
$f_{e}(a):=f(a)+f(-a)$ approximates $f(a)$. We track the quality of the
approximation via the parameter $\lambda$.

######  Fact 28.

Say there is a function that satisfies $f(a)\leq\lambda$ for $a\in[-1,0]$,
$f(a)\leq 1-\lambda$ for $a\in[0,1]$, and $0\leq f(a)$ for all $a\in[-1,1]$.
Then $f_{e}(a):=f(a)+f(-a)$ is an even function satisfying $0\leq f_{e}(a)\leq
1$ for $a\in[-1,1]$. Furthermore, when $a\in[0,1]$:

$\displaystyle f(a)\leq f_{e}(a)\leq f(a)+\lambda.$ (133)

We have all the tools in place to construct the family of polynomials for
hybrid estimation. A sketch of the construction is shown in Figure 11, which
displays the critical property proven by the following lemma: that $P(a)$ is
bounded away from $1/2$ for values close to $a_{\text{min}}$ and
$a_{\text{max}}$. That bound will later become $\gamma$ from the previous
discussion. The criterion $a_{\text{mid}}\geq\kappa/k$ allows us to determine
when $a_{\text{mid}}$ is too close to the origin for the construction to work.

(a) $[a_{\text{min}},a_{\text{max}}]=[0.3,0.6]$

(b) $[a_{\text{min}},a_{\text{max}}]=[0.05,0.2]$

Figure 11:  Sketch of the construction of
$P_{\text{hybrid},\tau,\eta,k,a_{\text{mid}}}(a)$ or $P(a)$ for short from
Lemma 29. Here we selected $\tau=\eta=0.025$, $k=4$, which make $\kappa\approx
1.87$, $\kappa/k\approx 0.47$ and $\text{deg}(P_{\text{erf},k,\eta})=21$. In
(a) we have $a_{\text{mid}}\geq\kappa/k$, so we see that $P(a)$ is contained
in the gray regions asserted in
$(\ref{eqn:hybridbound1},\ref{eqn:hybridbound2})$. The region at most
$\lambda$ above $f(a)$ is highlighted in dark gray. But in (b) where
$a_{\text{mid}}<\kappa/k$, we see that $f(-a)$ is large on the interval
$[a_{\text{min}},a_{\text{max}}]$ causing the shape of $P(a)$ to be distorted
and no longer be contained in the gray regions.  Figure 12:  Line defined by
the points in (136) used to transform $P_{\text{erf},k,\eta}$ to $f_{0}$ in
the construction of $P_{\text{hybrid},\tau,\eta,k,a_{\text{mid}}}(a)$ from
Lemma 29.

######  Lemma 29.

Consider any $\tau,\eta\in(0,1)$, and let $\kappa=\kappa(\tau)$ be as in Fact
27. Consider any $a_{\text{min}},a_{\text{max}}$ that satisfy
$0<a_{\text{min}}<a_{\text{max}}<1$. Furthermore, let
$\Delta:=a_{\text{max}}-a_{\text{min}}$ and consider any $k$ satisfying $1\leq
k\leq 2/\Delta$. Finally, let
$a_{\text{mid}}:=\frac{1}{2}(a_{\text{min}}+a_{\text{max}})$ and suppose that
$a_{\text{mid}}\geq\kappa/k$.

Then there exists an even semi-Pellian polynomial
$P_{\text{hybrid},\tau,\eta,k,a_{\text{mid}}}(a)$ or $P(a)$ for short, that
satisfies:

$\displaystyle a_{\text{min}}\leq a\leq a_{\text{mid}}\hskip 14.22636pt$
$\displaystyle\to\hskip
14.22636ptP(a)\leq\frac{1}{2}+0.11k(a-a_{\text{mid}})+\eta+0.25\tau$ (134)
$\displaystyle a_{\text{mid}}\leq a\leq a_{\text{max}}\hskip 14.22636pt$
$\displaystyle\to\hskip
14.22636ptP(a)\geq\frac{1}{2}+0.11k(a-a_{\text{mid}})-\eta-0.25\tau.$ (135)

This polynomial has the same degree as $P_{\text{erf},k,\eta}(x)$ from Lemma
25.

###### Proof.

We will obtain $P(x)$ by taking $P_{\text{erf},k,\eta}(x)$ and performing a
series of degree-preserving transformations. Our first goal is to take
$P_{\text{erf},k,\eta}(x)$, which is between $\pm(1+\eta)$, and
$\leq-(1-\eta-\tau)$ for small $x$, and transform it to an $f_{0}(x)$ which is
in $[0,1-\lambda]$, and $\leq\lambda$ for small $x$ as required by Fact 28.
Let $\lambda$ be chosen such that the following points are colinear:

$\displaystyle\vec{p}_{1}:=(-(1+\eta),0);\hskip
14.22636pt\vec{p}_{2}:=(-(1-\eta-\tau),\lambda);\hskip
14.22636pt\vec{p}_{2}:=(1+\eta,1-\lambda)$ (136)

We find this is solved by:

$\displaystyle\lambda:=\frac{2\eta+\tau}{4\eta+\tau+2}$ (137)

Furthermore, we find the line $y=(1+x+\eta)/(4\eta+\tau+2)$ contains these
points. Accordingly, let:

$\displaystyle f_{0}(x):=\frac{1+P_{\text{erf},k,\eta}(x)+\eta}{4\eta+\tau+2}$
(138)

We want to plug a shifted $f_{0}$ into Fact 28, so we will first prove that
$f_{0}$ meets some requirements for all $x\in[-2,2]$. First, Lemma 25 implies
that $P_{\text{erf},k,\eta}(x)\geq-(1+\eta)$, so since we pass through
$\vec{p}_{1}$ we have $f_{0}(x)\geq 0$. Second, $P_{\text{erf},k,\eta}(x)\leq
1+\eta$, so since we pass through $\vec{p}_{3}$ we also have $f_{0}(x)\leq
1-\lambda$. Third, Fact 27 implies that for $kx\leq-\kappa$ we have
$\text{erf}(kx)\leq-(1-\tau)$, so
$P_{\text{erf},k,\eta}(x)\leq-(1-\eta-\tau)$, so since we pass through
$\vec{p}_{2}$ we have $f_{0}\leq\lambda$.

Now we are ready to use Fact 28. Let $f(a):=f_{0}(a-a_{\text{mid}})$ with
$x=a-a_{\text{mid}}$. We know that $a\in[0,1]$, but the polynomial
construction must work for any $a\in[-1,1]$. Since $a_{\text{mid}}\in[0,1]$ it
is ensured that $x\in[-2,1]\subset[-2,2]$ so the approximation holds. Since
the function was shifted to the right, we have $f(a)\geq 0$ for $a\in[-1,1]$,
and we have $f(a)\leq 1-\lambda$ for $a\in[0,1]$. Since we assumed
$a_{\text{mid}}\geq\kappa/k$, we know that for $a\in[-1,0]$ we have
$kx=k(a-a_{\text{mid}})\leq ka_{\text{mid}}\leq-\kappa$, which implies
$f(a)\leq\lambda$. We meet the requirements of Fact 28, so let
$P_{\text{hybrid},\tau,\eta,k,a_{\text{mid}}}(a):=f(a)+f(-a)$.

$P_{\text{hybrid},\tau,\eta,k,a_{\text{mid}}}(a)$, or $P(a)$ for short, is an
even function by construction. Since it is a linear combination of polynomials
it is itself a polynomial, and polynomials that are even functions are even
polynomials. From Fact 28, we know that $0\leq P(a)\leq 1$, so $P(a)$ is semi-
Pellian. The transformations from $P_{\text{erf},k,\eta}$ to $P(a)$ were all
linear, so the degree is unchanged.

It remains to show the desired bounds on $P(a)$. These stem from Fact 26. For
$kx\in[-1,0]$ we have $\text{erf}(kx)\leq 0.8kx$, so
$P_{\text{erf},k,\eta}(x)\leq 0.8kx+\eta$, so:

$\displaystyle f_{0}(x)$
$\displaystyle\leq\frac{1+(0.8kx+\eta)+\eta}{4\eta+\tau+2}$ (139)
$\displaystyle=\frac{1}{2}+\left[\frac{1+(0.8kx+\eta)+\eta}{4\eta+\tau+2}-\frac{1}{2}\right]$
(140)
$\displaystyle=\frac{1}{2}+\frac{2(1+0.8kx+2\eta)-(4\eta+\tau+2)}{2(4\eta+\tau+2)}$
(141) $\displaystyle\leq\frac{1}{2}+\frac{\tau}{2(4\cdot 0+0+2)}-\frac{2\cdot
0.8(-x)}{2(4\cdot 1+1+2)}$ (142)
$\displaystyle\leq\frac{1}{2}+0.11kx-0.25\tau$ (143) $\displaystyle
f_{0}(x)+\lambda$ $\displaystyle\leq\frac{1}{2}+0.11kx+\eta+0.25\tau$ (144)

where we plugged in $0\leq\eta,\tau\leq 1$ to obtain a very loose but workable
bound, and observed $\lambda\leq\eta+\tau/2$. Similarly, for $kx\in[0,1]$ we
have $\text{erf}(kx)\geq 0.8kx-\eta$, so we derive:

$\displaystyle f_{0}(x)$
$\displaystyle\geq\frac{1+(0.8kx-\eta)+\eta}{4\eta+\tau+2}$ (145)
$\displaystyle=\frac{1}{2}+\frac{2(1+0.8kx)-(4\eta+\tau+2)}{2(4\eta+\tau+2)}$
(146) $\displaystyle\geq\frac{1}{2}+\frac{2\cdot 0.8kx}{2(4\cdot
1+1+2)}-\frac{4\eta+\tau}{2(4\cdot 0+0+2)}$ (147)
$\displaystyle\geq\frac{1}{2}+0.11kx-\eta-0.25\tau$ (148)

The transformation $x=a-a_{\text{mid}}$ makes the intervals $kx\in[-1,0]$ and
$kx\in[0,1]$ correspond to $a\in[a_{\text{mid}}-1/k,a_{\text{mid}}]$ and
$a\in[a_{\text{mid}},a_{\text{mid}}+1/k]$ respectively. Since we assumed
$k\leq 2/\Delta$, the intervals $[a_{\text{min}},a_{\text{mid}}]$ and
$[a_{\text{mid}},a_{\text{max}}]$ are subintervals. From Fact 28, we thus
derive the desired bounds via $f_{0}(x)\leq P(a)\leq f_{0}(x)+\lambda$. ∎

We have yet to take into account the Born rule: when we sample from $P(a)$, we
actually toss a coin that comes up heads with probability $|P(a)|^{2}$.
Fortunately, as the following lemma shows, it suffices to bound $x$ away from
$1/2$ even when tossing a coin with bias $x^{2}$ in order to decide if $x$ is
big or small.

######  Lemma 30.

Say there is a coin that comes up heads with probability $x^{2}$, and for any
$\gamma,\delta>0$ let $A_{t,\gamma,\delta}(x)$ be the probability that more
than $\frac{1}{4}+\gamma^{2}$ of
$\lceil\frac{1}{2}\gamma^{-2}\ln(\delta^{-1})\rceil$ tosses come up heads.
Then:

$\displaystyle\text{if }x\geq\frac{1}{2}+\gamma\text{ then
}A_{\gamma,\delta}(x)$ $\displaystyle\geq 1-\delta,$ (149)
$\displaystyle\text{if }x\leq\frac{1}{2}-\gamma\text{ then
}A_{\gamma,\delta}(x)$ $\displaystyle\leq\delta.$ (150)

###### Proof.

We can derive $x\geq\frac{1}{2}+\gamma$ implies
$x^{2}\geq\frac{1}{4}+\gamma^{2}+\gamma$, and $x\leq t-\gamma$ implies
$x^{2}\leq\frac{1}{4}+\gamma^{2}-\gamma$. The claims on $A_{t,\gamma,\delta}$
follow from two applications of the Chernoff-Hoeffding theorem. Let
$\mathbf{S}$ be the random variable denoting the number of heads, and let $m$
be the number of tosses. Then, if $x^{2}\geq\frac{1}{4}+\gamma^{2}+\gamma$:

$\displaystyle\text{Pr}\left[\mathbf{S}\geq
m\left(\frac{1}{4}+\gamma^{2}\right)\right]\leq\text{Pr}[\mathbf{S}\geq\mathbb{E}(\mathbf{S})+\gamma
m]\leq e^{-2\gamma^{2}m}$ (151)

Demanding $e^{-2\gamma^{2}m}\leq\delta$ and solving for $m$ completes the
proof. A similar argument follows for the bound when
$x^{2}\leq\frac{1}{4}+\gamma^{2}-\gamma$. ∎

Having constructed the polynomial and shown how to use it to distinguish
$a\leq a^{(t)}_{\text{min}}+0.1\Delta_{t}$ and $a\geq
a^{(t)}_{\text{max}}-0.1\Delta_{t}$, all that remains to show is how to deal
with the restriction that we must have $a^{(t)}_{\text{mid}}\geq\kappa/k$ for
the polynomial construction to work properly. Recall that we would ideally
like to pick the slope $k\propto 1/\Delta^{1-\beta}_{t}$. Since $\kappa$ is
roughly constant, this essentially translates the condition
$a^{(t)}_{\text{mid}}\geq\kappa/k$ to
$a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$. If this is not the
case, then we must go ‘full quantum’ ($\beta=0$) and set the slope to be
$k\propto 1/\Delta_{t}$ instead. Then the condition is
$a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}$ which is always true.

We find that the consequences of this behavior are to knock out an extra
$O(a^{-1})$ term in the total query complexity and an extra
$O(a^{-1/(1-\beta)})$ term in the depth. Intuitively, these arise as follows.
At iteration $t$ we have $a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}]$,
so, implying that $a_{\text{mid}}$ is lower bounded by $a-\Delta_{t}/2\geq
a-\Delta_{t}^{1-\beta}/2$. At a certain time $t^{*}$, $\Delta_{t}$ becomes
small enough $(\Delta_{t}^{1-\beta}\leq a)$ so that the bound
$a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$ is assured. So, the
algorithm divides into two phases. In the first phase $(t\leq t^{*})$ we have
$\Delta_{t}^{1-\beta}\geq a$ and the algorithm is essentially fully quantum.
The complexity and depth are then given by $O(a^{-1})$ and
$O(a^{-1/(1-\beta)})$ respectively. In the second phase $(t>t^{*})$ we are
guaranteed to have $a^{(t)}_{\text{mid}}\geq\kappa/k$, so the algorithm has
the desired complexity and depth of $O(1/\varepsilon^{1+\beta})$ and
$O(1/\varepsilon^{1-\beta})$ respectively.

Recall that $\mathbf{d}$ is the maximum degree of any particular polynomial,
and that $\mathbf{D}$ is the sum of the degrees of all the polynomials. These
correspond to query depth and query complexity respectively.

Figure 13:  Sketch of an argument for bounding
$\mathbf{d}:=\max_{t}d^{(t)}_{\text{max}}$ in Theorem 31 in the case when
$T>t^{*}$. When $t\leq t^{*}$ then there is a chance that
$a^{(t)}_{\text{mid}}<\frac{1}{2}\Delta_{t}^{1-\beta}$ so we cannot rule out
the more expensive scaling of $d^{(t)}_{\text{max}}\in O(\Delta^{-1}_{t})$.
But after $t>t*$, we have the cheaper scaling of
$\tilde{O}(\Delta^{-(1-\beta)}_{t})$. So the maximum must occur at either
$t=t^{*}$ or $t=T$.

######  Theorem 31.

Hybrid quantum-classical estimation via polynomial sampling. For any
$\varepsilon,\delta>0$ and $0\leq\beta<1$, there exists an amplitude
estimation algorithm satisfying:

$\displaystyle\exists
f(\varepsilon,a,\delta)\in\tilde{O}((a^{-1}+\varepsilon^{-(1+\beta)})\log(\delta^{-1}))\text{
such that }\Pr[\mathbf{D}\geq f(\varepsilon,a,\delta)]\leq\delta$ (153)
$\displaystyle\exists
g(\varepsilon,a)\in\tilde{O}(a^{-1/(1-\beta)}+\varepsilon^{-(1-\beta)})\text{
such that }\Pr[\mathbf{d}\geq g(\varepsilon,a)]\leq\delta$ (154)

Here, $\tilde{O}$ hides log factors in $\varepsilon$.

###### Proof.

The algorithm proceeds as follows:

  1. 1.

Initialize $a^{(0)}_{\text{min}}\leftarrow 0$ and
$a^{(0)}_{\text{max}}\leftarrow 1$. Let
$\Delta_{t}:=a^{(t)}_{\text{max}}-a^{(t)}_{\text{min}}$ and
$a^{(t)}_{\text{mid}}=a^{(t)}_{\text{min}}+0.5\Delta_{t}$ throughout.

  2. 2.

Let $T:=\lceil\log_{0.9}(\varepsilon)\rceil$. For $t=0,1,2,...,T-1$, do:

    1. (a)

If $a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$, set:

$\displaystyle\eta_{t},\tau_{t}$ $\displaystyle:=0.01\cdot\Delta_{t}^{\beta},$
(155) $\displaystyle k_{t}$
$\displaystyle:=\frac{\kappa(\tau_{t})}{2}\frac{1}{\Delta_{t}^{1-\beta}},$
(156) $\displaystyle\gamma_{t}$ $\displaystyle:=0.01\cdot\Delta_{t}^{\beta}$
(157)

Otherwise, set:

$\displaystyle\eta_{t},\tau_{t}$ $\displaystyle:=0.01,$ (158) $\displaystyle
k_{t}$ $\displaystyle:=\frac{\kappa(\tau_{t})}{2}\frac{1}{\Delta_{t}},$ (159)
$\displaystyle\gamma_{t}$ $\displaystyle:=0.01$ (160)

    2. (b)

Obtain $P_{t}(a)$ from Lemma 29. Set $\delta_{t}:=\delta/T$ and
$m_{t}:=\lceil\frac{1}{2}\gamma_{t}^{-2}\ln(\delta_{t}^{-1})\rceil$ and sample
from $\mathbf{b}_{P_{t}}$ a total of $m_{t}$ times and let $\mathbf{S}^{(t)}$
be the total.

    3. (c)

If $\mathbf{S}^{(t)}>m_{t}\left(\frac{1}{4}+\gamma_{t}^{2}\right)$, then set:

$\displaystyle[a^{(t+1)}_{\text{min}},\hskip
2.84526pta^{(t+1)}_{\text{max}}]\leftarrow[a^{(t)}_{\text{min}}+0.1\Delta_{t},\hskip
2.84526pta^{(t)}_{\text{max}}]$ (161)

Otherwise, set:

$\displaystyle[a^{(t+1)}_{\text{min}},\hskip
2.84526pta^{(t+1)}_{\text{max}}]\leftarrow[a^{(t)}_{\text{min}},\hskip
2.84526pta^{(t)}_{\text{max}}-0.1\Delta_{t}]$ (162)

  3. 3.

Let $\mathbf{\hat{a}}\leftarrow a^{(T)}_{\text{mid}}$ (or anything else in the
interval $[a^{(T)}_{\text{min}},a^{(T)}_{\text{max}}]$).

We begin by proving correctness. At the beginning we have $\Delta_{0}=1$, and
each of the sub-steps of step 2 sets $\Delta_{t+1}=0.9\Delta_{t}$, so
$\Delta_{t}=0.9^{t}$. At the end we have $\Delta_{T}=0.9^{T}\leq\varepsilon$,
so, provided $a\in[a^{(T)}_{\text{min}},a^{(T)}_{\text{max}}]$, anything
inside the interval $[a^{(T)}_{\text{min}},a^{(T)}_{\text{max}}]$ is within
$\varepsilon$ of $a$. So the algorithm returns correctly if at all iterations
of step 2 we have $a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}]$.

We will show that the probability step 2c) adjusts the interval in a way to
make $a\not\in[a^{(t+1)}_{\text{min}},a^{(t+1)}_{\text{max}}]$ is at most
$\delta_{t}$. Then, by the union bound, the probability any of the steps fail
is $\delta$.

There are two ways we could fail to have
$a\not\in[a^{(t+1)}_{\text{min}},a^{(t+1)}_{\text{max}}]$ after step 2c):
either we have $a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{min}}+0.1\Delta_{t}]$
and $\mathbf{S}^{(t)}>m_{t}(\frac{1}{4}+\gamma_{t}^{2})$, or we have
$a\in[a^{(t)}_{\text{max}}-0.1\Delta_{t},a^{(t)}_{\text{max}}]$ and
$\mathbf{S}^{(t)}<m_{t}(\frac{1}{4}+\gamma_{t}^{2})$. To show that these are
both unlikely, we invoke Lemma 30. Say
$a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{min}}+0.1\Delta_{t}]$ implies
$P_{t}(a)\leq\frac{1}{2}-\gamma_{t}$, and
$a\in[a^{(t)}_{\text{max}}-0.1\Delta_{t},a^{(t)}_{\text{max}}]$ implies
$P_{t}(a)\geq\frac{1}{2}+\gamma_{t}$. Then Lemma 30 asserts that any of the
events causing $a\not\in[a^{(t+1)}_{\text{min}},a^{(t+1)}_{\text{max}}]$
happen with probability at most $\delta_{t}$.

So all that remains is to show the bounds on $P_{t}(a)$ in terms of
$\gamma_{t}$. We can show this using Lemma 29, provided we meet its
requirements. The requirement that $1\leq k_{t}\leq 2/\Delta_{t}$ is always
satisfied. But the requirement that
$a^{(t)}_{\text{mid}}\geq\kappa(\tau_{t})/k_{t}$, demanded that in step 2a) we
select the parameters conditionally.

We begin with the case where
$a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$. Here, we see that
we selected $k_{t}:=\frac{1}{\Delta_{t}^{1-\beta}}\frac{\kappa(\tau_{t})}{2}$,
implying $\kappa(\tau_{t})/k_{t}=\frac{1}{2}\Delta_{t}^{1-\beta}$. So we have
$a^{(t)}_{\text{mid}}\geq\kappa(\tau_{t})/k_{t}$ as desired. Also observe that
$\tau_{t}<1/4$, so $\kappa(\tau_{t})>1$, so
$k_{t}\geq\frac{1}{2}\frac{1}{\Delta_{t}^{1-\beta}}$. Then, Lemma 29
demonstrates:

$\displaystyle
a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{min}}+0.1\Delta_{t}]\hskip
14.22636pt\to\hskip 14.22636ptP_{t}(a)$
$\displaystyle\leq\frac{1}{2}-0.11k_{t}(0.4\Delta_{t})+\eta_{t}+0.25\tau_{t}$
(163) $\displaystyle\leq\frac{1}{2}-\left(0.11\cdot\frac{1}{2}\cdot
0.4-0.01-0.25\cdot 0.01\right)\cdot\Delta_{t}^{\beta}$ (164)
$\displaystyle\leq\frac{1}{2}-0.01\cdot\Delta_{t}^{\beta}=\frac{1}{2}-\gamma_{t}$
(165) $\displaystyle
a\in[a^{(t)}_{\text{max}}-0.1\Delta_{t},a^{(t)}_{\text{max}}]\hskip
14.22636pt\to\hskip 14.22636ptP_{t}(a)$
$\displaystyle\geq\frac{1}{2}+0.11k_{t}(0.4\Delta_{t})-\eta_{t}-0.25\tau_{t}$
(166) $\displaystyle\geq\frac{1}{2}+\gamma_{t}$ (167)

In the case where $a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$,
we instead select $\eta_{t},\tau_{t}=0.001$, implying $\kappa(\tau_{t})>1$ as
before. That way $\frac{\kappa(\tau_{t})}{k_{t}}\leq\frac{1}{2}\Delta_{t}$. We
always have $\frac{1}{2}\Delta_{t}\leq a^{(t)}_{\text{mid}}$, so the
conditions of Lemma 29 are satisfied. So, we derive:

$\displaystyle
a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{min}}+0.1\Delta_{t}]\hskip
14.22636pt\to\hskip 14.22636ptP_{t}(a)$
$\displaystyle\leq\frac{1}{2}-0.11\left(\frac{1}{2}\cdot\frac{1}{\Delta_{t}}\right)(0.4\Delta_{t})+\eta_{t}+0.25\tau_{t}$
(168) $\displaystyle\leq\frac{1}{2}-\left(0.11\cdot\frac{1}{2}\cdot
0.4-0.01-0.25\cdot 0.01\right)$ (169)
$\displaystyle\leq\frac{1}{2}-0.01\geq\frac{1}{2}-\gamma_{t}$ (170)
$\displaystyle
a\in[a^{(t)}_{\text{max}}-0.1\Delta_{t},a^{(t)}_{\text{max}}]\hskip
14.22636pt\to\hskip 14.22636ptP_{t}(a)$
$\displaystyle\geq\frac{1}{2}+0.11\left(\frac{1}{2}\cdot\frac{1}{\Delta_{t}}\right)(0.4\Delta_{t})-\eta_{t}-0.25\tau_{t}$
(171) $\displaystyle\geq\frac{1}{2}+0.01\geq\frac{1}{2}+\gamma_{t}$ (172)

So in both cases we meet the assumptions of Lemma 30, completing the
correctness portion of the proof.

Now we prove the properties of $\mathbf{D}$ and $\mathbf{d}$. To do so, we
bound the maximum degree $d^{(t)}_{\text{max}}$ and the sum of all the degrees
$d^{(t)}$ at each iteration of step 2. The following bounds rely on the
guarantee that $a\in[a^{(t)}_{\text{min}},a^{(t)}_{\text{max}}]$ for all $t$,
which is only true probabilistically. Hence the bounds are themselves
probabilistic.

We start with $\mathbf{d}$ via $d^{(t)}_{\text{max}}$. The degree
$d^{(t)}_{\text{max}}$ is given by Lemma 25, and since we always have
$\log(1/\eta_{t})\leq k_{t}$ we have $d^{(t)}_{\text{max}}\in
O(k_{t}\sqrt{\log(1/\eta_{t})})$. If
$a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{x}$, then we have
$d^{(t)}_{\text{max}}\in
O(\Delta_{t}^{-(1-\beta)}\sqrt{\log(\Delta_{t}^{-2\beta})}\cdot\sqrt{\log(\Delta_{t}^{-\beta})})\leq\tilde{O}(\Delta_{t}^{-(1-\beta)})$
where $\tilde{O}$ hides log factors in $\Delta_{t}$. Otherwise if
$a^{(t)}_{\text{mid}}<\frac{1}{2}\Delta_{t}^{1-\beta}$, we have
$d^{(t)}_{\text{max}}\leq O(\Delta_{t}^{-1})$.

We have $\mathbf{d}=\max_{t}d^{(t)}_{\text{max}}$. To maximize over all $t$,
we must analyze the condition
$a_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$, since when this is the
case we have the cheaper degree of $O(\Delta_{t}^{-(1-\beta)})$. We argue that
there is some $t^{*}$ such that for $t>t^{*}$ the algorithm is guaranteed to
satisfy $a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$.

Observe that $a-\Delta_{t}/2\leq a^{(t)}_{\text{mid}}\leq a+\Delta_{t}/2$, and
since $\Delta_{t}\leq\Delta_{t}^{1-\beta}$ we also have
$a^{(t)}_{\text{mid}}\geq a-\Delta_{t}^{1-\beta}/2$. That means that as soon
as $\frac{1}{2}\Delta_{t}^{1-\beta}\geq a-\Delta_{t}^{1-\beta}/2$, we are
guaranteed that $a^{(t)}_{\text{mid}}\geq\frac{1}{2}\Delta_{t}^{1-\beta}$.
This happens when $a\geq\Delta_{t}^{1-\beta}$, that is, when
$t>t^{*}:=\lceil\log_{0.9}(a)\rceil$.

Let’s assume $T>t^{*}$. Before $t^{*}$ we have $d^{(t)}_{\text{max}}\in
O(\Delta_{t}^{-1})$, and afterwards we have
$d^{(t)}_{\text{max}}\in\tilde{O}(\Delta_{t}^{-(1-\beta)})$. Both of these
functions are increasing in $t$, so we maximize $d^{(t)}_{\text{max}}$ over
all $t$ by just considering their values at $t^{*}$ and $T$. See Figure 13. We
saw above that at $t^{*}$ we have $\Delta_{t}\geq a^{1/(1-\beta)}$, and at $T$
we have $\Delta_{t}\leq\varepsilon$. So we have established:

$\displaystyle\max_{t}d^{(t)}_{\text{max}}\in\max\left[O(a^{-1/(1-\beta)}),\tilde{O}(\varepsilon^{-(1-\beta)})\right]=\tilde{O}\left(a^{-1/(1-\beta)}+\varepsilon^{-(1-\beta)}\right)$
(173)

where the final $\tilde{O}$ hides log factors in $\varepsilon$, but not log
factors in $a^{1/(1-\beta)}$.

Otherwise, assume $T\leq t^{*}$. Then we have $d^{(t)}_{\text{max}}\in
O(\Delta_{t}^{-1})$ always, and since this function is increasing the maximum
occurs at $t=T$. But at $t\leq t^{*}$ we have $a<\Delta_{t}^{1-\beta}$, which
implies $\Delta_{t}^{-1}\leq a^{-1/(1-\beta)}$. So in this case we again have
$\max_{t}d^{(t)}_{\text{max}}\in O(a^{-1/(1-\beta)})$. This establishes the
bound on $\mathbf{d}$ for both cases.

Now we bound the sum of the degrees $\mathbf{D}$ via the sum of all degrees at
a particular iteration $d^{(t)}$. We simply have
$d^{(t)}=m_{t}d^{(t)}_{\text{max}}$, so in the $t\leq t^{*}$ case we have
$d^{(t)}\in O(\Delta_{t}^{-1}\log(\delta_{t}^{-1}))$, and in the $t>t^{*}$
case we have
$d^{(t)}\in\tilde{O}(\Delta_{t}^{-(1-\beta)}\cdot\Delta_{t}^{-2\beta}\log(\delta_{t}^{-1}))=\tilde{O}(\Delta_{t}^{-(1+\beta)}\log(\delta_{t}^{-1}))$.
Since $\delta_{t}$ is independent of $t$, we can just bound the first factor
in the products, recalling that $\Delta_{t}=0.9^{t}$:

$\displaystyle\sum_{t=0}^{t^{*}}\Delta_{t}^{-1}+\sum_{t=t^{*}+1}^{T-1}\Delta_{t}^{-(1+\beta)}$
$\displaystyle\leq\frac{1}{0.9}\sum_{t=0}^{t^{*}-1}\Delta_{t}^{-1}+\sum_{t=0}^{T-1}\Delta_{t}^{-(1+\beta)}$
(174)
$\displaystyle=\frac{1}{0.9}\frac{0.9^{-t*}-1}{0.9^{-1}-1}+\frac{(0.9^{T})^{-(1+\beta)}-1}{0.9^{-(1+\beta)}-1}$
(175) $\displaystyle\in O(a^{-1}+\varepsilon^{-(1+\beta)})$ (176)

Looking at the $\log(\delta_{t}^{-1})$ term, we have $T\in
O(\log(1/\varepsilon))$, so we have
$\log(\delta_{t}^{-1})\in\tilde{O}(\log(\delta^{-1}))$ where the $\tilde{O}$
hides log factors in $\varepsilon$. This establishes the bound on
$\mathbf{D}$. ∎

##  6 Acknowledgements

The authors are grateful for fruitful discussions with Stefan Woerner, Julien
Gacon, Giacomo Nannicini, John Martyn, Nikitas Stamatopoulos, and Pawel
Wocjan. Part of this work was completed while PR was supported by Scott
Aaronson’s Vannevar Bush Faculty Fellowship, although the majority of the work
was performed at IBM Quantum.

## References

  * [CH22] Arjan Cornelissen, Yassine Hamoudi A Sublinear-Time Quantum Algorithm for Approximating Partition Functions arXiv:2207.08643 Proceedings of the 34th Symposium on Discrete Algorithms (SODA) (2022)
  * [vACGN22] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, Giacomo Nannicini Quantum tomography using state-preparation unitaries arXiv:2207.08800 Proceedings of the 34th Symposium on Discrete Algorithms (SODA) (2022)
  * [Zhao&22] Yunpeng Zhao, Haiyan Wang, Kuai Xu, Yue Wang, Ji Zhu, Feng Wang Adaptive Algorithm for Quantum Amplitude Estimation  arXiv:2206.08449 (2022)
  * [MML22] Alberto Manzano, Daniele Musso, Álvaro Leitao Real Quantum Amplitude Estimation arXiv:2204.13641 EPJ Quantum Technol. 10, 2 (2022)
  * [Rosmanis22] Ansis Rosmanis Hybrid Quantum-Classical Search Algorithms arXiv:2202.11443 (2022)
  * [WDL21] Jiasu Wang, Yulong Dong, Lin Lin On the energy landscape of symmetric quantum signal processing arXiv:2110.04993 Quantum 6, 850 (2021)
  * [LdW21] Noah Linden, Ronald de Wolf Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation arXiv:2109.10215 Quantum 6, 872 (2021)
  * [Guirgica-Tiron&21] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright, William Zeng Low depth amplitude estimation on a trapped ion quantum computer arXiv:2109.09685 Physical Review Research 4, 033034 (2021)
  * [MRTC21] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang A Grand Unification of Quantum Algorithms arXiv:2105.02859 PRX Quantum 2, 040203 (2021)
  * [Rall21] Patrick Rall Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation arXiv:2103.09717 Quantum 5, 566 (2021)
  * [GKLPZ20] Tudor Giurgica-Tironc, Iordanis Kerenidisa, Farrokh Labibd, Anupam Prakash, and William Zeng Low depth algorithms for quantum amplitude estimation arXiv:2012.03348 Quantum 6, 745 (2020)
  * [VO20] Ramgopal Venkateswaran, Ryan O’Donnell Quantum Approximate Counting with Nonadaptive Grover Iterations arXiv:2010.04370 38th International Symposium on Theoretical Aspects of Computer Science (STACS) (2020)
  * [AHNTW20] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions arXiv:2009.11270 Quantum 6, 789 (2020)
  * [YLRJ20] Kwangmin Yu, Hyunkyung Lim, Pooja Rao, Dasol Jin Comparison of Amplitude Estimation Algorithms by Implementation arXiv:2005.05300 (2020)
  * [Chao&20] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy Finding Angles for Quantum Signal Processing with Machine Precision arXiv:2003.02831 (2020)
  * [Nakaji20] Kouhei Nakaji Faster Amplitude Estimation arXiv:2003.02417 QIC20.13-14-2 (2020)
  * [LT20] Lin Lin, Yu Tong. Near-optimal ground state preparation Quantum 4, 372 arXiv:2002.12508 (2020)
  * [GGZW19] Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner Iterative Quantum Amplitude Estimation npj Quantum Inf 7, 52 arXiv:1912.05559 (2019)
  * [AR19] Scott Aaronson, Patrick Rall. Quantum Approximate Counting, Simplified Symposium on Simplicity in Algorithms. 2020, 24-32 arXiv:1908.10846 (2019)
  * [HW19] Aram W. Harrow, Annie Y. Wei. Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions Proc. of SODA 2020 arXiv:1907.09965 (2019)
  * [Suzuki&19] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, Naoki Yamamoto Amplitude estimation without phase estimation arXiv:1904.10246 Quantum Information Processing, 19, 75 (2019)
  * [Haah18] Jeongwan Haah Product Decomposition of Periodic Functions in Quantum Signal Processing Quantum 3, 190. arXiv:1806.10236 (2018)
  * [GSLW18] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics arXiv:1806.01838 (2018)
  * [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019) Pages 193–204 (2019)
  * [LC17] Guang Hao Low, Isaac L. Chuang Hamiltonian Simulation by Uniform Spectral Amplification arXiv:1707.05391 (2017)
  * [LC1610] Guang Hao Low, Isaac L. Chuang Hamiltonian Simulation by Qubitization Quantum 3, 163 arXiv:1610.06546 (2016)
  * [LC1606] Guang Hao Low, Isaac L. Chuang Optimal Hamiltonian Simulation by Quantum Signal Processing Phys. Rev. Lett. 118, 010501 arXiv:1606.02685 (2016)
  * [CO16] Earl T. Campbell, Joe O’Gorman An efficient magic state approach to small angle rotations Quantum Science and Technology, 1, 015007  arXiv:1603.04230 (2016)
  * [LYC16] Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang The methodology of resonant equiangular composite quantum gates arXiv:1603.03996 Phys. Rev. X 6, 041067 (2016)
  * [Montanaro15] Ashley Montanaro Quantum speedup of Monte Carlo methods Proc. Roy. Soc. Ser. A, vol. 471 no. 2181 arXiv:1504.06987 (2015)
  * [YLC14] Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang Fixed-point quantum search with an optimal number of queries arXiv:1409.3305 Phys. Rev. Lett. 113, 210501 (2014)
  * [AKLV13] Itai Arad, Alexei Kitaev, Zeph Landau, Umesh Vazirani “An area law and sub-exponential algorithm for 1D systems” arXiv:1301.1162
  * [Demeyer07] J. Demeyer “Diophantine Sets over Polynomial Rings and Hilbert’s Tenth Problem for Function Fields” PhD Thesis at Universiteit Gent. (2007)
  * [BHMT00] Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp Quantum Amplitude Amplification and Estimation Quantum Computation and Quantum Information, 305:53-74 arXiv:quant-ph/0005055 (2000)
  * [NW98] Ashwin Nayak, Felix Wu. The quantum query complexity of approximating the median and related statistics arXiv:quant-ph/9804066 Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC 1999) Pages 384-393 (1998)
  * [Rivlin69] Theodore Rivlin An Introduction to the Approximation of Functions SIAM Review Vol. 12, Iss. 2 Dover Publications, Inc. New York. (1969)
  * [CP34] C. Clopper, E. Pearson The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika, vol. 26, no. 4, pp. 404–413. (1934)