Proof. Let \(g(\theta) \mathrel{\vcenter{:}}= f(\cos\theta)\), and recall that \(c_k=\frac{2}{\pi}\int_{-\pi}^{0} g(\theta)\cos(k\theta)\,d\theta\). The \(\ell_1\) norm of the coefficient vector \(\hat{\mathbf{c}}\) can be expressed as \[\label{eq:coeff-vec-l1-norm} \norm{\hat{\mathbf{c}}}_1 = \abs{c_0} + \sum_{k=1}^d \abs{c_k} + \sum_{k=d+1}^{2d-1} \frac{2d-k}{d} \abs{c_k} \mathrel{\vcenter{:}}= \abs{c_0} + \sum_{k=1}^{2d-1} w_k \abs{c_k}.\tag{4}\]

We begin by bounding the zeroth coefficient: \[\label{eq:zeroth-coeff-upper-bound} \abs{c_0} = \abs*{ \frac{2}{\pi}\int_{-\pi}^{0} g(\theta)\,\mathrm{d}\theta } \leq \frac{2}{\pi}\int_{-\pi}^{0}|g(\theta)|\,\mathrm{d}\theta \leq 2B_0.\tag{5}\]

[thmitem:l1-norm-bound-general]: the general case. By Parseval’s identity (e.g., [92]) for the cosine Fourier coefficients of \(g\), we obtain \[\label{eq:nonzeroth-coeff-general} \sum_{k=1}^{\infty}\abs{c_k}^2 \leq \frac{\abs{c_0}^2}{2}+\sum_{k=1}^{\infty}\abs{c_k}^2 = \frac{2}{\pi}\int_{-\pi}^{0}\abs{g(\theta)}^2\,\mathrm{d}\theta \leq 2B_0^2.\tag{6}\] Here, the last inequality uses \(\abs{g(\theta)}\leq B_0\).

Applying the Cauchy–Schwarz inequality to 4 , it follows that \[\label{eq:coeff-general-bound} \begin{align} \norm{\hat{\mathbf{c}}}_1 &= \abs{c_0} + \sum_{k=1}^{2d-1} w_k \abs{c_k} \\ &\leq 2B_0 + \rbra*{ \sum_{k=1}^{2d-1} w_k^2 }^{1/2} \rbra*{ \sum_{k=1}^{2d-1}|c_k|^2 }^{1/2}\\ &\leq 2B_0 + \rbra*{ \frac{4d}{3} }^{1/2} \sqrt{2} B_0 \leq O(B_0\sqrt{d}). \end{align}\tag{7}\] Here, the second line follows from 5 , and the third line follows from 6 and the fact that \[\sum_{k=1}^{2d-1} w_k^2 = \sum_{k=1}^{d}1+\sum_{k=d+1}^{2d-1}\rbra*{ \frac{2d-k}{d} }^2 = d+\frac{1}{d^2}\sum_{j=1}^{d-1}j^2 \leq \frac{4d}{3}.\]

[thmitem:l1-norm-bound-first-conti]: absolutely continuous with bounded angular first derivative. For every \(k\geq 1\), integration by parts gives \[\label{eq:coeff-first-conti} \begin{align} \abs{c_k} &= \abs*{\frac{2}{\pi}\int_{-\pi}^{0} g(\theta)\cos(k\theta)\,\mathrm{d}\theta}\\ &= \abs*{\frac{2}{\pi} \cdot \frac{g(\theta)\sin(k\theta)}{k} \bigg|_{-\pi}^{0} - \frac{2}{\pi k}\int_{-\pi}^{0} g'(\theta)\sin(k\theta)\,\mathrm{d}\theta}\\ &\leq \frac{2}{\pi k}\int_{-\pi}^{0}|g'(\theta)|\,\mathrm{d}\theta\\ &\leq \frac{2B_1}{\pi k}. \end{align}\tag{8}\] Here, the third line follows from \(\frac{g(\theta)\sin(k\theta)}{k} \big|_{-\pi}^{0} = 0\) as \(\sin(0)=\sin(-k\pi)=0\), and the last line uses the condition \(\int_{-\pi}^{0}|g'(\theta)|\,\mathrm{d}\theta\leq B_1\).

Plugging [eq:zeroth-coeff-upper-bound,eq:coeff-first-conti] into 4 , we conclude that \[\norm{\hat{\mathbf{c}}}_1 = \abs{c_0} + \sum_{k=1}^{2d-1} w_k \abs{c_k} \leq \abs{c_0} + \sum_{k=1}^{2d-1} \abs{c_k} \leq 2B_0 + \frac{2B_1}{\pi}\sum_{k=1}^{2d-1}\frac{1}{k} \leq O(B_0 + B_1 \log{d}).\] Here, the first inequality uses the fact that \(0 \leq w_k \leq 1\), and the last inequality follows from the Euler–Maclaurin formula.

[thmitem:l1-norm-bound-twice-conti]: twice continuously differentiable with bounded angular second derivative. Analogously to 8 , integrating by parts once more, for any \(k\ge 1\), it follows that \[\label{eq:coeff-twice-conti} \begin{align} \abs{c_k} &= \abs*{- \frac{2}{\pi k}\int_{-\pi}^{0} g'(\theta)\sin(k\theta)\,\mathrm{d}\theta}\\ &= \frac{2}{\pi k} \abs*{ -\frac{g'(\theta)\cos(k\theta)}{k} \bigg|_{-\pi}^{0} +\frac{1}{k}\int_{-\pi}^{0} g''(\theta)\cos(k\theta)\,\mathrm{d}\theta }\\ &\leq \frac{2}{\pi k^2}\int_{-\pi}^{0}|g''(\theta)|\,\mathrm{d}\theta\\ &\leq \frac{2B_2}{\pi k^2}. \end{align}\tag{9}\] Here, the boundary term vanishes in the third line because \(g'(-\pi)=g'(0)=0\), as \(g'(\theta)=-f'(\cos\theta)\sin\theta\), and the last line uses the condition \(\int_{-\pi}^{0}\left|g''(\theta)\right|\,\mathrm{d}\theta \leq B_2\).

Plugging [eq:zeroth-coeff-upper-bound,eq:coeff-twice-conti] into 4 , we conclude that \[\norm{\hat{\mathbf{c}}}_1 \leq \abs{c_0} + \sum_{k=1}^{2d-1} \abs{c_k} \leq 2B_0 + \frac{2B_2}{\pi}\sum_{k=1}^{2d-1}\frac{1}{k^2} \leq O(B_0 + B_2).\] Here, the last inequality also follows from the Euler–Maclaurin formula. ◻

Proof. Consider a \(m\)-time sequential repetition of the algorithm \(\mathcal{A}\), and let \(X_i\) be a random variable indicating whether the \(i\)-th repetition succeeds, then we obtain a random variable \(X = \frac{1}{m} \sum_{i=1}^m X_i\) such that \(\mathbb{E}[X]=p\). Now let \(\hat{X}=\frac{1}{m} \sum_{i=1}^m \hat{X}_i\) be the additive-error estimation, where \(\hat{X}_i\) is the outcome of \(\mathcal{A}\) in the \(i\)-th repetition. By the Chernoff–Hoeffding bound (e.g., [93]), we know that \[\mathrm{Pr}\!\left[|\hat{X}-p|\geq \epsilon\right] \leq 2\exp(-2m\epsilon^2).\] By choosing \(m=\ceil*{2/\epsilon^{2}}\), this choice of \(m\) ensures that this procedure based on \(\mathcal{A}\) succeeds with probability at least \(2/3\).

Furthermore, the space complexity of our algorithm is \(O(\log{m}) = O(\log{1/\epsilon}) = O(s(n))\) since we can simply reuse the workspace. Also, the time complexity is \(m\cdot t(n) = O(\epsilon^{-2} t(n))\) as desired. ◻

Proof. Our randomized algorithm leverages the equivalence between space-bounded randomized computation and Markov chains, see [95] for a detailed introduction.

First, we construct a row-stochastic matrix \(\hat{B}\) from \(B\) by adding an additional column and row. Let \(\hat{B}[i,j]\) denote the entry at the \(i\)-th column and the \(j\)-th row of \(\hat{B}\). Specifically, \[\hat{B}[i,j] \mathrel{\vcenter{:}}= \begin{cases} B[i,j], & \text{ if } 1 \leq i,j \leq l;\\ 1-\sum_{s=j}^{l} B[s,j],& \text{ if } i=l+1 \text{ and } 1\leq j \leq l+1;\\ 0, & \text{ if } 1 \leq i \leq l \text{ and } j=l+1.\\ \end{cases}\]

Next, we view \(\hat{B}\) as a transition matrix of a Markov chain since \(\hat{B}\) is row-stochastic. We consequently have a random walk on the directed graph \(G=(V,E)\) where \(V=\{1,2,\cdots,l\}\cup \{\perp\}\) and \((u,v)\in E\) iff \(\hat{B}(u,v)>0\). In particular, the probability that a \(k\)-step random walk starting at node \(s\) and ending at node \(t\) is exactly \(\hat{B}^k[s,t]=B^k[s,t]\). This is because the walker who visits the dummy node \(\perp\) will not reach other nodes.

Finally, note that \(\hat{B}\) is a \((l+1)\times (l+1)\) matrix, the matrix powering of \(\hat{B}^k\) can be computed in \(O(\log{l}+\log{k})\) space. In addition, the overall time complexity is \(O(\ell k)\) since we simulate the dyadic rationals (with \(\ell\)-bit precision) of a single transition exactly by \(\ell\) coin flips. ◻

Proof. We begin with the polynomial approximation \(P^{(f)}_{d'}\) obtained from the degree-\(d\) averaged Chebyshev truncation expressed in ?? . The degree \(d'\) is \(2d-1\) if \(f\) is odd, and \(2d-2\) if \(f\) is even. To bound the truncation error of \(P^{(f)}_{d'}\), we require a degree-\(d\) polynomial \(P^*_{f,d}\) such that \(\max_{x\in[-1,1]} |f(x)-P^*_{f,d} (x)| \leq \epsilon\). By utilizing 6, we obtain the desired error bound \(\max_{x\in[-1,1]} |f(x)-P^{(f)}_{d'}(x)| \leq 4\epsilon\).

Computing the coefficients.

To compute the coefficients \(\hat{c}_k\) for \(0 \leq k \leq d'\), it suffices to compute the Chebyshev coefficients \(c_k\) for \(0 \leq k \leq 2d-1\). Noting that \(c_k = \frac{2}{\pi}\int_{-\pi}^{0} F_k(\theta) \mathrm{d}\theta\) where \(F_k(\theta)\mathrel{\vcenter{:}}=\cos(k \theta) f(\cos{\theta})\), we can estimate the numerical integration using the composite trapezium rule, e.g., [96]. The application of this method yields the following: \[\label{eq:integration-summations} \begin{align} \int_{-\pi}^{0} \!F_k(\theta) \mathrm{d}\theta &\approx \frac{\pi}{m} \rbra*{ \frac{F_k(\theta_0)}{2} + \sum_{l=1}^{m-1} F_k(\theta_l) + \frac{F_k(\theta_m)}{2} },\\ \text{ where } \theta_l &\mathrel{\vcenter{:}}= \frac{\pi l}{m}-\pi \text{ for } l=0,1,\cdots,m. \end{align}\tag{10}\] Moreover, we know the upper bound on the numerical errors for computing the coefficient \(c_k\): \[\label{eq:integration-errors} \varepsilon_{d',k}^{(f)} \mathrel{\vcenter{:}}= \sum_{l=1}^m \abs*{ \int_{\theta_{l-1}}^{\theta_l} F_k(\theta)\mathrm{d}\theta - \frac{\pi}{2m} \cdot \left( F_k(\theta_{l-1}) + F_k(\theta_l) \right) } \leq \frac{\pi^3}{12m^2} \max_{\xi\in[-\pi,0]} \abs*{ F_k''(\xi) }.\tag{11}\] To obtain an upper bound on the number of intervals \(m\), we need to ensure that the error of the numerical integration is within \[\varepsilon_{d'}^{(f)} = \sum_{k=0}^d \varepsilon^{(f)}_{d',k} + \sum_{k=d+1}^{d'} \frac{2d-k}{d} \varepsilon^{(f)}_{d',k} \leq \sum_{k=0}^{d'} \varepsilon^{(f)}_{d',k} \leq \epsilon.\] Plugging the assumption \(|F_k''(\xi)| \leq O(d^{\gamma})\) into 11 , by choosing an appropriate value of \(m=\Theta(\epsilon^{-1/2}d^{(\gamma+1)/2})\), we establish that \(\varepsilon^{(f)}_{d'} \leq O(d^{\gamma+1})/m^2 \leq \epsilon\). Moreover, to guarantee that the accumulated error is \(O(\epsilon/d)\) in 10 , we need to evaluate the integrand \(F_k(\theta)\) with \(\ell\)-bit precision, where \(\ell=O(\log{(dm/\epsilon)})=O(\log(\epsilon^{-3/2}d^{(\gamma+3)/2}))\).

Lastly, the desired \(\ell_1\)-norm bounds for the coefficient vector \(\hat{\mathbf{c}}\) follow directly from 7 by setting that \(B_0\mathrel{\vcenter{:}}= B\) and, in [thmitem:polyApprox-l1-norm-bound-first-conti,thmitem:polyApprox-l1-norm-bound-twice-conti], using the assumed angular derivative bounds as \(B_1=O(B)\) and \(B_2=O(B)\).

Analyzing time and space complexity.

The presented numerical integration algorithm is deterministic, and therefore, the time complexity for computing the integral is \(O(m t(\ell))\), where \(t(\ell)\) is the time complexity for evaluating the integrand \(F_k(\theta)\) within \(2^{-\ell}\) accuracy (i.e., \(\ell\)-bit precision) in \(O(\ell)\) space. The space complexity required for computing the numerical integration is the number of bits required to index the integral intervals and represent the resulting coefficients. To be specific, the space complexity is \[\begin{align} \max\big\{O(\log{m}),O(\ell),\log\|\hat{\mathbf{c}}\|_{\infty}\big\} &\leq O\big(\max\big\{ \log\big(\epsilon^{-\frac{3}{2}}d^{\frac{\gamma+3}{2}}\big),\log B \big\} \big) \\ &\leq O\big(\log\big(\epsilon^{-\frac{3}{2}}d^{\frac{\gamma+3}{2}}B\big)\big). \end{align}\] Here, \(\|\hat{\mathbf{c}}\|_{\infty}\) satisfies the upper bound \[\|\hat{\mathbf{c}}\|_{\infty} = \max_{0 \leq k \leq d'} \frac{2}{\pi} \abs*{\int_{-\pi}^0 \cos(k\theta) f(\cos{\theta}) \mathrm{d}\theta} \leq \max_{-\pi \leq \theta \leq 0} O(|f(\cos\theta)|) \leq O(B),\] and the last inequality is due to the fact that \[\forall A, B > 0, ~\Theta(\max\{\log A, \log B\}) = \Theta(\log(AB)). \qedhere\] ◻

Proof. We start from a degree-\(d\) polynomial \(\tilde{P}_d^\mathrm{sgn}\) that well-approximates \(\mathrm{sgn}(x)\):

By [prop:poly-approx-sgn], we obtain a degree-\(d\) polynomial \(\tilde{P}^\mathrm{sgn}_d\) that well approximates the function \(\mathop{\mathrm{erf}}(\kappa x)\) where \(\kappa=O(\delta^{-1}\sqrt{\log{\epsilon^{-1}}})\).

To utilize 11, it suffices to upper bound the second derivative \(\max_{\xi \in [-\pi,0]}|F_k''(\xi)|\) for any \(0 \leq k \leq d'\), as specified in [fact:sign-func-derivative-bound]. The proof is deferred to the end of this part.

Note that both \(\kappa\) and \(k\) are at most \(O(d)\). By [fact:sign-func-derivative-bound], we have \(\max_{\xi \in [-\pi,0]}|F_k''(\xi)| \leq O(d^3)\) for any \(0 \leq k \leq d'\). Utilizing 11, we obtain a polynomial approximation \(P_{d'}^{\mathrm{sgn}}(x) = \hat{c}_0/2+\sum_{k=1}^{d'} \hat{c}_k T_k(x)\) with a degree of \(d'=2d-1 \leq \tilde{C}_{\mathrm{sgn}} \delta^{-1}\log{\epsilon^{-1}}\), where \(\tilde{C}_{\mathrm{sgn}}\) is a universal constant. This polynomial satisfies \(\max_{x\in [-1,1]} |\mathop{\mathrm{erf}}(\kappa x)-P_{d'}^{\mathrm{sgn}}(x)| \leq 4\epsilon\). Then, we can derive: \[\max_{x\in[-1,1]\setminus[-\delta,\delta]} |\mathrm{sgn}(x)-P^{\mathrm{sgn}}_{d'}(x)| \leq \epsilon + \max_{x\in[-1,1]} |\mathop{\mathrm{erf}}(\kappa x)-P^{\mathrm{sgn}}_{d'}(x)| \leq C_{\mathrm{sgn}}\epsilon, \quad \text{where } C_{\mathrm{sgn}}=5.\]

Moreover, to bound the norm \(\|\hat{\mathbf{c}}\|_1\), it suffices to consider the function \(\mathop{\mathrm{erf}}(\kappa x)\) due to [prop:poly-approx-sgn]. Let \(g(\theta)\mathrel{\vcenter{:}}= \mathop{\mathrm{erf}}(\kappa\cos\theta)\). We observe that \(|g(\theta)|\leq 1\) and \(g'(\theta)=-\frac{2\kappa}{\sqrt{\pi}}\sin\theta \cdot e^{-\kappa^2\cos^2\theta}\). Since \(\sin\theta\leq 0\) on \([-\pi,0]\), we have \(g'(\theta)\geq 0\) on this interval. Hence, it follows that \(\int_{-\pi}^0 |g'(\theta)|\,\mathrm{d}\theta =g(0)-g(-\pi) =\mathop{\mathrm{erf}}(\kappa)-\mathop{\mathrm{erf}}(-\kappa) =2\mathop{\mathrm{erf}}(\kappa)\leq 2\). Therefore, by 11[thmitem:polyApprox-l1-norm-bound-first-conti] and the assumption \(d'\geq 2\), we obtain \(\|\hat{\mathbf{c}}\|_1 \leq \hat{C}_{\mathrm{sgn}}\log d'\) for some universal constant \(\hat{C}_{\mathrm{sgn}}\).

For the complexity of computing coefficients \(\{\hat{c}_k\}_{k=1}^{d'}\), note that the evaluation of the integrand \(F(\theta)\) requires \(\ell\)-bit precision, where \(\ell=O(\log(\epsilon^{-3/2}d^{3}))\). Following \(t(\ell) = \tilde{O}(\ell)\) specified in [remark:evaluating-funcs], any entry of the coefficient vector \(\hat{\mathbf{c}}\) can be computed in deterministic time \(O(\epsilon^{-1/2}d^{2} t(\ell)) = \tilde{O}(\epsilon^{-1/2}d^{2})\) and space \(O(\log(\epsilon^{-3/2} d^3))\).

Finally, we note that \(\max_{x\in[-1,1]}|P_{d'}^{\mathrm{sgn}}(x)| \leq 1+\epsilon\) due to numerical errors in computing the coefficients \(\{\hat{c}_k\}_{k=1}^{d'}\). We finish the proof by considering the normalized polynomial \(\hat{P}_{d'}^{\mathrm{sgn}}/(1+\epsilon)\) rather than \(\hat{P}_{d'}\) and adjusting the coefficient vector \(\hat{\mathbf{c}}\) of \(P_{d'}^{\mathrm{sgn}}\) accordingly. ◻

Proof of [fact:sign-func-derivative-bound]. Through a straightforward calculation, we have derived that \[\label{eq:sign-func-derivative-bound} \begin{align} |F_k''(\theta)| =& \frac{2}{\sqrt{\pi}} \left|\kappa \exp(-\kappa^2 \cos^2{\theta}) \cos{\theta} \cos(k \theta) \right| + \left|k^2\cos(k \theta) \mathop{\mathrm{erf}}(\kappa \cos(\theta))\right|\\ &+\frac{4}{\sqrt{\pi}} \left|\kappa^3 \exp(-\kappa^2\cos^2{\theta}) \cos{\theta} \cos(k \theta) \sin^2{\theta}\right|\\ &+\frac{4}{\sqrt{\pi}} \left|k \kappa \exp(-\kappa^2 \cos^2{\theta})\sin{\theta}\sin(k \theta)\right|\\ \leq& \frac{2}{\sqrt{\pi}} \kappa + k^2+\frac{4}{\sqrt{\pi}}\kappa^3+\frac{4}{\sqrt{\pi}}k\kappa. \end{align}\tag{12}\] The last line owes to the facts that \(|\mathop{\mathrm{erf}}(x)|\leq 1\), \(\exp(-x^2) \leq 1\), \(|\sin{x}|\leq 1\), and \(|\cos{x}|\leq 1\) for any \(x\). We complete the proof by noting that 12 holds for any \(0 \leq k \leq d'\). ◻

Proof. We begin by noticing that the truncation error of \(\sum_{k=0}^K a_k x^k\), as shown in [96], is \((1-\delta)^{k+1} \leq e^{-\delta(k+1)} \leq \epsilon\), implying that \(K \geq \Omega(\delta^{-1} \ln{\epsilon^{-1}})\). Without loss of generality, we can assume that \(\|\mathbf{a}\|_1 \geq \epsilon/2\).³⁴

Construction of polynomial approximations.

Our construction involves three approximations, as described in Lemma 37 of [55]. We defer the detailed proofs of all three approximations to the end of this subsection.

The first approximation combines the assumed \(\sum_{k=0}^K a_k x^k\) with \(\arcsin(x)\)’s Taylor series.

The second approximation truncates the series at \(l=L\), and bounds the truncation error.

The third approximation approximates the functions \(\sin^l(x)\) in \(\hat{f}_2(x)\) using a tail bound of the binomial distribution. Notably, this construction not only quadratically improves the dependence on \(\delta\), but also ensures that the integrand’s second derivative is bounded when combined with 11.

We adopt the third approximation as our construction by rearranging the summations and introducing a new parameter \(m\). The value of \(m\) is defined as \(m\mathrel{\vcenter{:}}= m'-\hat{l}\) if \(f\) is even and \(m\mathrel{\vcenter{:}}= m'-\hat{l}-1\) if \(f\) is odd. Moreover, the definition of \(m\) depends on the parity of \(l=2\hat{l}+1\)³⁵ if \(f\) is neither even nor odd. By applying this approach, we can derive the following: \[\label{eq:low-weight-approx-rearranging-terms} \begin{align} \hat{f}^{(\mathrm{even})}_3(x) &= \textstyle \sum\limits_{m=-M}^M c^{(\mathrm{even})}_m \cos(\pi x m),\\ \text{ where } c^{(\mathrm{even})}_m &\mathrel{\vcenter{:}}= (-1)^m \sum\limits_{k=0}^K a_k \sum\limits_{\hat{l}=0}^{L/2} b^{(k)}_{2\hat{l}} \tbinom{2\hat{l}}{m+\hat{l}} 2^{-2\hat{l}}; \\ \hat{f}^{(\mathrm{odd})}_3(x) &= \textstyle \sum\limits_{m=-M}^M c^{(\mathrm{odd})}_m \sin\big(\pi x \big(m+\tfrac{1}{2}\big)\big),\\ \text{ where } c^{(\mathrm{odd})}_m &\mathrel{\vcenter{:}}=(-1)^m \sum\limits_{k=0}^K a_k \sum\limits_{\hat{l}=0}^{(L-1)/2} b^{(k)}_{2\hat{l}+1} \tbinom{2\hat{l}+1}{m+\hat{l}+1} 2^{-2\hat{l}-1}. \end{align}\tag{14}\]

We then notice that the rearrangement of terms in 14 can be directly applied to the definition of \(\hat{f}_3(x)\) in [prop:third-low-weight-approximation]. As a consequence, we obtain the following bound on the accumulative error: \[\|f - \hat{f}_3\|_{\mathcal{I}_{\delta}} \leq \|f - \hat{f}_1\|_{\mathcal{I}_{\delta}} + \|\hat{f}_1 - \hat{f}_2\|_{\mathcal{I}_{\delta}} + \|\hat{f}_2 - \hat{f}_3\|_{\mathcal{I}_{\delta}} \leq \epsilon.\] Additionally, we remark that \(\|\mathbf{c}\|_1 \leq \|\mathbf{a}\|_1\), which follows from \(\|\mathbf{b}^{(k)}\|_1=1\) (see [prop:first-low-weight-approx]) and \(\sum_{m=0}^l \binom{l}{m}=2^l\).

Analyzing time and space complexity.

To evaluate the bounded polynomial approximation \(\hat{f}_3(x)\) with \(\epsilon\) accuracy, it is necessary to approximate the summand with \(\ell\)-bit precision, where \(\ell=O(\log(KLM\epsilon^{-1}))=O(\log(\delta^{-4}\epsilon^{-1}))\). Since the summand is a product of a constant number of holonomic functions, approximating \(b^{(k)}_l\) with \(\ell\)-bit precision is sufficient. Other quantities in the summand can be evaluated with the desired accuracy in deterministic time \(\tilde{O}(\ell)\) and space \(O(\ell)\) as stated in [remark:evaluating-funcs].

We now present a bounded-error randomized algorithm for estimating \(b^{(k)}_l\). As \(\mathbf{b}^{(1)}\) is entry-wise non-negative and \(\sum_{i=1}^l b_i^{(1)} < \|\mathbf{b}^{(1)}\|_1=1\) following [prop:first-low-weight-approx], we can express the recursive formula in 13 as the matrix powering of a sub-stochastic matrix \(B_1\): \[B_1^k \mathrel{\vcenter{:}}= \begin{pmatrix} b_1^{(1)} & b_2^{(1)} & \cdots & b_{l-1}^{(1)} & b_l^{(1)}\\ 0 & b_1^{(1)} & \cdots & b_{l-2}^{(1)} & b_{l-1}^{(1)}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & b_{1}^{(1)} & b_{2}^{(1)}\\ 0 & 0 & \cdots & 0 & b_{1}^{(1)}\\ \end{pmatrix}^k = \begin{pmatrix} b_1^{(k)} & b_2^{(k)} & \cdots & b_{l-1}^{(k)} & b_l^{(k)}\\ 0 & b_1^{(k)} & \cdots & b_{l-2}^{(k)} & b_{l-1}^{(k)}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & b_{1}^{(k)} & b_{2}^{(k)}\\ 0 & 0 & \cdots & 0 & b_{1}^{(k)}\\ \end{pmatrix} \mathrel{\vcenter{:}}= B_k.\]

In addition, we approximate the sub-stochastic matrix \(B_1\) by dyadic rationals with \(\ell\)-bit precision, denoted as \(\hat{B}_1\). Utilizing 10, we can compute any entry \(\hat{B}_1^k[s,t]\) with a randomized algorithm that runs in \(O(\ell k)\) time and \(\log(l+1)\) space with acceptance probability \(\hat{B}_1^k[s,t]\). To evaluate \(\hat{B}_1^k[s,t]\) with an additive error of \(\epsilon\), we use the sequential repetitions outlined in 8. Specifically, we repeat the algorithm \(m=2\epsilon^{-2} \ln(KLM) = O(\epsilon^{-2}\log(\delta^{-4}))\) times, and each turn succeeds with probability at least \(1-1/(3KLM)\). Noting that the number of the evaluation of \({b^{(k)}_l}\) for computing \(\hat{f}_3(x)\) is \(O(KLM)\), and by the union bound, we can conclude that the success probability of evaluating all coefficients in \(\mathbf{c}\) is at least \(2/3\).

Finally, we complete the proof by analyzing the overall computational complexity. It is evident that our algorithm utilizes \(O(\ell+\log{m}) = O(\log(\delta^{-4}\epsilon^{-3}))\) space because indexing \(m\) repetitions requires additional \(O(\log{m})\) bits. Moreover, since there are \(O(KLM)\) summands in \(\hat{f}_3(x)\), and evaluating \(b^{(k)}_l\) takes \(m\) repetitions with time complexity \(O(\ell K)\) for a single turn, the overall time complexity is \(O(KLM\cdot\ell K\cdot\epsilon^{-2}\log(KLM))=\tilde{O}(\delta^{-5}\epsilon^{-2})\). ◻

Proof of 5. Our approach is based on Theorem 40 in [55] and Corollary 23 in [11]. Firstly, we obtain a Fourier approximation \(\hat{f}(x)\) of the given function \(f(x)\) by truncating it using 12. Next, we ensure that \(\hat{f}(x)\) is negligible outside the interval \([-x_0-r,x_0+r]\) by multiplying it with a suitable rectangle function, denoted as \(h(x)\). Finally, we derive a space-efficient polynomial approximation \(\hat{h}(x)\) of \(h(x)\) by applying 11.

Construction of a bounded function.

Let us begin by defining a linear transformation \(L(x)\mathrel{\vcenter{:}}=\frac{x-x_0}{r+\delta}\) that maps \([x_0-r-\delta,x_0+r+\delta]\) to \([-1,1]\). For convenience, we denote \(g(y)\mathrel{\vcenter{:}}= f(L^{-1}(y))\) and \(b_l\mathrel{\vcenter{:}}= a_l(r+\delta)^l\), then it is evident that \(g(y)\mathrel{\vcenter{:}}=\sum_{l=0}^{\infty} b_ly^l\) for any \(y\in[-1,1]\).

To construct a Fourier approximation by 12, we need to bound the truncation error \(\varepsilon_J^{(g)}\). We define \(\delta'\mathrel{\vcenter{:}}=\frac{\delta}{2(r+\delta)}\) and \(J\mathrel{\vcenter{:}}=\lceil (\delta')^{-1} \log(12B\epsilon^{-1}) \rceil\). This ensures that the truncation error \(\varepsilon_J^{(g)}\mathrel{\vcenter{:}}=\big|g(y)-\sum_{j=0}^{J-1} b_jy^j\big|\) for any \(y\in[-1+\delta',1-\delta']\) satisfies the following: \[\varepsilon_J^{(g)} = \abs*{ \sum_{j=J}^{\infty} b_jy^j } \leq \sum_{j=J}^{\infty} \big| b_j(1-\delta')^j \big| \leq (1-\delta')^J \sum_{j=J}^{\infty} |b_j| \leq (1-\delta')^J B \leq e^{-\delta' J} B \leq \frac{\epsilon}{12} \mathrel{\vcenter{:}}= \frac{\epsilon'}{4}.\] Afterward, let \(\hat{\mathbf{b}}\mathrel{\vcenter{:}}=(b_0,b_1,\cdots,b_{J-1})\), then we know that \(\|\hat{\mathbf{b}}\|_1 \leq \|\mathbf{b}\|_1 \leq B\) by the assumption. Now we utilize 12 and obtain the Fourier approximation \(\hat{g}(y)\):

\[\label{eq:smooth-funcs-Fourier-approxY} \hat{g}(y) \!\mathrel{\vcenter{:}}=\! \begin{cases} \sum_{m=-M}^M c_m^{(\mathrm{even})} \cos(\pi ym), & \text{if } f \text{ is even}\\ \sum_{m=-M}^M c_m^{(\mathrm{odd})} \sin\!\big(\pi y \big(m\!+\!\tfrac{1}{2}\big)\big), & \text{if } f \text{ is odd}\\ \sum_{m=-M}^M \Big(c_m^{(\mathrm{even})} \!\cos(\pi ym) + c_m^{(\mathrm{odd})} \!\sin\big(\pi y \big(m\!+\!\tfrac{1}{2}\big)\big)\Big), & \text{otherwise} \end{cases}.\tag{15}\] By appropriately choosing \(M=O\big( (\delta')^{-1}\!\log\big(\|\hat{\mathbf{b}}\|_1/\epsilon'\big)\big) = O\big( r \delta^{-1}\!\log\big(B/\epsilon\big) \big)\), we obtain that the vectors of coefficients \(\mathbf{c}^{(\mathrm{even})}\) and \(\mathbf{c}^{(\mathrm{odd})}\) satisfy \(\|\mathbf{c}^{(\mathrm{even})}\|_1 \leq \|\hat{\mathbf{b}}\|_1 \leq \|\mathbf{b}\|_1 \leq B\) and similarly \(\|\mathbf{c}^{(\mathrm{odd})}\|_1 \leq B\). Plugging \(f(x)=g(L(x))\) into 15 , we conclude that \(\hat{f}(x)=\hat{g}(L(x))\) is a Fourier approximation of \(f\) with an additive error of \(\epsilon/3\) on the interval \([x_0-r-\delta/2, x_0+r+\delta/2]\): \[\hat{f}(x) = \hat{g}\Big( \frac{x\!-\!x_0}{r\!+\!\delta} \Big) = \begin{cases} \sum\limits_{m=-M}^M c_m^{(\mathrm{even})} \!\!\cos\!\big(\pi m \big(\frac{x-x_0}{r+\delta}\big) \big), & \text{if } f \text{ is even}\\ \sum\limits_{m=-M}^M c_m^{(\mathrm{odd})} \!\!\sin\!\big(\pi \big(m+\tfrac{1}{2}\big) \big(\frac{x-x_0}{r+\delta}\big) \big), & \text{if } f \text{ is odd}\\ \sum\limits_{m=-M}^M c_m^{(\mathrm{even})} \!\!\cos\!\big(\pi m \big(\frac{x-x_0}{r+\delta}\big) \big) + c_m^{(\mathrm{odd})} \sin\!\big(\pi \big(m+\tfrac{1}{2}\big) \big(\frac{x-x_0}{r+\delta}\big) \big), & \text{otherwise} \end{cases}.\]

Making the error negligible outside the interval.

Subsequently, we define the function \(h(x) = \hat{f}(x) \cdot R(x)\) such that it becomes negligible outside the interval of interest, i.e., \([x_0-r-\delta/2,x_0+r+\delta/2]\). Here, the approximate rectangle function \(R(x)\) is \(\tilde{\epsilon}\)-close to \(1\) on the interval \([x_0-r,x_0+r]\), and is \(\tilde{\epsilon}\)-close to \(0\) on the interval \([-1,1] \setminus [x_0-r-2\tilde{\delta}, x_0+r+2\tilde{\delta}]\), where \(\tilde{\epsilon}\mathrel{\vcenter{:}}=\epsilon/(3B)\) and \(\tilde{\delta}\mathrel{\vcenter{:}}=\delta/4\). Moreover, \(|R(x)|\leq 1\) for any \(x \in [-1,1]\). Similar to [11], \(R(x)\) can be expressed as a linear combination of Gaussian error functions: \[\begin{align} R(x) &\mathrel{\vcenter{:}}= \frac{1}{2} \rbra*{ \mathop{\mathrm{erf}}\!\big( \kappa (x - x_0 + r + \tilde{\delta}) \big) - \mathop{\mathrm{erf}}\big( \kappa (x - x_0 - r - \tilde{\delta}) \big) },\\ \text{where } \kappa &\mathrel{\vcenter{:}}= \frac{2}{\tilde{\delta}} \log^{1/2} \rbra*{\frac{\sqrt{2}}{\sqrt{\pi} \tilde{\epsilon}}} = \frac{8}{\delta} \log^{1/2} \rbra*{\frac{\sqrt{18}B}{\sqrt{\pi}\epsilon}}. \end{align}\]

Bounded polynomial approximation via averaged Chebyshev truncation.

We present an algorithmic, space-efficient, randomized polynomial approximation method using averaged Chebyshev truncation to approximate the function \(h(x)\mathrel{\vcenter{:}}=\hat{f}(x) \cdot R(x)\). As suggested in [prop:time-efficient-smooth-funcs], we use an explicit polynomial approximation \(P^*_d(x)\) of the bounded function \(h(x)\) of degree \(d=O(\delta^{-1} \log(B\epsilon^{-1}))\) that satisfies the conditions specified in 16 .

To utilize 11, we need to bound the second derivative \(\max_{\xi\in[-\pi,0]} |F_k''(\xi)|\), where the integrand \(F_k(\theta)\mathrel{\vcenter{:}}=\cos(k\theta) h(\cos\theta)\) for any \(0 \leq k \leq {d'}\) with \(d'=2d-1\). We will calculate this upper bound directly in [fact:smooth-funcs-derivative], and the proof is deferred to the end of this section.

Together with [fact:smooth-funcs-derivative], we are ready to apply 11 to \(h(x)=\hat{f}(x)R(x)\), resulting in a degree-\(d'\) polynomial \(P_{d'} = \hat{c}_0/2 + \sum_{k=1}^{d'} \hat{c}_k T_k\) where \(d'=2d-1\) and \(\hat{c}_k\) is defined as in ?? . Since \(P_{d'}\) is the degree-\(d\) averaged Chebyshev truncation of the function \(h\) and satisfies 16 , we define intervals \(\mathcal{I}_{\mathrm{int}}\mathrel{\vcenter{:}}=[x_0-r,x_0+r]\) and \(\mathcal{I}_{\mathrm{ext}}\mathrel{\vcenter{:}}= [-1,1] \setminus [x_0-r-\delta/2, x_0+r+\delta/2]\) to obtain: \[\label{eq:smooth-funcs-approxpoly-errors} \begin{align} \|f(x)-P_{d'}(x)\|_{\mathcal{I}_{\mathrm{int}}} &\leq \|f(x)-h(x)\|_{\mathcal{I}_{\mathrm{int}}} + \|h(x)-P_{d'}(x)\|_{\mathcal{I}_{\mathrm{int}}} \leq \epsilon + 4\epsilon = O(\epsilon), \\ \|P_{d'}(x)-0\|_{\mathcal{I}_{\mathrm{ext}}} & \leq \|P_{d'}(x)-h(x)\|_{\mathcal{I}_{\mathrm{ext}}} + \|h(x)-0\|_{\mathcal{I}_{\mathrm{ext}}} \leq 4\epsilon + 2B \cdot \frac{\epsilon}{3B} \leq O(\epsilon). \end{align}\tag{19}\]

We can achieve the desired error bound by observing 19 implies: \[\|P_{d'}(x)\|_{[-1,1]} \leq \|P_{d'}(x)\|_{\mathcal{I}_{\mathrm{ext}}} + \|P_{d'}(x)\|_{[-1,1] \setminus \mathcal{I}_{\mathrm{ext}}} \leq O(\epsilon) + B.\] Moreover, since \(|R(x)|\leq 1\) and the low-weight Fourier approximation satisfies \(|\hat{f}(x)|\leq O(B)\) on \([-1,1]\), we have \(\|h(x)\|_{[-1,1]}\leq O(B)\). By 11[thmitem:polyApprox-l1-norm-bound-general], we deduce that the norm of the coefficient vector \(\hat{\mathbf{c}}\) of the polynomial \(P_{d'}\) is bounded by \(\|\hat{\mathbf{c}}\|_1 \leq O(B\sqrt d)\).

Analyzing time and space complexity.

The construction of \(\hat{f}(x)\) can be implemented in bounded-error randomized time \(\tilde{O}((\delta')^{-5}\epsilon^{-2}B^2)\) and space \(O(\log((\delta')^{-4}\epsilon^{-1}B))\), given that this construction uses 12 with \(\delta'=\frac{\delta}{2(r+\delta)} \in (0,\frac{1}{2}]\) and \(\epsilon'=\frac{\epsilon}{3B}\). Having \(\hat{f}(x)\), we can construct a bounded polynomial approximation \(\hat{h}(x)\) deterministically using 11. This construction can be implemented in deterministic time \(O(d^{(\gamma+1)/2}\epsilon^{-1/2} t(\ell)) \leq \tilde{O}(d^2\epsilon^{-1/2})\) and space \(O(\log(d^{(\gamma+3)/2}\epsilon^{-3/2}B)) \leq O(\log(d^3\epsilon^{-3/2}B))\) since the integrand \(F_k(\theta)\) is a product of a constant number of (compositions of) holonomic functions ([remark:evaluating-funcs]). Therefore, our construction can be implemented in bounded-error randomized time \(\tilde{O}(\max\big\{ (\delta')^{-5} \epsilon^{-2} B^2, d^2\epsilon^{-1/2} \big\})\) and space \(O(\max\{\log((\delta')^{-4} \epsilon^{-1} B), \log(d^3 \epsilon^{-3/2} B) \}) \leq O(\log(d^3(\delta')^{-4}\epsilon^{-3/2}B))\). ◻

Proof. Consider the function \(f(x)\mathrel{\vcenter{:}}=\frac{\ln(1/x)}{2\ln(2/\beta)}\). We apply 5 to \(f\) by choosing the same parameters as in Lemma 11 of [73], specifically \(\epsilon'=\epsilon/2\), \(x_0=1\), \(r=1-\beta\), \(\delta=\beta/2\), and \(B=1/2\).³⁶ This results in a space-efficient randomized polynomial approximation \(\tilde{P}_{d'}\in\mathbb{R}[x]\) of degree \(d'=2d-1 = O(\delta^{-1} \log(\epsilon^{-1} B)) \leq \tilde{C}_{\ln} \beta^{-1} \log{\epsilon^{-1}}\), where \(\tilde{P}_{d'}\) corresponds to some degree-\(d\) averaged Chebyshev truncation and \(\tilde{C}_{\ln}\) is a universal constant. By appropriately choosing \(\eta \leq 1/2\) such that \(C'_{\ln} \epsilon = \eta/4\) for a universal constant \(C'_{\ln}\), this polynomial approximation \(\tilde{P}_{d'}\) satisfies the following inequalities: \[\label{eq:conditions-log} \begin{align} \|f(x)-\tilde{P}_{d'}(x)\|_{[\beta,2-\beta]} & \leq C'_{\ln} \epsilon = \tfrac{\eta}{4}\\ \|\tilde{P}_{d'}(x)\|_{[-1,1]} &\leq B+ C'_{\ln} \epsilon \leq \tfrac{1}{2} + C'_{\ln} \epsilon = \tfrac{1}{2}+\tfrac{\eta}{4}\\ \|\tilde{P}_{d'}(x)\|_{[-1,\beta/2]} &\leq C'_{\ln} \epsilon = \tfrac{\eta}{4}. \end{align}\tag{20}\] Additionally, using 5, the coefficient vector \(\mathbf{c}^{(\tilde{P})}\) of \(\tilde{P}_{d'}\) satisfies \[\norm[\big]{ \mathbf{c}^{(\tilde{P})} }_1 \leq O\rbra[\big]{B\sqrt{d'}} \leq \hat{C}'_{\ln}\sqrt{d'},\] where \(\hat{C}'_{\ln}\) is a universal constant. Noticing that \(\delta'=\frac{\delta}{2(r+\delta)}=\frac{\beta/2}{2(1-\beta+\beta/2)}=\frac{\beta}{4(1-\beta/2)}=\Theta(\beta)\), our utilization of 5 yields a bounded-error randomized algorithm that requires space \[O(\log(d^3 (\delta')^{-4} \epsilon^{-3/2} B)) = O(\log(d^3 \beta^{-4} \epsilon^{-3/2}))\] and time \[\tilde{O}(\max\{(\delta')^{-5} \epsilon^{-2} B^2, d^2 \epsilon^{-1/2} \}) = \tilde{O}(\max\{\beta^{-5}\epsilon^{-2}, d^2 \epsilon^{-1/2}\}).\]

Furthermore, noting that the real-valued function \(f(x)\) is defined only when \(x>0\), \(\tilde{P}_{d'}(x)\) is not an even polynomial in general. Instead, we consider \(P^{\ln}_{d'}(x)\mathrel{\vcenter{:}}=(1+\eta)^{-1}(\tilde{P}_{d'}(x)+\tilde{P}_{d'}(-x))\) for all \(x\in[-1,1]\). Together with 20 , we have derived that: \[\label{eq:log-polynomial-error} \begin{align} & \|f(x) - P^{\ln}_{d'}(x)\|_{[\beta,1]} \\ \leq~& \big\|f(x) - \tfrac{1}{1+\eta} \tilde{P}_{d'}(x) \big\|_{[\beta,1]} + \big\|\tfrac{1}{1+\eta}\tilde{P}_{d'}(-x)\big\|_{[\beta,1]}\\ \leq~& \big\|f(x) - \tilde{P}_{d'}(x)\big\|_{[\beta,1]} + \big\|\tilde{P}_{d'}(x) - \tfrac{1}{1+\eta} \tilde{P}_{d'}(x)\big\|_{[\beta,1]} + \big\|\tfrac{1}{1+\eta} \tilde{P}_{d'}(-x)\big\|_{[\beta,1]}\\ \leq~& \tfrac{\eta}{4} + \tfrac{\eta}{1+\eta}\cdot \big(\tfrac{1}{2} + \tfrac{\eta}{4}\big) + \tfrac{1}{1+\eta}\cdot \tfrac{\eta}{4}\\ \leq~& \eta. \end{align}\tag{21}\]

Here, the last line owes to the fact that \(\eta > 0\). Consequently, 21 implies that \(\|f(x)-P^{\ln}_{d'}(x)\|_{[\beta,1]} \leq 4C'_{\ln} \epsilon \mathrel{\vcenter{:}}= C_{\ln} \epsilon\) for another universal constant \(C_{\ln}\). Notice \(P^{\ln}_{d'}\) is an even polynomial with \(\deg(P^{\ln}_{d'}) \leq \tilde{C}_{\ln} \beta^{-1} \log \epsilon^{-1}\), 20 yields that: \[\begin{align} \|P^{\ln}_{d'}(x)\|_{[-1,1]} = \|P^{\ln}_{d'}(x)\|_{[0,1]} \leq \|\tfrac{1}{1+\eta}\tilde{P}_{d'}(x)\|_{[0,1]} + \|\tfrac{1}{1+\eta}\tilde{P}_{d'}(x)\|_{[-1,0]} \leq \tfrac{1}{1+\eta} \cdot \tfrac{1+\eta}{2} + \tfrac{1}{1+\eta} \cdot \tfrac{\eta}{2} \leq 1. \end{align}\] Here, the last inequality is due to \(\eta \leq 1/2\).

It remains to verify how the coefficient vector changes when passing from \(\tilde{P}_{d'}\) to \(P^{\ln}_{d'}\). Write \(\tilde{P}_{d'}(x)=\frac{\tilde{c}_0}{2}+\sum_{k=1}^{d'}\tilde{c}_kT_k(x)\). Since \(T_k(-x)=(-1)^kT_k(x)\), the polynomial \(P^{\ln}_{d'}(x)=(1+\eta)^{-1} \rbra[\big]{ \tilde{P}_{d'}(x)+\tilde{P}_{d'}(-x)}\) has coefficients \(c^{\ln}_0=\frac{2}{1+\eta}\tilde{c}_0\) and \(c^{\ln}_k=\frac{1+(-1)^k}{1+\eta}\tilde{c}_k\) for each \(1 \leq k \leq d'\). Therefore, we obtain: for a universal constant \(\hat{C}_{\ln}\), \[\|\mathbf{c}^{\ln}\|_1 \leq \frac{2}{1+\eta}\abs*{\tilde{c}_0}+\sum_{k=1}^{d'}\frac{\abs*{1+(-1)^k}}{1+\eta}\abs*{\tilde{c}_k} \leq 2\norm{\mathbf{c}^{(\tilde{P})}}_1 \leq 2 \hat{C}'_{\ln} \sqrt{d'} \mathrel{\vcenter{:}}= \hat{C}_{\ln} \sqrt{d'}.\] Here, the second inequality uses the fact that \(2/(1+\eta) \leq 2\). The same coefficient-computation time and space bounds hold for \(\mathbf{c}^{\ln}\), since each coefficient of \(P^{\ln}_{d'}\) is obtained from the corresponding coefficient of \(\tilde{P}_{d'}\) by multiplication by the explicitly computable factor \((1+(-1)^k)/(1+\eta)\). ◻

Proof of [prop:first-low-weight-approx]. We construct a Fourier series by a linear combination of the power of sines. We first note that \(x = \frac{2}{\pi}\cdot\arcsin\!\left( \sin\left( \frac{x\pi}{2} \right) \right)\) for all \(x \in [-1,1]\), and plug it into \(\hat{f}_1(x)\mathrel{\vcenter{:}}=\sum_{k=0}^K a_kx^k\), which deduces that \(\|f-\hat{f}_1\|_{\mathcal{I}_{\delta}} \leq \epsilon/4\) by the assumption. Let \(\mathbf{b}^{(k)}\) be the coefficients of \(\left( \frac{\arcsin{y}}{\pi/2} \right)^k=\sum_{l=0}^{\infty} b_l^{(k)} y^l\) for all \(y \in [-1,1]\), then we result in our first approximation. Moreover, we observe that \(\frac{\pi}{2}\cdot\mathbf{b}^{(1)}\) is exactly the Taylor series of arcsin, whereas we know that \(\left( \frac{\arcsin{y}}{\pi/2} \right)^{k+1} = \left( \frac{\arcsin{y}}{\pi/2} \right)^{k} \cdot \left( \sum_{l=0}^{\infty} b_l^{(1)} y^l \right)\) for \(k > 1\), which derives 13 by comparing the coefficients. In addition, notice that \(\|\mathbf{b}^{(k)}\|_1 = \sum_{l=0}^{\infty} b^{(k)}_l 1^l = \left(\frac{\arcsin{1}}{\pi/2}\right)^k=1\), together with straightforward reasoning follows from 13 , we deduce the desired property for \(\{b^{(k)}_l\}\). ◻

Proof of [prop:second-low-weight-approx]. We truncate the summation over \(l\) in \(f_1(x)\) at \(l=L\), and it suffices to bound the truncation error. For all \(k \in \mathbb{N}\) and \(x \in [-1+\delta,1-\delta]\), we obtain the error bound: \[\Bigg| \sum_{l=\lfloor L \rfloor}^{\infty} b^{(k)}_l \sin^l\!\left(\tfrac{x\pi}{2}\right)\Bigg| \! \leq \! \sum_{l=\lfloor L \rfloor}^{\infty} b^{(k)}_l \Big| \sin^l\!\left( \tfrac{x\pi}{2} \right) \Big| \! \leq \! \sum_{l=\lfloor L \rfloor}^{\infty} b^{(k)}_l |1-\delta^2|^l \leq (1-\delta^2)^L \sum_{l=\lfloor L \rfloor}^{\infty} b^{(k)}_l \leq (1-\delta^2)^L.\] Here, the second inequality owing to \(\forall \delta \in [0,1]\), \(\sin\!\left( (1-\delta)\frac{\pi}{2} \right) \leq 1-\delta^2\), and the last inequality is due to \(\|\mathbf{b}^{(k)}\|_1=1\) in [prop:first-low-weight-approx]. By appropriately choosing \(L\mathrel{\vcenter{:}}=\delta^{-2} \ln(4\|\mathbf{a}\|_1 \epsilon^{-1})\), we obtain that \(\|\hat{f}_1-\hat{f}_2\|_{\mathcal{I}_{\delta}} \leq \sum_{k=0}^K \abs{a_k} (1-\delta^2)^L \leq \|\mathbf{a}\|_1\cdot \exp(-\delta^2 L) \leq \epsilon/4\). ◻

Proof of [prop:third-low-weight-approximation]. We upper-bound \(\sin^l(x)\) in \(\hat{f}_2(x)\) defined in [prop:second-low-weight-approx] using a tail bound of binomial coefficients. We obtain that \[\sin^l(z)=\rbra*{ \frac{e^{-\mathrm{i}z}-e^{\mathrm{i}z}}{-2\mathrm{i}} }^l=\rbra*{ \frac{\mathrm{i}}{2} }^l\sum_{m=0}^l (-1)^m \binom{l}{m} \exp(\mathrm{i}z(2m-l))\] by a direct calculation, which implies the counterpart for real-valued functions: \[\label{eq:power-of-sine} \sin^l(z) = \begin{cases} 2^{-l} (-1)^{(l+1)/2} \sum\limits_{m'=0}^l (-1)^{m'} \binom{l}{m'} \sin(z(2m'-l)), & \text{if } l \text{ is odd;}\\ 2^{-l} (-1)^{l/2} \sum\limits_{m'=0}^l (-1)^{m'} \binom{l}{m'} \cos(z(2m'-l)), & \text{if } l \text{ is even.} \end{cases}\tag{22}\] Recall that the Chernoff bound (e.g., Corollary A.1.7 in [100]) which corresponds a tail bound of binomial coefficients, and assume that \(l \leq L\), we have derived that: \[\label{eq:binomial-tail-bounds} \sum_{m'=0}^{\lfloor l/2 \rfloor-M} 2^{-l} \binom{l}{m'} = \sum_{m'=\lceil l/2 \rceil+M}^l 2^{-l} \binom{l}{m'} \leq e^{-\frac{2M^2}{l}} \leq e^{-\frac{2M^2}{L}} \leq \rbra*{ \frac{\epsilon}{4\|a\|_1} }^2 \leq \frac{\epsilon}{4\|a\|_1}.\tag{23}\] Here, we choose \(M=\lceil \delta^{-1} \ln(4\|\mathbf{a}\|_1\epsilon^{-1}) \rceil\), and the last inequality is because of the assumption \(\epsilon \leq 2\|\mathbf{a}\|_1\). As stated in [prop:first-low-weight-approx], \(b^{(k)}_l=0\) if \(k\) and \(l\) have different parities. Consequently, we only need to consider all odd (resp., even) \(l \leq L\) for odd (resp., even) functions. If the function \(f\) is neither even nor odd, we must consider all \(l \leq L\). Plugging 23 into 22 , we can derive that:

• If \(l\) is odd, \[\label{eq:truncating-power-of-sine-odd} \norm[\bigg]{ \sin^l(z) - 2^{-l} (-1)^{(l+1)/2} \sum_{m'=(l+1)/2-M}^{(l+1)/2+M} (-1)^{m'} \binom{l}{m'} \sin(z(2m'-l)) }_{\mathcal{I}_{\delta}} \leq \frac{\epsilon}{2\norm*{\mathbf{a}}_1};\tag{24}\]

• If \(l\) is even, \[\label{eq:truncating-power-of-sine-even} \norm[\bigg]{ \sin^l(z) - 2^{-l} (-1)^{l/2} \sum_{m'=l/2-M}^{l/2+M} (-1)^{m'} \binom{l}{m'} \cos(z(2m'-l)) }_{\mathcal{I}_{\delta}} \leq \frac{\epsilon}{2\norm*{\mathbf{a}}_1}.\tag{25}\]

Plugging [eq:truncating-power-of-sine-odd,eq:truncating-power-of-sine-even] into \(\hat{f}_2(x)\), and substituting \(z=x\pi/2\), this equation leads to \(\hat{f}_3(x)\) as desired. In addition, combining \(\sum_{k=0}^K |a_k| \sum_{l=0}^{\lfloor L \rfloor} |b^{(k)}_l| \leq \sum_{k=0}^{K} |a_k| = \|\mathbf{a}\|_1\) with [eq:truncating-power-of-sine-odd,eq:truncating-power-of-sine-even], we achieve that \(\|\hat{f}_2-\hat{f}_3\|_{\mathcal{I}_{\delta}} \leq \epsilon/2\). ◻

Proof of [fact:smooth-funcs-derivative]. We begin by deriving an upper bound of the second derivative of the integrand \(F_k(\theta)\): \[\label{eq:smooth-funcs-derivative} \begin{align} |F''_k(\theta)| &\leq \sum_{m=-M}^M \frac{\abs{c_m}}{2} \abs*{\frac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(+)}(\theta) - \frac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(-)}(\theta)} \\ &\leq \frac{\norm*{\mathbf{c}}_1}{2} \max_{-\pi \leq \theta \leq 0} \rbra*{ \abs*{\frac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(+)}(\theta)} + \abs*{\frac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(-)}(\theta)} }. \end{align}\tag{26}\]

By a straightforward calculation, we have the second derivatives of \(H_{k,m}^{\pm}(\theta)\) if \(f\) is even: \[\begin{align} \tfrac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(\pm)}(\theta)\!=\! &-k^2 \cos(k \theta) \cos\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &-\tfrac{\pi ^2 m^2}{(\delta +r)^2} \sin^2(\theta) \cos(k \theta) \cos\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &+\tfrac{\pi m}{\delta +r} \cos{\theta} \cos(k \theta) \sin\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &-\tfrac{2 \pi k m}{\delta +r} \sin(\theta) \sin(k \theta) \sin\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &-\tfrac{2 \kappa}{\sqrt{\pi }} \cos{\theta} \cos(k \theta) \cos\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}\\ &-\tfrac{4 \sqrt{\pi } \kappa m}{\delta +r} \sin^2(\theta) \cos(k \theta) \sin\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos{\theta}-x_0 \mp r \mp \frac{\delta}{4}\big)^2}\\ &+\tfrac{4 \kappa k}{\sqrt{\pi }} \sin(\theta) \sin(k \theta) \cos\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}\\ &-\tfrac{4 \kappa^3}{\sqrt{\pi }} \sin^2(\theta) \cos(k \theta) \cos\!\big(\tfrac{\pi m (\cos{\theta}-x_0)}{\delta +r}\big) \big(\cos{\theta}-x_0 \mp r \mp \frac{\delta}{4}\big) e^{-\kappa ^2 \big(\cos{\theta}-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}. \end{align}\]

Noting that all functions appear in \(\frac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(\pm)}(\theta)\), viz. \(\sin{x}\), \(\cos{x}\), \(\exp(-x^2)\), and \(\mathop{\mathrm{erf}}(x)\), are at most \(1\), as well as \(|x_0\pm r \pm \delta/4| \leq 7/2\), then we obtain that \[\label{eq:summand-derivative} \begin{align} &\big|\tfrac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(\pm)}(\theta)\big| \\ \leq~& k^2 + \tfrac{2\kappa}{\sqrt{\pi}} + \tfrac{4\kappa k}{\sqrt{\pi}} + \tfrac{18\kappa^3}{\sqrt{\pi}} + m \cdot \big( \tfrac{\pi}{\delta+r} + \tfrac{2\pi k}{\delta+r} + \tfrac{4\sqrt{\pi}\kappa}{\delta+r} \big) + m^2 \cdot \tfrac{\pi^2}{(\delta+r)^2}\\ \leq~& (d')^2 + O(d) + O(d^2) + O(d^3) + \tfrac{M}{\delta+r} \cdot (O(1) \!+\! O(d) \!+\! O(d)) + M^2 \cdot \tfrac{O(1)}{(\delta+r)^2}\\ =~& O(d^3). \end{align}\tag{27}\]

Here, the second line according to \(k \leq d'=2d-1\) and \(\kappa \leq O(d)\), also the last line is due to facts that \(M \leq O(rd)\) and \(1/2 \leq r/(\delta+r) \leq 1\) if \(0 < \delta \leq r\) and \(0 < r \leq 2\). Additionally, a similar argument shows that the upper bound in 27 applies to odd functions and functions that are neither even nor odd as well. This is because a direct computation yields the second derivatives of \(H^{(\pm)}_{k,m}(\theta)\) when \(f\) is odd: \[\begin{align} \tfrac{\mathrm{d}^2}{\mathrm{d}\theta^2} H_{k,m}^{(\pm)}(\theta)\!=\! &-k^2 \cos (k \theta) \sin\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &-\tfrac{\pi \big(m+\tfrac{1}{2}\big)}{\delta +r} \cos \theta \cos (k \theta) \cos\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &-\tfrac{\pi ^2 \big(m+\tfrac{1}{2}\big)^2}{(\delta +r)^2} \sin ^2\theta \cos (k \theta) \sin\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &+\tfrac{2 \pi k \big(m+\tfrac{1}{2}\big)}{\delta +r} \sin \theta \sin (k \theta) \cos\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) \mathop{\mathrm{erf}}\!\big(\kappa \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)\big)\\ &+\tfrac{4 \sqrt{\pi } \kappa \big(m+\tfrac{1}{2}\big)}{\delta +r} \sin ^2\theta \cos (k \theta) \cos\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}\\ &-\tfrac{2 \kappa}{\sqrt{\pi }} \cos \theta \cos (k \theta) \sin\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}\\ &+\tfrac{4 \kappa k}{\sqrt{\pi }} \sin \theta \sin (k \theta) \sin\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}\\ &-\tfrac{4 \kappa ^3}{\sqrt{\pi }} \sin ^2\theta \cos (k \theta) \big(\!\cos \theta\!-\!x_0 \!\mp\! r \!\mp\! \tfrac{\delta}{4}\big) \sin\!\big(\tfrac{\pi \big(m+\tfrac{1}{2}\big) (\cos \theta-x_0)}{\delta +r}\big) e^{-\kappa ^2 \big(\cos \theta-x_0 \mp r \mp \tfrac{\delta}{4}\big)^2}. \end{align}\]

Substituting 27 into 26 , and noticing that the coefficient vector \(\|\mathbf{c}^{(\mathrm{even})} + \mathbf{c}^{(\mathrm{odd})}\|_1 \leq B\) regardless of the parity of \(f\), we conclude that \(|F''_k(\theta)| \leq O(Bd^3)\). ◻

Proof. As specified in [prop:angles-for-Chebyshev-polys], we first notice that we can derive the sequence of rotation angles corresponding to Chebyshev polynomials \(T_k(x)\) by directly factorizing them.

Then, we implement the quantum singular value transformation \(T_k^{\mathrm{(SV)}}(A)\), utilizing an alternating phase modulation ([prop:phase-modulation]) with the aforementioned sequence of rotation angles, denoted by \(V\).

Owing to the robustness of QSVT (Lemma 22 in [101], full version of [11]), we have that \(\big\| T_k^{\rm (SV)}(U) - T_k^{\rm (SV)}(U')\big\| \leq 4k\sqrt{\|A-A'\|} = 4k\sqrt{\epsilon}\), where \(U'\) is a \((1,a,0)\)-bitstring indexed encoding of \(A\). Moreover, with a tighter bound for \(A\) and \(A'\), namely \(\|A-A'\| + \big\|\frac{A+A'}{2}\big\|^2 \leq 1\), we can deduce that \(\|T_k^{\mathrm{(SV)}}(U) - T_k^{\mathrm{(SV)}}(U')\| \leq k \frac{\sqrt{2}}{\sqrt{1-\|(A+A')/2\|^2}} \|A-A'\| \leq \frac{\sqrt{2}}{\sqrt{1-\zeta}} k\epsilon\) following [101], indicating an improved dependence of \(\epsilon\). Finally, we can compute the description of the resulting quantum circuits in \(O(\log{k}) = O(s(n))\) space and \(O(k)\) times because of the implementation specified in [prop:phase-modulation]. ◻

Proof. For the \(\epsilon_2\)-state preparation operator \(P_{\abs{\mathbf{y}}}\) such that \[P_{\abs{\mathbf{y}}}\lvert{\bar{0}}\rangle=\sum_{i=0}^{m-1} \sqrt{\hat{y}'_i} \lvert{i}\rangle,\quad\text{where } y'_i\mathrel{\vcenter{:}}= \frac{\abs*{y_i}}{\norm{\mathbf{y}}_1} \quad\text{and}\quad \sum_{i=0}^{m-1} \abs*{y'_i-\hat{y}'_i}\leq \epsilon_2,\] we utilize a scheme introduced by Zalka [102] (also independently rediscovered in [103] and [104]). We make an additional analysis of the required classical computational complexity, and the proof of [prop:real-state-preparation] follows immediately afterward:

Applying [prop:real-state-preparation] to the normalized nonnegative vector \((y'_0,\ldots,y'_{m-1})\) with \(\epsilon=\epsilon_2\) gives the desired \(P_{|\mathbf{y}|}\) with the same deterministic time, space, and oracle-call bounds as in the statement. The signs of the coefficients are implemented separately by the diagonal unitary \(D_{\mathbf{y}} = \sum_{i=0}^{m-1}\sigma_i\lvert{i}\rangle\langle{i}\rvert + \rbra*{ I-\sum_{i=0}^{m-1}\lvert{i}\rangle\langle{i}\rvert }\), where \(\sigma_i\in\{\pm 1\}\) satisfies \(y_i=\sigma_i|y_i|\).

Now consider the bitstring indexed encoding \(\rbra[\big]{ P_{\abs{\mathbf{y}}}^{\dagger} D_\mathbf{y}\otimes I_{s+a} } W \rbra[\big]{ P_{\abs{\mathbf{y}}}\otimes I_{s+a} }\) of \(A\) acting on \(s+a+\lceil\log{m}\rceil\) qubits. Let \(y'_i\mathrel{\vcenter{:}}= \abs{y_i}/\norm{\mathbf{y}}_1\) so that \(y_i = \sigma_i y'_i \norm{\mathbf{y}}_1\), then we obtain the implementation error: \[\begin{align} & \big\| A - \|\mathbf{y}\|_1 \big(\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \tilde{\Pi}\big) \rbra[\big]{ P_{\abs{\mathbf{y}}}^{\dagger}D_\mathbf{y}\otimes I_{s+a} } W \rbra[\big]{ P_{\abs{\mathbf{y}}} \otimes I_{s+a} } \left(\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \Pi\right) \big\| \\ = & \norm[\big]{ \textstyle \norm{\mathbf{y}}_1 \sum_{i=0}^{m-1} \sigma_i y'_i A_i - \norm{\mathbf{y}}_1 \sum_{i=0}^{m-1} \sigma_i \hat{y}'_i \, \tilde{\Pi} U_i \Pi} \\ \leq & \norm[\big]{ \textstyle \norm{\mathbf{y}}_1 \sum_{i=0}^{m-1} \sigma_i y'_i \big(A_i-\tilde{\Pi} U_i \Pi\big) } + \norm[\big]{ \norm{\mathbf{y}}_1 \sum_{i=0}^{m-1} \sigma_i \big(y'_i-\hat{y}'_i\big) \tilde{\Pi} U_i \Pi } \\ \leq & \norm{\mathbf{y}}_1 \textstyle\sum_{i=0}^{m-1} y'_i \norm{ A_i-\tilde{\Pi} U_i \Pi} + \norm{\mathbf{y}}_1 \sum_{i=0}^{m-1} \abs*{y'_i-\hat{y}'_i} \norm{\tilde{\Pi} U_i \Pi} \\ \leq & \norm{\mathbf{y}}_1 \rbra{ \textstyle \sum_{i=0}^{m-1} y'_i } \epsilon_1 + \epsilon_2 \, \norm{\mathbf{y}}_1 \\ = & (\epsilon_1 + \epsilon_2) \|\mathbf{y}\|_1. \end{align}\] Here, the second line uses \(y_i=\sigma_i y'_i\norm{\mathbf{y}}_1\), \(\langle{\bar{0}}\rvert P^\dagger_{\abs{\mathbf{y}}}D_\mathbf{y}\lvert{i}\rangle=\sigma_i\sqrt{\hat{y}'_i}\), and \(\langle{i}\rvert P_{\abs{\mathbf{y}}}\lvert{\bar{0}}\rangle=\sqrt{\hat{y}'_i}\) for each \(0\leq i<m\); the third and fourth lines follow from the triangle inequality and \(\abs{\sigma_i}=1\); and the fifth line follows because each \(U_i\) is a \((1,a,\epsilon_1)\)-bitstring indexed encoding of \(A_i\), \(\norm{\tilde{\Pi}U_i\Pi}\leq 1\), and the error bound guaranteed by [prop:real-state-preparation].

Finally, the diagonal unitary \(D_{\mathbf{y}}\) is computed from the signs of the coefficients and does not change the asymptotic deterministic time or space bounds of the classical preprocessing, which completes the proof. ◻

Proof of [prop:real-state-preparation]. We follow the analysis presented in [105], with a particular focus on the classical computational complexity required for this state preparation procedure. The algorithm for preparing the state \(\lvert{\psi}\rangle\) expresses the weight \(W_x\) as a telescoping product, given by \[\label{eq:state-preparation-telescoping-product} \begin{align} \forall x \in \{0,1\}^l,~W_x &= W_{x_1} \cdot \frac{W_{x_1 x_2}}{W_{x_1}} \cdot \frac{W_{x_1 x_2 x_3}}{W_{x_1 x_2}} \cdots \frac{W_x}{W_{x_1\cdots x_{l-1}}},\\ \text{ where } W_x &\mathrel{\vcenter{:}}= \sum_{y\in\{0,1\}^{l-|x|}} |\langle xy | \psi \rangle|^2. \end{align}\tag{28}\]

To estimate \(\lvert{\psi}\rangle\) up to accuracy \(\epsilon\) in the \(\ell_2\) norm, it suffices to approximate each weight \(W_x\) up to additive error \(\varepsilon \mathrel{\vcenter{:}}= O(\epsilon^2/m)\), as indicated in [105]. To compute \(W_{x'}\), we need \(2^{l-|x'|}\) oracle calls to \(\mathrm{Eval}(\cdot, \varepsilon)\). Evaluating all terms in 28 requires computing \(W_{x_1}, W_{x_1x_2}, \cdots, W_x\) for any \(x\in\{0,1\}^l\), which can be achieved by \(2^{l-1}+2^{l-2}+\cdots+1 = 2^l\) oracle calls to \(\mathrm{Eval}(\cdot, \varepsilon)\). As we need to compute 28 for all \(x\in\{0,1\}^l\), the overall number of oracle calls to \(\mathrm{Eval}(\cdot, \varepsilon)\) is \(2^{2l}=m^2\). The remaining computation can be achieved in deterministic time \(\tilde{O}(m^2\log(m/\epsilon))\) and space \(O(\log(m/\epsilon^2))\) where the time complexity is because of the iterated integer multiplication. ◻

Proof. Following 8, we have \(\| A - \alpha \tilde{\Pi} U \Pi \| \leq \epsilon\), where \(\tilde{\Pi}\) and \(\Pi\) are the corresponding orthogonal projections. Because \(U\) is a \((1, a, \epsilon/\alpha)\)-bitstring indexed encoding \(A/\alpha\), we obtain that \(\|A / \alpha\| \leq \| U \| + \epsilon/\alpha = 1 + \epsilon/\alpha\), equivalently \(\|A\| \leq \alpha + \epsilon\).

Adjusting the encoding through a single-qubit rotation.

Consider an integer \(k \mathrel{\vcenter{:}}= 4\ceil*{\pi(\alpha+1)/4}+1 \leq 9\alpha = O(\alpha)\) so that \(k \equiv 1 \pmod 4\) and \(\gamma \mathrel{\vcenter{:}}= (\alpha+\epsilon)\sin(\pi/2k) \leq 1\). We define new orthogonal projections \(\tilde{\Pi}' \mathrel{\vcenter{:}}= \tilde{\Pi} \otimes \lvert{0}\rangle\langle{0}\rvert\) and \(\Pi' \mathrel{\vcenter{:}}= \Pi \otimes \lvert{0}\rangle\langle{0}\rvert\), and combine them with \(U' = U \otimes R_\gamma\), where \(R_\gamma = \begin{psmallmatrix} \gamma & -\sqrt{1-\gamma^2} \\ \sqrt{1-\gamma^2} & \gamma \end{psmallmatrix}\). By noting that \(\tilde{\Pi'} U' \Pi' = \gamma \tilde{\Pi} U \Pi \otimes \lvert{0}\rangle\langle{0}\rvert\), we deduce that \(U'\) is a \((1, a + 1, \gamma \epsilon/\alpha)\)-bitstring indexed encoding of \(\gamma A/\alpha \otimes \lvert{0}\rangle\langle{0}\rvert\), which is consequently a \((1, a+1, 2\gamma\epsilon/\alpha)\)-bitstring indexed encoding of \(\sin\rbra[\big]{\frac{\pi}{2k}} A \otimes \lvert{0}\rangle\langle{0}\rvert\). An error bound follows: \[\left\| \frac{\gamma}{\alpha} A - \sin\left(\frac{\pi}{2k}\right) A \right\| = \left\| \frac{\epsilon}{\alpha} \sin\left(\frac{\pi}{2k}\right) A \right\| \leq \frac{\epsilon}{\alpha} \sin\left(\frac{\pi}{2k}\right) (\alpha+\epsilon) = \frac{\gamma \epsilon}{\alpha}.\]

Renormalizing the encoding via robust oblivious amplitude amplification.

We follow the construction in [101], the full version of [11], and perform a meticulous analysis of the complexity. We observe that it suffices to consider \(k \geq 3\), as for \(U'\) is already a \((1,a+1,2\gamma\epsilon/\alpha)\)-bitstring indexed encoding of \(A\otimes \lvert{0}\rangle\langle{0}\rvert\) when \(k=1\). Let \(\varepsilon \mathrel{\vcenter{:}}= 2\gamma\epsilon/\alpha\), and for simplicity, we first start by considering the case with \(\varepsilon=0\). By 8, we have \(\tilde{\Pi}' U' \Pi' = \sin\rbra*{\frac{\pi}{2k}} A \otimes \lvert{0}\rangle\langle{0}\rvert\). Let \(T_k\in\mathbb{R}[x]\) be the degree-\(k\) Chebyshev polynomial (of the first kind). By employing 13, we can apply the QSVT associated with \(T_k\) to the bitstring indexed encoding \(U'\), yielding: \[\tilde{\Pi}' T_k^{\mathrm{(SV)}}(U') \Pi' = T_k\rbra[\Big]{\sin\rbra[\Big]{\frac{\pi}{2k}}} A \otimes \lvert{0}\rangle\langle{0}\rvert\\ = \cos\Big( \frac{k-1}{2}\pi \Big) A \otimes \lvert{0}\rangle\langle{0}\rvert\\ = A \otimes \lvert{0}\rangle\langle{0}\rvert.\] Here, the second equality is due to \(T_k\big(\sin\big(\frac{\pi}{2k}\big)\big) = T_k\big(\cos\big(\frac{\pi}{2}-\frac{\pi}{2k}\big)\big) = \cos\big( \frac{k-1}{2} \pi \big)\), and the last equality holds because \(k\equiv 1 \pmod 4\).

Next, we move on the case with \(\varepsilon > 0\) and restrict it to \(\varepsilon \leq 1/3\).⁴⁰ Let \(A' \mathrel{\vcenter{:}}= \tilde{\Pi}' U' \Pi'\) and \(\hat{A} \mathrel{\vcenter{:}}= \sin\rbra*{\frac{\pi}{2k}} A \otimes \lvert{0}\rangle\langle{0}\rvert\), then we have \(\|A' - \hat{A}\| \leq \varepsilon\), indicating that \(\big\|\frac{A'+\hat{A}}{2}\big\|^2 \leq \frac{4}{9}\mathrel{\vcenter{:}}=\zeta\)⁴¹ and \(\|A'-\hat{A}\| + \big\|\frac{A'+\hat{A}}{2}\big\|^2 \leq \frac{1}{3} + \frac{4}{9} < 1\). By employing 13, as well as the facts that \(\frac{\sqrt{2}}{\sqrt{1-\zeta}} < 2\) and \(2k\varepsilon = 4k\gamma\epsilon/\alpha \leq 36\epsilon\), we can construct a \((1,a+2,36\epsilon)\)-bitstring indexed encoding of \(A\), denoted by \(V\).

Finally, we provide the computational resources required for implementing \(V\). As shown in 13, the implementation of \(V\) requires \(O(\alpha)\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\), and \(O(\alpha)\) single-qubit gates. Furthermore, the description of the resulting quantum circuit can be computed in deterministic time \(O(\alpha)\) and space \(O(s)\). ◻

Proof of 6. By using 13, we obtain \((1,a+1,4k\sqrt{\epsilon_1})\)-bitstring indexed encodings \(V_k\) corresponding to \(T_k(A)\), where \(1 \leq k \leq d'=2d-1\). If \(\hat{c}_0 \neq 0\), let \(V_0\) denote the trivial exact bitstring indexed encoding of \(T_0(A)/2 = I/2\) acting on the same \(s+a+1\) qubits; this can be implemented by a single-qubit rotation on the additional ancillary qubit. The descriptions of quantum circuits \(\{V_k\}_{k=0}^{d'}\) can be computed in \(O(s(n))\) space and \(\sum_{k=0}^{d'} k=O(d^2)\) time.

If \(U\) is a block-encoding, then all \(V_k\) are associated with the same projections. Otherwise, since \(P_{d'}\) is either even or odd, only one parity of Chebyshev polynomials appears in \(P_{d'}\); hence all relevant \(V_k\) are associated with the same projections by [prop:phase-modulation]. Employing 14, we obtain a \((\|\hat{\mathbf{c}}\|_1, \hat{a}, 4d'\sqrt{\epsilon_1}\|\hat{\mathbf{c}}\|_1+\epsilon_2\|\hat{\mathbf{c}}\|_1)\)-bitstring indexed encoding \(V_{\rm unnorm}\) for \(P_{d'}(A)=\hat{c}_0I/2+\sum_{k=1}^{d'} \hat{c}_k T_k(A)\), where \(\hat{a}\mathrel{\vcenter{:}}= a+\lceil\log{d}\rceil+1\). The remaining analysis depends on whether \(P_{d'}(A)\) is a partial isometry (up to a normalization factor):

• Partial isometry \(P_{d'}(A)\): Since \(P_{d'}(A)\) is a partial isometry, we have \(\norm{P_{d'}(A)}=1\). On the other hand, \(\norm{P_{d'}(A)} \leq |\hat{c}_0|/2 + \sum_{k=1}^{d'} |\hat{c}_k| \leq \|\hat{\mathbf{c}}\|_1\), and hence \(\|\hat{\mathbf{c}}\|_1 \geq 1\). If \(\|\hat{\mathbf{c}}\|_1=1\), then we simply take \(V_{\rm normed}\mathrel{\vcenter{:}}= V_{\rm unnorm}\). Otherwise, we can renormalize \(V_{\rm unnorm}\) by utilizing 15 and obtain a \((1, a', 144d'\sqrt{\epsilon_1}\|\hat{\mathbf{c}}\|_1 + 36\epsilon_2\|\hat{\mathbf{c}}\|_1)\)-bitstring indexed encoding \(V_{\rm normed}\) that acts on \(s+a'\) qubits, where \(a' \mathrel{\vcenter{:}}= \hat{a}+2 = a+\lceil\log{d'}\rceil+3\). A direct calculation shows that the implementation of \(V_{\rm normed}\) makes \(\sum_{k=1}^{d'} k \cdot O(\|\hat{\mathbf{c}}\|_1)=O(d^2\|\hat{\mathbf{c}}\|_1)\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\), and multi-controlled single-qubit gates. The description of the quantum circuit \(V_{\rm normed}\) thus can be computed in deterministic time \[\max\{\tilde{O}\big((d')^2\|\hat{\mathbf{c}}\|_1\log(d'/\epsilon_2)\big),O((d')^2\|\hat{\mathbf{c}}\|_1)\} = \tilde{O}(d^2\|\hat{\mathbf{c}}\|_1\log(d/\epsilon_2))\] and space \(O(\max\{s(n), \log(d'/\epsilon_2^2)\}) = O(\max\{s(n), \log(d/\epsilon_2^2)\})\), as well as \(O\big((d')^2\|\hat{\mathbf{c}}\|_1\big) = O(d^2\|\hat{\mathbf{c}}\|_1)\) oracle calls to \(\mathrm{Eval}\) with precision \(\varepsilon\).

• General \(P_{d'}(A)\): We simply use the bitstring indexed encoding \(V_{\rm unnorm}\) without renormalizing it. Similarly, the implementation of \(V_{\rm unnorm}\) makes \(O(d^2)\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\), and multi-controlled single-qubit gates. Therefore, the description of the quantum circuit \(V_{\rm unnorm}\) can be computed in deterministic time \(\tilde{O}(d^2\log(d/\epsilon_2))\) and space \(O(\max\{s(n), \log(d/\epsilon_2^2)\})\), as well as \(O(d^2)\) oracle calls to \(\mathrm{Eval}\) with precision \(\varepsilon\).

Finally, we can extend our construction to any linear operator \(A\) by replacing \(P_{d'}(A)\) with \(P_{d'}^{\mathrm{(SV)}}\) as defined in 2, taking into account that the Chebyshev polynomial (of the first kind) \(T_k\) is either an even or an odd function. ◻

Proof. Following 1, we have \(P_{d'}^{\mathrm{sgn}}(x) = \hat{c}_0/2+\sum_{k=1}^{d'} \hat{c}_k T_k(x)\), where \(d'=2d-1\) and \(d'=O(\delta^{-1}\log{\epsilon^{-1}})\). The approximation error is given by: \[\label{eq:sign-approx-error} \forall x\in[-1,1] \setminus [-\delta,\delta],~|\mathrm{sgn}(x)-P_{d'}^{\mathrm{sgn}}(x)| \leq C_{\mathrm{sgn}}\epsilon \mathrel{\vcenter{:}}=\epsilon_2.\tag{30}\] To implement \(\mathrm{Eval}\) with precision \(\varepsilon = O(\epsilon_2^2/d')\), we can compute the corresponding entry \(\hat{c}_k\) of the coefficient vector, which requires deterministic time \(\tilde{O}\big(\varepsilon^{-1/2} (d')^2\big)=\tilde{O}(\epsilon_2^{-1} d^{5/2})\) and space \(O\big(\log(\varepsilon^{-3/2}(d')^3)\big)=O(\log(\epsilon_2^{-3}d^{9/2}))\).

Note that \(P_{d'}^{\mathrm{sgn}}(A)\) is not a partial isometry (up to a normalization factor) and \(\|\hat{\mathbf{c}}\|_1\leq \hat{C}_{\mathrm{sgn}}\log d'\). Using 6, we have a \(\rbra[\big]{\hat{C}_{\mathrm{sgn}}\log d', a_{\rm un}, \rbra{4d'\epsilon_1^{1/2}+\epsilon_2}\hat{C}_{\mathrm{sgn}}\log d'}\)-bitstring indexed encoding \(V_{\rm un}\), with projections \(\tilde{\Pi}\) and \(\Pi\), that acts on \(s+a_{\rm un}\) qubits and \(a_{\rm un} \mathrel{\vcenter{:}}= a+\lceil \log d' \rceil+1\).

Renormalizing the encoding of \(P^{\mathrm{sgn}}_{d'}(A)\).

Notably, the renormalization procedure (15) is still applicable when \(P_{d'}^{\mathrm{sgn}}(A)\) is restricted to appropriately chosen subspaces \(\Gamma_L\) and \(\Gamma_R\). Let \(A = \sum_{i=1}^{\mathrm{rank}(A)} \sigma_i \mathbf{u}_i \mathbf{v}_i^\dagger\) be the singular value decomposition of \(A\). We define \(A_{>\delta} \mathrel{\vcenter{:}}= \sum_{i: \sigma_i > \delta} \sigma_i \mathbf{u}_i \mathbf{v}_i^\dagger\), as well as subspaces \(\Gamma_L\mathrel{\vcenter{:}}=\mathrm{span}\{\mathbf{u}_i|\sigma_i > \delta\}\) and \(\Gamma_R\mathrel{\vcenter{:}}=\mathrm{span}\{\mathbf{v}_i | \sigma_i > \delta\}\). Consequently, we obtain the following for the bitstring indexed encoding \(V_{\rm un}\) with projections \(\tilde{\Pi}\) and \(\Pi\):

\[\label{eq:sign-subspace-isometry-unnorm} \begin{align} &\| \mathrm{sgn}^{\mathrm{(SV)}}(A_{> \delta}) - \hat{C}_{\mathrm{sgn}}\log d' \cdot \tilde{\Pi}|_{\Gamma_L} V_{\rm un} \Pi|_{\Gamma_R} \|\\ \leq~& \| \mathrm{sgn}^{\mathrm{(SV)}}(A_{> \delta}) - P_{d'}^\mathrm{sgn}(A_{> \delta}) \| + \| P_{d'}^\mathrm{sgn}(A_{> \delta}) - \hat{C}_{\mathrm{sgn}}\log d' \cdot \tilde{\Pi}|_{\Gamma_L} V_{\rm un} \Pi|_{\Gamma_R} \| \\ \leq~& \epsilon_2 + \| P_{d'}^\mathrm{sgn}(A_{> \delta}) - \hat{C}_{\mathrm{sgn}}\log d' \cdot \tilde{\Pi} V_{\rm un} \Pi \| \\ \leq~& \epsilon_2 + \rbra{4d'\epsilon_1^{1/2}+\epsilon_2}\hat{C}_{\mathrm{sgn}}\log d'. \end{align}\tag{31}\]

Here, the second line owes to the triangle inequality, the third line uses the fact that restricting to subspaces cannot increase the operator norm together with 30 , and the last line is because \(V_{\rm un}\) is a \(\rbra[\big]{\hat{C}_{\mathrm{sgn}}\log d', a_{\rm un}, \rbra{4d'\epsilon_1^{1/2}+\epsilon_2}\hat{C}_{\mathrm{sgn}}\log d'}\)-bitstring indexed encoding of \(P_{d'}^\mathrm{sgn}(A_{> \delta})\). Note that \(\mathrm{sgn}^{\mathrm{(SV)}}(A_{> \delta})\) is a partial isometry, and 31 implies that \(V_{\rm un}\) is a projected unitary encoding of \(\mathrm{sgn}^{\mathrm{(SV)}}(A_{> \delta})\). By applying 15 to \(V_{\rm un}\) with projections \(\tilde{\Pi}|_{\Gamma_L}\) and \(\Pi|_{\Gamma_R}\), we can obtain a \(\rbra[\big]{1, a_{\rm un}+2, 144\hat{C}_{\mathrm{sgn}} d'\log d'\epsilon_1^{1/2} + 36(\hat{C}_{\mathrm{sgn}}\log d'+1)\epsilon_2}\)-projected unitary encoding of \(\mathrm{sgn}^{\mathrm{(SV)}}(A_{> \delta})\), denoted as \(V\). Consequently, we can derive that:

\[\label{eq:sign-subspace-isometry-normed} \begin{align} &\| P^{\mathrm{sgn}}_{d'}(A_{>\delta}) - \tilde{\Pi}|_{\Gamma_L} V \Pi|_{\Gamma_R}\| \\ \leq~& \| P^{\mathrm{sgn}}_{d'}(A_{>\delta}) - \mathrm{sgn}^{\mathrm{(SV)}}(A_{>\delta})\| + \| \mathrm{sgn}^{\mathrm{(SV)}}(A_{>\delta}) - \tilde{\Pi}|_{\Gamma_L} V \Pi|_{\Gamma_R}\| \\ \leq~& \epsilon_2 + 144\hat{C}_{\mathrm{sgn}}d'\log d' \epsilon_1^{1/2} + 36(\hat{C}_{\mathrm{sgn}}\log d' +1)\epsilon_2. \end{align}\tag{32}\]

Here, the second line follows from the triangle inequality, and the third line additionally owes to 30 . Noting that 15 essentially applies a Chebyshev polynomial to \(V_{\rm un}\) and preserves the projections \(\tilde{\Pi}|_{\Gamma_L}\) and \(\Pi|_{\Gamma_R}\), then we have \(\|\tilde{\Pi} V \Pi\| \leq 1\). Therefore, following 32 , we conclude that \(P^{\mathrm{sgn}}_{d'}(A)\) has a \(\rbra[\big]{1, a', 144\hat{C}_{\mathrm{sgn}}d'\log d' \epsilon_1^{1/2} + (36\hat{C}_{\mathrm{sgn}}\log d' +37)\epsilon_2 }\)-bitstring indexed encoding \(V\) that acts on \(s+a'\) qubits, where \(a'\mathrel{\vcenter{:}}= a+ \ceil*{\log{d'}} +3\).⁴²

Lastly, we can complete the remaining analysis similarly to 6 with a partial isometry \(P_{d'}(A)\). Since \(\|\hat{\mathbf{c}}\|_1 \leq \hat{C}_{\mathrm{sgn}}\log d'\), the quantum circuit of \(V\) makes \(O(d^2\log d)\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), and \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\) as well as \(O(d^2\log d)\) multi-controlled single-qubit gates. We note that \(d'=O(d) \leq 2^{O(s(n))}\) and \(\epsilon_2 \geq 2^{-O(s(n))}\). Moreover, we can compute the description of \(V\) in \(O(s(n))\) space since each oracle call to \(\mathrm{Eval}\) with precision \(\varepsilon\) can be computed in \(O(\log(\epsilon_2^{-3} d^{9/2}))\) space. Additionally, the time complexity for computing the description of \(V\) is \[\max\{\tilde{O}(d^2(\log d)\log(d/\epsilon_2)), O(d^2\log d) \cdot \tilde{O}(\epsilon_2^{-1} d^{5/2})\} = \tilde{O}(\epsilon_2^{-1} d^{9/2}). \qedhere\] ◻

Proof. Following 2, we have \(P_{d'}^{\ln}(x) = c^{\ln}_0/2+\sum_{k=1}^{d'} c^{\ln}_k T_k(x)\), where \(P_{d'}^{\ln}\) corresponds to some degree-\(d\) averaged Chebyshev truncation and \(d'=2d-1\leq \tilde{C}_{\ln}\beta^{-1}\log\rbra{\epsilon^{-1}}\). For any \(\ln_{\beta}(x)\), we have \(|\ln_{\beta}(x)-P_{d'}^{\ln}(x)| \leq C_{\ln}\epsilon \mathrel{\vcenter{:}}=\epsilon_2\) for all \(x\in[\beta,1]\). To implement \(\mathrm{Eval}\) with precision \(\varepsilon = O(\epsilon_2^2/d)\), we can compute the corresponding entry \(c^{\ln}_k\) of the coefficient vector by a bounded-error randomized algorithm. This requires \(O(\log(\beta^{-4} \varepsilon^{-3/2} d^3))=O(\log(\beta^{-4} \epsilon_2^{-3} d^{9/2}))\) space and \(\tilde{O}(\max\{\beta^{-5}\varepsilon^{-2}, \varepsilon^{-1/2} d^2\}) = \tilde{O}(\max\{\beta^{-5} \epsilon_2^{-4} d^2, \epsilon_2^{-1} d^{5/2}\})\) time. Applying 6 with \(\|\mathbf{c}^{\ln}\|_1 \leq \hat{C}_{\ln}d'^{1/2}\), we conclude that \(P_{d'}^{\ln}\) has a \(\rbra[\big]{\hat{C}_{\ln}d'^{1/2}, \hat{a}, \rbra{4d'\epsilon_1^{1/2} + \epsilon_2} \hat{C}_{\ln} d'^{1/2}}\)-bitstring indexed encoding \(V\) that acts on \(s+\hat{a}\) qubits, where \(\hat{a}\mathrel{\vcenter{:}}= a+\lceil\log{d'}\rceil+1\).

Furthermore, the quantum circuit of \(V\) makes \(O((d')^2)=O(d^2)\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\), and multi-controlled single-qubit gates. We note that \(d'=2d-1 \leq 2^{O(s(n))}\), \(\epsilon_2 \geq 2^{-O(s(n))}\), and \(\beta \geq 2^{-O(s(n))}\). Additionally, we can compute the description of \(V\) in \(O(s(n))\) space since each oracle call to \(\mathrm{Eval}\) with precision \(\varepsilon\) can be computed in \(O(\log(\beta^{-4} \epsilon_2^{-3} d^{9/2}))\) space. The time complexity for computing the description of \(V\) is given by: \[\label{eq:log-poly-time-complexity} \begin{align} & \max\cbra*{ \tilde{O}(d^2 \log(d/\epsilon_2)), O(d^2) \tilde{O}(\max\{\beta^{-5} \epsilon_2^{-4} d^2, \epsilon_2^{-1} d^{5/2}\}) } \\ =~& \tilde{O}(\max\{\beta^{-5} \epsilon_2^{-4} d^4, \epsilon_2^{-1} d^{9/2}\}). \end{align}\tag{33}\]

Finally, to guarantee that the probability that all \(O((d')^2)=O(d^2)\) oracle calls to \(\mathrm{Eval}\) succeed is at least \(2/3\), we use a \(\ceil*{4\ln(d'+1)}\)-time sequential repetition of \(\mathrm{Eval}\) for each oracle call. Together with the Chernoff–Hoeffding bound and the union bound, the resulting randomized algorithm succeeds with probability at least \(1-(d')^2 \cdot 2e^{-4\ln(d'+1)} \geq 2/3\). We further note that the time complexity specified in 33 only increases by a \(\ceil*{4\ln(d'+1)}\) factor. ◻

Proof. Let the singular value decomposition of \(A\) be \(A = W\Sigma V^{\dagger} = \sum_{i} \sigma_i \lvert{\tilde{\psi_i}}\rangle\langle{\psi_i}\rvert\).⁴⁴ Note that \(U\) is a \((1,0,0)\)-bitstring indexed encoding, with projections \(\tilde{\Pi}\) and \(\Pi\), of \(A\). Let singular value threshold projectors \(\Pi_{\geq\delta}\) and \(\Pi'_{\geq\delta}\) be defined as \(\Pi_{\geq\delta} \mathrel{\vcenter{:}}= \Pi V\Sigma_{\geq \delta} V^{\dagger} \Pi\) and \({\Pi'}_{\geq\delta}\mathrel{\vcenter{:}}={\Pi'} W \Sigma_{\geq \delta} W^{\dagger} {\Pi'}\), respectively, with similar definitions for \(\Pi_{\leq \delta}\) and \({\Pi'}_{\leq \delta}\).

To discriminate whether the singular value corresponding to a given right singular vector of \(A\) exceeds a certain threshold, we need an \(\varepsilon\)-singular value discriminator \(U_P\). Specifically, it suffices to construct a \((1,a,\tilde{\epsilon})\)-bitstring indexed encoding \(U_P\) of \(P(A)\), associated with an appropriate odd polynomial \(P\), that satisfies 34 . The parameters \(a\) and \(\tilde{\epsilon}\) will be specified later. \[\label{eq:threshold-projections} \begin{align} \textstyle \Big\| \big(\langle{0}\rvert^{\otimes a}\otimes{\Pi'}_{\geq t+\delta}\big) U_P \big(\lvert{0}\rangle^{\otimes a}\otimes\Pi_{\geq t+\delta}\big) - \sum_{i \in \Lambda} \lvert{\tilde{\psi}_i}\rangle\langle{\psi_i}\rvert\Big\| &\leq \varepsilon,\\ \Big\| \big(\langle{0}\rvert^{\otimes a}\otimes{\Pi'}_{\leq t-\delta}\big) U_P \big(\lvert{0}\rangle^{\otimes a}\otimes\Pi_{\leq t-\delta}\big) - 0 \Big\| &\leq \varepsilon. \end{align}\tag{34}\] Here, the index set \(\Lambda \mathrel{\vcenter{:}}= \{ i \colon \sigma_i \geq t+\delta\}\). Additionally, following the proof in [11], \(\Pi'\) is defined as \(\tilde{\Pi}\) if \(\beta-\alpha \geq \sqrt{1-\alpha^2}-\sqrt{1-\beta^2}\), and as \(I-\tilde{\Pi}\) otherwise.⁴⁵

With the construction of this bitstring indexed encoding \(U_P\), we can apply an \(\varepsilon\)-singular value discriminator with \(\Pi' = \tilde{\Pi}\) by choosing \(t \mathrel{\vcenter{:}}= (\alpha+\beta)/2\) and \(\delta \mathrel{\vcenter{:}}= (\beta-\alpha)/2\); and with \(\Pi'=I-\tilde{\Pi}\) by choosing \(t\coloneq \rbra[\big]{\sqrt{1-\beta^2}+\sqrt{1-\alpha^2}}/2\) and \(\delta \mathrel{\vcenter{:}}= \rbra[\big]{\sqrt{1-\alpha^2}-\sqrt{1-\beta^2}}/2\), respectively. Next, we measure \(\lvert{0}\rangle\langle{0}\rvert^{\otimes a} \otimes\Pi'\): If the final state is in \(\mathrm{Img}\big(\lvert{0}\rangle\langle{0}\rvert^{\otimes a} \otimes\Pi'\big)\), there exists a singular value \(\sigma_i\) above \(\beta\) (resp., \(\sqrt{1-\alpha^2}\)); otherwise, all singular values \(\sigma_i\) must be below \(\alpha\) (resp., \(\sqrt{1-\beta^2}\)). Furthermore, we can make the error one-sided when \(\alpha=0\) or \(\beta=1\), since a space-efficient QSVT associated with an odd polynomial always preserves \(0\) singular values (see [remark:QSVT-parity-preserving]).

It remains to implement an \(\varepsilon\)-singular value discriminator \(U_P\) for some odd polynomial \(P\).

Implementing \(\varepsilon\)-singular value discriminator.

We begin by considering the following odd function \(Q(x)\) such that \(Q(A) \approx U_P\) and \(Q(A)\) satisfies 34 : \[Q(x)\mathrel{\vcenter{:}}= \tfrac{1}{2}\left[\big(1-\tfrac{\varepsilon}{2}\big)\cdot \mathrm{sgn}(x+t) + \big(1-\tfrac{\varepsilon}{2}\big)\cdot \mathrm{sgn}(x-t) + \varepsilon\cdot \mathrm{sgn}(x)\right].\]

Let \(B \mathrel{\vcenter{:}}= 1 + \log\frac{1+t}{\delta} + \log\frac{1}{\varepsilon}\), and choose \(\epsilon \mathrel{\vcenter{:}}= \frac{\varepsilon}{64B \cdot \max\cbra{1,36\hat{C}_{\mathrm{sgn}}+37,C_{\mathrm{sgn}}+38,\tilde{C}_{\mathrm{sgn}}}}\). Using the space-efficient polynomial approximation \(P_{d'}^{\mathrm{sgn}}\) of the sign function (1), with threshold parameter \(\delta/(1+t)\), error parameter \(\epsilon\), and the affine maps \(x\mapsto (x+t)/(1+t)\) and \(x\mapsto (x-t)/(1+t)\), we obtain the following degree-\(d'\) polynomial \(P\) associated with some degree-\(d\) averaged Chebyshev truncation: \[P(x)=\tfrac{1}{2}\left[\big(1-\tfrac{\varepsilon}{2}\big)\cdot P_{d'}^{\mathrm{sgn}}\rbra[\big]{\tfrac{x+t}{1+t}} + \big(1-\tfrac{\varepsilon}{2}\big)\cdot P_{d'}^{\mathrm{sgn}}\rbra[\big]{\tfrac{x-t}{1+t}} + \varepsilon\cdot P_{d'}^{\mathrm{sgn}}(x)\right].\]

Noting that \(P(x)\) is a convex combination of \(P_{d'}^{\mathrm{sgn}}\rbra[\big]{\tfrac{x+t}{1+t}}\), \(P_{d'}^{\mathrm{sgn}}\rbra[\big]{\tfrac{x-t}{1+t}}\), and \(P_{d'}^{\mathrm{sgn}}(x)\), the constant \(\hat{C}_{\mathrm{sgn}}\) specified in 1 remains the same, while \(\tilde{C}_{\mathrm{sgn}}\) absorbs the factor \(2\). Hence, \(P\) is a polynomial of degree \(d'=2d-1 \leq \tilde{C}_{\mathrm{sgn}}\frac{1+t}{\delta}\log\frac{1}{\epsilon}\), and the coefficient vector \(\hat{\mathbf{c}}^{(P)}\) satisfies \(\|\hat{\mathbf{c}}^{(P)}\|_1 \leq \hat{C}_{\mathrm{sgn}} \log{d'}\).

Recall the notation \(\|f\|_{\mathcal{I}}\) defined in 3.1.2, namely \(\|f\|_{\mathcal{I}} \mathrel{\vcenter{:}}= \sup\{|f(x)|: x\in \mathcal{I}\}\). Let \(D(x) \mathrel{\vcenter{:}}= \mathrm{sgn}(x) - P^{\mathrm{sgn}}_{d'}\), \(\mathcal{I}_{0} \mathrel{\vcenter{:}}= (0,t-\delta]\), and \(\mathcal{I}_{1} \mathrel{\vcenter{:}}= [t+\delta,1]\). Following 1, we obtain: \[\label{eq:singular-value-discriminator-poly-error} \begin{align} \|P(x)-Q(x)\|_{[\delta-t,0)} &= \|P(x) - Q(x)\|_{\mathcal{I}_0}\\ &\leq \tfrac{2-\varepsilon}{4}\|D\rbra[\big]{\tfrac{x+t}{1+t}}\|_{\mathcal{I}_0} + \tfrac{2-\varepsilon}{4}\|D\rbra[\big]{\tfrac{x-t}{1+t}}\|_{\mathcal{I}_0} + \tfrac{\varepsilon}{2} \|D(x)\|_{\mathcal{I}_0}\\ &\leq \big(1 - \tfrac{\varepsilon}{2}\big) C_{\mathrm{sgn}} \epsilon + \tfrac{\varepsilon}{2},\\ \|P(x)-Q(x)\|_{[-1,-t-\delta]} &= \|P(x) - Q(x)\|_{\mathcal{I}_1}\\ &\leq \tfrac{2-\varepsilon}{4}\|D\rbra[\big]{\tfrac{x+t}{1+t}}\|_{\mathcal{I}_1} + \tfrac{2-\varepsilon}{4}\|D\rbra[\big]{\tfrac{x-t}{1+t}}\|_{\mathcal{I}_1} + \tfrac{\varepsilon}{2} \|D(x)\|_{\mathcal{I}_1}\\ &\leq \big(1 -\tfrac{\varepsilon}{2} + \tfrac{\varepsilon}{2} \big) C_{\mathrm{sgn}} \epsilon. \end{align}\tag{35}\] Here, the equalities hold because both \(P\) and \(Q\) are odd functions.

Using 6 with \(P\), \(\epsilon_1 \mathrel{\vcenter{:}}= 0\), and \(\epsilon_2 \mathrel{\vcenter{:}}= \epsilon\), we obtain a \(\rbra{\|\hat{\mathbf{c}}^{(P)}\|_1, \ceil*{\log{d'}+1}, \epsilon\|\hat{\mathbf{c}}^{(P)}\|_1}\)-bitstring indexed encoding of \(P(A)\). Applying the same renormalization argument as in the proof of 3, we obtain a \((1, a, \tilde{\epsilon})\)-bitstring indexed encoding \(U_P\) of \(P(A)\), with \(a \mathrel{\vcenter{:}}= \lceil \log{d'} \rceil+3\) and \(\tilde{\epsilon} \mathrel{\vcenter{:}}= (36 \hat{C}_{\mathrm{sgn}} \log{d'} +37) \epsilon\). One can verify that \(\rbra{36 \hat{C}_{\mathrm{sgn}}\log d' + 37}\epsilon \leq \varepsilon/2\) and \(\rbra{C_{\mathrm{sgn}}+1}\epsilon \leq \varepsilon/2\). Together with 35 , we obtain: \[\begin{align} \textstyle \Big\| \big(\langle{0}\rvert^{\otimes a}\otimes{\Pi'}_{\geq t+\delta}\big) U_P \big(\lvert{0}\rangle^{\otimes a}\otimes\Pi_{\geq t+\delta}\big) - \sum_{i\in\Lambda} \lvert{\tilde{\psi}_i}\rangle\langle{\psi_i}\rvert\Big\| &\leq \big(1\!-\!\tfrac{\varepsilon}{2} \!+\! \tfrac{\varepsilon}{2} \big) C_{\mathrm{sgn}} \epsilon + \tilde{\epsilon} \leq \varepsilon, \\ \Big\| \big(\langle{0}\rvert^{\otimes a}{\Pi'}_{\leq t-\delta}\big) U_P \big(\lvert{0}\rangle^{\otimes a}\otimes\Pi_{\leq t-\delta}\big) - 0 \Big\| &\leq C_{\mathrm{sgn}} \epsilon + \tfrac{\varepsilon}{2} + \tilde{\epsilon} \leq \varepsilon. \end{align}\] Hence, we conclude that our construction of \(U_P\) indeed satisfies 34 .

Finally, we analyze the complexity of this \(\varepsilon\)-singular value discriminator \(U_P\). Following 3, the quantum circuit implementation of \(U_P\) requires \(O(d^2 \log{d})\) uses of \(U\), \(U^{\dagger}\), \(\mathrm{\small C}_{\Pi}\mathrm{\small NOT}\), \(\mathrm{\small C}_{\tilde{\Pi}}\mathrm{\small NOT}\), and multi-controlled single-qubit gates. Moreover, we can compute the description of the circuit implementation in deterministic time \(\tilde{O}(\epsilon^{-1} d^{9/2}) = \tilde{O}(\varepsilon^{-1} \delta^{-9/2})\) and space \(O(s(n))\), where \(\delta = \max\{\beta-\alpha, \sqrt{1-\alpha^2}-\sqrt{1-\beta^2}\}/2\). ◻

Proof of 7. It suffices to amplify the promise gap by QSVT. Note that the probability that a \(\texorpdfstring{\textrm{\textsf{BQ}\textsubscript{U}\textsf{SPACE}}}{[s(n)]}\) circuit \(C_x\) accepts is \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] = \| \lvert{1}\rangle\langle{1}\rvert_{\mathrm{out}} C_x \lvert{0^{k+m}}\rangle \|_2^2 \geq a\) for yes instances, whereas \(\mathrm{Pr}\!\left[C_x \text{ accepts }\right] = \| \lvert{1}\rangle\langle{1}\rvert_{\mathrm{out}} C_x \lvert{0^{k+m}}\rangle \|_2^2 \leq b\) for no instances. Then consider a \((1,0,0)\)-bitstring indexed encoding \(M_x\mathrel{\vcenter{:}}=\Pi_{\mathrm{out}} C_x \Pi_{\mathrm{in}}\) such that \(\| M_x \| \geq \sqrt{a}\) for yes instances while \(\| M_x \| \leq \sqrt{b}\) for no instances, where \(\Pi_{\mathrm{in}}\mathrel{\vcenter{:}}= \lvert{0}\rangle\!\langle{0}\rvert^{\otimes k+m}\) and \(\Pi_{\mathrm{out}}\mathrel{\vcenter{:}}= \lvert{1}\rangle\langle{1}\rvert_{\mathrm{out}} \otimes I_{m+k-1}\). Since \(\|M_x\|=\sigma_{\max}(M_x)\) where \(\sigma_{\max}(M_x)\) is the largest singular value of \(M_x\), it suffices to distinguish the largest singular value of \(M_x\) is either above \(\sqrt{a}\) or below \(\sqrt{b}\). By setting \(\alpha\mathrel{\vcenter{:}}=\sqrt{b}\), \(\beta\mathrel{\vcenter{:}}=\sqrt{a}\), and \(\varepsilon\mathrel{\vcenter{:}}=2^{-l(n)}\), this task is a direct corollary of 16. ◻

Proof of 17. Note that \(U_A\) is a \((1, a, 0)\)-block-encoding of \(A\), where \(a = s - r\).

We first consider the case where \(\alpha=\|\hat{\mathbf{c}}\|_1\), which holds for any \(P_{d'}\) and \(A\). By 6 with \(\epsilon_1 \mathrel{\vcenter{:}}= 0\) and \(\epsilon_2 \mathrel{\vcenter{:}}= \epsilon\), we can implement an \(O(s)\)-qubit quantum circuit \(U'\) that is a \((\|\hat{\mathbf{c}}\|_1, \hat{a}, \epsilon\|\hat{\mathbf{c}}\|_1)\)-block-encoding of \(P_{d'}(A)\), using \(O(d^2)\) queries to \(U_A\), where \(\hat{a} = a + \lceil\log d'\rceil + 1\). Assume that \(U'\) is a \((1, \hat{a}, 0)\)-block-encoding of \(A'\), then \(\| \|\hat{\mathbf{c}}\|_1 A' - P_{d'}(A) \| \leq \|\hat{\mathbf{c}}\|_1\epsilon\). Additionally, we can compute the quantum circuit description of \(U'\) in deterministic space \(O(s+\log(1/\epsilon))\) given the coefficient vector \(\hat{\mathbf{c}}\) of \(P_{d'}\). As the quantum tester \(\mathcal{T}(Q, U_A, P_{d'}, \epsilon)\) is mainly based on the Hadamard test, by employing 19, we have that \(\mathcal{T}\) outputs \(0\) with probability \[\mathrm{Pr}\!\left[x = 0\right] = \frac{1}{2}\big(1+\operatorname{Re}(\mathrm{Tr}(A'\rho))\big) = \frac{1}{2}\left(1+\operatorname{Re}\!\left(\mathrm{Tr}\Big(\frac{P_{d'}(A)}{\|\hat{\mathbf{c}}\|_1}\rho\Big)\right)\right) \pm \frac{1}{2} \epsilon.\] It is left to construct the estimation procedure \(\hat{\mathcal{T}}\). As detailed in 8, we obtain an estimation \(\widetilde{x}\) by sequentially repeating the quantum tester \(\mathcal{T}(Q,U_A,P_{d'},\epsilon)\) for \(O(1/\epsilon_H^2)\) times. This repetition ensures that \(|\widetilde{x} - \operatorname{Re}(\mathrm{Tr}(A'\rho))| \leq \epsilon_H\) holds with probability at least \(\Omega(1)\), and derives a further implication on \(P_{d'}(A)\): \[\mathrm{Pr}\!\left[ \left| \|\hat{\mathbf{c}}\|_1 \widetilde{x} - \operatorname{Re}(\mathrm{Tr}(P_{d'}(A)\rho)) \right| \leq (\epsilon + \epsilon_H) \|\hat{\mathbf{c}}\|_1 \right] \geq \Omega(1).\] We thus conclude that construction of the estimation procedure \(\hat{\mathcal{T}}(Q, U_A, P_{d'}, \epsilon, \epsilon_H, \delta)\) by utilizing \(O(\log(1/\delta)/\epsilon_H^2)\) sequential repetitions of \(\mathcal{T}(Q, U_A, P_{d'}, \epsilon)\). Similarly following 8, \(\hat{\mathcal{T}}(Q, U_A, P_d, \epsilon, \epsilon_H, \delta)\) outputs an estimate \(\widetilde{x}\) satisfies the following condition: \[\mathrm{Pr}\!\left[ \left| \|\hat{\mathbf{c}}\|_1 \widetilde{x} - \operatorname{Re}(\mathrm{Tr}(P_{d'}(A)\rho)) \right| \leq (\epsilon + \epsilon_H) \|\hat{\mathbf{c}}\|_1 \right] \geq 1-\delta.\] In addition, a direct calculation indicates that we can implement \(\hat{\mathcal{T}}(Q, U_A, P_{d'}, \epsilon, \epsilon_H, \delta)\) in quantum space \(O(s+\log(1/\epsilon) + \log(1/\epsilon_H) + \log \log(1/\delta))\) as desired.

Next, we move to the case where \(\alpha=1\), applicable to certain \(P_{d'}\) and \(A\), namely when \(P_{d'}(A)\) is a partial isometry in 6 or \(P_{d'}=P^{\mathrm{sgn}}_{d'}\) in 3. The proof is similar, and we just sketch the key points as follows. Using 6 with \(\epsilon_1 \mathrel{\vcenter{:}}= 0\) and \(\epsilon_2 \mathrel{\vcenter{:}}= \epsilon/36\), we can implement an \(O(s)\)-qubit quantum circuit \(U'\) that is a \((1, a', \epsilon\|\hat{\mathbf{c}}\|_1)\)-block-encoding of \(P_{d'}(A)\), using \(O(d^2\|\hat{\mathbf{c}}\|_1)\) queries to \(U_A\), where \(a' = a + \lceil\log d'\rceil + 3\). Assume that \(U'\) is a \((1, a', 0)\)-block-encoding of \(A'\), then \(\| A' - P_{d'}(A) \| \leq \|\hat{\mathbf{c}}\|_1\epsilon\). Similarly, \(\mathcal{T}\) outputs \(0\) with probability \[\label{eq:state-tester-pacc} \mathrm{Pr}\!\left[x = 0\right] = \frac{1}{2}\big(1+\operatorname{Re}(\mathrm{Tr}(A'\rho))\big) = \frac{1}{2}\left(1+\operatorname{Re}\left(\mathrm{Tr}\left({P_{d'}(A)}\rho\right)\right)\right) \pm \frac{1}{2} \|\hat{\mathbf{c}}\|_1\epsilon.\tag{36}\] Therefore, we can obtain an estimate \(\widetilde{x}\) such that \[\label{eq:state-tester-estimation-error} \mathrm{Pr}\!\left[ \left| \widetilde{x} - \operatorname{Re}(\mathrm{Tr}(P_{d'}(A)\rho)) \right| \leq \|\hat{\mathbf{c}}\|_1 \epsilon + \epsilon_H \right] \geq 1-\delta.\tag{37}\]

For the special case \(P_{d'} = P^{\mathrm{sgn}}_{d'}\), use 3 with \(\epsilon_1\mathrel{\vcenter{:}}= 0\) and \(\epsilon_2 \mathrel{\vcenter{:}}= \frac{\norm{\hat{\mathbf{c}}^{\mathrm{sgn}}}_1}{36\hat{C}_{\mathrm{sgn}}\log d' + 37}\,\epsilon\). Then the resulting block-encoding error is at most \((36\hat{C}_{\mathrm{sgn}}\log d' + 37)\epsilon_2 = \norm{\hat{\mathbf{c}}^{\mathrm{sgn}}}_1\epsilon\). Hence the corresponding formulas in [eq:state-tester-pacc,eq:state-tester-estimation-error] hold after replacing \(\norm{\hat{\mathbf{c}}}_1\) by \(\norm{\hat{\mathbf{c}}^{\mathrm{sgn}}}_1\). Since \(\norm{\hat{\mathbf{c}}^{\mathrm{sgn}}}_1\leq \hat{C}_{\mathrm{sgn}}\log d'\), as guaranteed by 1, this quantity can finally be upper-bounded by \(\hat{C}_{\mathrm{sgn}}\log d'\) whenever a coefficient-free bound is preferred. ◻

Proof. Inspired by time-efficient algorithms for the low-rank variant of GapQSD [62], we devise a space-efficient algorithm for GapQSD_log, presented in 3.

Let us demonstrate the correctness of 3 and analyze the computational complexity. We focus on the setting with \(s(n)=\Theta(\log{n})\). We set \(\varepsilon \mathrel{\vcenter{:}}= (\alpha-\beta)/4 \geq 2^{-O(s)}\) and assume that \(Q_0\) and \(Q_1\) are \(s(n)\)-qubit quantum circuits that prepare the purifications of \(\rho_0\) and \(\rho_1\), respectively. According to 18, we can construct \(O(s)\)-qubit quantum circuits \(U_{\rho_0}\) and \(U_{\rho_1}\) that encode \(\rho_0\) and \(\rho_1\) as \((1,O(s), 0)\)-block-encodings, using \(O(1)\) queries to \(Q_0\) and \(Q_1\) as well as \(O(1)\) one- and two-qubit quantum gates. Next, we apply 14 to construct a \((1,O(s),0)\)-block-encoding \(U_{\frac{\rho_0-\rho_1}{2}}\) of \(\frac{\rho_0 - \rho_1}{2}\), using \(O(1)\) queries to \(U_{\rho_0}\) and \(U_{\rho_1}\), as well as \(O(1)\) one- and two-qubit quantum gates.

Let \(\delta \mathrel{\vcenter{:}}= \frac{\varepsilon}{2^{r+3}}\), \(\epsilon \mathrel{\vcenter{:}}= \frac{\varepsilon}{64\,s\,\max\{1,36 \hat{C}_{\mathrm{sgn}},2 C_{\mathrm{sgn}}+37,\tilde{C}_{\mathrm{sgn}}\}}\),⁵⁰ and \(d' \mathrel{\vcenter{:}}= \tilde{C}_{\mathrm{sgn}} \cdot \frac{1}{\delta} \log\frac{1}{\epsilon} \leq 2^{O(s(n))}\), where \(\tilde{C}_{\mathrm{sgn}}\) comes from 1. Let \(P_{d'}^{\mathrm{sgn}} \in \mathbb{R}[x]\) be the polynomial specified in 1 with \(d' = 2d-1\). Let \(\epsilon_H = \varepsilon/4\). By employing 3 (with \(\epsilon_1 \mathrel{\vcenter{:}}= 0\) and \(\epsilon_2 \mathrel{\vcenter{:}}= \epsilon\)) and the corresponding estimation procedure \(\hat{\mathcal{T}}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \Theta(\epsilon), \epsilon_H, 1/10)\) from 17, we obtain the values \(x_i\) for \(i\in\{0,1\}\), ensuring the following inequalities: \[\label{eq:GapQSDlog-tester-pacc} \mathrm{Pr}\!\left[ \left| x_i - \mathrm{Tr}\left(P_{d'}^{\mathrm{sgn}}\Big(\frac{\rho_0-\rho_1}{2}\Big)\rho_i\right) \right| \leq (36 \hat{C}_{\mathrm{sgn}}\log{d'}+37)\epsilon + \epsilon_H \right] \geq 0.9 \text{ for } i\in\{0,1\}.\tag{38}\] Here, the implementation uses \(O(d^2 \log{d})\) queries to \(U_{\frac{\rho_0-\rho_1}{2}}\) and \(O(d^2 \log{d})\) multi-controlled single-qubit gates. Moreover, the circuit descriptions of \(\hat{\mathcal{T}}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \epsilon, \epsilon_H, 1/10)\) can be computed in deterministic time \(\tilde{O}(d^{9/2}/\epsilon)\) and space \(O(s(n))\).

Now let \(x \mathrel{\vcenter{:}}= (x_0-x_1)/2\). We will finish the correctness analysis of 3 by showing \(\mathrm{Pr}\!\left[\left|x - \mathrm{T}(\rho_0, \rho_1)\right| \leq \varepsilon\right] > 0.8\) through 38 . By considering the approximation error of \(P_{d'}^{\mathrm{sgn}}\) in 1 and the QSVT implementation error in 3, we derive the following inequality in [prop:td-technical], whose proof is presented immediately afterward:

Under the aforementioned choice of \(\delta\), \(\epsilon\), and \(\epsilon_H\), we have \(\epsilon_{H} = \varepsilon/4\), \(2^{r+1}\delta = \varepsilon/4\), and \((36 \hat{C}_{\mathrm{sgn}} \log{d'} +2 C_{\mathrm{sgn}}+37)\epsilon \leq \varepsilon/2\), and thus, \(\mathrm{Pr}\!\left[\left|x - \mathrm{T}(\rho_0, \rho_1)\right|\right] > 0.8\).

Finally, we analyze the computational resources required for 3. According to 17, we can compute \(x\) in BQL, with the resulting algorithm requiring \(O(d^2 \log{d} /\epsilon_H^2) = \tilde{O}(2^{2r}/\varepsilon^4)\) queries to \(Q_0\) and \(Q_1\). In addition, its circuit description can be computed in deterministic time \(\tilde{O}(d^{9/2}/\varepsilon) = \tilde{O}(2^{4.5r}/\varepsilon^{5.5})\). ◻

Proof of [prop:td-technical]. Using the triangle inequality, we obtain the following: \[\begin{align} \left| \frac{x_0-x_1}{2} - \mathrm{T}(\rho_0, \rho_1) \right| & = \left| \frac{x_0-x_1}{2} - \mathrm{Tr}\Big( \frac{\rho_0 - \rho_1}{2} \mathrm{sgn}\Big(\frac{\rho_0 - \rho_1}{2}\Big) \Big) \right| \\ & \leq \left| \frac{x_0-x_1}{2} - \mathrm{Tr}\Big(\frac{\rho_0-\rho_1}{2} P_{d'}^{\mathrm{sgn}}\Big(\frac{\rho_0-\rho_1}{2}\Big)\Big) \right| \\ & \qquad + \left| \mathrm{Tr}\Big(\frac{\rho_0-\rho_1}{2} P_{d'}^{\mathrm{sgn}}\Big(\frac{\rho_0-\rho_1}{2}\Big)\Big) - \mathrm{Tr}\Big( \frac{\rho_0 - \rho_1}{2} \mathrm{sgn}\Big(\frac{\rho_0 - \rho_1}{2}\Big) \Big) \right|. \end{align}\]

For the first term, by noting the QSVT implementation error in 3, we know by 38 that, with probability at least \(0.9^2 > 0.8\), it holds that \[\label{eq:td-first-term} \left| \frac{x_0-x_1}{2} - \mathrm{Tr}\Big(\frac{\rho_0-\rho_1}{2} P_{d'}^{\mathrm{sgn}}\Big(\frac{\rho_0-\rho_1}{2}\Big)\Big) \right| \leq (36 \hat{C}_{\mathrm{sgn}} \log{d'} +37)\epsilon + \epsilon_H.\tag{39}\] For the second term, let \(\frac{\rho_0-\rho_1}{2} = \sum_{j} \lambda_j \lvert{\psi_j}\rangle \langle{\psi_j}\rvert\), where \(\{ \lvert{\psi_j}\rangle \}\) is an orthonormal basis. Then, \[\label{eq:td-second-term} \left| \mathrm{Tr}\Big(\frac{\rho_0\!-\!\rho_1}{2} P_{d'}^{\mathrm{sgn}}\Big(\frac{\rho_0\!-\!\rho_1}{2}\Big)\Big) - \mathrm{Tr}\Big( \frac{\rho_0 \!-\! \rho_1}{2} \mathrm{sgn}\Big(\frac{\rho_0 \!-\! \rho_1}{2}\Big) \Big) \right| \leq \sum_j \left| \lambda_j P_{d'}^{\mathrm{sgn}}(\lambda_j) \!-\! \lambda_j \mathrm{sgn}(\lambda_j) \right|.\tag{40}\] We split the summation over \(j\) into three separate summations: \[\sum_j = \sum_{\lambda_j < -\delta} + \sum_{\lambda_j > \delta} + \sum_{-\delta \leq \lambda_j \leq \delta}.\] By noticing the approximation error of \(P_{d'}^{\mathrm{sgn}}\) in 1 and \(\sum_j |\lambda_j| = \mathrm{T}(\rho_0,\rho_1) \leq 1\), we obtain the following results for each of the three summations: \[\sum_{\lambda_j > \delta} \left| \lambda_j P_{d'}^{\mathrm{sgn}}(\lambda_j) - \lambda_j \mathrm{sgn}(\lambda_j) \right| = \sum_{\lambda_j > \delta} |\lambda_j| \left| P_{d'}^{\mathrm{sgn}}(\lambda_j) - 1 \right| \leq \sum_{\lambda_j > \delta} |\lambda_j| C_{\mathrm{sgn}} \epsilon \leq C_{\mathrm{sgn}} \epsilon,\] \[\sum_{\lambda_j < -\delta} \left| \lambda_j P_{d'}^{\mathrm{sgn}}(\lambda_j) - \lambda_j \mathrm{sgn}(\lambda_j) \right| = \sum_{\lambda_j < -\delta} |\lambda_j| \left| P_{d'}^{\mathrm{sgn}}(\lambda_j) + 1 \right| \leq \sum_{\lambda_j < -\delta} |\lambda_j| C_{\mathrm{sgn}} \epsilon \leq C_{\mathrm{sgn}} \epsilon,\] \[\sum_{-\delta \leq \lambda_j \leq \delta} \left| \lambda_j P_{d'}^{\mathrm{sgn}}(\lambda_j) - \lambda_j \mathrm{sgn}(\lambda_j) \right| \leq \sum_{-\delta \leq \lambda_j \leq \delta} 2|\lambda_j| \leq 2^{r+1}\delta.\] Hence, we derive the following inequality by summing over the aforementioned three inequalities: \[\label{eq:td-last-term} \sum_j \left| \lambda_j P_{d'}^{\mathrm{sgn}}(\lambda_j) - \lambda_j \mathrm{sgn}(\lambda_j) \right| \leq 2^{r+1} \delta + 2 C_{\mathrm{sgn}} \epsilon.\tag{41}\] By combining [eq:td-first-term,eq:td-second-term,eq:td-last-term], we conclude that \[\left|\frac{x_0-x_1}{2} - \mathrm{T}(\rho_0, \rho_1)\right| \leq (36 \hat{C}_{\mathrm{sgn}} \log{d'} + 37)\epsilon + \epsilon_H + 2 C_{\mathrm{sgn}} \epsilon + 2^{r+1} \delta. \qedhere\] ◻

Proof. We begin with a formal algorithm in 4.

Let us now demonstrate the correctness and computational complexity of 4. We concentrate on the scenario with \(s(n) = \Theta(\log{n})\) and \(\varepsilon = g/4 \geq 2^{-O(s)}\). Our strategy is to estimate the entropy of each of \(\rho_0\) and \(\rho_1\), respectively. We assume that \(Q_0\) and \(Q_1\) are \(s\)-qubit quantum circuits that prepare the purifications of \(\rho_0\) and \(\rho_1\), respectively. By 18, we can construct \((1,O(s), 0)\)-block-encodings \(U_{\rho_0}\) and \(U_{\rho_1}\) of \(\rho_0\) and \(\rho_1\), respectively, using \(O(1)\) queries to \(Q_0\) and \(Q_1\) as well as \(O(1)\) one- and two-qubit quantum gates.

Let \(\beta = \min\{ \frac{\varepsilon}{2^{r+6} \ln(2^{r+6}/\varepsilon)}, \frac{1}{4} \}\), \(\epsilon \mathrel{\vcenter{:}}= \frac{\varepsilon^{3/2}}{64\cdot 2^{r/2}s^2\max\{1,\hat{C}_{\ln},C_{\ln},\tilde{C}_{\ln}\}}\), and \(d' \mathrel{\vcenter{:}}= \tilde{C}_{\ln} \cdot \frac{1}{\beta} \log \frac{1}{\epsilon} = 2^{O(s(n))}\), where \(\tilde{C}_{\ln}\) comes from 2. Let \(P_{d'}^{\ln} \in \mathbb{R}[x]\) be the polynomial specified in 2 with \(d' = 2d-1\). Let \(\epsilon_H \mathrel{\vcenter{:}}= \frac{\varepsilon}{8\hat{C}_{\ln}\sqrt{d'}\ln(2/\beta)}\). By utilizing 4 (with \(\epsilon_1 \mathrel{\vcenter{:}}= 0\) and \(\epsilon_2 \mathrel{\vcenter{:}}= \epsilon\)) and the corresponding estimation procedure \(\hat{\mathcal{T}}(Q_i, U_{\rho_i}, P_{d'}^{\ln}, \epsilon, \epsilon_H, 1/10)\) from 17, we obtain the values \(x_i\) for \(i\in\{0,1\}\), ensuring the following inequalities: \[\label{eq:GapQEDlog-tester-pacc} \mathrm{Pr}\!\left[ \left| x_i - \mathrm{Tr}\left(P_{d'}^{\ln}\!\left(\rho_i\right)\rho_i\right) \right| \leq \hat{C}_{\ln} \sqrt{d'} \rbra{\epsilon + \epsilon_H} \right] \geq 0.9 \text{ for } i\in\{0,1\}.\tag{42}\] Here, the implementation uses \(O(d^2)\) queries to \(U_{\rho_i}\) and \(O(d^2)\) multi-controlled single-qubit gates. Moreover, the circuit descriptions of \(\hat{\mathcal{T}}(Q_i, U_{\rho_i}, P_{d'}^{\ln}, \epsilon, \epsilon_H, 1/10)\) can be computed in bounded-error time \(\tilde{O}(d^{9}/\epsilon^4)\) and space \(O(s(n))\).

We will finish the correctness analysis of 4 by showing \(\mathrm{Pr}\!\left[\left| 2 \ln\rbra[\big]{\tfrac{2}{\beta}} x_i - \mathrm{S}(\rho_i)\right| \leq \varepsilon\right] \geq 0.9\) through 42 . By considering the approximation error of \(P_{d'}^{\ln}\) in 2 and the QSVT implementation error in 4, we derive the following inequality in [prop:entropy-technical], the proof of which is presented immediately afterward:

Consequently, it is left to show that \(2 \ln\!\big(\tfrac{2}{\beta}\big) \rbra*{ \hat{C}_{\ln}\sqrt{d'}(\epsilon+\epsilon_H)+C_{\ln}\epsilon+2^{r+1}\beta} \leq \varepsilon\) for the specified value of \(\beta\), \(\epsilon\), and \(\epsilon_H\). This can be seen by noting that \[2\ln\rbra[\big]{\tfrac{2}{\beta}} \hat{C}_{\ln} \sqrt{d'} \epsilon_{H} = \tfrac{\varepsilon}{4}, \quad 2\ln\rbra[\big]{\tfrac{2}{\beta}} (\hat{C}_{\ln}\sqrt{d'} + C_{\ln}) \epsilon \leq \tfrac{\varepsilon}{2}, \quad\text{and}\quad 2 \ln\rbra[\big]{\tfrac{2}{\beta}} \cdot 2^{r+1} \beta \leq \tfrac{\varepsilon}{4}.\] The first identity and the second inequality are trivial. The third inequality, stated in [prop:GapQEDlog-beta-bound], is accompanied by a proof presented immediately afterward:

Finally, we analyze the computational resources required for 4. As per 17, we can compute \(x\) in BQL, with the resulting algorithm requiring \(O(d^2/\epsilon_H^2) = \tilde{O}(2^{3r}/\varepsilon^5)\) queries to \(Q_0\) and \(Q_1\). Furthermore, its circuit description can be computed in bounded-error randomized time \(\tilde{O}(d^{9}/\epsilon^4) = \tilde{O}(2^{11r}/\varepsilon^{15})\). ◻

Proof. Let \(Q_0\) and \(Q_1\) be the given \(s(n)\)-qubit quantum circuits where \(s(n)=\Theta(\log{n})\). Consider a classical-quantum mixed state on a classical register \(\mathsf{B}\) and a quantum register \(\mathsf{Y}\), denoted by \(\rho'_1 \mathrel{\vcenter{:}}= \frac{1}{2}\lvert{0}\rangle\langle{0}\rvert\otimes \rho_0 + \frac{1}{2} \lvert{1}\rangle\langle{1}\rvert\otimes \rho_1\), where \(\rho_0\) and \(\rho_1\) are states obtained by running \(Q_0\) and \(Q_1\), respectively, and tracing out the non-output qubits. We utilize our reduction to output classical-quantum mixed states \(\rho'_0\) and \(\rho'_1\), which are the output of \((s+2)\)-qubit quantum circuits \(Q'_0\) and \(Q'_1\),⁵² respectively, where \(\rho'_0\mathrel{\vcenter{:}}=(p_0\lvert{0}\rangle\langle{0}\rvert+p_1\lvert{1}\rangle\langle{1}\rvert)\otimes(\frac{1}{2}\rho_0+\frac{1}{2}\rho_1)\) and \(\mathsf{B}'\mathrel{\vcenter{:}}=(p_0,p_1)\) is an independent random bit with entropy \(\mathrm{H}(\mathsf{B}')=1-\frac{1}{2}[\alpha(n)+\beta(n)]\). Let \(\mathrm{S}_2(\rho)\mathrel{\vcenter{:}}=\mathrm{S}(\rho)/\ln{2}\) for any quantum state \(\rho\), we then have derived that: \[\label{eq:QJS-to-QED} \begin{align} \mathrm{S}_2(\rho'_0)-\mathrm{S}_2(\rho'_1) &= \mathrm{S}_2(\mathsf{B}',\mathsf{Y})_{\rho'_0} - \mathrm{S}_2(\mathsf{B},\mathsf{Y})_{\rho'_1}\\ &= [\mathrm{H}(\mathsf{B}')+\mathrm{S}_2(\mathsf{Y}|\mathsf{B}')_{\rho'_0}]-[\mathrm{H}(\mathsf{B})+\mathrm{S}_2(\mathsf{Y}|\mathsf{B})_{\rho'_1}]\\ &= \mathrm{S}_2(\mathsf{Y})_{\rho'_0} - \mathrm{S}_2(\mathsf{Y}|\mathsf{B})_{\rho'_1} + \mathrm{H}(\mathsf{B}') - \mathrm{H}(\mathsf{B})\\ &= \mathrm{S}_2(\mathsf{Y})_{\rho'_0}-\mathrm{S}_2(\mathsf{Y}|\mathsf{B})_{\rho'_1} -\tfrac{1}{2}[\alpha(n)+\beta(n)]\\ &= \mathrm{S}_2 \rbra*{ \tfrac{1}{2}\rho_0+\tfrac{1}{2}\rho_1 } - \tfrac{1}{2}(\mathrm{S}_2(\rho_0)+\mathrm{S}_2(\rho_1)) -\tfrac{1}{2}[\alpha(n)+\beta(n)]\\ &= \mathrm{QJS}_2(\rho_0,\rho_1) - \tfrac{1}{2}[\alpha(n)+\beta(n)]. \end{align}\tag{43}\] Here, the second line derives from the definition of quantum conditional entropy and acknowledges that both \(\mathsf{B}\) and \(\mathsf{B}'\) are classical registers. The third line owes to the independence of \(\mathsf{B}'\) as a random bit. Furthermore, the fifth line relies on the Joint entropy theorem (2).

By plugging 43 into the conditions in the promise of \(\textrm{\mathrm{\small GapQJS}}_{\log}[\alpha(n),\beta(n)]\), we can define \(g(n')\mathrel{\vcenter{:}}=\frac{\ln{2}}{2} \big( \alpha(n)-\beta(n) \big)\) and conclude that:

• If \(\mathrm{QJS}_2(\rho_0,\rho_1) \geq \alpha(n)\), then \(\mathrm{S}(\rho'_0)-\mathrm{S}(\rho'_1) \geq \frac{\ln{2}}{2} \big( \alpha(n)-\beta(n) \big) = g(n')\);

• If \(\mathrm{QJS}_2(\rho_0,\rho_1) \leq \beta(n)\), then \(\mathrm{S}(\rho'_0)-\mathrm{S}(\rho'_1) \leq -\frac{\ln{2}}{2} \big(\alpha(n)-\beta(n) \big) = -g(n')\).

As \(\rho'_1\) and \(\rho'_0\) are \(r'(n')\)-qubit states where \(n'\mathrel{\vcenter{:}}=3n\)⁵³ and \(r'(n')\mathrel{\vcenter{:}}= r(n)+1\), the output length of the corresponding space-bounded quantum circuits \(Q'_0\) and \(Q'_1\) is \(r'(n')\). Hence, \(\textrm{\mathrm{\small GapQJS}}_{s}[\alpha,\beta]\) is logspace Karp reducible to \(\textrm{\mathrm{\small GapQED}}_{s+3}[g]\) by mapping \((Q_0,Q_1)\) to \((Q'_0,Q'_1)\). ◻

Proof of [prop:entropy-technical]. We only prove the case with \(i=0\) while the case with \(i=1\) follows straightforwardly. By applying the triangle inequality with \(i=0\), we have: \[\left| 2\ln\!\big(\tfrac{2}{\beta}\big) x_0 - \mathrm{S}(\rho_0) \right| \leq \left| 2\ln\!\big(\tfrac{2}{\beta}\big) x_0 - 2\ln\!\big(\tfrac{2}{\beta}\big) \mathrm{Tr}\left(P_{d'}^{\ln}(\rho_0)\rho_0\right) \right| + \left| 2\ln\!\big(\tfrac{2}{\beta}\big) \mathrm{Tr}\left(P_{d'}^{\ln}(\rho_0)\rho_0\right) - \mathrm{S}(\rho_0) \right|.\] For the first term, by noting the QSVT implementation error in 4, we have by 42 that with probability at least \(0.9\), it holds that \[\label{eq:entropy-first-term} \left| 2\ln\!\big(\tfrac{2}{\beta}\big) x_0 - 2 \ln\!\big(\tfrac{2}{\beta}\big) \mathrm{Tr}\rbra[\big]{P_{d'}^{\ln}(\rho_0)\rho_0} \right| \leq 2 \ln\!\big(\tfrac{2}{\beta}\big) \hat{C}_{\ln} \sqrt{d'} (\epsilon + \epsilon_H).\tag{44}\] For the second term, let \(\rho_0 = \sum_{j} \lambda_j \lvert{\psi_j}\rangle \langle{\psi_j}\rvert\), where \(\{ \lvert{\psi_j}\rangle \}\) is an orthonormal basis. Then, \[\label{eq:entropy-second-term} \left| 2\ln\!\big(\tfrac{2}{\beta}\big) \mathrm{Tr}\rbra[\big]{P_{d'}^{\ln}(\rho_0)\rho_0} - \mathrm{S}(\rho_0) \right| \leq \sum_j \left| 2 \ln\!\big(\tfrac{2}{\beta}\big) \lambda_j P_{d'}^{\ln}(\lambda_j) - \lambda_j \ln(1/\lambda_j) \right|.\tag{45}\] We split the summation over \(j\) into two separate summations: \(\sum_j = \sum_{\lambda_j > \beta} + \sum_{\lambda_j \leq \beta}.\) By noticing the approximation error of \(P_{d'}^{\ln}\) in 2 and \(\sum_{j} |\lambda_j| = \mathrm{Tr}(\rho_0) \leq 1\), we can then obtain the following results for each of the two summations: \[\begin{align} \sum_{\lambda_j > \beta} \left| 2\ln\!\big(\tfrac{2}{\beta}\big) \lambda_j P_{d'}^{\ln}(\lambda_j) - \lambda_j \ln(1/\lambda_j) \right| & = \sum_{\lambda_j > \beta} |\lambda_j| \cdot \left| 2 \ln\!\big(\tfrac{2}{\beta}\big) P_{d'}^{\ln}(\lambda_j) - \ln(1/\lambda_j) \right| \\ & \leq \sum_{\lambda_j > \beta} |\lambda_j| \cdot 2 \ln\!\big(\tfrac{2}{\beta}\big) C_{\ln} \epsilon \\ & \leq 2 \ln\!\big(\tfrac{2}{\beta}\big) C_{\ln} \epsilon, \end{align}\] \[\begin{align} \sum_{\lambda_j \leq \beta} \left| 2 \ln\!\big(\tfrac{2}{\beta}\big) \lambda_j P_{d'}^{\ln}(\lambda_j) - \lambda_j \ln(1/\lambda_j) \right| & \leq \sum_{\lambda_j \leq \beta} \left( 2 \ln\!\big(\tfrac{2}{\beta}\big) |\lambda_j| + |\lambda_j| \ln(1/\lambda_j) \right) \\ & \leq 2 \ln\!\big(\tfrac{2}{\beta}\big) \cdot 2^r \beta + 2^r \beta\ln(1/\beta)\\ & \leq 2\ln\!\big(\tfrac{2}{\beta}\big) 2^{r+1} \beta. \end{align}\] Hence, we have derived the following inequality by summing over the aforementioned inequalities: \[\label{eq:entropy-last-term} \sum_j \left| 2 \ln\!\big(\tfrac{2}{\beta}\big) \lambda_j P_{d'}^{\ln}(\lambda_j) - \lambda_j \ln(1/\lambda_j) \right| \leq 2 \ln\!\big(\tfrac{2}{\beta}\big) C_{\ln} \epsilon + 2\ln\!\big(\tfrac{2}{\beta}\big) 2^{r+1} \beta.\tag{46}\] By combining [eq:entropy-first-term,eq:entropy-second-term,eq:entropy-last-term], we conclude that \[\left| 2\ln\!\big(\tfrac{2}{\beta}\big) x_0 - \mathrm{S}(\rho_0) \right| \leq 2 \ln\!\big(\tfrac{2}{\beta}\big) \left( \hat{C}_{\ln}\sqrt{d'} \rbra[\big]{\epsilon + \epsilon_H} + C_{\ln} \epsilon + 2^{r+1} \beta \right). \qedhere\] ◻

Proof of [prop:GapQEDlog-beta-bound]. Note that the choice of \(\beta\) is given by \(\beta \mathrel{\vcenter{:}}= \frac{\varepsilon}{2^{r+6} \ln(\frac{2^{r+6}}{\varepsilon})}\). Then, to demonstrate the inequality \(2 \ln(\frac{2}{\beta}) \cdot 2^{r+1} \beta \leq \tfrac{\varepsilon}{4}\), it suffices to prove that \[\label{eq:GapQEDlog-beta-bound} 2 \ln\left(\frac{2^{r+7} \ln(\frac{2^{r+6}}{\varepsilon})}{\varepsilon}\right) \cdot \frac{\varepsilon}{2^{5} \ln(\frac{2^{r+6}}{\varepsilon})} \leq \frac{\varepsilon}{4}.\tag{47}\]

Let \(x \mathrel{\vcenter{:}}= 2^{-r-6} \varepsilon \in (0, 1)\), then 47 becomes \(\ln\left(\frac{2}{x} \ln\left(\frac{1}{x}\right)\right) \leq 4 \ln\left(\frac{1}{x}\right)\). This simplifies further to \(2x^3\ln\left(\frac{1}{x}\right) \leq 1\).

To complete the proof, let \(f(x) = 2x^3\ln(\frac{1}{x})\), then its first derivative is \(f'(x) = 2x^2 \left(3\ln\left(\frac{1}{x}\right)-1\right)\). Note that \(f'(x) > 0\) for \(x \in (0, e^{-1/3})\) and \(f'(x) < 0\) for \(x \in (e^{-1/3}, 1)\). Thus, \(f(x)\) is monotonically increasing for \(x \in (0, e^{-1/3})\) and monotonically decreasing for \(x \in (e^{-1/3}, 1)\). Therefore, \(f(x)\) takes the maximum value at \(x = e^{-1/3}\), and consequently, \(f(x) \leq f(e^{-1/3}) = \frac{2}{3e} \leq 1\). ◻

Proof. We first present a formal algorithm in 5:

Constructing the unitary of interest via the space-efficient QSVT.

We consider the setting with \(s(n) = \Theta(\log{n})\) and \(\varepsilon = \alpha / 2\). Suppose \(Q_0\) and \(Q_1\) are \(s(n)\)-qubit quantum circuits that prepare the purifications of \(\rho_0\) and \(\rho_1\), respectively. Similar to 3, we first construct an \(O(s)\)-qubit quantum circuit \(U_{\frac{\rho_0 - \rho_1}{2}}\) that is a \((1,O(s), 0)\)-block-encoding of \(\frac{\rho_0-\rho_1}{2}\), using \(O(1)\) queries to \(Q_0\) and \(Q_1\) and \(O(1)\) one- and two-qubit quantum gates.

Let \(\delta = \frac{\varepsilon}{2^{r+3}}\), \(\epsilon \mathrel{\vcenter{:}}= \frac{\varepsilon}{64\,s\,\max\{1,36 \hat{C}_{\mathrm{sgn}},2 C_{\mathrm{sgn}}+37,\tilde{C}_{\mathrm{sgn}}\}}\), and \(d' \mathrel{\vcenter{:}}= \tilde{C}_{\mathrm{sgn}} \cdot \frac{1}{\delta} \log\frac{1}{\epsilon} = 2^{O(s(n))}\), where \(\tilde{C}_{\mathrm{sgn}}\) comes from 1. Let \(P_{d'}^{\mathrm{sgn}} \in \mathbb{R}[x]\) be the odd polynomial specified in 1. Let \(U_i \mathrel{\vcenter{:}}= \mathcal{T}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \epsilon)\) for \(i \in \{0,1\}\), then we have the following equalities: \[\forall i\in\{0,1\}, \quad U_i \lvert{0}\rangle\lvert{\bar 0}\rangle = \sqrt{p_i} \lvert{0}\rangle \lvert{\psi_{i,0}}\rangle + \sqrt{1 - p_i} \lvert{1}\rangle \lvert{\psi_{i,1}}\rangle, \quad\text{where } 0 \leq p_i \leq 1.\]

Let \(H\) be the Hadamard gate, then we derive the following equality for \(i\in\{0,1\}\): \[(H \otimes U_i) \lvert{0}\rangle \lvert{0}\rangle\lvert{\bar 0}\rangle = \sqrt{\frac{p_i}{2}} \lvert{0}\rangle\lvert{0}\rangle\lvert{\psi_{i,0}}\rangle + \underbrace{\sqrt{\frac{p_i}{2}} \lvert{1}\rangle\lvert{0}\rangle\lvert{\psi_{i,0}}\rangle + \sqrt{\frac{1-p_i}{2}} \lvert{0}\rangle\lvert{1}\rangle\lvert{\psi_{i,1}}\rangle + \sqrt{\frac{1-p_i}{2}} \lvert{1}\rangle\lvert{1}\rangle\lvert{\psi_{i,1}}\rangle}_{\sqrt{1 - \frac{p_i}{2}}\lvert{\perp_i}\rangle}.\]

Making the error one-sided by exact amplitude amplification.

Consider the Grover operator \(G_i \mathrel{\vcenter{:}}= - (H \otimes U_i) (I - 2\lvert{\bar 0}\rangle\langle{\bar 0}\rvert) (H \otimes U_i^\dagger) (I - 2\Pi_0)\), where \(\Pi_0\) is the projection onto the subspace spanned by \(\{ \lvert{0}\rangle\lvert{0}\rangle\lvert{\varphi}\rangle \}\) over all \(\lvert{\varphi}\rangle\). By employing the exact amplitude amplification (20), we can obtain that: \[\label{eq:exact-AA-coCertQSDlog} \begin{align} G_i (H \otimes U_i) \lvert{0}\rangle\lvert{0}\rangle\lvert{\bar 0}\rangle &= \sin(3\theta_i) \lvert{0}\rangle\lvert{0}\rangle\lvert{\psi_{i,0}}\rangle + \cos(3\theta_i) \lvert{\perp_i}\rangle,\\ \text{where } \sin^2(\theta_i) &= \frac{p_i}{2} \text{ when } \theta_i \in \sbra*{0, \frac{\pi}{4}}. \end{align}\tag{48}\] Let \(x_{i0}\) and \(x_{i1}\) be the measurement outcomes of the first two qubits of \(G_i (H \otimes U_i) \lvert{0}\rangle\lvert{0}\rangle\lvert{\bar 0}\rangle\) for \(i\in\{0,1\}\). 5 returns “yes” if \(x_{00} = x_{01} = x_{10} = x_{11} = 0\), and “no” otherwise. Let \(U_{P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0 - \rho_1}{2}\right)}\) be the unitary operator being controlled in the implementation of \(U_i \mathrel{\vcenter{:}}= \mathcal{T}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \epsilon)\), and note that by 3, \(U_{P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0 - \rho_1}{2}\right)}\) is a \((1, O(s), (36 \hat{C}_{\mathrm{sgn}} \log{d'} + 37)\epsilon)\)-block-encoding of \(P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0-\rho_1}{2}\right)\). We will show the correctness of our algorithm as follows:

• For yes instances (\(\rho_0=\rho_1\)), \(U_{P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0 - \rho_1}{2}\right)}\) is a \((1,O(s), 0)\)-block-encoding of the zero operator, following from [remark:QSVT-parity-preserving]. Consequently, \(\mathcal{T}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \epsilon)\) outputs \(0\) with probability \(1/2\) for \(i \in \{0,1\}\), i.e., \(p_0=p_1=1/2\). As a result, we have \(\theta_0 = \theta_1 = \pi/6\) and \(\sin^2(3\theta_0) = \sin^2(3\theta_1) = 1\). Substituting these values into 48 , we can conclude that \(x_{00} = x_{01} = x_{10} = x_{11} = 0\) with certainty, which completes the analysis.

• For no instances (\(\mathrm{T}(\rho_0, \rho_1) \geq \alpha\)), \(U_{P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0 - \rho_1}{2}\right)}\) is a \((1,O(s), 0)\)-block-encoding of \(A\) satisfying \[\left\| A - P_{d'}^{\mathrm{sgn}}\left(\frac{\rho_0-\rho_1}{2}\right) \right\| \leq (36 \hat{C}_{\mathrm{sgn}} \log{d'} +37)\epsilon.\] Let \(p_i\) be the probability that \(\mathcal{T}(Q_i, U_{\frac{\rho_0-\rho_1}{2}}, P_{d'}^{\mathrm{sgn}}, \epsilon)\) outputs \(0\) for \(i \in \{0,1\}\), then \(p_i = \frac{1}{2}\big(1+\operatorname{Re}(\mathrm{Tr}(\rho_i A))\big)\) following from 17. A direct calculation similar to [prop:td-technical] indicates that: \[\left| (p_0 - p_1) - \mathrm{T}(\rho_0, \rho_1) \right| \leq (36 \hat{C}_{\mathrm{sgn}}\log{d'}+2 C_{\mathrm{sgn}}+37)\epsilon + 2^{r+1} \delta.\] Under the choice of \(\delta\) and \(\epsilon\) (the same as in the proof of 10), we obtain that \(|(p_0 - p_1) - \mathrm{T}(\rho_0, \rho_1)| \leq \varepsilon\) which yields that \(\max\{ |p_0-1/2|, |p_1-1/2| \} \geq \varepsilon/2\).⁵⁴

  Noting that \(\mathrm{Pr}\!\left[x_{i0}=x_{i1}=0\right]=\sin^2(3\theta_i)\) for \(i \in \{0,1\}\), 5 will return “yes” with probability \(p_{{\rm yes}} = \sin^2(3\theta_0) \sin^2(3\theta_1)\). We provide an upper bound for \(p_{{\rm yes}}\) in [prop:coCertQSDlog-soundness-upper-bound], with the proof provided immediately afterward:

  Let \(f(\theta_0,\theta_1) \mathrel{\vcenter{:}}= \sin^2(3\theta_0) \sin^2(3\theta_1)\) be a function such that \(\sin^2(\theta_i) = p_i/2\) for \(i\in\{0,1\}\) and \(\max\{ |p_0-1/2|, |p_1-1/2| \} \geq \varepsilon/2\), then \(f(\theta_0,\theta_1) \leq 1 - \varepsilon^2/4\).

  Consequently, we finish the analysis by noticing \(p_{{\rm yes}} = f(\theta_0,\theta_1) \leq 1 - \varepsilon^2/4 = 1 - \alpha^2/16\).

Now we analyze the complexity of 5. Following 17, we can compute \(x_{00}, x_{01}, x_{10}, x_{11}\) in BQL. The quantum circuit that computes \(x_{00}, x_{01}, x_{10}, x_{11}\) takes \(O(d^2 \log{d}) = \tilde{O}(2^{2r}/\alpha^2)\) queries to \(Q_0\) and \(Q_1\), and its circuit description can be computed in deterministic time \(\tilde{O}(d^{9/2}/\alpha) = \tilde{O}(2^{4.5r}/\alpha^{5.5})\). Finally, we conclude the coRQ_UL containment of \(\overline{\mathrm{\small CertQSD}}\)_log by applying error reduction for coRQ_UL (5) to 5. ◻

Proof of [prop:coCertQSDlog-soundness-upper-bound]. We begin by stating the facts that \(\sin^2(\theta_i) = p_i/2\) for \(i \in \{0,1\}\) and \(\sin^2(3\theta) = \sin^6(\theta) - 6\cos^2(\theta) \sin^4(\theta) + 9\cos^4(\theta)\sin^2(\theta)\). Then we notice that \(0 \leq p_0,p_1 \leq 1\) and complete the proof by a direct calculation: \[\begin{align} f(\theta_0,\theta_1) & = \left( 2p_0^3 - 6p_0^2 + \tfrac{9}{2} p_0 \right) \left( 2p_1^3 - 6p_1^2 + \tfrac{9}{2} p_1 \right) \\ & \leq \left( 1 - \left( p_0 - \tfrac{1}{2} \right)^2 \right) \left( 1 - \left( p_1 - \tfrac{1}{2} \right)^2 \right) \\ & \leq 1 - \left( \max\left\{\left|p_0 - \tfrac{1}{2}\right|, \left|p_1 - \tfrac{1}{2}\right|\right\} \right)^2 \\ & \leq 1 - \tfrac{\varepsilon^2}{4}. \qedhere \end{align}\] ◻

Proof. Note that \(\mathrm{HS}^2(\rho_0,\rho_1) = \frac{1}{2} \left(\mathrm{Tr}(\rho_0^2)+\mathrm{Tr}(\rho_1^2)\right)-\mathrm{Tr}(\rho_0\rho_1)\). Let \(\varepsilon \mathrel{\vcenter{:}}= (\alpha - \beta)/100\). According to 9, we can use the SWAP test to estimate \(\mathrm{Tr}(\rho_0^2)\), \(\mathrm{Tr}(\rho_1^2)\), and \(\mathrm{Tr}(\rho_0\rho_1)\), and hence \(\mathrm{HS}^2(\rho_0,\rho_1)\), within additive error \(\varepsilon\) with high probability by performing \(O(1/\varepsilon^2)\) sequential repetitions. Therefore, we can conclude that \(\textrm{\mathrm{\small GapQHS}}_{\log}[\alpha(n),\beta(n)]\) is in BQL. ◻

Proof. We first provide a formal algorithm in 6.

Constructing the unitary of interest via the SWAP test.

We consider the setting with \(s(n)=\Theta(\log(n))\). Our main building block is the circuit implementation of the SWAP test (9). Specifically, we utilize the subroutine \(\textrm{\mathrm{\small SWAP}}(\rho_i,\rho_j)\) for \(i,j\in \{0,1\}\), which involves applying \(Q_i\) and \(Q_j\) to prepare quantum states \(\rho_i\) and \(\rho_j\), respectively, and then employing the SWAP test on these states \(\rho_i\) and \(\rho_j\). We denote by \(p_{ij}\) the probability that \(\textrm{\mathrm{\small SWAP}}(\rho_i,\rho_j)\) outputs \(0\) based on the measurement outcome of the control qubit in the SWAP test. Following 9, we have \(p_{ij} = \frac{1}{2}\big(1+\mathrm{Tr}(\rho_i\rho_j) \big)\) for \(i,j \in \{0,1\}\).

We define \(T_{ij}\mathrel{\vcenter{:}}=\textrm{\mathrm{\small SWAP}}(\rho_i,\rho_j)\) for \((i,j) \in \mathcal{I}\mathrel{\vcenter{:}}=\{(0,0), (1,1), (0,1)\}\), with the control qubit in \(\textrm{\mathrm{\small SWAP}}(\rho_i,\rho_j)\) serving as the output qubit of \(T_{ij}\). By introducing another ancillary qubit, we construct \(T'_{ij} \mathrel{\vcenter{:}}= \textrm{\mathrm{\small CNOT}}(I \otimes T_{ij})\) for \((i,j) \in \mathcal{I}\), where \(\textrm{\mathrm{\small CNOT}}\) is controlled by the output qubit of \(T_{ij}\) and targets on the new ancillary qubit. It is effortless to see that \(T'_{ij}\) prepares the purification of \(\varrho(p_{ij})\) with \(\varrho(p_{ij})\mathrel{\vcenter{:}}= p_{ij} \lvert{0}\rangle\langle{0}\rvert + (1-p_{ij})\lvert{1}\rangle\langle{1}\rvert\) for \((i,j)\in\mathcal{I}\).

By applying 18, we can construct quantum circuits \(T''_{ij}\) for \((i,j)\in\mathcal{I}\) that serve as \((1, O(s), 0)\)-block-encoding of \(\varrho(p_{ij})\), using \(O(1)\) queries to \(T'_{ij}\) and \(O(1)\) one- and two-qubit quantum gates. Notably, \((X \otimes I) T''_{01}\), with \(X\) acting on the qubit of \(\varrho(p_{01})\), prepares the purification of \(X \varrho(p_{01}) X^\dagger = p_{01}\lvert{1}\rangle\langle{1}\rvert + (1-p_{01})\lvert{0}\rangle\langle{0}\rvert = \varrho(1-p_{01})\), leading to the equality: \[\varrho(\rho_0,\rho_1)\mathrel{\vcenter{:}}= \frac{1}{4} \varrho(p_{00}) + \frac{1}{4} \varrho(p_{11}) + \frac{1}{2} \varrho(1-p_{01}) = \varrho\!\left(\frac{1}{2} + \frac{\mathrm{HS}^2(\rho_0, \rho_1)}{4}\right).\]

Consequently, we employ 14 to construct a unitary quantum circuit \(U\) that is a \((1,m, 0)\)-block-encoding of \(\varrho\big(\frac{1}{2} + \frac{\mathrm{HS}^2(\rho_0, \rho_1)}{4}\big)\) using \(O(1)\) queries to \(T''_{00}\), \(T''_{11}\), \(T''_{01}\), and \(O(1)\) one- and two-qubit quantum gates, where \(m \mathrel{\vcenter{:}}= O(s)\). The construction ensures the following: \[\label{eq:coCertQHSlog-unitary} U \lvert{0}\rangle \lvert{0}\rangle^{\otimes m} = \underbrace{\left( \frac{1}{2} + \frac{\mathrm{HS}^2(\rho_0, \rho_1)}{4} \right)}_{\sin(\theta)} \lvert{0}\rangle\lvert{0}\rangle^{\otimes m} + \cos(\theta) \lvert{\perp}\rangle, \text{ where } \langle{0}\rvert\langle{0}\rvert^{\otimes m} \lvert{\perp}\rangle = 0.\tag{49}\]

Making the error one-sided.

Let us consider the Grover operator \(G \mathrel{\vcenter{:}}= - U (I - 2\lvert{\bar 0}\rangle\langle{\bar 0}\rvert) U^\dagger (I - 2\lvert{\bar 0}\rangle\langle{\bar 0}\rvert)\). By applying 20, we derive that \[G U \lvert{0}\rangle\lvert{0}\rangle^{\otimes m} = \sin(3\theta) \lvert{0}\rangle\lvert{0}\rangle^{\otimes m} + \cos(3\theta) \lvert{\perp}\rangle.\] Subsequently, we measure all qubits of \(G U \lvert{0}\rangle\lvert{0}\rangle^{\otimes m}\) in the computational basis, represented as \(x\in\{0,1\}^{m+1}\). Hence, 6 returns “yes” if the outcome \(x\) is \(0^{m+1}\) and “no” otherwise. 6 accepts with probability \(\sin^2(3\theta)\). Now we analyze the correctness of the algorithm:

• For yes instances (\(\rho_0 = \rho_1\)), we have \(\mathrm{HS}^2(\rho_0, \rho_1) = 0\). Following 49 , we obtain \(\sin(\theta) = 1/2\) and thus \(\sin^2(3\theta) = 1\). We conclude that 6 will always return “yes”.

• For no instances, we have \(\mathrm{HS}^2(\rho_0, \rho_1) \geq \alpha\). According to 49 , we derive that: \[\label{eq:coCertQHSlog-in-coRQUL-soundness} \begin{align} &\sin(\theta) = \frac{1}{2} + \frac{\mathrm{HS}^2(\rho_0,\rho_1)}{4} \geq \frac{1}{2} + \frac{\alpha}{4},\\ \frac{1}{4} \leq &\sin^2(\theta) = \rbra*{ \frac{1}{2} + \frac{\mathrm{HS}^2(\rho_0,\rho_1)}{4} }^2 \leq \rbra*{ \frac{1}{2} + \frac{1}{4} }^2 = \frac{9}{16}. \end{align}\tag{50}\] As a result, considering the fact that \(\sin^2(3\theta) = f(\sin^2(\theta))\) where \(f(x) \mathrel{\vcenter{:}}= 16x^3 - 24x^2 + 9x\), we require [prop:coCertQHSsoundness] and the proof is given immediately afterward:

  The polynomial function \(f(x)\mathrel{\vcenter{:}}= 16x^3 - 24x^2 + 9x\) is monotonically decreasing in \([1/4,9/16]\). Moreover, we have \[\forall \alpha\in[0,1],\quad f\rbra*{\rbra[\Big]{\frac{1}{2}+\frac{\alpha}{4}}^2} \leq 1-\frac{\alpha^2}{2}.\]

  Combining 50 and [prop:coCertQHSsoundness], we have that \(\sin^2(3\theta) = f(\sin^2(\theta)) \leq f\big(\big(\frac{1}{2}+\frac{\alpha}{4}\big)^2\big) \leq 1-\frac{\alpha^2}{2}\). Hence, 6 will return “no” with probability at least \(\alpha^2/2\).

Regarding the computational complexity of 6, this algorithm requires \(O(s(n))\) qubits and performs \(O(1)\) queries to \(Q_0\) and \(Q_1\). Finally, we finish the proof by applying error reduction from coRQ_UL (5) to 6. ◻

Proof of [prop:coCertQHSsoundness]. Through a direct calculation, we have \(f'(x) = 48x^2 - 48x + 9 \leq 0\) for \(x \in [1/4, 3/4]\), then \(f(x)\) is monotonically decreasing in \([1/4, 9/16] \subseteq [1/4, 3/4]\). Moreover, it is left to show that: \[f\rbra*{ \rbra[\Big]{ \frac{1}{2} + \frac{\alpha}{4} }^2 } = \frac{\alpha^6}{256}+\frac{3 \alpha^5}{64}+\frac{9 \alpha^4}{64}-\frac{\alpha^3}{8}-\frac{3 \alpha^2}{4}+1 \leq 1-\frac{\alpha^2}{2}.\] Equivalently, it suffices to show that \(g(x) \mathrel{\vcenter{:}}= -\frac{x^4}{256}-\frac{3 x^3}{64}-\frac{9 x^2}{64}+\frac{x}{8}+\frac{1}{4} \geq 0\) for \(0 \leq x \leq 1\). We first compute the first derivative of \(g(x)\), which is \(g'(x)=-\frac{x^3}{64}-\frac{9 x^2}{64}-\frac{9 x}{32}+\frac{1}{8}\). Setting \(g'(x)\) equal to zero, we obtain three roots: \(x_1=-4\), \(x_2=\frac{1}{2} (-\sqrt{33}-5) < 0\), and \(x_3=\frac{1}{2} (\sqrt{33}-5) \in (0,1)\).

Since \(g'(0)=1/8 > 0\) and \(g'(1)=-5/16 < 0\), we conclude that \(g(x)\) is monotonically increasing in \([0,x_3]\) and monotonically decreasing in \([x_3,1]\). Therefore, we can determine the minimum value of \(g(x)\) by evaluating \(g(0)=\frac{1}{4}\) and \(g(1)=\frac{47}{256}\). Since both values are greater than zero, we conclude that \(\min\{g(0),g(1)\} = \min\big\{\frac{1}{4},\frac{47}{256}\big\} > 0\), as desired. ◻

Proof. Consider a promise problem \((\mathcal{L}_{yes},\mathcal{L}_{no})\in \texorpdfstring{\textrm{\textsf{BQ}\textsubscript{U}\textsf{L}}}[a(n),b(n)]\), then we know that the acceptance probability \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \geq a(n)\) if \(x \in \mathcal{L}_{yes}\), whereas \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \leq b(n)\) if \(x \in \mathcal{L}_{no}\). Now we notice that the acceptance probability can be expressed in terms of the fidelity between a single-qubit pure state \(\rho_0\) and a single-qubit mixed state \(\rho_1\) that is prepared by two logarithmic-qubit quantum circuits \(Q_0\) and \(Q_1\), respectively: \[\label{eq:GapQSDlog-BQL-hard} \begin{align} \mathrm{Pr}\!\left[C_x \text{ accepts}\right] =& \left\|\lvert{1}\rangle\langle{1}\rvert_{\mathrm{out}}C_x\lvert{\bar{0}}\rangle\right\|^2_2\\ =&\mathrm{Tr}\rbra*{ \lvert{1}\rangle\langle{1}\rvert_{\mathrm{out}}\mathrm{Tr}_{\overline{\mathrm{out}}}\rbra*{ C_x \lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert C_x^{\dagger} } }\\ =& 1 - \mathrm{Tr}\rbra*{ \lvert{0}\rangle\langle{0}\rvert_{\mathrm{out}}\mathrm{Tr}_{\overline{\mathrm{out}}}\rbra*{ C_x \lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert C_x^{\dagger} } }\\ =& 1 - \mathrm{F}^2(\rho_0,\rho_1) \end{align}\tag{51}\] In particular, the corresponding \(Q_0\) is simply the identity, while \(Q_1\) is exactly the circuit \(C_x\). We then prepare \(\rho_0\) and \(\rho_1\), specifically \(\rho_0 \mathrel{\vcenter{:}}= \lvert{0}\rangle\!\langle{0}\rvert_{\mathrm{out}}\) and \(\rho_1 \mathrel{\vcenter{:}}= \mathrm{Tr}_{\overline{\mathrm{out}}}\rbra[\big]{C_x \lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert C_x^{\dagger}}\), by tracing out all non-output qubits. By utilizing 1, we have derived that:

• For yes instances, \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] = 1-\mathrm{F}^2(\rho_0,\rho_1) \geq a(n)\) deduces that \[\mathrm{T}(\rho_0,\rho_1) \geq 1-\mathrm{F}(\rho_0,\rho_1) \geq 1 - \sqrt{1-a(n)};\]

• For no instances, \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] = 1-\mathrm{F}^2(\rho_0,\rho_1) \leq b(n)\) yields that \[\mathrm{T}(\rho_0,\rho_1) \leq \sqrt{1-\mathrm{F}^2(\rho_0,\rho_1)} \leq \sqrt{b(n)}.\]

Therefore, we prove that \(\textrm{\mathrm{\small GapQSD}}_{\log}[1-\sqrt{1-a(n)},\sqrt{b(n)}]\) is \(\texorpdfstring{\textrm{\textsf{BQ}\textsubscript{U}\textsf{L}}}[a(n),b(n)]\)-hard, and we complete the argument by combining this with error reduction for BQ_UL (5). ◻

Proof. For any promise problem \((\mathcal{L}_{yes},\mathcal{L}_{no})\in \texorpdfstring{\textrm{\textsf{BQ}\textsubscript{U}\textsf{L}}}[a(n),b(n)]\), we have that the acceptance probability \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \geq a(n)\) if \(x \in \mathcal{L}_{yes}\), whereas \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \leq b(n)\) if \(x \in \mathcal{L}_{no}\). For convenience, let the output qubit be the register \(\mathsf{O}\). Now we construct a new quantum circuit \(C'_x\) with an additional ancillary qubit on the register \(\mathsf{F}\) initialized to zero: \[\label{eq:GapQHSlog-hardness} C'_x \mathrel{\vcenter{:}}= C^{\dagger}_x \textrm{\mathrm{\small CNOT}}_{\mathsf{O}\rightarrow \mathsf{F}} C_x.\tag{52}\] And we say that \(C'_x\) accepts if the measurement outcome of all qubits (namely the working qubit of \(C_x\) and \(\mathsf{F}\)) are all zero. Through a direct calculation, we obtain: \[\label{eq:GapQHSlog-BQL-hard-pacc} \begin{align} \mathrm{Pr}\!\left[C'_x \text{ accepts}\right] &= \big\| (\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \lvert{0}\rangle\langle{0}\rvert_{\mathsf{F}}) C^{\dagger}_x \textrm{\mathrm{\small CNOT}}_{\mathsf{O}\rightarrow \mathsf{F}} C_x (\lvert{\bar{0}}\rangle\otimes \lvert{0}\rangle_{\mathsf{F}})\big\|_2^2 \\ &= \big| \langle{\bar{0}}\rvert C_x^{\dagger} \lvert{0}\rangle\langle{0}\rvert_{\mathsf{O}} C_x \lvert{\bar{0}}\rangle \big|^2\\ &= \rbra*{1- \langle{\bar{0}}\rvert C_x^{\dagger} \lvert{1}\rangle\langle{1}\rvert_{\mathsf{O}} C_x \lvert{\bar{0}}\rangle}^2\\ &= \rbra*{1-{\rm Pr}\sbra*{ C_x \text{ accepts} }}^2. \end{align}\tag{53}\] Here, the second line owes to \(\textrm{\mathrm{\small CNOT}}_{\mathsf{O}\rightarrow \mathsf{F}} = \lvert{0}\rangle\langle{0}\rvert_{\mathsf{O}}\otimes I_{\mathsf{F}} + \lvert{1}\rangle\langle{1}\rvert_{\mathsf{O}} \otimes X_{\mathsf{F}}\), and the last line is because of 51 . Interestingly, by defining two pure states \(\lvert{\psi_0}\rangle\!\langle{\psi_0}\rvert \mathrel{\vcenter{:}}= \lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \lvert{0}\rangle\langle{0}\rvert_{\mathsf{F}}\) and \(\lvert{\psi_1}\rangle\!\langle{\psi_1}\rvert \mathrel{\vcenter{:}}= C'_x (\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \lvert{0}\rangle\langle{0}\rvert_{\mathsf{F}}) {C'}^{\dagger}_x\) corresponding to \(Q_0 = I\) and \(Q_1=C'_x\), respectively, we deduce the following from 53 : \[\label{eq:GapQHSlog-BQL-hard} \mathrm{Pr}\!\left[C'_x \text{ accepts}\right] = \abs{\langle \psi_0 | \psi_1 \rangle}^2 = 1-\mathrm{HS}^2(\lvert{\psi_0}\rangle\!\langle{\psi_0}\rvert,\lvert{\psi_1}\rangle\!\langle{\psi_1}\rvert).\tag{54}\] Combining [eq:GapQHSlog-BQL-hard-pacc,eq:GapQHSlog-BQL-hard], and writing \(p_{\rm acc} \mathrel{\vcenter{:}}= {\rm Pr}\sbra*{ C_x\text{ accepts} }\), we obtain \[\mathrm{HS}^2(\lvert{\psi_0}\rangle\!\langle{\psi_0}\rvert,\lvert{\psi_1}\rangle\!\langle{\psi_1}\rvert) = 1-(1-p_{\rm acc})^2 = 2 p_{\rm acc} - p_{\rm acc}^2.\] Since the map \(p_{\rm acc} \mapsto 2p_{\rm acc}-p_{\rm acc}^2\) is monotonically non-decreasing on \([0,1]\), it follows that:

• For yes instances, \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \geq a(n)\) implies that \[\mathrm{HS}^2(\lvert{\psi_0}\rangle\!\langle{\psi_0}\rvert,\lvert{\psi_1}\rangle\!\langle{\psi_1}\rvert) \geq 2a(n)-a(n)^2.\]

• For no instances, \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] \leq b(n)\) yields that \[\mathrm{HS}^2(\lvert{\psi_0}\rangle\!\langle{\psi_0}\rvert,\lvert{\psi_1}\rangle\!\langle{\psi_1}\rvert) \leq 2b(n)-b(n)^2.\]

We thus establish that \(\texorpdfstring{\textrm{\mathrm{\small GapQHS}\textsubscript{log}}}[2a(n)-a^2(n), 2b(n)-b^2(n)]\) is \(\texorpdfstring{\textrm{\textsf{BQ}\textsubscript{U}\textsf{L}}}[a(n),b(n)]\)-hard, and we complete the argument by combining this with error reduction for BQ_UL (5). ◻

Proof. To prove the first item, we follow the construction in 21 and replace \(Q_0\) with a circuit that flips the output qubit. Consequently, the corresponding quantum states are \[\widehat{\rho}_0 = \lvert{1}\rangle\!\langle{1}\rvert_{\mathrm{out}} \quad \text{and} \quad \widehat{\rho}_1 = \mathrm{Tr}_{\overline{\mathrm{out}}}\rbra[\big]{C_x \lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert C_x^{\dagger}}.\] Therefore, we obtain \(\mathrm{Pr}\!\left[C_x \text{ accepts}\right] = \mathrm{F}^2(\widehat{\rho}_0,\widehat{\rho}_1)\), which implies \(\mathrm{T}(\widehat{\rho}_0,\widehat{\rho}_1)=0\) (due to perfect completeness) for yes instances, while \(\mathrm{T}(\widehat{\rho}_0,\widehat{\rho}_1) \geq 1-\mathrm{F}(\widehat{\rho}_0,\widehat{\rho}_1) \geq 1-\sqrt{b(n)}\) for no instances. We then complete the proof by combining this with error reduction for coRQ_UL (5).

For the second item, we proceed as in the construction of 22 and replace \(C'_x\) with \[\widetilde{C}'_x \mathrel{\vcenter{:}}= C^{\dagger}_x X^{\dagger}_{\mathsf{O}} \textrm{\mathrm{\small CNOT}}_{\mathsf{O}\rightarrow \mathsf{F}} X_{\mathsf{O}} C_x.\] The corresponding pure states are then \[\lvert{\widetilde{\psi}_0}\rangle\!\langle{\widetilde{\psi}_0}\rvert\mathrel{\vcenter{:}}=\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \lvert{0}\rangle\langle{0}\rvert_{\mathsf{F}} \quad\text{and}\quad \lvert{\widetilde{\psi}_1}\rangle\!\langle{\widetilde{\psi}_1}\rvert\mathrel{\vcenter{:}}= \widetilde{C}'_x (\lvert{\bar{0}}\rangle\langle{\bar{0}}\rvert\otimes \lvert{0}\rangle\langle{0}\rvert_{\mathsf{F}}) \rbra[\big]{\widetilde{C}'_x}^{\dagger}.\] It follows that \(\mathrm{Pr}^2[C_x\text{ accepts}] = 1-\mathrm{HS}^2\rbra*{\lvert{\widetilde{\psi}_0}\rangle\!\langle{\widetilde{\psi}_0}\rvert, \lvert{\widetilde{\psi}_1}\rangle\!\langle{\widetilde{\psi}_1}\rvert}\), which implies \[\mathrm{HS}^2\rbra*{\lvert{\widetilde{\psi}_0}\rangle\!\langle{\widetilde{\psi}_0}\rvert, \lvert{\widetilde{\psi}_1}\rangle\!\langle{\widetilde{\psi}_1}\rvert} = 0\] for yes instances, while \(\mathrm{HS}^2\rbra*{\lvert{\widetilde{\psi}_0}\rangle\!\langle{\widetilde{\psi}_0}\rvert, \lvert{\widetilde{\psi}_1}\rangle\!\langle{\widetilde{\psi}_1}\rvert} \geq 1-b^2(n)\) for no instances. We thus similarly conclude the proof by integrating this with 5. ◻

Proof. By 21, it suffices to reduce \(\textrm{\mathrm{\small GapQSD}}_{\log}[1-1/p(n),1/p(n)]\) to \(\textrm{\mathrm{\small GapQJS}}_{\log}[\alpha(n),\beta(n)]\). Consider logarithmic-qubit quantum circuits \(Q_0\) and \(Q_1\), which is a \(\textrm{\mathrm{\small GapQSD}}_{\log}\) instance. We can obtain \(\rho_k\) for \(k\in\{0,1\}\) by performing \(Q_k\) on \(\lvert{0^n}\rangle\) and tracing out the non-output qubits. We then have the following:

• If \(\mathrm{T}(\rho_0,\rho_1) \geq 1-1/p(n)\), then 3 yields that \[\mathrm{QJS}_2(\rho_0,\rho_1) \geq 1-\mathrm{H_2}\left(\tfrac{1-\mathrm{T}(\rho_0,\rho_1)}{2}\right) \geq 1-\mathrm{H_2}\left(\tfrac{1}{2p(n)}\right) \geq 1-\tfrac{\sqrt{2}}{\sqrt{p(n)}} \geq \alpha(n),\] where the third inequality owing to \(\mathrm{H_2}(x)\leq 2\sqrt{x}\) for all \(x\in[0,1]\).

• If \(\mathrm{T}(\rho_0,\rho_1) \leq 1/p(n)\), then 3 indicates that \[\mathrm{QJS}_2(\rho_0,\rho_1) \leq \mathrm{T}(\rho_0,\rho_1) \leq \tfrac{1}{p(n)} \leq \beta(n).\]

Therefore, we can utilize the same quantum circuits \(Q_0\) and \(Q_1\), along with their corresponding quantum states \(\rho_0\) and \(\rho_1\), respectively, to establish a logspace Karp reduction from \(\textrm{\mathrm{\small GapQSD}}_{\log}[1-1/p(n),1/p(n)]\) to \(\textrm{\mathrm{\small GapQJS}}_{\log}[\alpha(n),\beta(n)]\), as required. ◻

Proof. By combining [lemma:GapQSDlog-BQLhard,lemma:GapQJSlog-BQL-hard], we establish that \(\textrm{\mathrm{\small GapQJS}}_{\log}[\alpha(n),\beta(n)]\) is BQ_UL-hard for \(\alpha(n) \leq 1-\sqrt{2}/\sqrt{p(n)}\) and \(\beta(n) \geq 1/p(n)\), where \(p(n)\) is some deterministic logspace computable polynomial. The GapQSD_log-hard (and simultaneously GapQJS_log-hard) instances, as specified in 21, consist of \(s(n)\)-qubit quantum circuits \(Q_0\) and \(Q_1\) that prepare a purification of \(r(n)\)-qubit quantum (mixed) states \(\rho_0\) and \(\rho_1\), respectively, where \(1 \leq r(n) \leq s(n) = \Theta(\log{n})\).

Subsequently, by employing 6, we construct \((s+3)\)-qubit quantum circuits \(Q'_0\) and \(Q'_1\) that prepare a purification of \((r+1)\)-qubit quantum states \(\rho'_0=\big(p\lvert{0}\rangle\langle{0}\rvert+(1-p)\lvert{1}\rangle\langle{1}\rvert\big)\otimes (\frac{1}{2}\rho_0 + \frac{1}{2}\rho_1)\) satisfying \(\mathrm{H_2}(p)=1- \rbra*{ \alpha(n)+\beta(n) }/2\) and \(\rho'_1=\frac{1}{2}\lvert{0}\rangle\langle{0}\rvert\otimes \rho_0 + \frac{1}{2}\lvert{1}\rangle\langle{1}\rvert\otimes \rho_1\), respectively. Following 6, \(\texorpdfstring{\textrm{\mathrm{\small GapQED}\textsubscript{log}}}[g(n)]\) is BQ_UL-hard as long as \[g(n)=\tfrac{\ln{2}}{2} \big(\alpha(n/3)-\beta(n/3)\big) \leq \tfrac{\ln{2}}{2}\Big(1-\tfrac{\sqrt{2}}{\sqrt{p(n/3)}} - \tfrac{1}{p(n/3)}\Big).\] Therefore, \(\textrm{\mathrm{\small GapQSD}}_{s}\) is logspace Karp reducible to \(\textrm{\mathrm{\small GapQED}}_{s+1}\) by mapping \((Q_0,Q_1)\) to \((Q'_0,Q'_1)\). ◻