E Approximation theory
In this section we collect some polynomial approximation of useful functions that can be used in your quantum algorithms. As we learned in Section 5.4.3, in order to obtain efficient quantum algorithms we often need a low-degree polynomial approximation of certain functions. This is an interesting link between approximation theory (where it’s relatively easy to obtain some lower bounds) and quantum algorithms. We will start by recalling an important tool in approximation theory.
Chebyshev polynomials play an important role in approximation theory (see, for example, (Iske 2018)).
Definition E.1 (Chebyshev polynomial) For \(n \in \mathbb{N}_{0}\), the Chebyshev polynomial \(T_{n}\) of degree \(n\) is the function defined on the interval \([-1, \, 1]\) by \[T_{n}(x) := \cos (n \arccos(x)).\]
E.1 Polynomial approximation of \(\log(x)\)
Lemma E.1 (Polynomial approximations of logarithm (Gilyén and Li 2019)) Let \(\beta\in(0,1]\), \(\epsilon\in(0,{1}/{6}]\). Then there exists a polynomial \(\tilde{S}\) of degree \(O({\frac{1}{\beta}\log (\frac{1}{\epsilon} )})\) such that \(|\tilde{S}(x)-\frac{\log_b(x)}{3\log_b(2/\beta)}|\leq\epsilon\) for all \(x \in [\beta,1]\) and base \(b \in \mathbb{N}\), and for all \(x\in [-1,1]\) \(1/2\leq \tilde{S}(x) = \tilde{S}(-x) \leq 1/2\).
E.2 Polynomial approximation of \(1/x\)
We are going to approximate \(1/x\) using Chebychev polynomial, with some additional tricks, which will be used to decrease the degree of the polynomial approximation. As
The function \(1/x\) has an essential discontinuity in \(x=0\) since
\[\lim_{x\to 0-} \frac{1}{x} = -\infty \text{ and } \lim_{x\to 0+} \frac{1}{x} = +\infty.\]
In this section we will follow (Childs, Kothari, and Somma 2017) and show that \(1/x\) can be approximated arbitrarily closely on the set \([-1,\, -\delta ] \cup [\delta,\, 1 ]\), where \(0<\delta<1\), by a linear combination of Chebyshev polynomials. We start by approximating \(1/x\) with the following function:
\[\begin{equation} g_{b}(x) := \begin{cases} (1-(1-x^{2})^{b})/x, \text{ if } x \in \mathbb{R}\setminus\{0\}\\ 0, \text{ if } x=0 \end{cases} \tag{E.1} \end{equation}\] where \(b>0\) is a positive constant.
Lemma E.2 The function (E.1) is continuous in \(\mathbb{R}\).
Proof. We need to show the continuity of \(g_{b}\) in \(x=0\). This follows by an application of L’Hôpital’s rule: \[ \lim_{x\to 0} \frac{1-(1-x^{2})^{b}}{x} = \lim_{x\to 0} \frac{2bx(1-x^{2})^{b-1}}{1} = 0 = g_{b}(0).\]
The following lemma shows that \(g_{b}\) approximates \(1/x\) arbitrarily closely on the set \([-1,\, -\delta ] \cup [\delta,\, 1 ]\), \(0<\delta<1\), if \(b\) is large enough.
Lemma E.3 Let \(\epsilon>0\) and \(0<\delta<1\). If \(b \ge \max \{1, \delta^{-2}\log(1/(\epsilon \delta))\}\), then \(|g_{b}(x)-1/x|<\epsilon\) for all \(x \in [-1,\, -\delta ] \cup [\delta,\, 1 ]\).
Proof. From the inequality \(e^{a}\ge 1+a\), \(a \in \mathbb{R}\), and \(b>1\) it follows with \(a:=-\delta^{2}\) \[ (1-\delta^{2})^{b} \le e^{-\delta^{2} b}.\] Therefore, for \(x \in [-1,\, -\delta ] \cup [\delta,\, 1 ]\) we have \[ \left| g_{b}(x)-\frac{1}{x} \right| = \frac{(1-x^{2})^{b}}{|x|} \le \frac{(1-\delta^{2})^{b}}{\delta} \le \frac{e^{-\delta^{2} b}}{\delta} \le \epsilon.\]
The following lemma shows that \(g_{m}\), \(m \in \mathbb{N}\), is on the interval \([-1, \, 1]\) equal to a linear combination of Chebyshev polynomials of degree at most \(2m-1\).
Lemma E.4 Let \(m \in \mathbb{N}\) be a positive integer. Then,
\[\begin{equation} g_{m}(x) = 4 \sum_{n=0}^{m-1} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \tag{E.2} \end{equation}\]
for all \(x \in [-1, \, 1]\).
Proof. For \(x=0\) the equality (E.2) follows from the definitions of Chebyshev polynomials and \(g_{m}\). We are left with the task to prove
\[\frac{1-(1-x^{2})^{m}}{x} = 4 \sum_{n=0}^{m-1} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \] for all \(x \in [-1, \, 1]\setminus\{0\}\). Choose \(\theta \in \mathbb{R}\) such that \(x=\cos (\theta)\). Because \(\sin^{2}(\theta) + \cos^{2}(\theta) = 1\) and \(T_{n}(\cos (\theta))= \cos (n \theta)\), we need to prove that
\[\begin{equation} 1 - \sin^{2m}(\theta) = 4 \sum_{n=0}^{m-1} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) \cos ((2n+1)\theta) \cos (\theta), \tag{E.3} \end{equation}\] where in the previous equation we moved \(\cos(\theta)\) from the denominator of the l.h.s. to the r.h.s..
In order to complete the proof we can proceed in two different ways. Either we will write the left and right side of Equation (E.3) respectively in the form
\[\begin{equation} \sum_{j=0}^{m} a_{j} \cos(2j\theta) \text{ and } \sum_{j=0}^{m} b_{j} \cos(2j\theta), \tag{E.4} \end{equation}\]
and, finally, verify that \(a_{j}=b_{j}\) for all \(j \in \{0,\,\dots,\,m\}\). This approach follows the original proof of (Childs, Kothari, and Somma 2017). Another way is to just convert the l.h.s. of Equation (E.3) so it matches the coefficients of the r.h.s. We will start with the second approach, as it is the canonical one, but we discuss the second one later, as it is the one presented in the original proof.
Using the binomial formula for complex numbers \(a,\,b \in \mathbb{C}\) and \(p \in \mathbb{N}_{0}\), which is stated in Theorem A.6
\[ (a+b)^{p}= \sum_{j=0}^{p}\binom{p}{j} a^{p-j}b^{j},\] we obtain a nice expansion of the \(\sin(\theta)^{2m}\) as:
\[\begin{equation*} \begin{split} \sin^{2m}(\theta) & = \left(\frac{e^{i\theta}-e^{-i\theta}}{2i}\right)^{2m}\\ & = \frac{1}{2^{2m}i^{2m}} \sum_{j=0}^{2m}\binom{2m}{j} (-e^{-i\theta})^{2m-j}(e^{i\theta})^{j}\\ & = \frac{(-1)^{m}}{2^{2m}} \sum_{j=0}^{2m}\binom{2m}{j} (-1)^{j} e^{i(2j-2m)\theta} \\ & = \frac{1}{2^{2m}}\binom{2m}{m} + \frac{(-1)^{m}}{2^{2m}} \sum_{j=0}^{m-1} \left( \binom{2m}{j} (-1)^{j} e^{i(2j-2m)\theta} + \binom{2m}{2m-j} (-1)^{2m-j} e^{-i(2j-2m)\theta}\right) \\ & = \frac{1}{2^{2m}}\binom{2m}{m} + \frac{2}{2^{2m}} \sum_{j=0}^{m-1} \binom{2m}{j} (-1)^{m-j} \frac{e^{i(2j-2m)\theta}+e^{-i(2j-2m)\theta}}{2}\\ & = \frac{1}{2^{2m}}\binom{2m}{m} + \frac{2}{2^{2m}} \sum_{j=0}^{m-1} \binom{2m}{j} (-1)^{m-j} \cos(2(j-m)\theta). \end{split} \end{equation*}\]
To give more context on some of the steps in the previous series of equations, we have done the following:
- we wrote the \(\sin\) using the euler formula.
- we used the binomial theorem
- we used that \((-1)^{j}=(-1)^{2m-j}\) to factor out the minus sign
- we exploited the symmetry of the binomial, and removed the middle term (\(\frac{1}{2^{2m}}\binom{2m}{m}\)) from the summation.
- we collect back the \((-1)^m\) in the summation
- we used again Euler formula (multiplying and dividing everything by \(2\)) to obtain a \(\cos\) in the summation.
Thus, we have \[\begin{equation} 1-\sin^{2m}(\theta) = \left( 1-\frac{1}{2^{2m}}\binom{2m}{m}\right)+\frac{2}{2^{2m}} \sum_{j=0}^{m-1} (-1)^{m-j-1} \binom{2m}{j} \cos(2(j-m)\theta). \tag{E.5} \end{equation}\]
Note that we factored the \(-\) sign in the third term in the exponent of the \((-1)\) factor. Now we perform a substitution, and set \(k=m-j\). Recall that cosine is an even function, and thus \(\cos(2(j-m)\theta) = \cos(2(m-j)\theta) =\cos(2k\theta)\). Also recalling again the symmetry of the binomial coefficients, i.e. \(\binom{2m}{j} = \binom{2m}{2m-j} = \binom{2m}{m+k}\), we can rewrite our function as:
\[\begin{equation} 1 - \sin^{2m}(\theta) = 1 - \frac{1}{2^{2m}} \binom{2m}{m} + \frac{2}{2^{2m}} \sum_{k=1}^{m} \binom{2m}{m+k} (-1)^{k-1} \cos(2k\theta)\,. \end{equation}\]
Note also that because of the substition step, now we have the index of \(k\) that goes from \(1\) to \(m\). Now we have a first trick: \(2^{2m}=(1+1)^{2m} = \sum_{i=0}^{2m} \binom{2m}{i}\).This allows to rewrite the first two terms of the summation as:
\[\begin{equation} 1 - \frac{1}{2^{2m}} \binom{2m}{m} = \frac{2^{2m}-\binom{2m}{m}}{2^{2m}} = \frac{1}{2^{2m}}\sum_{k=1}^{m} \left( \binom{2m}{m+k} + \binom{2m}{m-k} \right) = \frac{2}{2^{2m}}\sum_{k=1}^{m} \binom{2m}{m+k} \,. \end{equation}\]
Where we used the fact that \(\binom{2m}{m}\) is the central term in \(\sum_{i=0}^{2m} \binom{2m}{i}\), and its symmetry again. Thus, the whole equation can be rewritten by factoring \(\binom{2m}{m+k}\) as:
\[\begin{align} 1 - \sin^{2m}(\theta) = &\frac{2}{2^{2m}}\sum_{k=1}^{m} \binom{2m}{m+k}+ \frac{2}{2^{2m}} \sum_{k=1}^{m} \binom{2m}{m+k} (-1)^{k-1} \cos(2k\theta)\\ = & 1 - \sin^{2m}(\theta) =\frac{2}{2^{2m}} \sum_{k=1}^{m} \binom{2m}{m+k} \times \Big(1+(-1)^{k-1} \cos(2k\theta)\Big)\,, \end{align}\]
Now we rewrite the last factor as a telescoping sum as: \[\begin{equation} 1+(-1)^{k-1} \cos(2k\theta) = \sum_{n=0}^{k-1} (-1)^n \left( \cos(2\theta (n+1)) + \cos(2\theta n) \right)\,. \end{equation}\]
Now, we want to obtain a product of cosines, as Equation (E.3), we use the standard formula (Section A.5.0.1) of \(\cos(x+y)+\cos(x-y)=2\cos(x)\cos(y)\). Specifically, we set \(x+y=2\theta (n+1)\) and \(x-y = 2\theta n\), so we obtain the value of \(x=(2n+1)\theta\) and \(y = \theta\). Thanks to these two passages we can rewrite
\[\begin{equation} 1-\sin^{2m}(\theta) =\frac{2}{2^{2m}} \sum_{k=1}^{m} \binom{2m}{m+k} \times \Big(2\sum_{n=0}^{k-1} (-1)^n \cos((2n+1)\theta) \cos \theta\Big)\,. \end{equation}\]
We need one more step to obtain the coefficients of the Chebychev polynomial from the previous equation, which is a simple change in the order of the summations. To be very explicit, we are just using the following observation: \[\sum_{k=1}^m f_k (\sum_{n=0}^{k-1} c_n) = \sum_{k=1}^m \sum_{n=0}^{k-1}f_kc_n = \sum_{n=1}^{m-1}c_n(\sum_{k=n+1}^m f_k).\]
Thus, we obtain
\[\begin{equation} 1-\sin^{2m}(\theta) = \frac{4}{2^{2m}} \sum_{n=0}^{m-1} ((-1)^n \left( \sum_{k=n+1}^m \binom{2m}{m+k}\right) \cos((2n+1)\theta)\cos(\theta)). \end{equation}\]
The proof ends here, but for completeness, we report the other approach here. We can start by comparing comparing the first equation of (E.4) with (E.5), we obtain the following formulas for \(a_{j}\): \[\begin{equation*} a_{j} = \begin{cases} 1-\frac{1}{2^{2m}}\binom{2m}{m}, \text{ if } j=0\\ (-1)^{j-1} \frac{2}{2^{2m}} \binom{2m}{m-j}, \text{ if } j \in \{1,\,\dots,m\}. \end{cases} \end{equation*}\]
Using the trigonometric identity \(2\cos(\theta_{1})\cos(\theta_{2})=\cos(\theta_{1}-\theta_{2}) +\cos(\theta_{1}+\theta_{2})\), the right side of (E.3) simplifies to \[\begin{equation} 2 \sum_{n=0}^{m-1} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) (\cos ((2n+2)\theta) +\cos ((2n)\theta)). \tag{E.6} \end{equation}\]
Comparing the second equation of (E.4) with (E.6), we obtain the following formulas for \(b_{k}\): \[\begin{equation*} \begin{split} b_{0} & = \frac{2}{2^{2m}}\sum_{k=1}^{m}\binom{2m}{m+k}=\frac{1}{2^{2m}}\left(\sum_{k=1}^{m} \binom{2m}{m+k}+\sum_{k=1}^{m} \binom{2m}{m+k} \right) \\ & = \frac{1}{2^{2m}} \left(\sum_{k=1}^{m} \binom{2m}{m-k}+\sum_{k=m+1}^{2m} \binom{2m}{k} \right) \\ & = \frac{1}{2^{2m}} \left(\sum_{k=0}^{m-1} \binom{2m}{k}+\sum_{k=m+1}^{2m} \binom{2m}{k} \right) \\ & = \frac{1}{2^{2m}} \left(\sum_{k=0}^{2m} \binom{2m}{k}- \binom{2m}{m} \right) \\ & = 1 - \frac{1}{2^{2m}} \binom{2m}{m}, \end{split} \end{equation*}\]
and, for \(j \in \{1,\, \dots, \, m-1 \}\), \[\begin{equation*} \begin{split} b_{j} & = \frac{2}{2^{2m}} (-1)^{j-1} \sum_{l=j}^{m}\binom{2m}{m+l} + \frac{2}{2^{2m}} (-1)^{j} \sum_{l=j+1}^{m}\binom{2m}{m+l} \\ & = \frac{2}{2^{2m}} (-1)^{j-1} \binom{2m}{m+j} \\ & = \frac{2}{2^{2m}} (-1)^{j-1} \binom{2m}{m-j}, \end{split} \end{equation*}\]
and, for \(j = m\), \[\begin{equation*} b_{m} = \frac{1}{2^{2m}} (-1)^{m-1} \binom{2m}{2m} = \frac{(-1)^{m-1}}{2^{2m}}. \end{equation*}\] Thus, \(a_{j}=b_{j}\) for all \(j \in \{0,\,\dots,\,m\}\).
Although \(g_{m}\) is the sum of \(m\) Chebyshev polynomials, the following lemma shows that for \(m\) large enough the sum can be truncated while still remaining close to \(g_{m}\).
Lemma E.5 Let \(0<\epsilon<1\) and \(m \in \mathbb{N} \cap [2, \, \infty [\). Set \(k_{0}:=\min \{m-1, \, \lfloor \sqrt{3m \log(4(m-1)/\epsilon) }\rfloor \}\). Then,
\[\begin{equation} \left| g_{m}(x) - 4 \sum_{n=0}^{k_{0}} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \right| \le \epsilon \tag{E.7} \end{equation}\]
for all \(x \in [-1, \, 1]\).
Proof. If \(k_{0}=m-1\) then we know from Lemma E.4 that the left side of Inequality (E.7) is 0. Next, assume \(k_{0}<m-1\). Consider a random variable \(X\) that follows the binomial distribution with parameters \(2m\) and \(1/2\). It is very simple to see that the expected value of this random variable is just \(m\). The probability of getting at least \(m+n+1\), \(n<m\), successes in \(2m\) independent Bernoulli trials is given by
\[ \Pr(X \ge m+n+1) = \frac{1}{2^{2m}} \sum_{k=n+1}^{m} \binom{2m}{m+k}.\] On the other hand, the Chernoff bound of Theorem C.8 gives \[ \Pr(X \ge m+k+1) = \Pr\left(X \ge \left(1+\frac{k+1}{m}\right)m\right) \le e^{\frac{-((k+1)/m)^{2}m}{2+(k+1)/m}} \le e^{-\frac{k^{2}}{3m}}.\]
Therefore, we have
\[\begin{equation*} \begin{split} \left| g_{m}(x) - 4 \sum_{n=0}^{k_{0}} (-1)^{n} \left( \frac{\sum_{k=n+1}^{m} \binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \right| & = \left| 4 \sum_{n=k_{0}+1}^{m-1} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \right| \\ & \le \left| 4 \sum_{n=k_{0}+1}^{m-1} e^{-\frac{k^{2}}{3m}} T_{2n+1}(x) \right| \\ & \le 4 (m-1) e^{-\frac{k_{0}^{2}}{3m}} \\ & \le \epsilon, \\ \end{split} \end{equation*}\] where we used the fact the \(T_{2n+1}(x)| \le 1\) for \(x \in [-1, \, 1]\).
We are now ready to state the main result of this section that expresses the fact that the function \(1/x\) can be approximated arbitrarily closely by linear combination of Chebyshev polynomials with a minimal number of terms.
Corollary E.1 (Low degree polynomial approximation of 1/x) Let \(0<\epsilon<1\) and \(0<\delta<1\). Set \(m := \lceil \delta^{-2}\log(2/(\epsilon \delta))\rceil\) and \(k_{0}:=0\) if \(m=1\) or \(k_{0}:=\min \{m-1, \, \lfloor \sqrt{3m \log(8(m-1)/\epsilon) }\rfloor \}\) otherwise. Then, \[\begin{equation} \left| \frac{1}{x} - 4 \sum_{n=0}^{k_{0}} (-1)^{n} \left(\frac{\sum_{k=n+1}^{m}\binom{2m}{m+k}}{2^{2m}} \right) T_{2n+1}(x) \right| \le \epsilon \tag{E.8} \end{equation}\] for all \(x \in [-1,\, -\delta ] \cup [\delta,\, 1 ]\).
Interestingly, there is another way of obtaining the decomposition of \(\frac{1-(1-x^2)^{2m}}{x}\) with Chebychev polynomials, which is more akin to the canonical way one would approach the problem, so we report it here as an exercise, as it might be more mathematically challenging to solve than what we presented before.
Exercise E.1 Can you prove Lemma E.4 using the orthogonality of Chebychev polynomials?
Proof. We give just a hint for the proof.
\[\begin{equation} \frac{1}{(1-x^2)^{2m}}{x} = \sum_{n=0}^\infty a_n T_n(x) \end{equation}\]
what we want is an explicit expression for \(a_n\), so we exploit the orthogonality of Chebychev polynomials (which are orthogonal under the measure \(\mu(x)=\frac{1}{\sqrt{1-x^2}}\) on the interval \([1,1]\), i.e. we have:
\[\begin{equation} \int_{-1}^1 T_n(x)\,T_m(x)\,\frac{\mathrm{d}x}{\sqrt{1-x^2}} = \begin{cases} 0 & if n \ne m, \\ \pi & if n=m=0, \\ \frac{\pi}{2} & if n=m \ne 0. \end{cases} \end{equation}\]
Therefore, multiplying by a polynomial \(T_l(x)\) and the measure \(\mu(x)\) on both sides, we can read
\[\begin{equation} \int_{-1}^{1} \frac{1-(1-x^2)^{2m}}{x} \frac{T_l(x)}{\sqrt{1-x^2}} = \int_{-1}^{1} \sum_{n=0}^\infty a_n \frac{T_nT_l}{\sqrt{1-x^2}} = \sum_{n=0}^\infty a_n \frac{\pi}{2}dx = \frac{\pi}{2} a_n. \end{equation}\]
The task now is to compute the integral on the l.h.s..