---
abstract: 'We present a simple algorithm to solve the quantum linear system problem (QLSP), i.e. preparing a quantum state $\ket{x}$ that is proportional to $A^{-1}\ket{b}$. The algorithm decomposes a general QLSP into an initial state preparation problem solved by the time-optimal adiabatic quantum computation, and an eigenstate filtering problem solved by quantum signal processing. The algorithm does not rely on phase estimation, variable-time amplitude amplification, or in fact any amplitude amplification procedure. The probability of success is $\Omega(1)$. The query complexity of the algorithm is ${\mathcal{O}}(\kappa(\log(\kappa)/\log\log(\kappa)+\log(1/\epsilon)))$, which is near-optimal with respect to the condition number $\kappa$ up to a logarithmic factor, and is optimal with respect to the target accuracy $\epsilon$.'
author:
- Lin Lin
- Yu Tong
bibliography:
- 'qlsp.bib'
title: 'Solving quantum linear system problem with near-optimal complexity'
---

¶

The quantum linear systems problem (QLSP) aims at preparing a state $\ket{x}=A^{-1}\ket{b}/{\lVertA^{-1}\ket{b}\rVert}_2$ on a quantum computer, where $A\in{\mathbb{C}}^{N\times N}$, and $\ket{b}\in{\mathbb{C}}^N$, $N=2^n$. Due to the wide range of applications of linear systems in scientific and engineering computation, the efficient solution of QLSP has received significant attention in recent years [@HarrowHassidimLloyd2009; @ChildsKothariSomma2017; @GilyenSuLowEtAl2019; @SubasiSommaOrsucci2019; @AnLin2019; @ChakrabortyGilyenJeffery2018; @WossnigZhaoPrakash2018; @CaoPapageorgiouPetrasEtAl2013; @XuSunEndoEtAl2019; @Bravo-PrietoLaRoseCerezoEtAl2019]. All QLSP solvers share the desirable property that the complexity with respect to the matrix dimension can be only $\text{poly}(n)$, which is exponentially faster compared to every known classical solver. However, the pre-constant of the original Harrow, Hassidim, and Lloyd (HHL) algorithm scales as ${\mathcal{O}}(\kappa^2/\epsilon)$, where $\kappa$ is the condition number of $A$, and $\epsilon$ is the target accuracy. This is significantly weaker compared to classical methods such as the steepest descent (SD) or conjugate gradient (CG) methods with respect to both $\kappa$ and $\epsilon$. For instance, for positive definite matrices, the complexity of SD and CG is only ${\mathcal{O}}( {\kappa}\log(1/\epsilon))$ and ${\mathcal{O}}( \sqrt{\kappa}\log(1/\epsilon))$, respectively [@Saad2003].

In the past few years, there have been significant progresses towards reducing the pre-constants for quantum linear solvers. In particular, the linear combination of unitary (LCU) [@ChildsKothariSomma2017] and quantum signal processing (QSP) [@LowChuang2017; @GilyenSuLowEtAl2019] techniques can reduce the query complexity to ${\mathcal{O}}(\kappa^2 \log(\kappa/\epsilon))$. Therefore the algorithm is optimal with respect to $\epsilon$, but is still suboptimal with respect to $\kappa$. The scaling with respect to $\kappa$ can be reduced by the variable-time amplitude amplification (VTAA) [@Ambainis2012] technique, and the resulting complexity for solving QLSP is ${\mathcal{O}}(\kappa{~}\text{poly}(\log(\kappa/\epsilon)))$ [@ChildsKothariSomma2017]. However, VTAA requires considerable modification of the LCU or QSP algorithm, and has significant overhead itself. To the extent of our knowledge, the performance of VTAA for solving QLSP has not been quantitatively reported in the literature.

The recently developed randomization method (RM) [@SubasiSommaOrsucci2019] is the first algorithm that yields near-optimal scaling with respect to $\kappa$, without using techniques such as VTAA. RM was inspired by adiabatic quantum computation (AQC) [@FarhiGoldstoneGutmannEtAl2000; @AlbashLidar2018; @JansenRuskaiSeiler2007]. The time complexity of the vanilla AQC is at best ${\mathcal{O}}(\kappa^2/\epsilon)$ [@ElgartHagedorn2012] , and RM improves the time complexity to ${\mathcal{O}}(\kappa\log (\kappa)/\epsilon)$. On the other hand, if we optimize the scheduling function of AQC, then the resulting time-optimal AQC can achieve even lower time complexity as ${\mathcal{O}}(\kappa/\epsilon)$ [@AnLin2019]. This is similar to the time-optimal AQC for performing Grover’s search [@RolandCerf2002]. Furthermore, numerical observation indicate that the time complexity of the quantum approximate optimization algorithm (QAOA) [@FarhiGoldstoneGutmann2014] can be only ${\mathcal{O}}(\kappa \text{poly}(\log(1/\epsilon)))$ [@AnLin2019]. The reason of such significant improvement of the accuracy due to QAOA remains an open question.

In this Letter, we present an algorithm to solve QLSP with query complexity ${\mathcal{O}}(\kappa(\log(\kappa)/\log\log(\kappa)+\log(1/\epsilon)))$, with $\Omega(1)$ probability of success and without using any amplitude amplification procedure. For any $\delta>0$, a quantum algorithm that is able to solve a generic QLSP with cost ${\mathcal{O}}(\kappa^{1-\delta})$ would imply **BQP**=**PSPACE**  [@HarrowHassidimLloyd2009; @FarhiGoldstoneGutmannEtAl2000]. Therefore our algorithm is near-optimal with respect to $\kappa$ up to a logarithmic factor, and is optimal with respect to $\epsilon$. Similar to AQC, our algorithm treats QLSP as an eigenvalue problem. The first term of the complexity comes from an initial state preparation problem. We use the time-optimal AQC to prepares an initial state $\ket{x_0},$ with only a nontrivial overlap with the true solution as ${\lvert\braket{x_0|x}\rvert}\sim {\mathcal{O}}(1)$. The second term comes from an eigenstate filtering problem. We filter out the unwanted components in $\ket{x_0}$, and the filtered state is then $\epsilon$-close to $\ket{x}$ upon measurement. Our filtering polynomial yields the *optimal* compression ratio among all polynomials, and can be efficiently implemented using QSP [@GilyenSuLowEtAl2019; @LowChuang2017]. We confirm the complexity analysis using numerical examples for solving QLSP, and find that the degree of the filtering polynomial needed is rather modest. The solution can be highly accurate (with fidelity as high as $1-10^{-10}$), which is difficult to achieve using AQC based methods, either due to the $\epsilon^{-1}$ scaling for AQC and RM, or due to the difficulty of numerical optimization for QAOA.

*Block-encoding and quantum signal processing:* For simplicity we assume $N=2^n$, and the normalization condition ${\lVertA\rVert}_2=1,\braket{b|b}=1$. We also assume $A$ is Hermitian, as general matrices can be treated using the standard matrix dilation method (included in the supplementary materials).

An $(m+n)$-qubit unitary operator $U$ is called an $(\alpha, m, \epsilon)$-block-encoding of an $n$-qubit operator $A$, if $${\lVertA-\alpha(\bra{0^m}\otimes I) U (\ket{0^m}\otimes I)\rVert}_2\leq \epsilon.
\label{eqn:block_encoding}$$ Many matrices used in practice can be efficiently block-encoded. For instance, if all entries of $A$ satisfies ${\lvertA_{ij}\rvert}\le 1$, and $A$ is Hermitian and $d$-sparse (i.e. each row / column of $A$ has no more than $d$ nonzero entries), then $A$ has a $(d,n+2,0)$-encoding $U$ [@ChildsKothariSomma2017; @BerryChildsKothari2015].

With a block-encoding available, QSP allows us to construct a block-encoding for an arbitrary polynomial eigenvalue transformation of $A$.

\[thm:qsp\] **(Quantum signal processing [@GilyenSuLowEtAl2019])** : Let $U$ be an $(\alpha,m,\epsilon)$-block-encoding of a Hermitian matrix $A$. Let $P\in{\mathbb{R}}[x]$ be a degree-$\ell$ real polynomial and ${\lvertP(x)\rvert}\le 1/2$ for any $x\in[-1,1]$. Then there exists a $(1, m+2,4 \ell \sqrt{\epsilon} / \alpha)$-block-encoding ${\widetilde{U}}$ of $P(A/\alpha)$ using $\ell$ queries of $U,U^{\dagger}$ .

Compared to methods such as LCU, one distinct advantage of QSP is that the number of extra ancilla qubits needed is only $1$. Hence QSP may be carried out efficiently even for near-term to intermediate-term devices. Furthermore, a polynomial can be expanded into different basis functions as $P(x)=\sum_{k=0}^{\ell} c_k f_k(x)$, where $f_k$ can be the monomial $x^k$, the Chebyshev polynomial $T_k(x)$, or any other polynomial. The performance of LCU crucially depends on the 1-norm ${\lVertc\rVert}_1:=\sum_{k=0}^\ell |c_k|$, which can be very different depending on the expansion [@ChildsKothariSomma2017]. The block encoding ${\widetilde{U}}$ in QSP is independent of such a choice, and therefore provides a more intrinsic representation of matrix function.

We may readily apply QSP to solve QLSP. We assume $A$ is given by its $(\alpha,m,\epsilon)$-block-encoding, and its eigenvalues are contained in $\mathcal{D}_{1/\kappa}:=[-1,-1/\kappa]\cup[1/\kappa, 1]$. We first find a polynomial $P(x)$ satisfying $|P(x)|\le \frac12$ for any $x\in[-1,1]$, and $P(x)\approx 1/(2 c x)$ on ${\mathcal{D}}_{1/\alpha\kappa}$ for some $c>\alpha\kappa$. Then we have $$\begin{aligned}
{\widetilde{U}}\ket{0^{m+2}}\ket{b}=&\ket{0^{m+2}}(P(A/\alpha)\ket{b})+\ket{\phi}\\
\approx& \ket{0^{m+2}}\left(\frac{\alpha}{2c}A^{-1}\ket{b}\right)+\ket{\phi},
\end{aligned}$$ where $\ket{\phi}$ is orthogonal to all states of the form $\ket{0^{m+2}}\ket{\psi}$. Measuring the ancilla qubits, we obtain the solution $\ket{x}$ with probability $\Theta\left(\left(\frac{\alpha}{2c}{\lVertA^{-1}\ket{b}\rVert}_2\right)^2\right)$. Assuming ${\lVertA^{-1}\ket{b}\rVert}_2\sim {\mathcal{O}}(1)$, the probability of success is ${\mathcal{O}}(1/\kappa^2)$. Using amplitude amplification [@BrassardHoyerMoscaEtAl2002], the number of repetitions needed for success can be improved to ${\mathcal{O}}(\kappa)$. Furthermore, the query complexity of application of ${\widetilde{U}}$ is ${\mathcal{O}}(\alpha\kappa\log(\kappa/\epsilon))$. Therefore the overall query complexity of QSP to solve QLSP is ${\mathcal{O}}(\alpha\kappa^2\log(\kappa/\epsilon))$.

We observe that the quadratic scaling with respect to $\kappa$ is very much attached to the procedure above: each application of QSP costs ${\mathcal{O}}(\kappa)$ queries of $U,U^{\dagger}$, and the other from that QSP needs to be performed for ${\mathcal{O}}(\kappa)$ times. The same argument applies to LCU. To reduce the $\kappa$ complexity, one must involve significantly modify method, such as the modified LCU based on VTAA [@ChildsKothariSomma2017].

*Adiabatic computation:* Instead of tackling the linear system problem directly, AQC converts a QLSP into an eigenvalue problem. For simplicity we further restrict $A$ to be Hermitian positive definite, and the treatment for Hermitian indefinite matrices and general matrices can be found in the supplementary materials. Let $Q_{b}=I-\ket{b}\bra{b}$. We introduce $$H_0=\begin{pmatrix}
0 & Q_b\\
Q_b & 0
\end{pmatrix}, \quad H_1=\begin{pmatrix}
0 & AQ_b\\
Q_bA & 0
\end{pmatrix}.
\label{eq:ham_qlsp}$$ If $\ket{x}$ satisfies $A\ket{x}\propto\ket{b}$, we have $Q_bA\ket{x}=Q_b\ket{b}=0$. Define $\ket{0}\ket{b}=(b,0)^{\top},\ket{0}\ket{x}=(x,0)^{\top}$. Then $\ket{0}\ket{b}$ and $\ket{0}\ket{x}$ are in the null space of $H_0,H_1$, respectively, and therefore we need to find the eigenvector corresponding to the eigenvalue 0. The form of the matrices in Eq.  is important for achieving ${\mathcal{O}}(\kappa)$ complexity. Furthermore, the other eigenvector in the null space of $H_1$ is $\ket{1}\ket{b}=(0,b)^{\top}$, which is orthogonal to the solution vector $\ket{0}\ket{x}$, and is not accessible via the adiabatic evolution $$\frac{1}{T}{\imath}\partial_s \left|\psi_T(s)\right> = H(f(s))\left|\psi_T(s)\right>, \quad    \ket{\psi_T(0)}=\ket{0}\ket{b}.$$ Here $H(f(s)) = (1-f(s))H_0 + f(s)H_1, 0\le s\le 1$. The function $f:[0,1]\rightarrow [0,1]$ is called a scheduling function, and is a strictly increasing mapping with $f(0) = 0, f(1) = 1$. The simplest choice is $f(s)=s$, which gives the “vanilla AQC”. Besides $\ket{0}\ket{x}$, all other eigenstates of $H_1$ that can be connected to $\ket{0}\ket{b}$ through an adiabatic evolution are separated from $\ket{0}\ket{x}$ by an energy gap of at least $1/\kappa$ [@AnLin2019]. The time complexity of vanilla AQC is at least $T\sim {\mathcal{O}}(\kappa^2/\epsilon)$ [@JansenRuskaiSeiler2007; @AnLin2019; @AlbashLidar2018; @ElgartHagedorn2012].

By properly choosing a scheduling function $f(s)$, the time-optimal AQC can find an $\epsilon$-approximation to $\ket{0}\ket{x}$, with time complexity ${\mathcal{O}}(\kappa/\epsilon)$. Using truncated Dyson series for simulating the time-dependent Hamiltonian [@LowWiebe2018], the query complexity is ${\widetilde{{\mathcal{O}}}}(\kappa/\epsilon)$. This choice of the scheduling function and the Hamiltonian simulation are discussed in supplemental materials. As mentioned before, the fact that the $0$-eigenspace of $H(f(s))$ is two dimensional is not a problem because $\ket{\psi_T(t)}$ is orthogonal to $\ket{1}\ket{b}$ for all $t$.

*Eigenstate filtering:* The main difficulty of the time-optimal AQC is that it can be costly to reach high accuracy. Nonetheless, if we choose the simulation time to be ${\mathcal{O}}(\kappa/\epsilon_0)$ for some constant target accuracy (e.g. $\epsilon_0=0.5$), the query complexity to prepare a state $\ket{{\widetilde{x}}_0}$ $$\ket{{\widetilde{x}}_0}=\gamma \ket{0}\ket{x}+ \sqrt{1-|\gamma|^2}\ket{{\widetilde{y}}}
$$ is only ${\mathcal{O}}(\kappa\log(\kappa))$, where $\gamma= \Omega(1)$ and $(\bra{0}\bra{x})\ket{{\widetilde{y}}}=0$. Our goal is therefore to construct a filtering polynomial $P(H_1)$ so that $$P(H_1)\ket{0}\ket{x}\approx \ket{0}\ket{x}, \quad P(H_1)\ket{0}\ket{y}\approx 0,$$ *i.e.* it filters out the unwanted component $\ket{0}\ket{y}$ while leaving $\ket{0}\ket{x}$ intact. Since $\ket{0}\ket{x}$ is an eigenstate of $H_1$, this filtering problem can be implemented by QSP.

We use the following $2\ell$-degree polynomial $$R_{\ell}(x;\Delta)=\frac{T_{\ell}\left(-1+2\frac{x^{2}-\Delta^{2}}{1-\Delta^{2}}\right)}{T_{\ell}\left(-1+2\frac{-\Delta^{2}}{1-\Delta^{2}}\right)}.$$ A plot of the polynomial is given in Fig. \[minimax\_poly\]. $R_{\ell}(x;\Delta)$ has several nice properties:

\[lem:minimax\_poly\] (i) $R_{\ell}(x;\Delta)$ solves the minimax problem $$\underset{p(x)\in\mathbb{P}_{2\ell}[x],p(0)=1}{\mathrm{minimize}}  \max_{x\in\mathcal{D}_{\Delta}}|p(x)|.$$

\(ii) $|R_{\ell}(x;\Delta)|\leq2e^{-\sqrt{2}\ell\Delta}$ for all $x\in\mathcal{D}_{\Delta}$ and $0<\Delta\leq1/\sqrt{12}$. Also $R_{\ell}(0;\Delta)=1$.

\(iii) $|R_{\ell}(x;\Delta)|\leq1$ for all $|x|\leq1$.

![The polynomial $R_{\ell}(x,\Delta)$ for $\ell=16$ and $30$, $\Delta=0.1$.[]{data-label="minimax_poly"}](minimax_poly){width="0.7\linewidth"}

Now consider a Hermitian matrix $H$, with a known eigenvalue $\lambda$ that is separated from other eigenvalues by a gap $\Delta$. $H$ is assumed to have an $(\alpha,m,0)$-block-encoding denoted by $U_H$. In order to preserve the $\lambda$-eigenstate while filtering out all other eigenstates, Lemma \[lem:minimax\_poly\] (i) states that $R_{\ell}$ achieves the best compression ratio of the unwanted components, among all polynomials of degrees up to $2\ell$. To prepare a quantum circuit, we define ${\widetilde{H}}=(H-\lambda I)/(\alpha+|\lambda|)$ and ${\widetilde{\Delta}}=\Delta/2\alpha$, then we can also construct a $(1,m+1,0)$-block-encoding for ${\widetilde{H}}$ (see supplemental materials). The gap separating 0 from other eigenvalues of ${\widetilde{H}}$ is lower bounded by ${\widetilde{\Delta}}$.

Because of (ii) of Lemma \[lem:minimax\_poly\], we have that $$\|R_\ell({\widetilde{H}},{\widetilde{\Delta}})-P_\lambda\|_2\leq 2e^{-\sqrt{2}\ell{\widetilde{\Delta}}}.$$ where $P_{\lambda}$ is the projection operator onto the eigenspace corresponding to $\lambda$. Also because of (iii), $(1/2)R_{\ell}(x;{\widetilde{\Delta}})$ satisfies the requirements in Theorem \[thm:qsp\], which enables us to implement $(1/2)R_{\ell}({\widetilde{H}};{\widetilde{\Delta}})$ using QSP. This gives the following theorem:

\[thm:eigenstate\_filter\] **(Eigenstate filtering):** Let $H$ be a Hermitian matrix and $U_H$ is an $(\alpha,m,0)$-block-encoding of $H$. If $\lambda$ is an eigenvalue of $H$ that is separated from the rest of the spectrum by a gap $\Delta$, then we can construct a $(2,m+3,\epsilon)$-block-encoding of $P_\lambda$, by $\mathcal{O}((\alpha/\Delta)\log(1/\epsilon))$ applications of (controlled-) $U_H$ and $U^{\dagger}_H$.

Suppose we can prepare a state $\ket{\psi} = \gamma \ket{\psi_\lambda} + \sqrt{1-|\gamma|^2}\ket{\psi^\perp_\lambda}$ using an oracle $O_\psi$, where $\ket{\psi_\lambda}$ is a $\lambda$-eigenvector and $\braket{\psi_\lambda|\psi^\perp_\lambda}=0$, for some $0<\gamma\leq 1$. Theorem \[thm:eigenstate\_filter\] states that we can get an $\epsilon$-approximation to $\ket{\psi_{\lambda}}$ with $\mathcal{O}((\alpha/\Delta)\log(1/\epsilon))$ queries to $U_H,$ with a successful application of the block-encoding of $P_\lambda$, denoted by $U_{P_\lambda}$. The probability of applying this block-encoding successfully, [*i.e.* ]{}getting all 0’s when measuring ancilla qubits, is at least $\gamma^2/4$. Therefore when $\gamma = \Omega(1)$, and $\ket{\psi}$ can be repeatedly prepared, we only need to run $U_{P_\lambda}$ on average $\mathcal{O}(1)$ times to obtain $\ket{\psi_{\lambda}}$ successfully.

We remark that the eigenstate filtering procedure can also be implemented by alternative methods such as LCU. The polynomial $R_{\ell}(\cdot,{\widetilde{\Delta}})$ can be expanded exactly into a linear combination of the first $2\ell+1$ Chebyshev polynomials. The 1-norm of the expansion coefficients is upper bounded by $2 \ell+2$ because $|R_{\ell}(x,{\widetilde{\Delta}})|\leq 1$. However, this comes at the expense of additional ${\mathcal{O}}(\log \ell)$ qubits needed for the LCU expansion [@ChildsKothariSomma2017].

*Applications to QLSP:* For the QLSP given by a $d$-sparse Hermitian matrix $A\in{\mathbb{C}}^{2^n\times 2^n}$ whose eigenvalues are contained in $\mathcal{D}_{1/\kappa}$ and $\ket{b}$, we assume the entries of $A$ can queried by oracles $$O_{A,1}\vert j,l\rangle  =  \vert j,\nu(j,l)\rangle,\quad
O_{A,2}\vert j,k,z\rangle  =  \vert j,k,A_{jk}\oplus z\rangle,
\label{eq:oracles_A}$$ where $j,k,l,z\in [N]$, and $\nu(j,l)$ is the row index of the $l$-th nonzero element in the $j$-th column. $\ket{b}$ can be prepared by an oracle $O_{B}\vert0\rangle  =  \vert b\rangle$. This is the same as in [@ChildsKothariSomma2017; @SubasiSommaOrsucci2019]. The oracles can be used to construct a $(d,n+2,0)$-block-encoding of $A$. Furthermore, as discussed in the supplemental materials, we can construct a $(d,n+4,0)$-block-encoding of $H_1$, denoted by $U_{H_1}$ in (\[eq:ham\_qlsp\]) by applying $O_B, O_{A,1}, O_{A,2}$ twice.

As noted before the null space of $H_1$ is spanned by $\ket{0}\ket{x}$ and $\ket{1}\ket{b}$, and the eigenvalue 0 is separated from the rest of the spectrum by a gap of $1/\kappa$ [@AnLin2019]. Thus if we are given an initial state $$\ket{{\widetilde{x}}_0} = \gamma_0 \ket{0}\ket{x} + \gamma_1 \ket{1}\ket{b} + \gamma_2 \ket{{\widetilde{y}}} 
\label{eqn:x0expand}$$ with $|\gamma_0|=\Omega(1)$ and $\ket{{\widetilde{y}}}$ orthogonal to the 0-eigenspace, then we can run the eigenstate filtering algorithm described above to precision $\epsilon$ to obtain $R_{\ell}(H_1/d;1/d\kappa)\ket{{\widetilde{x}}_0}$. The $\ket{{\widetilde{y}}}$ component will be filtered out, while the $\ket{0}\ket{x}$ and $\ket{1}\ket{b}$ components remain. To further remove the $\ket{1}\ket{b}$ component, we measure the first qubit. Upon getting an outcome 0, the outcome state will just be $\ket{0}\ket{x}+\mathcal{O}(\epsilon)$. The success probability of applying the eigenstate filtering is lower bounded by $|\gamma_0|^2+|\gamma_1|^2$, and the success probability of obtaining 0 in measurement is $|\gamma_0|^2/(|\gamma_0|^2+|\gamma_1|^2)+\mathcal{O}(\epsilon)$. Thus the total success probability is $\Omega(1)$. Each single application of eigenstate filtering applies $U_{H_1}$, and therefore $O_{A,1}$, $O_{A,2}$, and $O_{B}$, for ${\mathcal{O}}(d\kappa\log(1/\epsilon))$ times. It only needs to be repeated $\Omega(1)$ times so the total query complexity of eigenstate filtering is still ${\mathcal{O}}(d\kappa\log(1/\epsilon))$.

The initial state $\ket{{\widetilde{x}}_0}$ can be prepared using the time-optimal AQC procedure. Again we first assume $H$ is Hermitian positive definite. To make $\gamma_0=\Omega(1)$ we only need to run AQC to constant precision. Thus the time complexity of AQC is $\mathcal{O}(\kappa)$. However we still need to implement AQC on a quantum circuit. To do this we use the time-dependent Hamiltonian simulation introduced in [@LowWiebe2018], which gives a ${\mathcal{O}}(d\kappa\log(d\kappa)/\log\log(d\kappa))$ query complexity to achieve ${\mathcal{O}}(1)$ precision. This procedure also needs to be repeated $\mathcal{O}(1)$ times. It should be noted that $\gamma_1$ in Eq.  comes entirely from the error of the Hamiltonian simulation, since AQC should ensure that the state is orthogonal to $\ket{1}\ket{b}$ for all $t$. The procedure above can be generalized to Hermitian indefinite matrices, and general matrices (see supplemental materials). Therefore our QLSP solver can be summarized as

\[thm:qlsp\] $A$ is a $d$-sparse matrix whose eigenvalues are in $\mathcal{D}_{1/\kappa}$ and can be queried through oracles $O_{A,1}$ and $O_{A,2}$ in (\[eq:oracles\_A\]), and $\ket{b}$ is given by an oracle $O_B$. Then $\ket{x}\propto A^{-1}\ket{b}$ can be obtained with fidelity $1-\epsilon$ using $\mathcal{O}(d\kappa(\log(d\kappa)/\log\log(d\kappa)+\log(1/\epsilon)))$ queries to $O_{A,1}$, $O_{A,2}$, and $O_B$.

The number of qubits needed in the eigenvalue filtering procedure using QSP is $\mathcal{O}(n)$. In the Hamiltonian simulation $\mathcal{O}(n+\log(d\kappa))$ qubits are needed (see supplemental materials). Therefore the total number of qubits needed is $\mathcal{O}(n+\log(d\kappa))$.

We present numerical results in Fig. \[fig:qls\_results\] to validate the complexity estimate. In the numerical test, $A$ is formed by adding a randomly generated symmetric positive definite tridiagonal matrix $B$, whose smallest eigenvalue is very close to 0, to a scalar multiple of the identity matrix. After properly rescaling, the eigenvalues of $A$ lie in $[-1,1]$. This construction enables us to estimate condition number with reasonable accuracy without computing eigenvalues. The off-diagonal elements of $B$ are drawn uniformly from $[-1,0]$ and the diagonal elements are the negative of sums of two adjacent elements on the same row. The $(0,0)$ and $(N,N)$ elements of $B$ are slightly larger so that $B$ is positive definite.

![Left: fidelity $\eta^2$ converges to 1 exponentially as $\ell$ in the eigenvalues filtering algorithm increases, for different $\kappa$. Right: the smallest $\ell$ needed to achieve fixed fidelity $\eta^2$ grows linearly with respect to condition number $\kappa$. The initial state in eigenstate filtering is prepared by running AQC for $T=0.2\kappa$, which achieves an initial fidelity of about 0.6.[]{data-label="fig:qls_results"}](plot_qls){width="50.00000%"}

*Discussion:* In this paper, we have introduced a simple algorithm to solve QLSP with near-optimal complexity with respect to both $\kappa$ and $\epsilon$. In the case when the precise value of $\kappa$ is not known *a priori*, the knowledge of an upper bound of $\kappa$ would suffice. The problem of directly targeting at the solution $A^{-1}\ket{b}  $ is that a $(\beta,m,\epsilon)$ block-encoding of $A^{-1}$ requires at least $\beta\ge\kappa$ to make sure that ${\lVertA^{-1}/\beta\rVert}_2\le 1$. Therefore the probability of success is already ${\mathcal{O}}(\kappa^{-2})$, and the number of repetitions needed is already ${\mathcal{O}}(\kappa)$ with the help of amplitude amplification. Motivated by the success of AQC, our algorithm solves views QLSP as an eigenvalue problem, which can be implemented via $P \ket{{\widetilde{x}}_0}$, where $P$ is an approximate projection operator, and $P \ket{{\widetilde{x}}_0}$ encodes the solution $\ket{x}$. The advantage of such a filtering procedure is that $P$ is bounded independent of $\kappa$, and its $(\beta,m,\epsilon)$ block-encoding only requires $\beta\sim{\mathcal{O}}(1)$. Therefore assuming ${\mathcal{O}}(1)$ overlap between $\ket{{\widetilde{x}}_0}$ and the solution vector, which can be satisfied by running the time-optimal AQC to constant precision, the probability of success of the filtering procedure is already ${\mathcal{O}}(1)$ without any amplitude amplification procedure.

We remark that the eigenstate filtering procedure can be implemented via other choices of eigensolvers. Other approaches to prepare eigenstates include (i) phase estimation, (ii) the filtering method developed by Poulin and Wocjan [@PoulinWocjan2009], (iii) ground state preparation method based on LCU developed by Ge [*et al* ]{}. [@GeTuraCirac2019], and (iv) a variant of the third approach based on Chebyshev expansion and LCU (Appendix D of [@GeTuraCirac2019]). Some of these methods are focused on ground state but can be adapted to compute interior eigenstates as well.

Now we compare our method with each of the methods mentioned above. For phase estimation, as discussed in Appendix B of [@GeTuraCirac2019], directly using phase estimation has a $1/\epsilon$ dependence on the allowed error. For the second and third approaches, the original paper by Poulin and Wocjan was intended for a different task, but a modified version (Appendix C of [@GeTuraCirac2019]) and the third approach by Ge [*et al* ]{}[@GeTuraCirac2019] can both attain ${\widetilde{\mathcal{O}}}((\alpha/\Delta)\log(1/\epsilon))$ query complexity, which is similar to our method modulo logarithmic factors. However our filtering method, which is based on QSP, uses significantly fewer qubits, which does not depend on either $\epsilon$ or $\Delta$. The fourth approach filters eigenstates using matrix polynomials. Our method is optimal in this sense, because it solves the the minimax problem as recorded in Lemma \[lem:minimax\_poly\] (i).

We also remark that although we did not consider the dependence on the initial overlap $\gamma$ since it is assumed to be $\Omega(1)$, it can be easily seen that with amplitude amplification we can get a $1/\gamma$ dependence in the query complexity, with some additional logarithmic factors. In order to implement the QSP-based eigenstate filtering procedure, one still needs to find the phase factors associated with the block encoding ${\widetilde{U}}$. For a given polynomial $R_\ell(\cdot,\Delta)$, the phase factors are obtained on a classical computer in time that is polynomial in the degree and the logarithm of precision [@GilyenSuLowWiebe2018Long Theorems 3-5]. However, this procedure requires solution of all roots of a high degree polynomial, which can be unstable for the range of polynomials $\ell\sim 100$ considered here. The stability of such procedure has recently been improved by Haah [@Haah2019], though the number of bits of precision needed still scales as ${\mathcal{O}}(\ell \log(\ell/\epsilon))$. In this sense, there is no algorithm yet to evaluate the QSP phase factors that is numerically stable in the usual sense, i.e. the number of bits of precision needed is ${\mathcal{O}}(\text{poly}\log(\ell/\epsilon))$. We note that these phase factors in the eigenvalue filtering procedure only depend on ${\widetilde{\Delta}}$ and $\ell$, and therefore can be reused for different matrices once they are obtained on a classical computer.

*Acknowledgements:* This work was partially supported by the Department of Energy under Grant No. DE-SC0017867, the Quantum Algorithm Teams Program under Grant No. DE-AC02-05CH11231, the Google Quantum Research Award (L.L.), and by the Air Force Office of Scientific Research under award number FA9550-18-1-0095 (L.L. and Y.T.). We thank Dong An, Yulong Dong, Nathan Wiebe for helpful discussions.

**Supplemental Materials:\
Solving quantum linear system problem with near-optimal complexity**

Block encoding {#sec:apdx_block_encoding}
==============

When discussing the number of queries to an oracle $O,$ we do not distinguish between $O$ and its controlled version. The asymptotic notations $\mathcal{O}$, $\Omega$ are used for the limit $\kappa\rightarrow\infty$ and $\epsilon\rightarrow 0$. We use ${\widetilde{\mathcal{O}}}$ to mean $\mathcal{O}$ multiplied by a poly-logarithmic part. Sometimes we do not distinguish between the different ways of measuring error, e.g. in terms of fidelity or 2-norm distance of density matrices, since the query complexity is logarithmic in the error defined in both ways. Floating-point arithmetic is assumed to be exact for conciseness. If floating-point error is taken into account this will only lead to a logarithmic multiplicative overhead in the number of primitive gates, and a logarithmic additive overhead in the number of qubits needed.

The technique of block-encoding has been recently discussed extensively [@GilyenSuLowEtAl2019; @LowChuang2019]. Here we discuss how to construct block-encoding for $H-\lambda I$ which is used in eigenstate filtering, and $Q_b$, $H_0$, and $H_1$ which are used in QLSP and in particular the Hamiltonian simulation of AQC. We first introduce a simple technique we need to use repeatedly.

Given $U_A$, an $(\alpha,a,0)$-block-encoding of $A$ where $\alpha>0$, we want to construct a block encoding of $A+cI$ for some $c\in{\mathbb{C}}$. This is in fact a special case of the linear combination of unitaries (LCU) technique introduced in [@ChildsKothariSomma2017]. Let $$Q=\frac{1}{\sqrt{\alpha+|c|}}\left(
\begin{array}{cc}
\sqrt{|c|} & -\sqrt{\alpha} \\
\sqrt{\alpha} & \sqrt{|c|}
\end{array}
\right)$$ and $\ket{q}=Q\ket{0}$. Since $(\bra{0^m}\otimes I) U_A (\ket{0^m}\otimes I) = A/\alpha$, we have $$(\bra{q}\bra{0^m}\otimes I) (\ket{0}\bra{0}\otimes e^{i\theta}I + \ket{1}\bra{1}\otimes U_A) (\ket{q}\ket{0^m}\otimes I) = \frac{1}{\alpha+|c|}(A+cI),$$ where $\theta = \mathrm{arg} (c)$. Therefore Fig. \[fig:circuit\_shift\] gives an $(\alpha+|c|,a+1,0)$-block-encoding of $e^{-i\theta}(A+cI)$.

![Quantum circuit for block-encoding of $e^{-i\theta}(A+cI)$, where $c=e^{i\theta}|c|$. $R_{-\theta}$ is a phase shift gate. The three registers are the ancilla qubit for $Q$ and $\ket{q}$, the ancilla register of $U_A$, and the main register, respectively.[]{data-label="fig:circuit_shift"}](plot_shift_block_encoding){width="40.00000%"}

Therefore we may construct an $(\alpha+|\lambda|,m+1,0)$-block-encoding of $H-\lambda I$. We remark that here we do not need the phase shift gate since $\lambda \in {\mathbb{R}}$. This is at the same time a $(1,m+1,0)$-block-encoding of ${\widetilde{H}}=(H-\lambda I)/(\alpha+|\lambda|)$.

Now we construct a block-encoding of $Q_b=I-\ket{b}\bra{b}$ with $\ket{b}=O_B\ket{0}$. Let $S_0=I-2\ket{0}\bra{0}$ be the reflection operator about the hyperplane orthogonal to $\ket{0}$. Then $S_b := O_B S_0 O_B^\dagger = I-2\ket{b}\bra{b}$ is the reflection about the hyperplane orthogonal to $\ket{b}$. Note that $Q_b = (S_b+I)/2$. Therefore we can use the technique illustrated in Fig. \[fig:circuit\_shift\] to construct a $(1,1,0)$-block-encoding of $Q_b$. Here $\ket{q}=\ket{+}=\frac12 (\ket{0}+\ket{1})$. Since $H_0 = \sigma_x \otimes Q_b$, we naturally obtain a $(1,1,0)$-block-encoding of $H_0$. We denote the block-encoding as $U_{H_0}$

For the block-encoding of $H_1$, first note that $$H_1 = \left(
\begin{array}{cc}
I & 0 \\
0 & Q_b 
\end{array}
\right)
\left(
\begin{array}{cc}
0 & A \\
A & 0 
\end{array}
\right)
\left(
\begin{array}{cc}
I & 0 \\
0 & Q_b 
\end{array}
\right).$$

From the block-encoding of $Q_b$, we can construct the block-encoding of controlled-$Q_b$ by replacing all gates with their controlled counterparts. The block matrix in the middle is $\sigma_x \otimes A$. For a $d$-sparse matrix $A$, we have a $(d,n+2,0)$-block-encoding of $A$, and therefore we obtain a block-encoding of $\sigma_x \otimes A$. Then we can use the result for the product of block-encoded matrix [@GilyenSuLowEtAl2019 Lemma 30] to obtain a $(d,n+4,0)$-block-encoding of $H_1$, denoted as $U_{H_1}$.

Gate-based implementation of time-optimal adiabatic quantum computing {#sec:apdx_aqc}
=====================================================================

Consider the adiabatic evolution $$\frac{1}{T}{\imath}\partial_s \left|\psi_T(s)\right> = H(f(s))\left|\psi_T(s)\right>, \quad                        \ket{\psi_T(0)}=\ket{0}\ket{b},$$ Where $H(f)=(1-f)H_0+fH_1$ for $H_0$ and $H_1$ defined in (\[eq:ham\_qlsp\]). It is proved in [@AnLin2019] that the gap between $0$ and the rest of the eigenvalues of $H(f)$ is lower bounded by $1-f+f/\kappa$. With this bound it is proved that in order to get an $\epsilon$-approximate solution of the QLSP for a positive definite $A$ we need to run for time $\mathcal{O}(\kappa/\epsilon)$ using the optimal scheduling [@AnLin2019 Theorem 1].

In order to carry out AQC efficiently using a gate-based implementation, we use the recently developed time-dependent Hamiltonian simulation method based on truncated Dyson series introduced in [@LowWiebe2018]. In Hamiltonian simulation, several types of input models for the Hamiltonian are in use. Hamiltonians can be input as a linear combination of unitaries [@BerryChildsCleveEtAl2015], using its sparsity structure [@AharonovTaShma2003; @LowChuang2017], or using its block-encoding [@LowChuang2019; @LowWiebe2018]. For a time-dependent Hamiltonian Low and Wiebe designed an input model based on block-encoding named HAM-T [@LowWiebe2018 Definition 2], as a block-encoding of $\sum_s\ket{s}\bra{s}\otimes H(s)$ where $s$ is a time step and $H(s)$ is the Hamiltonian at this time step.

In the gate-based implementation of the time-optimal AQC, we construct HAM-T in Fig. \[fig:circuit\_ham\_t\]. We need to use the block-encodings $U_{H_0}$ and $U_{H_1}$ introduced in the previous section. We denote $n_0$ and $n_1$ as the number of ancilla qubits used in the two block-encodings. We know that $n_0=1$ and $n_1=n+4$. Our construction of HAM-T satisfies $$(\bra{s} \bra{0^{l+1+n_0}} \otimes I \otimes \bra{0^{n_1+1}}) \text{HAM-T} 
(\ket{s} \ket{0^{l+1+n_0}} \otimes I \otimes \ket{0^{n_1+1}}) = H(f(s))/d,$$ for any $s\in \mathcal{S}=\{j/2^l:j=0,1,\ldots,2^l-1\}$.

![Quantum circuit for HAM-T. The registers from top to bottom are: (1) input register for $s$ (2) register for storing $f(s)$ (3) register for a control qubit (4) ancilla register for $U_{H_0}$ (5) main register for input state $\ket{\phi}$ (6) ancilla register for $U_{H_1}$ (7) register for changing normalizing factor from $\alpha(s)$ to $d$. []{data-label="fig:circuit_ham_t"}](ham_t_circuit){width="60.00000%"}

In this unitary HAM-T we also need the unitary $$U_{f}\ket{s}\ket{z} = \ket{s}\ket{z\oplus f(s)}$$ to compute the scheduling function needed in the time-optimal AQC, and the unitaries $$\begin{aligned}
V_1 &= \sum_{s\in\mathcal{S}} \ket{s}\bra{s}\otimes\frac{1}{\sqrt{1-s+ds}}\left(
\begin{array}{cc}
\sqrt{1-s} & -\sqrt{ds} \\
\sqrt{ds} & \sqrt{1-s}
\end{array}
\right) \\
V_2 &= \sum_{s\in\mathcal{S}} \ket{s}\bra{s}\otimes\left(
\begin{array}{cc}
\frac{\alpha(s)}{d} & -\sqrt{1-\left(\frac{\alpha(s)}{d}\right)^2} \\
\sqrt{1-\left(\frac{\alpha(s)}{d}\right)^2} & \frac{\alpha(s)}{d}
\end{array}
\right), \\
\end{aligned}$$ where $\alpha(s) = 1-s+ds$. Here $V_1$ is used for preparing the linear combination $(1-f(s))U_{H_0}+f(s)U_{H_1}$. Without $V_2$ the circuit would be a $(\alpha(s),l+n_0+n_1+2,0)$-block-encoding of $\sum_s \ket{s}\bra{s}\otimes H(s)$, but with $V_2$ it becomes a $(d,l+n_0+n_1+2,0)$-block-encoding, so that the normalizing factor is time-independent, as is required for the input model in [@LowWiebe2018]. For the AQC with positive definite $A$ we have $n_0=1$ and $n_1=n+4$. For indefinite case we have $n_0=2$ and $n_1=n+4$.

Following Corollary 4 of [@LowWiebe2018], we may analyze the different components of costs in the Hamiltonian simulation of AQC. For time evolution from $s=0$ to $s=1$, HAM-T is a $(dT,l+n_0+n_1+2,0)$-block-encoding of $\sum_s \ket{s}\bra{s}\otimes TH(s)$. With the scheduling function given in [@AnLin2019] we have $\|TH(s)\|_2=\mathcal{O}(Td)$ and $\|\frac{\mathrm{d(}TH(s))}{\mathrm{d}s}\|_2=\mathcal{O}(dT\kappa^{p-1})$. We choose $p=1.5$ and by Theorem 1 of [@AnLin2019] we have $T=\mathcal{O}(\kappa)$. We only need to simulate up to constant precision, and therefore we can set $l=\mathcal{O}(\log(d\kappa))$. The costs are then

1.  Queries to HAM-T: $\mathcal{O}\left(d\kappa\frac{\log(d\kappa)}{\log\log(d\kappa)}\right)$,

2.  Qubits: $\mathcal{O}(n+\log(d\kappa))$,

3.  Primitive gates: $\mathcal{O}\left(d\kappa(n+\log(d\kappa))\frac{\log(d\kappa)}{\log\log(d\kappa)}\right)$.

The matrix dilation method
==========================

In order to extend the time-optimal AQC method to Hermitian indefinite matrices, we follow [@AnLin2019 Theorem 2], where $H_0$ and $H_1$ are given by $$\begin{aligned}
H_0 &= \sigma_{+}\otimes [(\sigma_z \otimes I_N)Q_{+,b}] + \sigma_{-}\otimes [Q_{+,b}(\sigma_z \otimes I_N)], \\
H_1 &= \sigma_{+}\otimes [(\sigma_z \otimes A)Q_{+,b}] + \sigma_{-}\otimes [Q_{+,b}(\sigma_z \otimes A)].
\end{aligned}
\label{eqn:Hdilation}$$ Here $\sigma_{\pm}=\sigma_x \pm i\sigma_{y}$ and $Q_{+,b}=I_N - \ket{+}\ket{b}\bra{+}\bra{b}$. The dimension of the dilated matrices $H_0,H_1$ is $4N$. The lower bound for the gap of $H(f)$ then becomes $\sqrt{(1-f)^2+f^2/\kappa}$ [@SubasiSommaOrsucci2019]. The initial state is $\ket{0}\ket{-}\ket{b}$ and the goal is to obtain $\ket{0}\ket{+}\ket{x}$. After running the AQC we can remove the second qubit by measuring it with respect to the $\{\ket{+},\ket{-}\}$ basis and accepting the result corresponding to $\ket{+}$. The resulting query complexity remains unchanged. We remark that the matrix dilation here is only needed for AQC. The eigenstate filtering procedure can still be applied to the original matrix of dimension $2N$.

For a general matrix, we may first consider the extended linear system. Define adjoint QLSP as $\ket{y}=(A^{\dagger})^{-1}\ket{b}/{\lVert(A^{\dagger})^{-1}\ket{b}\rVert}_2$, and consider an extended QLSP $\mathfrak{A}\ket{\mathfrak{x}} = \ket{\mathfrak{b}}$ in dimension $2N$ where $$\mathfrak{A} = \sigma_+ \otimes A + \sigma_- \otimes A^{\dagger}
    =\left(\begin{array}{cc}
        0 & A \\
        A^\dagger & 0
    \end{array}\right), \quad  \ket{\mathfrak{b}} = \ket{+,b}.$$ Here $\mathfrak{A}$ is a Hermitian matrix of dimension $2N$, with condition number $\kappa$ and $\|\mathfrak{A}\|_2 = 1$, and $\ket{\mathfrak{x}} := \frac{1}{\sqrt{2}}(\ket{1,x}+\ket{0,y})$ solves the extended QLSP. Therefore the time-optimal AQC can be applied to the Hermitian matrix $\mathfrak{A}$ to prepare an $\epsilon$-approximation of $x$ and $y$ simultaneously. The dimension of the corresponding $H_0,H_1$ matrices is $8N$. Again the matrix dilation method used in Eq. is not needed for the eigenstate filtering step.

Optimal Chebyshev filtering polynomial {#sec:apdx_optimal_poly}
======================================

In this section we prove Lemma \[lem:minimax\_poly\]. We define $$Q_\ell(x;\Delta) = T_{\ell}\left(-1+2\frac{x^2-\Delta^2}{1-\Delta^2}\right),$$ then $R_{\ell}(x;\Delta)=Q_{\ell}(x;\Delta)/Q_{\ell}(0;\Delta)$. We need to use the following lemma:

\[lem:minimax\_poly\_2\] For any $p(x)\in\mathbb{P}_{2\ell}[x]$ satisfying $|p(x)|\leq1$ for all $x\in\mathcal{D}_{\Delta}$, $|Q_{\ell}(x;\Delta)|\geq|p(x)|$ for all $x\notin\mathcal{D}_{\Delta}$.

We prove by contradiction. If there exists $q(x)\in\mathbb{P}_{2\ell}[x]$ such that $|q(x)|\leq1$ for all $x\in\mathcal{D}_\Delta$ and there exists $y\notin\mathcal{D}_\Delta$ such that $|q(y)|>|Q_{\ell}(x;\Delta)|$, then letting $h(x)=Q_{\ell}(x;\Delta)-q(x)\frac{Q_{\ell}(y;\Delta)}{q(y)}$, we want to show $h(x)$ has at least $2\ell+1$ distinct zeros.

First note that there exist $-1=y_{1}<y_{2}<\cdots<y_{\ell+1}=1$ such that $|T_{\ell}(y_{j})|=1$, and $T_{\ell}(y_{j})T_{\ell}(y_{j+1})=-1$. Therefore there exist $\Delta=x_{1}<x_{2}<\cdots<x_{\ell+1}=1$ such that $|Q_{\ell}(\pm x_{j};\Delta)|=1$, and $Q_{\ell}(x_{j};\Delta)Q_{\ell}(x_{j+1};\Delta)=-1$. In other words, $Q_{\ell}(\cdot;\Delta)$ maps each $(x_{j},x_{j+1})$ and $(-x_{j+1},-x_{j})$ to $(-1,1)$, and the mapping is bijective for each interval. Because $|\frac{Q_{\ell}(y;\Delta)}{q(y)}|<1$, there exists $z_{j},w_{j}\in(x_{j},x_{j+1})$ for each $j$ such that $h(z_{j})=h(-w_{j})=0$. Therefore $\{z_{j}\}$ and $\{-w_{j}\}$ give us $2\ell$ distinct zeros. Another zero can be found at $y$ as $h(y)=Q_{\ell}(y)-Q_{\ell}(y)=0$. Therefore there are $2\ell+1$ distinct zeros.

However $h(x)$ is of degree at most $2\ell$. This shows $h(x)\equiv0$. This is clearly impossible since $h(1)=Q_{\ell}(1;\Delta)-q(1)\frac{Q_{\ell}(y;\Delta)}{q(y)}=1-q(1)\frac{Q_{\ell}(y;\delta)}{q(y)}>0$.

Therefore any $y\notin \mathcal{D}_{\Delta}$, $R_\ell(\cdot;\Delta)$ solves the minimax problem $$\underset{\substack{p(x)\in\mathbb{P}_{2\ell}[x] \\ p(y)=R_\ell(y;\Delta)}}{\mathrm{minimize}}  \max_{x\in\mathcal{D}_{\Delta}}|p(x)|.$$ This implies (i) of Lemma \[lem:minimax\_poly\]. To prove (ii), we need to use the following lemma:

Let $T_{\ell}(x)$ be the $\ell$-th Chebyshev polynomial, then $$T_{\ell}(1+\delta)\geq\frac{1}{2}e^{\ell\sqrt{\delta}}$$ for $0\leq\delta\leq3-2\sqrt{2}$.

The Chebyshev polynomial can be rewritten as $T_{\ell}(x)=\frac{1}{2}(z^{\ell}+\frac{1}{z^{\ell}})$ for $x=\frac{1}{2}(z+\frac{1}{z})$. Let $x=1+\delta$, then $z=1+\delta\pm\sqrt{2\delta+\delta^{2}}$. The choice of $\pm$ does not change the value of $x$, so we choose $z=1+\delta+\sqrt{2\delta+\delta^{2}}\geq1+\sqrt{2\delta}$. Since $\log(1+\sqrt{2\delta})\geq\sqrt{2\delta}-\delta\geq\sqrt{\delta}$ for $0\leq\delta\leq 3-2\sqrt{2}$, we have $z^{\ell}\geq e^{\ell\sqrt{\delta}}$. Thus $T_{\ell}(x)\geq\frac{1}{2}e^{\ell\sqrt{\delta}}$.

We use this lemma to prove (ii). Since $|T_\ell(-1+2\frac{-\Delta^2}{1-\Delta^2})|\geq T_\ell(1+2\Delta^2)$, when $\Delta^2\leq 1/12$, we have $2\Delta^2\leq 1/6< 3-2\sqrt{2}$. Thus by the above lemma we have $|T_\ell(-1+2\frac{-\Delta^2}{1-\Delta^2})|\geq \frac{1}{2}e^{\ell\sqrt{2\Delta}}$. Since $|T_\ell(-1+2\frac{x^2-\Delta^2}{1-\Delta^2})|\leq 1$ for $x\in\mathcal{D}_\Delta$, we have the inequality in (ii). (iii) follows straightforwardly from the monotonicity of Chebyshev polynomials outside of $[-1,1]$.
