Space-bounded quantum state testing

via space-efficient quantum singular value transformation
François Le GallEmail<EMAIL_ADDRESS>Yupan LiuEmail<EMAIL_ADDRESS>Qisheng WangEmail<EMAIL_ADDRESS>Graduate School of Mathematics, Nagoya University

Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary ) and two-sided error (), approached from a quantum (mixed) state testing perspective:

* The first family of natural complete problems for unitary $\coRQL$, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance;

* A new family of (arguably simpler) natural complete problems for , namely space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and (von Neumann) entropy difference.

In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as $Q_0$ and $Q_1$, which prepare quantum states $\rho_0$ and $\rho_1$, respectively, with access to their “source code”. Our goal is to decide whether $\rho_0$ is $\epsilon_1$-close to or $\epsilon_2$-far from $\rho_1$ with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure (either -complete or -complete),  our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states.

Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by cite.GSLW19Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest.
Our technique provides a unified approach for designing space-bounded quantum algorithms.
Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for (special forms of) the projected unitary encoding.

§ INTRODUCTION

In recent years, exciting experimental advancements in quantum computing have been achieved, but concerns about their scalability persist. It thus becomes essential to characterize the computational power of feasible models of quantum computation that operate under restricted resources, such as time (i.e., the number of gates in the circuit) and space (i.e., the number of qubits on which the circuit acts).
This paper specifically focuses on the latter aspect: what is the computational power of quantum computation with a limited number of qubits?

Previous studies [92, 95, 91] on complete problems of space-bounded quantum computation have primarily focused on well-conditioned versions of standard linear-algebraic problems [89, 34, 36] and have been limited to the two-sided error scenario. In contrast, we propose a novel family of complete problems that not only characterize the one-sided error scenario (and extend to the two-sided scenario) but also arise from a quantum property testing perspective. Our new complete problems are arguably more natural and simpler, driven by recent intriguing challenges of verifying the intended functionality of quantum devices.

Consider the situation where a quantum device is designed to prepare a quantum (mixed) state $\rho_0$, but a possibly malicious party could provide another quantum device that outputs a different $n$-qubit (mixed) state $\rho_1$, claiming that $\rho_0 \!\approx_{\epsilon}\! \rho_1$. The problem of testing whether $\rho_0$ is $\epsilon_1$-close to or $\epsilon_2$-far from $\rho_1$ with respect to a specified distance-like measure, given the ability to produce copies of $\rho_0$ and $\rho_1$, is known as quantum state testing <cit.>.
Quantum state testing (resp., distribution testing) typically involves utilizing sample accesses to quantum states $\rho_0$ and $\rho_1$ (resp., distributions $D_0$ and $D_1$) and determining the number of samples required to test the closeness between quantum states (resp., distributions).
This problem is a quantum (non-commutative) generalization of classical property testing, which is a fundamental problem in theoretical computer science (see [43]), specifically (tolerant) distribution testing (see [21]). Moreover, this problem is an instance of the emerging field of quantum property testing (see [68]), which aims at designing quantum testers for the properties of quantum objects.

In this paper, we investigate quantum state testing problems where quantum states $\rho_0$ and $\rho_1$ are preparable by computationally constrained resources, specifically state-preparation circuits (viewed as the “source code” of devices) that are (log)space-bounded.
Our main result conveys a conceptual message that testing quantum states prepared in bounded space is (computationally) as easy as preparing these states in a space-bounded manner. Consequently, we can introduce the first family of natural $\coRQUL$-complete promise problems since Watrous [93] introduced unitary  and  (known as $\RQUL$ and $\coRQUL$, respectively) in 2001, as well as a new family of natural -complete promise problems.

Our main technique is a space-efficient variant of the quantum singular value transformation (QSVT) [50],  distinguishing itself from prior works primarily focused on time-efficient QSVT. As time-efficient QSVT provides a unified framework for designing time-efficient quantum algorithms [50, 73], we believe our work indicates a unified approach to designing space-bounded quantum algorithms, potentially facilitating the discovery of new complete problems for  and its one-sided error variants.
Subsequently, we will first state our main results and then provide justifications for the significance of our results from various perspectives.

§.§ Main results

We will commence by providing definitions for time- and space-bounded quantum circuits. We say that a quantum circuit $Q$ is (poly)time-bounded if $Q$ is polynomial-size and acts on $\poly(n)$ qubits. Likewise, we say that a quantum circuit $Q$ is (log)space-bounded if $Q$ is polynomial-size and acts on $O(\log{n})$ qubits. It is worthwhile to note that primary complexity classes, e.g., , , and , mentioned in this paper correspond to promise problems.

Complete characterizations of quantum logspace from state testing.
While prior works [89, 34, 36] on -complete problems have mainly focused on well-conditioned versions of standard linear-algebraic problems (in $\DETs$), our work takes a different perspective by exploring quantum property testing. Specifically, we investigate the problem of space-bounded quantum state testing, which aims to test the closeness between two quantum states that are preparable by (log)space-bounded quantum circuits (devices), with access to the corresponding “source code” of these devices.

We begin by considering a computational problem that serves as a “white-box” space-bounded counterpart of quantum state certification [19], equivalent to quantum state testing with one-sided error.
Our first main theorem (<Ref>) demonstrates the first family of natural $\coRQUL$-complete problems in the context of space-bounded quantum state certification with respect to the trace distance ($\td$) and the squared Hilbert-Schmidt distance ($\HS$).

The following (log)space-bounded quantum state certification problems are $\coRQUL$-complete: for any $\alpha(n) \geq 1/\poly(n)$, decide whether

* $\coCertQSD_{\log}$: $\rho_0=\rho_1$ or $\td(\rho_0,\rho_1) \geq \alpha(n)$;

* $\coCertQHS_{\log}$: $\rho_0=\rho_1$ or $\HS(\rho_0,\rho_1) \geq \alpha(n)$;

By extending the error requirement from one-sided to two-sided, we broaden the scope of space-bounded quantum state testing to include two more distance-like measures: the quantum entropy difference, denoted by $\S(\rho_0)-\S(\rho_1)$,  and the quantum Jensen-Shannon divergence ($\QJS_2$). As a result, we establish our second main theorem, introducing a new family of natural -complete problems:

The following (log)space-bounded quantum state testing problems are $\BQL$-complete: for any $\alpha(n)$ and $\beta(n)$ such that $\alpha(n)-\beta(n) \geq 1/\poly(n)$, or for any $g(n) \geq 1/\poly(n)$, decide whether

* $\GapQSD_{\log}$: $\td(\rho_0,\rho_1) \geq \alpha(n)$ or $\td(\rho_0,\rho_1) \leq \beta(n)$;

* $\GapQED_{\log}$: $\S(\rho_0)-\S(\rho_1) \geq g(n)$ or $\S(\rho_1)-\S(\rho_0) \geq g(n)$;

* $\GapQJS_{\log}$: $\QJS_2(\rho_0,\rho_1) \geq \alpha(n)$ or $\QJS_2(\rho_0,\rho_1) \leq \beta(n)$;

* $\GapQHS_{\log}$: $\HS(\rho_0,\rho_1) \geq \alpha(n)$ or $\HS(\rho_0,\rho_1) \leq \beta(n)$;

Notably, <Ref><ref> demonstrates that our algorithm for  exhibits a polynomial advantage in space over the best-known classical algorithms [94], since Watrous implicitly showed in <cit.> that  is contained in (classical) poly-logarithmic space.[Notably, our algorithm for  provides an alternating proof for the original statement that $(\alpha,\beta)$- is in  when $\alpha(n)-\beta(n) \geq \exp(-\poly(n))$. In particular, Watrous [94] provided an algorithm in  to solve the Trace Norm Approximation problem on estimating $\|X\|_1$ with polynomial precision, given that the polynomial-size matrix $X$ enables evaluation of all entries in deterministic $O(\log{n})$ space.]

Space-efficient quantum singular value transformation. Proving our main theorems mentioned above poses a significant challenge: establishing the containment in the relevant class ( or ), which is also the difficult direction for showing the known family of -complete problems [89, 34, 36].

Proving the containment for the one-sided error scenario is not an effortless task: such a task is not only already relatively complicated for , but also additionally requires novel techniques for . On the other hand, for two-sided error scenarios, while showing the containment is straightforward for , it still demands sophisticated techniques for all other problems, such as , , and .

As explained in <Ref>, our primary technical contribution and proof technique involve developing a space-efficient variant of the quantum singular value transformation (QSVT), which constitutes our third main theorem (<Ref>).

§.§ Background on space-bounded quantum computation

Watrous [92, 95] initiated research on space-bounded quantum computation and showed that fundamental properties, including closure under complement, hold for $\BQSPACE[s(n)]$ with $s(n)\geq \Omega(\log{n})$.
Watrous also investigated classical simulations of space-bounded quantum computation (with unbounded error), presenting deterministic simulations in $O(s^2(n))$ space and unbounded-error randomized simulations in $O(s(n))$ space.
A decade later, van Melkebeek and Watson [91] provided a simultaneous $\tilde{O}(t(n))$ time and $O(s(n)+\log{t(n)})$ space unbounded-error randomized simulation for a bounded-error quantum algorithm in $t(n)$ time and $s(n)$ space.
The complexity class corresponding to space-bounded quantum computation with $s(n)=\Theta(\log(n))$ is known as , or $\BQUL{}$ if only unitary gates are permitted.

Significantly, several developments over the past two decades have shown that $\BQL{}$ is well-defined, independent of the following factors in chronological order:

* The choice of gateset. The Solovey-Kitaev theorem [61] establishes that most quantum classes are gateset-independent, given that the gateset is closed under adjoint and all entries in gates have reasonable precision. The work of [91] presented a space-efficient counterpart of the Solovay-Kitaev theorem, implying that  is also gateset-independent.

* Error reduction. Repeating $\BQUL$ sequentially necessitates reusing the workspace, making it unclear how to reduce errors for $\BQUL{}$ as intermediate measurements are not allowed. To address this issue, the work of [31] adapted the witness-preserving error reduction for [75] with several other ideas to the space-efficient setting.

* Intermediate measurements. In the space-bounded scenario, the principle of deferred measurement is not applicable since this approach leads to an exponential increase in space complexity. Initially,  appeared to be seemingly more powerful than $\BQUL{}$ since we cannot directly demonstrate that $\BPL \subseteq \BQUL$. Recently, Fefferman and Remscrim[36] (as well as [48, 47]) proved the equivalence between  and $\BQUL{}$, indicating a space-efficient approach to eliminating intermediate measurements.

-complete problems.
Identifying natural complete problems for the class  (or $\BQUL$) is a crucial and intriguing question.
Ta-Shma [89] proposed the first candidate -complete problem, building upon the work of Harrow, Hassidim, and Lloyd [55] which established a -complete problem for inverting a (polynomial-size) well-conditioned matrix. Specifically, Ta-Shma showed that inverting a well-conditioned matrix with polynomial precision is in . Similarly, computing eigenvalues of an Hermitian matrix is also in . These algorithms offer a quadratic space advantage over the best-known classical algorithms that saturate the classical simulation bound [92, 95, 91].
Fefferman and Lin [34] later improved upon this result to obtain the first natural $\BQUL$-complete problem by ingeniously utilizing amplitude estimation to avoid intermediate measurements.

More recently, Fefferman and Remscrim [36] further extended this natural $\BQUL$-complete problem (or -complete, equivalently) to a family of natural -complete problems. They showed that a well-conditioned version of standard $\DETs$-complete problems is -complete, where $\DETs$ denotes the class of problems that are $\NC^1$ (Turing) reducible to intDET, including well-conditioned integer determinant (DET), well-conditioned matrix powering (MATPOW), and well-conditioned iterative matrix product (ITMATPROD), among others.

$\RQUL{}$- and $\coRQUL{}$-complete problems.
Watrous [93] introduced the one-sided error counterpart of $\BQUL$, namely $\RQUL$ and $\coRQUL$, and developed error reduction techniques. Moreover, Watrous proved that the undirected graph connectivity problem (USTCON) is in $\RQUL \cap \coRQUL$ whereas Reingold [84] demonstrated that USTCON is in  several years later.
Recently, Fefferman and Remscrim [36] proposed a “verification” version of the well-conditioned iterative matrix product problem (vITMATPROD) as a candidate -complete problem. However, although this problem is known to be -hard, its containment remains unresolved.
Specifically, vITMATPROD requires to decide whether a single entry in the product of polynomially many well-conditioned matrices is equal to zero.

§.§ Time-bounded and space-bounded distribution and state testing

We summarize prior works and our main results for time-bounded[The problem of time-bounded distribution (resp., state) testing aims to test the closeness between two distributions (resp., states) that are preparable by (poly)time-bounded circuits (devices), with access to the corresponding “source code” of these devices.] and space-bounded distribution and state testing with respect to $\ell_1$ norm, entropy difference, and $\ell_2$ norm in <Ref>.

Interestingly, the sample complexity of testing the closeness of quantum states (resp., distributions) depends on the choice of distance-like measures,[It is noteworthy that the quantum entropy difference is not a distance.] including the one-sided error counterpart known as quantum state certification[19]. In particular, for distance-like measures such as the $\ell_1$ norm, called total variation distance in the case of distributions [24] and trace distance in the case of states [19], as well as classical entropy difference [57, 99] and its quantum analog [3, 79], the sample complexity of distribution and state testing is polynomial in the dimension $N$.  However, for distance-like measures such as the $\ell_2$ norm, called Euclidean distance in the case of distributions [24] and Hilbert-Schmidt distance in the case of states [19], the sample complexity is independent of dimension $N$.

$\ell_1$ norm     $\ell_2$ norm     Entropy

[87, 51]
[52, 51]

[94, 97]
[13, 83]
[9, 97]

[13] and <Ref><ref>

Time- and space-bounded distribution or state testing.

As depicted in <Ref>, this phenomenon that the required sample complexity for distribution and state testing, with polynomial precision and exponential dimension, depends on the choice of distance-like measure has reflections on time-bounded quantum state testing:

* For $\ell_1$ norm and entropy difference, the time-bounded scenario is seemingly much harder than preparing states or distributions since $\QSZK \subseteq \BQP$ and $\SZK \subseteq \BPP$ are unlikely.

* For $\ell_2$ norm, the time-bounded scenario is as easy as preparing states or distributions.

However, interestingly, a similar phenomenon does not appear for space-bounded quantum state testing. Although no direct classical counterpart has been investigated before in a complexity-theoretic fashion, namely space-bounded distribution testing, there is another closely related model (a version of streaming distribution testing) that does not demonstrate an analogous phenomenon either, as we will discuss in <Ref>.

§.§.§ Time-bounded distribution and state testing

We review prior works on time-bounded state (resp., distribution) testing, with a particular focus on testing the closeness between states (resp., distributions) are preparable by (poly)time-bounded quantum (resp., classical) circuits (device), with access to the “source code” of corresponding devices. For time-bounded distribution testing, we also recommend a brief survey [53] by Goldreich and Vadhan.

$\ell_1$ norm scenarios. Sahai and Vadhan [87] initiated the study of the time-bounded distribution testing problem, where distributions $D_0$ and $D_1$ are efficiently samplable, and the distance-like measure is the total variation distance. Their work named this problem Statistical Difference (). In particular, the promise problem $(\alpha,\beta)$- asks whether $D_0$ is $\alpha$-far from or $\beta$-close to $D_1$ with respect to $\|D_0-D_1\|_{\rm TV}$.
Although sampling from the distribution is in ,[Rigorously speaking, as an instance in , sample-generating circuits are not necessarily (poly)time-uniform.] testing the closeness between these distributions is -complete [87, 51], where  is the class of promise problems possessing statistical zero-knowledge proofs.
It is noteworthy that the  containment of $(\alpha,\beta)$- for any $\alpha(n)-\beta(n) \geq 1/\poly(n)$ is currently unknown.[The works of [87, 51] demonstrated that $(\alpha,\beta)$- is in  for any constant $\alpha^2-\beta > 0$. The same technique works for the parameter regime $\alpha^2(n)-\beta(n) \geq 1/O(\log{n})$. However, further improvement of the parameter regime requires new ideas, as clarified in [44].
Recently, the work of [14] improved the parameter regime to $\alpha^2(n)-\beta(n) \geq 1/\poly(n)$ by utilizing a series of tailor-made reductions. Currently, we only know that $(\alpha,\beta)$- for $\alpha(n)-\beta(n) \geq 1/\poly(n)$ is also in $\AM\cap\coAM$[17]. ]
In addition, we note that  is contained in $\AM \cap \coAM$[35, 2].

Following the pioneering work [87], Watrous [94] introduced the time-bounded quantum state testing problem, where two quantum states $\rho_0$ and $\rho_1$ that are preparable by time-bounded quantum circuits $Q_0$ and $Q_1$, respectively, as well as the distance-like measure is the trace distance. This problem is known as the Quantum State Distinguishability (), specifically, $(\alpha,\beta)$- asks whether $\rho_0$ is $\alpha$-far from or $\beta$-close to $\rho_1$ with respect to  $\td(\rho_0,\rho_1)$. Analogous to its classical counterpart,  is -complete [94, 97], whereas the  containment for any $\alpha(n) - \beta(n) \geq 1/\poly(n)$ remains an open question.[Like  and , the techniques in [94, 97] show that $(\alpha,\beta)$- is in  for $\alpha^2(n)-\beta(n)\geq 1/O(\log{n})$, and the same limitation also applies to the quantum settings. A recent result [66] following the line of work of [14] improved the parameter regime to $\alpha^2(n)-\sqrt{2\ln{2}}\beta(n) \geq 1/\poly(n)$, but the differences between classical and quantum distances make it challenging to push the bound further. In <cit.>, Watrous implicitly proved a  upper bound for the parameter regime $\alpha(n)-\beta(n) \geq \exp(-\poly(n))$. ]
Additionally, it is worth noting that $\mathsf{QIP(2)}$ contains  [94, 97].

Entropy difference scenarios. Beyond $\ell_1$ norm, another distance-like measure commonly considered in time-bounded quantum state testing (or distribution testing) is the (quantum) entropy difference, which also corresponds to the (quantum) Jensen-Shannon divergence. The promise problem Entropy Difference (), first introduced by Goldreich and Vadhan [52] following the work of [87], asks whether efficiently samplable distributions $D_0$ and $D_1$ satisfy $\H(D_0)-\H(D_1) \geq g$ or $\H(D_1)-\H(D_0) \geq g$ for $g=1$. They demonstrated that  is -complete.
Ben-Aroya, Schwartz, and Ta-Shma [9] further investigated the promise problem Quantum Entropy Difference (), which asks whether $\S(\rho_0)-\S(\rho_1) \geq g$ or $\S(\rho_1)-\S(\rho_0) \geq g$, for efficiently preparable quantum states $\rho_0$ and $\rho_1$ and $g=1/2$. They showed that  is -complete.
Moreover, the  (resp., ) containment for  (resp., ) automatically holds for any $g(n) \geq 1/\poly(n)$.

Furthermore, Berman, Degwekar, Rothblum, and Vasudevan [14] demonstrated that the Jensen-Shannon divergence problem (), asking whether $\JS(D_0,D_1) \geq \alpha$ or $\JS(D_0,D_1) \leq \beta$ for efficiently samplable distributions $D_0$ and $D_1$, is -complete. Their work accomplished this result by reducing the problem to , and this containment applies to  $\alpha(n)-\beta(n) \geq 1/\poly(n)$. Recently,  Liu [66] showed a quantum counterpart, referred to as the Quantum Jensen-Shannon Divergence Problem (), is -complete.
Notably, the quantum Jensen-Shannon divergence is a special instance of the Holevo $\chi$ quantity [56].[In particular, the quantum Jensen-Shannon divergence coincides with the Holevo $\chi$ quantity on size-$2$ ensembles with a uniform distribution, which arises in the Holevo bound [56]. See <cit.>.]

$\ell_2$ norm scenarios.
For the quantum setting, it is straightforward that applying the SWAP test [13][We note that the SWAP test also applies to mixed states, see Proposition 9 in [63].] to efficiently preparable quantum states $\rho_0$ and $\rho_1$ can lead to a  containment, in particular, additive-error estimations of $\Tr(\rho_0^2)$, $\Tr(\rho^2_1)$, and $\Tr(\rho_0\rho_1)$ with polynomial precision.
Recently, the work of [83] observed that time-bounded quantum state testing with respect to the squared Hilbert-Schmidt distance is -complete.
For the classical setting, namely the squared Euclidean distance, the -completeness is relatively effortless.[Specifically, we achieve  containment by following the approach in <cit.>. On the other hand, the  hardness owes to the fact that the squared Euclidean distance between the distribution $(p_{\rm acc}, 1-p_{\rm acc})$ from the output bit of any  algorithm and the distribution $(1,0)$ is $(1-p_{\rm acc})^2$.]

§.§.§ Space-bounded distribution and state testing

To the best of our knowledge, no prior work has specifically focused on space-bounded distribution testing from a complexity-theoretic perspective. Instead, we will review prior works that are (closely) related to this computational problem. Afterward, we will delve into space-bounded quantum state testing, which constitutes the main contribution of our work.

Space-bounded distribution testing and related works.
We focus on a computational problem involving two $\poly(n)$-size classical circuits $C_0$ and $C_1$, which generate samples from the distributions $D_0$ and $D_1$ respectively. Each circuit contains a read-once polynomial-length random-coins tape.[It is noteworthy that random coins are provided as input to classical circuits $C_0$ and $C_1$ for generating samples from the corresponding distributions in the time-bounded scenario, such as  and .] The input length and output length of the circuits are $O(\log{n})$. The task is to decide whether $D_0$ is $\alpha$-far from or $\beta$-close to $D_1$ with respect to some distance-like measure. Additionally, we can easily observe that space-bounded distribution testing with respect to the squared Euclidean distance ($\ell_2$ norm) is -complete, much like its time-bounded counterpart.

Several models related to space-bounded distribution testing have been investigated previously. Earlier streaming-algorithmic works [32, 42] utilize entries of the distribution as the data stream, with entries given in different orders for different models. On the other hand, a later work [26] considered a data stream consisting of a sequence of i.i.d. samples drawn from distributions and studied low-space streaming algorithms for distribution testing.

Regarding (Shannon) entropy estimation, previous streaming algorithms considered worst-case ordered samples drawn from $N$-dimensional distributions and required $\poly\log(N/\epsilon)$ space, where $\epsilon$ is the additive error. Recently, Acharya, Bhadane, Indyk, and Sun [1] addressed the entropy estimation problem with i.i.d. samples drawn from distributions as the data stream and demonstrated the first $O(\log(N/\epsilon))$ space streaming algorithm. The sample complexity, viewed as the time complexity, was subsequently improved in [6].

However, for the total variation distance ($\ell_1$ norm), previous works focused on the trade-off between the sample complexity and the space complexity (memory constraints), achieving only a nearly-log-squared space streaming algorithm [28].

Notably, the main differences between the computational and streaming settings lie in how we access the sampling devices.[Of course, not all distributions can be described as a polynomial-size circuit (i.e., a succinct description).] In the computational problem, we have access to the “source code” of the devices and can potentially use them for purposes like “reverse engineering”. Conversely, the streaming setting utilizes the sampling devices in a “black-box” manner, obtaining i.i.d. samples. As a result, a logspace streaming algorithm will result in a  containment.[In particular, the sample-generating circuits $C_0$ and $C_1$ in space-bounded distribution testing can produce the i.i.d. samples in the data stream.]

Space-bounded quantum state testing.
Among the prior works on streaming distribution testing, particularly entropy estimation, the key takeaway is that the space complexity of the corresponding computational problem is $O(\log(N/\epsilon))$. This observation leads to a conjecture that the computational hardness of space-bounded distribution and state testing is independent of the choice of commonplace distance-like measures. Our work, in turn, provides a positive answer for space-bounded quantum state testing.

Space-bounded state testing with respect to the squared Hilbert-Schmidt distance ($\ell_2$ norm) is -complete, as shown in <Ref><ref>. Specifically, the  containment follows from the SWAP test [13], similar to the time-bounded scenario. Moreover, proving  hardness, as well as -hardness for state certification, are also straightforward.[In particular, considering any  circuit $C_x$ that accepts with probability $p_{\rm acc} = |\ket{1}\bra{1}_{\Out} C_x \ket{\bar{0}}|_2^2$, we can construct a new circuit $C'_x$ from $C_x$ such that $C'_x$ accepts with probability $| \ket{\bar{0}}\bra{\bar{0}} C'_x \ket{\bar{0}}|2^2 = p{\rm acc}^2 = \Tr(\rho_0\rho_1) = 1-\HS(\rho_0,\rho_1)$, where pure states $\rho_0=\ket{\bar{0}}\bra{\bar{0}}$ and $\rho_1=C'_x\ket{\bar{0}}\bra{\bar{0}}{C'_x}^{\dagger}$. See <Ref> for details. ]

Regarding space-bounded state testing with respect to the trace distance ($\ell_1$ norm), we note that <cit.> implicitly established an  containment. The -hardness, as well as -hardness for state certification, is adapted from [83]. Similarly, we derive the -hardness for space-bounded state testing with respect to the quantum Jensen-Shannon divergence and the quantum entropy difference from previous works [66].

Finally, we devote the remainder of this section to our main technique (<Ref>), and consequently, we present  (resp., ) containment for state testing (resp., certification) problems for other distance-like measures beyond the squared Hilbert-Schmidt distance.

§.§ Proof technique: Space-efficient quantum singular value transformation

The quantum singular value transformation (QSVT)[50] is a powerful and efficient framework for manipulating the singular values $\{\sigma_i\}_i$ of a linear operator $A$, using a corresponding projected unitary encoding $U$ of $A=\tilde{\Pi} U \Pi$ for projectors $\tilde{\Pi}$ and $\Pi$. The singular value decomposition is $A=\sum_i \sigma_i \ket{\tpsi_i}\bra{\psi_i}$ where $\ket{\tpsi_i}$ and $\ket{\psi_i}$ are left and right singular vectors, respectively. QSVT has numerous applications in  quantum algorithm design, and is even considered a grand unification of quantum algorithms [73].
To implement the transformation $f^{\SV}(A)=f^{\SV}(\tilde{\Pi} U \Pi)$, we require a degree-$d$ polynomial $\hat{P}_d(x)$ that satisfies two conditions. Firstly, $\hat{P}_d$ well-approximates $f$ on the interval of interest $\calI$, with $\max_{x \in \calI\setminus \calI_{\delta}}|\hat{P}_d(x)-f(x)| \leq \epsilon$, where $\calI_{\delta} \subseteq \calI\subseteq [-1,1]$ and typically $\calI_{\delta}:=(-\delta,\delta)$. Secondly, $\hat{P}_d$ is bounded, with $\max_{x \in [-1,1]}|\hat{P}_d(x)| \leq 1$. The degree of $\hat{P}_d$ depends on the precision parameters $\delta$ and $\epsilon$, with $d=O(\delta^{-1} \log{\epsilon^{-1}})$, and all coefficients of $\hat{P}_d$ can be computed efficiently.

According to [50], we can use an alternating phase modulation to implement $\hat{P}_d^{\SV}(\tilde{\Pi} U \Pi)$,[This procedure is a generalization of quantum signal processing, as explained in <cit.>.] which requires a sequence of rotation angles $\Phi \in \bbR^d$.
For instance, consider $\hat{P}_d(x)=T_d(x)$ where $T_d(x)$ is the $d$-th Chebyshev polynomial (of the first kind), then we know that $\phi_1 = (1-d)\pi/2$ and $\phi_j=\pi/2$ for all $j\in\{2,3,\cdots,d\}$.
QSVT techniques, including classical pre-processing and quantum circuit implementation, are generally time-efficient. Additionally, the quantum circuit implementation of QSVT is already space-efficient because implementing QSVT with a degree-$d$ bounded polynomial for any $s(n)$-qubit projected unitary encoding requires $O(s(n))$ qubits, where $s(n)\geq \Omega(\log{n})$.
However,  the classical pre-processing in the QSVT techniques is typically not space-efficient.
Indeed, prior works on classical pre-processing for QSVT, specifically angle-finding algorithms in [54, 22, 29], which have time complexity polynomially dependent on the degree $d$, do not consider the space-efficiency.
Therefore, the use of previous angle-finding algorithms may lead to an exponential increase in space complexity.
This raises a fundamental question on making the classical pre-processing space-efficient as well:
[Space-efficient QSVT]

Can we implement a degree-$d$ QSVT for any $s(n)$-qubit projected unitary encoding with $d \leq 2^{O(s(n))}$, using only $O(s(n))$ space in both classical pre-processing and quantum circuit implementation?

QSVT via Chebyshev interpolation.
Recently, Metger and Yuen [77] constructed bounded polynomial approximations of the sign and square root functions with exponential precision in polynomial space by utilizing Chebyshev interpolation, which offers a partial solution to <Ref>.[To clarify, we can see from [77] that directly adapting their construction shows that implementing QSVT for any $s(n)$-qubit block-encoding with $O(s(n))$-bit precision requires $\poly(s(n))$ classical and quantum space for any $s(n) \geq \Omega(\log{n})$.
However, <Ref> (space-efficient QSVT) seeks to reduce the dependence of $s(n)$ in the space complexity from polynomial to linear. ]
The key ingredient behind their approach is the near-minimax approximation by Chebyshev interpolation [80]. More precisely, for any continuous function $f\colon[-1,1]\rightarrow \bbR$, if there is a degree-$d$ polynomial $\hat{P}_d$ satisfying $\max_{x\in[-1,1]} |f(x)-\hat{P}_d(x)| \leq \epsilon$, then we have a Chebyshev interpolation polynomial $P_d(x):=\frac{c_0}{2} + \sum_{k=1}^d c_k T_k$ where $c_k:=\frac{2}{\pi}\int_{-1}^1 \frac{f(x)T_k(x)}{\sqrt{1-x^2}} \dx$ such that $\max_{x\in[-1,1]} |P_d(x)-f(x)|\leq O(\epsilon \log{d})$.
As the angles for any Chebyshev polynomial $T_k(x)$ are explicitly known, the implementation involves applying a Chebyshev polynomial to a bitstring indexed encoding, which additionally requires projectors $\tilde{\Pi}$ and $\Pi$ span on the corresponding subset of $\{\ket{0},\ket{1}\}^{\otimes s}$,[To ensure that $\tilde{\Pi} U \Pi$ admits a matrix representation, we require the basis of projectors $\tilde{\Pi}$ and $\Pi$ to have a well-defined order, leading us to focus exclusively on bitstring indexed encoding. Additionally, for simplicity, we assume no ancillary qubits are used here, and refer to <Ref> for a formal definition.] and implementing the Chebyshev interpolation polynomial by LCU techniques [11]. It is noteworthy that combining the aforementioned techniques causes a super-quadratic dependence of the degree $d$ in the query complexity to $U$.

A refined analysis indicates that applying a Chebyshev interpolation polynomial to a bitstring indexed encoding for any $d \leq 2^{O(s(n))}$ and $\epsilon \geq 2^{-O(s(n))}$ requires $O(s(n))$ qubits and deterministic $O(s(n))$ space, provided that an evaluation oracle $\Eval_{P_d}$ estimates coefficients $\{c_k\}_{k=0}^d$ of the Chebyshev interpolation polynomial with $O(\log(\epsilon/d))$ precision. This result leads to the establishment of a space-efficient variant of QSVT:

Let $f\colon\bbR \rightarrow \bbR$ be a continuous function bounded on $\calI \subseteq [-1,1]$. If there exists a degree-$d$ polynomial $\hat{P}_d$ that approximates $h\colon[-1,1] \rightarrow \bbR$, where $h$ approximates $f$ only on $\calI$, such that $\max_{x \in [-1,1]} |h(x)-\hat{P}_d(x)| \leq \epsilon$, then Chebyshev interpolation yields another degree-$d$ polynomial $P_d$ satisfying the following conditions: $\max_{x \in \calI} |f(x)-P_d(x)| \leq O(\epsilon \log{d})$ and $\max_{x \in [-1,1]} |P_d(x)| \leq 1$.

Furthermore, we have an algorithm $\calA_f$ that computes any coefficient $\{c_k\}_{k=0}^d$ of the Chebyshev interpolation polynomial $P_d$ space-efficiently. The algorithm is deterministic for bounded $f$, and bounded-error randomized for piecewise-smooth $f$. Additionally, for any $s(n)$-qubit bitstring indexed encoding $U$ of $A=\tilde{\Pi} U \Pi$ with $d\leq 2^{O(s(n))}$, we can implement the quantum singular value transformation $P_d^{\SV}(A)$ using $O(d^2\|\bfc\|_1)$ queries[The dependence of $\|\bfc\|_1$ arises from renormalizing the bitstring indexed encoding via amplitude amplification.] In addition, $\|\bfc\|_1$ is generally upper-bounded by $O(d)$ for all piecewise-smooth functions. However, for specific functions, such as the sign function, we can improve the upper bound to $O(\log{d})$. to $U$ with $O(s(n))$ qubits.

Our techniques in <Ref> offer two advantages over the techniques proposed by [77]. Firstly, our techniques can handle any piecewise-smooth function, such as the normalized logarithmic function $\ln_{\beta}(x):=\frac{\ln(1/x)}{2\ln(2/\beta)}$ on the interval $\calI=[\beta,1]$ for any $\beta \geq 2^{-O(s(n))}$, whereas the techniques from [77] are restricted to functions that are bounded on the interval $\calI=[-1,1]$. Secondly, our technique is constant overhead in terms of the space complexity of the bitstring indexed encoding $U$, while the techniques from [77] are only poly-logarithmic overhead.

In addition, it is noteworthy that applying the space-efficient QSVT with the sign function will imply a unified approach to error reduction for the classes ,  and .

Computing the coefficients.
We will implement the evaluation oracle $\Eval_{P_d}$ to prove <Ref>. To estimate the coefficients $\{c_k\}_{k=0}^d$ resulting from Chebyshev interpolation for any function $f$ that is bounded on the interval $\calI=[-1,1]$, we can use standard numerical integral techniques,[We remark that using a more efficient numerical integral technique, such as the exponentially convergent trapezoidal rule, may improve the required space complexity for computing coefficients by a constant factor.] given that the integrand's second derivative in $\{c_k\}_{k=0}^d$ is bounded by $\poly(d)$.

However, implementing the evaluation oracle for piecewise-smooth functions $f$ on an interval $\calI \subsetneq [-1,1]$ is relatively convoluted. We cannot simply apply Chebyshev interpolation to $f$. Instead, we consider a low-degree Fourier approximation $g$ resulting from implementing smooth functions to Hamiltonians <cit.>. We then make the error vanish outside $\calI$ by multiplying with a Gaussian error function, resulting in $h$ which approximates $f$ only on $\calI$. Therefore, we can apply Chebyshev interpolation and our algorithm for bounded functions to $h$ through a somewhat complicated calculation.

Finally, we need to compute the coefficients of the low-degree Fourier approximation $g$. Interestingly, this step involves the stochastic matrix powering problem, which lies at the heart of space-bounded derandomization, e.g.,[88, 23, 81]. We utilize space-bounded random walks on a directed graph to estimate the power of a stochastic matrix. Consequently, we can only develop a bounded-error randomized algorithm $\calA_f$ for piecewise-smooth functions.[The classical pre-processing in space-efficient QSVT is not part of the deterministic Turing machine producing the quantum circuit description in the  model (<Ref>). Instead, we treat it as a component of quantum computation, allowing the use of randomized algorithms since $\BPL \subseteq \BQL$ [36].]

§.§ Proof overview: A general framework for quantum state testing

Our framework enables space-bounded quantum state testing, specifically for proving <Ref> and  <Ref>, and is based on the one-bit precision phase estimation [60], also known as the Hadamard test[4]. Prior works [89, 34] have employed (one-bit precision) phase estimation in space-bounded quantum computation.

To address quantum state testing problems, we reduce them to estimating $\Tr(P_d(A)\rho)$, where $\rho$ is a (mixed) quantum state prepared by a quantum circuit $Q_{\rho}$, $A$ is an Hermitian operator block-encoded in a unitary operator $U_A$, and $P_d$ is a space-efficiently computable degree-$d$ polynomial. This approach has been applied in time-bounded quantum state testing, including fidelity estimation [45] and subsequently trace distance estimation [100].

$\ket{0}$     H     1     H

$\ket{\bar 0}$     [alternate]     [2]U_P_d(A) [alternate]     [alternate]     [alternate]

$\ket{\bar 0}$     [2]  Q_ρ    [alternate]     [alternate]     [alternate]     [alternate]

$\ket{\bar 0}$     [alternate]     [alternate]     [alternate]     [alternate]

General framework for quantum state testing $\calT(Q_{\rho},U_A,P_d)$.

To implement a unitary operator $U_{P_d(A)}$ that (approximately) block-encodes $P_d(A)$ in a space-efficient manner, we require $P_d$ to meet the conditions specified in <Ref>. As illustrated in <Ref>, we denote the quantum circuit as $\calT(Q_{\rho}, U_A, P_d)$, where we exclude the precision for simplicity. The measurement outcome of $\calT(Q_{\rho}, U_A, P_d)$ will be $0$ with a probability close to $\frac{1+\Tr(P_d(A)\rho)}{2}$. This property allows us to estimate $\Tr(P_d(A)\rho)$ within an additive error $\epsilon$ using $O(1/\epsilon^2)$ sequential repetitions, resulting in a  containment.

As an example of the application, $\mathcal{T}(Q_{i}, U_{\frac{\rho_0-\rho_1}{2}}, P_d^{\sign})$ is utilized in , where $U_{\frac{\rho_0-\rho_1}{2}}$ is a block-encoding of $\frac{\rho_0-\rho_1}{2}$, and $P_d^{\sign}$ is a space-efficient polynomial approximation of the sign function. Similarly, $\mathcal{T}(Q_{i}, U_{\rho_{i}}, P_d^{\ln})$ is utilized in , where $U_{\rho_{i}}$ is a block-encoding of $\rho_{i}$ for $i\in\binset$, and $P_d^{\ln}$ is a space-efficient polynomial approximation of the normalized logarithmic function. Both $P_d^{\sign}$ and $P_d^{\ln}$ can be obtained by employing <Ref>.[In particular, $P_d^{\sign}$ is given in <Ref>, as well as $P_d^{\ln}$ is given in <Ref>.]

Making the error one-sided. The main challenge is constructing a unitary $U$ of interest, such as $\calT(Q_{\rho},U_A,P_d)$, that accepts with a certain fixed probability $p$ for yes instances ($\rho_0=\rho_1$), while having a probability that polynomially deviates from $p$ for no instances.
As an example, we consider  and express $\HS(\rho_0,\rho_1)$ as a linear combination of $\Tr(\rho_0^2)$, $\Tr(\rho_1^2)$, and $\Tr(\rho_0\rho_1)$. We thus design a unitary quantum algorithm employing the LCU technique, which accepts with probability $\left(\frac{1}{2} + \frac{1}{4} \HS(\rho_0, \rho_1)\right)^2$, equal $1/4$ for yes instances. Applying the exact amplitude amplification [10, 16], we achieve perfect completeness, and the analysis demonstrates that the acceptance probability polynomially deviates from $1$ for no instances. By applying error reduction for , the resulting algorithm is indeed in .

Moving on to , we consider the quantum circuit $U_{i} = \mathcal{T}(Q_{i}, U_{\frac{\rho_0-\rho_1}{2}}, P_d^{\sign})$ for $i \in \binset$. Let $p_{i}$ be the probability that the measurement outcome of $U_i\ket{\bar{0}}$ in <Ref> is $0$. Since our space-efficient QSVT preserves parity, specifically the approximation polynomial $P_d^{\sign}$ satisfies $P_d^{\sign}(0)=0$,[Let $f$ be any odd function such that space-efficient QSVT associated with $f$ can be implemented by <Ref>. It follows that the corresponding approximation polynomial $P_d^{(f)}$ is also odd. See <Ref>.] we obtain $p_0=p_1=1/2$ for yes instances ($\rho_0=\rho_1$).
With a simple modification, $U_0$ and $U_1$ enable algorithm $\calA$ to meet the condition of exact amplitude amplification for yes instances. Further analysis shows that $\calA$ accepts with probability polynomially away from $1$ for no instances.

We thus can conclude a  containment similar to .

§.§ Discussion and open problems

Since space-efficient quantum singular value transformation (QSVT) offers a unified framework for designing quantum logspace algorithms, it suggests a new direction to find applications of space-bounded quantum computation.
An intriguing candidate is solving positive semidefinite programming (SDP) programs with constant precision [58, 8].
A major challenge in achieving a  containment for this problem is that iteratively applying the space-efficient QSVT super-constantly many times may lead to a bitstring indexed encoding requiring $\omega(\log{n})$ ancillary qubits, raising the question:

* Is it possible to have an approximation scheme (possibly under certain conditions) that introduces merely $O(1)$ additional ancillary qubits in the bitstring indexed encoding per iteration, such that applying space-efficient QSVT $\log{n}$ times results in a bitstring indexed encoding with at most $O(\log{n})$ ancillary qubits?

Furthermore, as quantum distances investigated in this work are all instances of a quantum analog of symmetric $f$-divergence, there is a natural question on other instances:

* Can we demonstrate that space-bounded quantum state testing problems with respect to other quantum distances are also -complete, such as quantum analogs of squared Hellinger distance or quantum analogs of triangular discrimination [66]?

In addition, there is a question on improving the efficiency of the space-efficient QSVT:

* Can we improve the query complexity of $U$ and $U^{\dagger}$ in the space-efficient QSVT implementation (e.g., for the sign function) from $O(d^2 \log{d})$ to $O(d)$?

Notably, classical pre-processing in QSVT techniques usually involves finding the sequence of $z$-axis rotation angles, while our approach instead uses Chebyshev interpolation and the LCU technique. A solution thus involves developing a space-efficient angle-finding algorithm. An interesting direction from a recent work [76], which investigated QSVT with $\mathrm{SU}(2)$ rotations, may shed light on Question <ref> since finding $\mathrm{SU}(2)$ rotation angles appears easier.

§.§ Related works: more on quantum state testing problems

Testing the spectrum of quantum states was studied in [79]: for example, whether a quantum state is maximally mixed or $\epsilon$-far away in trace distance from mixed states can be tested using $\Theta(N/\epsilon^2)$ samples.
Later, it was generalized in [19] to quantum state certification with respect to fidelity and trace distance.
Estimating distinguishability measures of quantum states [83] is another topic, including the estimation of fidelity [33, 102, 45] and trace distance [98, 100].

Entropy estimation of quantum states has been widely studied in the literature.
Given quantum purified access, it was shown in [41] that the von Neumann entropy $\S(\rho)$ can be estimated within additive error $\epsilon$ with query complexity $\tilde O(N/\epsilon^{1.5})$.
If we know the reciprocal $\kappa$ of the minimum non-zero eigenvalue of $\rho$, then $\S(\rho)$ can be estimated with query complexity $\tilde O(\kappa^2/\epsilon)$ [27].
We can estimate $\S(\rho)$ within multiplicative error $\epsilon$ with query complexity $\tilde O(n^{\frac{1}{2}+\frac{1+\eta}{2\epsilon^2}})$ [39], provided that $\S(\rho) = \Omega(\epsilon + 1/\eta)$.
If $\rho$ is of rank $r$, then $\S(\rho)$ can be estimated with query complexity $\tilde O(r^2/\epsilon^2)$ [98].
Estimating the Rényi entropy $S_\alpha(\rho)$ given quantum purified access was first studied in [39], and then was improved in [98, 67].
In addition, the work of [38] investigates the (conditional) hardness of  with logarithmic depth or constant depth.

Paper organization.
Our paper begins by introducing key concepts in <Ref>, including quantum distance and divergences, space-bounded quantum computation, Chebyshev polynomials and interpolation, and a toolkit for space-bounded randomized and quantum computation. In <Ref>, we demonstrate our space-efficient variant of quantum singular value transformation (<Ref>) and offer examples for bounded functions and piecewise-smooth functions. We also provide a simple proof of space-efficient error reduction for unitary quantum computation. Then, in <Ref>, we formally define space-bounded quantum state testing problems with four distance-like measures, and present the first family of natural $\coRQUL$-complete problems (<Ref>), as well as a novel family of natural -complete problems (<Ref>).

§ PRELIMINARIES

We assume that the reader is familiar with quantum computation and the theory of quantum information.
For an introduction, the textbooks by [78] and [30] provide a good starting point, while for a more comprehensive survey on quantum complexity theory, refer to [96].

In addition, we adopt the convention that the logarithmic function $\log$ has a base of $2$, denoted by $\log(x):=\log_2(x)$ for any $x \in \bbR^{+}$. For the purpose of clarity, we will denote the operator norm as $\|A\|:=\|A\|_{2\rightarrow 2}$.
Moreover, for the sake of simplicity, we utilize the notation $\ket{\bar{0}}$ to represent $\ket{0}^{\otimes a}$ with $a>1$.

§.§ Distances and divergences for quantum states

We will provide an overview of relevant quantum distances and divergences, along with useful inequalities among different quantum distance-like measures.
Additionally, we recommend <cit.> for a nice survey on quantum distance and divergences.

For any quantum states $\rho_0$ and $\rho_1$, we define several distance-like measures and relevant quantities:

* Trace distance. $\td(\rho_0,\rho_1):=\frac{1}{2}\Tr|\rho_0-\rho_1|=\frac{1}{2}\Tr(((\rho_0-\rho_1)^\dagger(\rho_0-\rho_1))^{1/2}).$

* (Uhlmann) Fidelity. $\F(\rho_0,\rho_1):=\Tr|\sqrt{\rho_0}\sqrt{\rho_1}|$.

* Squared Hilbert-Schmidt distance. $\HS(\rho_0,\rho_1):=\frac{1}{2}\Tr(\rho_0-\rho_1)^2.$

* von Neumann entropy. $\S(\rho):=-\Tr(\rho \ln \rho)$ for any quantum state $\rho$.

* Quantum Jensen-Shannon divergence. $\QJS(\rho_0,\rho_1) := \S\big(\tfrac{\rho_0+\rho_1}{2}\big)-\tfrac{\S(\rho_0)+\S(\rho_1)}{2}$.

The trace distance and the squared Hilbert-Schmidt distance reach the minimum of $0$ when $\rho_0$ equals $\rho_1$, while the fidelity attains a maximum value of $1$. Additionally, there are two equalities when at least one of the two states is a pure state:

* For a pure state $\rho_0$ and a mixed state $\rho_1$, $\F^2(\rho_0,\rho_1) = \Tr(\rho_0 \rho_1)$.

* For two pure states $\rho_0$ and $\rho_1$, $\Tr(\rho_0 \rho_1) = 1 - \HS(\rho_0,\rho_1)$.

Moreover, we have $\HS(\rho_0,\rho_1) = \frac{1}{2}(\Tr(\rho_0^2) + \Tr(\rho_1^2)) - \Tr(\rho_0\rho_1)$. Additionally, Fuchs and van de Graaf [37] showed a well-known inequality between the trace distance and the fidelity:

For any states $\rho_0$ and $\rho_1$,

\[1-\F(\rho_0,\rho_1) \leq \td(\rho_0,\rho_1) \leq \sqrt{1-\F^2(\rho_0,\rho_1)}.\]

The joint entropy theorem (<Ref>) enhances our understanding of entropy in classical-quantum states and is necessary for our usages of the von Neumann entropy.

Suppose $p_i$ are probabilities corresponding to a distribution $D$, $\ket{i}$ are orthogonal state of a system $A$, and $\{\rho_i\}_i$ is any set of density operators for another system $B$. Then $\S\big( \sum_i p_i\ket{i}\bra{i} \otimes \rho_i \big) = \H(D) + \sum_i p_i \S(\rho_i)$.

Let us now turn our attention to the quantum Jensen-Shannon divergence, which is defined in [71].
For simplicity, we define $\QJS_2(\rho_0,\rho_1):=\QJS(\rho_0,\rho_1)/\ln 2$ using the base-$2$ (matrix) logarithmic function.  Notably, when considering size-$2$ ensembles with a uniform distribution, the renowned Holevo bound [56] (see Theorem 12.1 in [78]) indicates that the quantum Shannon distinguishability studied in [37] is at most the quantum Jensen-Shannon divergence. Consequently, this observation yields inequalities between the trace distance and the quantum Jensen-Shannon divergence.[For a detailed proof of these inequalities, please refer to <cit.>.]

For any quantum states $\rho_0$ and $\rho_1$, we have

\[1-\binH\left(\tfrac{1-\td(\rho_0,\rho_1)}{2}\right) \leq \QJS_2(\rho_0,\rho_1) \leq \td(\rho_0,\rho_1).\]

Here, the binary entropy $\binH(p):=-p\log(p)-(1-p)\log(1-p)$.

§.§ Space-bounded quantum computation

We say that a function $s(n)$ is space-constructible if there exists a deterministic space $s(n)$ Turing machine that takes $1^n$ as an input and output $s(n)$ in the unary encoding.
Moreover, we say that a function $f(n)$ is $s(n)$-space computable if there exists a deterministic space $s(n)$ Turing machine that takes $1^n$ as an input and output $f(n)$.
Our definitions of space-bounded quantum computation are formulated in terms of quantum circuits, whereas many prior works focused on quantum Turing machines [97, 95, 91]. For a discussion on the equivalence between space-bounded quantum computation using quantum circuits and quantum Turing machines, we refer readers to <cit.> and <cit.>.

We begin by defining time-bounded and space-bounded quantum circuit families, and then proceed to the corresponding complexity class $\BQUSPACE[s(n)]$. It is worth noting that we use the abbreviated notation $C_x$ to denote that the circuit $C_{|x|}$ takes input $x$.

A (unitary) quantum circuit is a sequence of quantum gates, each of which belongs to some fixed gateset that is universal for quantum computation, such as $\{\Hadamard, \CNOT, \textsc{T}\}$.
For a promise problem $\calL = (\calL_{\yes},\calL_{\no})$, we say that a family of quantum circuits $\{C_x: x\in \calL\}$ is $t(n)$-time-bounded if there is a deterministic Turing machine that, on any input $x \in \calL$, runs in time $O(t(|x|))$, and outputs a description of $C_x$ such that $C_x$ accepts (resp., rejects) if $x \in \calL_{\yes}$ (resp., $x \in \calL_{\no}$).
Similarly, we say that a family of quantum circuits $\{C_x: x\in \calL\}$ is $s(n)$-space-bounded if there is a deterministic Turing machine that, on any input $x \in \calL$, runs in space $O(s(|x|))$ (and hence time $2^{O(s(|x|))}$), and outputs a description of $C_x$ such that $C_x$ accepts (resp., rejects) if $x \in \calL_{\yes}$ (resp., $x \in \calL_{\no}$), as well as $C_x$ is acting on $O(s(|x|))$ qubits and has $2^{O(s(|x|)}$ gates..

Let $s\colon\bbN \rightarrow \bbN$ be a space-constructible function such that $s(n)\! \geq\! \Omega(\log{n})$. Let $a(n)$ and $b(n)$ be functions that are computable in deterministic space $s(n)$.
A promise problem $(\calL_{\yes},\calL_{\no})$ is in $\BQUSPACE[s(n),a(n),b(n)]$ if there exists a family of $s(n)$-space-bounded  (unitary) quantum circuits $\{C_x\}_{x\in\calL}$, where $n=|x|$, satisfying the following:

* The output qubit is measured in the computational basis after applying $C_x$. We say that $C_x$ accepts $x$ if the measurement outcome is $1$, whereas $C_x$ rejects $x$ if the outcome is $0$.

* $\Pr{C_x \text{ accepts } x} \geq a(|x|)$ if $x \in \calL_{\yes}$, whereas $\Pr{C_x \text{ accepts } x} \leq b(|x|)$ if $x \in \calL_{no}$.

We remark that <Ref> is gateset-independent, given that the gateset is closed under adjoint and all entries in chosen gates have reasonable precision. This property is due to the space-efficient Solovay-Kitaev theorem presented in [91].
Moreover, we can achieve error reduction for $\BQUSPACE[s(n),a(n),b(n)]$ as long as $a(n)-b(n) \geq 2^{-O(s(n))}$, which follows from [31] or our space-efficient QSVT-based construction in <Ref>.
We thereby define $\BQUSPACE[s(n)]:=\BQUSPACE[s(n),2/3,1/3]$ to represent (two-sided) bounded-error unitary quantum space, and $\BQUL:=\BQUSPACE[O(\log{n})]$ to denote unitary quantum logspace.

We next consider general space-bounded quantum computation, which allows intermediate quantum measurements. As indicated in <cit.>, for any quantum channel $\Phi$ mapping from density matrices on $k_1$ qubits to density matrices on $k_2$ qubits, we can exactly simulate this quantum channel $\Phi$ by a unitary quantum circuit acting on $2k_1+k_2$ qubits. Therefore, we extend <Ref> to general quantum circuits, which allows local operations, such as intermediate measurements in the computational basis, resetting qubits to their initial states, and tracing out qubits.
Now we proceed with a definition on $\BQSPACE[s(n)]$.

Let $s\colon\bbN \rightarrow \bbN$ be a space-constructible function such that $s(n) \geq \Omega(\log{n})$. Let $a(n)$ and $b(n)$ be functions that are computable in deterministic space $s(n)$.
A promise problem $(\calL_{\yes},\calL_{\no})$ is in $\BQSPACE[s(n),a(n),b(n)]$ if there exists a family of $s(n)$-space-bounded general quantum circuits $\{\Phi_x\}_{x\in\calL}$, where $n=|x|$, satisfying the following holds:

* The output qubit is measured in the computational basis after applying $\Phi_x$. We say that $\Phi_x$ accepts $x$ if the measurement outcome is $1$, whereas $\Phi_x$ rejects $x$ if the outcome is $0$.

* $\Pr{\Phi_x \text{ accepts } x} \geq a(|x|)$ if $x \in \calL_{\yes}$, whereas $\Pr{\Phi_x \text{ accepts } x} \leq b(|x|)$ if $x \in \calL_{no}$.

It is noteworthy that unitary quantum circuits, which correspond to unitary channels, are a specific instance of general quantum circuits that correspond to quantum channels. we thus infer that $\BQUSPACE[s(n)] \subseteq \BQSPACE[s(n)]$ for any $s(n) \geq \Omega(\log{n})$. However, the opposite direction was a long-standing open problem.
Recently, Fefferman and Remscrim [36] demonstrated a remarkable result that $\BQSPACE[s(n)] \subseteq \BQUSPACE[O(s(n))]$.
In addition, it is evident that $\BQSPACE[s(n)]$ can achieve error reduction since it admits sequential repetition simply by resetting working qubits. Therefore, we define $\BQSPACE[s(n)]:=\BQSPACE[s(n),2/3,1/3]$ to represent (two-sided) bounded-error general quantum space, and denote general quantum logspace by $\BQL:=\BQSPACE[O(\log{n})]$.

We now turn our attention to one-sided bounded-error unitary quantum space $\RQUSPACE[s(n)]$ and $\coRQUSPACE[s(n)]$ for $s(n) \geq \Omega(\log{n})$. These complexity classes were first introduced by Watrous [93] and have been further discussed in [36]. We proceed with the definitions:

* $\RQUSPACE[s(n),a(n)]:=\BQUSPACE[s(n),a(n),0]$;

* $\coRQUSPACE[s(n),b(n)]:=\BQUSPACE[s(n),1,b(n)]$.

Note that $\RQUSPACE[s(n),a(n)]$ and $\coRQUSPACE[s(n),b(n)]$ can achieve error reduction, as shown in [93] or our space-efficient QSVT-based construction in <Ref>. We define

\[\RQUSPACE[s(n)]:=\BQUSPACE\big[s(n),\tfrac{1}{2},0\big] \text{ and } \coRQUSPACE[s(n)]:=\BQUSPACE\big[s(n),1,\tfrac{1}{2}\big]\]

to represent one-sided bounded-error unitary quantum space, as well as logspace counterparts

\[\RQUL:=\RQUSPACE[O(\log{n})] \text{ and } \coRQUL:=\coRQUSPACE[O(\log{n})].\]

We observe that changing the gateset in space-efficient Solovay-Kitaev theorem [91] can cause errors, revealing the gateset-dependence of unitary quantum space classes with one-sided bounded-error. To address this issue, we adopt a larger gateset $\mathcal{G}$ for $\RQUSPACE[s(n)]$ and $\coRQUSPACE[s(n)]$, which includes any single-qubit gates whose amplitudes can be computed in deterministic $O(s(n))$ space.

§.§ Near-minimax approximation by Chebyshev interpolation

We will define Chebyshev polynomials and introduce Chebyshev interpolation, which is notable for providing near-minimax approximations. These concepts are essential to our space-efficient quantum singular value transformation techniques (<Ref>).

The Chebyshev polynomials (of the first kind) $T_k(x)$ are defined via the following recurrence relation: $T_0(x):=1$, $T_1(x):=x$, and $T_{k+1}(x):=2x T_k(x)-T_{k-1}(x)$. For $x \in [-1,1]$, an equivalent definition is $T_k(\cos \theta) = \cos(k \theta)$.

In order to use Chebyshev polynomials for interpolation, we first need to define an inner product between two functions, $f$ and $g$, as long as the following integral exists:

\[\innerprodF{f}{g} := \frac{2}{\pi} \int_{-1}^1 \frac{f(x)g(x)}{\sqrt{1-x^2}} \dx = \frac{2}{\pi} \int_{-\pi}^0 f(\cos\theta)g(\cos\theta) \dtheta.\]

The Chebyshev polynomials form an orthonormal basis in this inner product space induced by $\innerprodF{\cdot}{\cdot}$.
As a result, any degree-$d$ polynomial $P_d$ can be represented as a linear combination of Chebyshev polynomials using a technique called Chebyshev interpolation, see <cit.> for the details. In particular, $P_d=\frac{1}{2}\innerprodF{T_0}{P_d}+\sum_{k=1}^d \innerprodF{T_k}{P_d} T_k$. It is noteworthy that <Ref> is first proven in [80].

For any continuous function $f\colon[-1,1]\rightarrow \bbR$, if there exists an explicit degree-$d$ polynomial $\hat{P}_d\in\bbR[x]$ such that $\max_{x\in[-1,1]} |f(x)-\hat{P}_d(x)| \leq \epsilon$, then we know that
$P_d=\frac{1}{2} \innerprodF{T_0}{f}+\sum_{k=1}^d \innerprodF{T_k}{f} T_k$ satisfies $\max_{x\in[-1,1]} |f(x)-P_d(x)| \leq O(\epsilon \log d)$.

§.§ Tools for space-bounded randomized and quantum algorithms

Our convention assumes that for any algorithm $\calA$ in bounded-error randomized time $t(n)$ and space $s(n)$, $\calA$ outputs the correct value with probability at least $2/3$  (viewed as “success probability”).
We first proceed with space-efficient success probability estimation.

Let $\calA$ be a randomized (resp., quantum) algorithm that outputs the correct value with probability $p$, has time complexity $t(n)$, and space complexity $s(n)$. We can obtain an additive-error estimation $\hat{p}$ such that $|p - \hat{p}| \leq \epsilon$, where $\epsilon \geq 2^{-O(s(n))}$. Moreover, this estimation can be computed in bounded-error randomized (resp., quantum) time $O(\epsilon^{-2} t(n))$ and space $O(s(n))$.

Consider a $m$-time sequential repetition of the algorithm $\calA$, 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 $\bbE[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 $\calA$ in the $i$-th repetition. By the Chernoff-Hoeffding bound (e.g., Theorem 4.12 in [74]), we know that $\Pr{|\hat{X}-p|\geq \epsilon} \leq 2\exp(-2m\epsilon^2)$. By choosing $m=2\epsilon^{-2}$, this choice of $m$ ensures that each run of $\calA$ succeeds with probability at least $2/3$.

Furthermore, the space complexity of our algorithm is $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.

Notably, when applying <Ref> to a quantum algorithm, we introduce intermediate measurements to retain space complexity through reusing working qubits. While space-efficient success probability estimation without intermediate measurements is possible,[Fefferman and Lin [34] noticed that one can achieve space-efficient success probability estimation for quantum algorithms without intermediate measurements via quantum amplitude estimation [16]. ] we will use <Ref> for convenience, given that $\BQL=\BQUL$ [36].

The SWAP test was originally proposed for pure states in [13]. Subsequently, in [63], it was demonstrated that the SWAP test can also be applied to mixed states.

Suppose $\rho_0$ and $\rho_1$ are two $n$-qubit mixed quantum states.
There is a $(2n+1)$-qubit quantum circuit that outputs $0$ with probability $\frac{1+\Tr(\rho_0\rho_1)}{2}$, using $1$ sample of each $\rho_0$ and $\rho_1$ and $O(n)$ one- and two-qubit quantum gates.

A matrix $B$ is said to be sub-stochastic if all its entries are non-negative and the sum of entries in each row (respectively, column) is strictly less than $1$. Moreover, a matrix $B$ is row-stochastic if all its entries are non-negative and the sum of entries in each row is equal to $1$.

Let $B$ be an $l \times l$ sub-stochastic matrix, where each entry of $B$ requires at most $\ell$-bit precision. Then, there exists an explicit randomized algorithm that computes the matrix power $B^k[s,t]$ in $\log(l+1)$ space and $O(\ell k)$ time. Specifically, the algorithm accepts with probability $B^k[s,t]$.

Our randomized algorithm leverages the equivalence between space-bounded randomized computation and Markov chains, see <cit.> 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] := \begin{cases}
B[i,j], & \text{ if } 1 \leq i,j \leq l;\\
1-\sum_{j=1}^{l+1-i} b^{(1)}_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 $\log(l)$ 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.

§ SPACE-EFFICIENT QUANTUM SINGULAR VALUE TRANSFORMATIONS

We begin by defining the projected unitary encoding and its special forms, viz. the bitstring indexed encoding and the block-encoding, as well as notations on singular value decomposition and singular value transformation.

Let $U$ be an $(\alpha, a, \epsilon)$-projected unitary encoding of a linear operator $A$ if $\|A- \alpha \tilde{\Pi} U \Pi\| \leq \epsilon$, where $U$ and orthogonal projectors $\tilde{\Pi}$ and $\Pi$ act on $s+a$ qubits, and both $\rank(\tilde{\Pi})$ and $\rank(\Pi)$ are at least $2^a$ ($a$ is viewed as the number of ancillary qubits).
Furthermore, we are interested in two special forms of the projected unitary encoding:

* Bitstring indexed encoding. We say that a projected unitary encoding is a bitstring indexed encoding if both orthogonal projectors $\tilde{\Pi}$ and $\Pi$ span on $\tilde{S},S \subseteq \{\ket{0},\ket{1}\}^{\otimes(a+s)}$, respectively.[Typically, to ensure these orthogonal projectors coincide with space-bounded quantum computation, we additionally require the corresponding subsets $\tilde{S}$ and $S$ admit space-efficient set membership, namely deciding the membership of these subsets is in deterministic $O(s+a)$ space.]
In particular, for any $\ket{\tilde{s_i}} \in \tilde{S}$ and $\ket{s_j} \in S$, we have a matrix representation $A_{\tilde{S},S}(i,j) := \bra{\tilde{s}_i} U \ket{s_j}$ of $A$.

* Block-encoding. We say that a projected unitary encoding is a block-encoding if both orthogonal projectors are of the form $\Pi=\tilde{\Pi}=\ket{0}\bra{0}^{\otimes a}\otimes I_s$. We use the shorthand $A=(\bra{\bar{0}}\otimes I_s) U (\ket{\bar{0}}\otimes I_s)$ for convenience.

Given a projected unitary encoding of $A$, denoted by $U$, associated with orthogonal projectors $\Pi$ and $\tilde{\Pi}$ on a finite-dimensional Hilbert space $\calH_U$.
Namely, $A=\tilde{\Pi} U \Pi$. Then there exists orthonormal bases of $\Pi$ and $\tilde{\Pi}$ such that $\Pi$: $\left\{ \ket{\psi_{i}}: i \in [d] \right\}$, where $d:=\rank(\Pi)$, of a subspace $\Img(\Pi)=\span\left\{\ket{\psi_i}\right\}$;
$\tilde{\Pi}$: $\big\{ \ket{\tilde{\psi}_i}: i\in[\tilde{d}] \big\}$, where $\tilde{d}:=\rank(\tilde{\Pi})$, of a subspace $\Img(\tilde{\Pi})=\span\big\{\ket{\tilde{\psi}_i}\big\}$.
These bases ensure that the singular value decomposition $\tilde{\Pi} U \Pi = \sum_{i=1}^{\min\{d,\tilde{d}\}} \sigma_i \ket{\tilde{\psi}_i}\bra{\psi_i}$ where singular values $\sigma_i > \sigma_j$ for any $i < j \in [\min\{d,\tilde{d}\}]$.

Let $f\colon \bbR \rightarrow \bbC$ be an even or odd function. We consider a linear operator $A\in \bbC^{\tilde{d}\times d}$ satisfying the singular value decomposition $A = \sum_{i=1}^{\min\{d,\tilde{d}\}} \sigma_i \ket{\tpsi_i}\bra{\tpsi_i}$. We define the singular value transformation corresponding to $f$ as follows:

\[f^{\SV}(A) := \begin{cases}
\sum_{i=1}^{\min\{d,\tilde{d}\}} f(\sigma_i) \ket{\tpsi_i}\bra{\psi_i},&\text{for odd }f,\\
\sum_{i=1}^d f(\sigma_i) \ket{\psi_i}\bra{\psi_i},&\text{for even }f.
\end{cases}\]

Here, for $i \in \{\min\{d,\tilde{d}\}+1,\cdots,d-1,d\}$, we define $\sigma_i:=0$.

It is worth noting that $f^{\SV}(A)=f(A)$ when $A$ is an Hermitian matrix.

With these definitions in place, we present the main (informal) theorem in this section:

Let $f\colon\bbR \rightarrow \bbR$ be a continuous function bounded on the closed interval of interest $\calI \subseteq [-1,1]$. If there exists a degree-$d$ polynomial $\hat{P}_d$ that approximates $h\colon[-1,1] \rightarrow \bbR$, where $h$ approximates $f$ only on $\calI$, such that $\max_{x \in [-1,1]} |h(x)-\hat{P}_d(x)| \leq \epsilon$, then Chebyshev interpolation yields another degree-$d$ polynomial $P_d$ satisfying the following conditions: $\max_{x \in \calI} |f(x)-P_d(x)| \leq O(\epsilon \log{d})$ and $\max_{x \in [-1,1]} |P_d(x)| \leq 1$.

Moreover, we have space-efficient classical algorithms for computing any entry in the coefficient vector $\bfc$ of the Chebyshev interpolation polynomial $P_d$:

* If $f$ is a bounded function,[This conclusion also applies to a linear combination of bounded functions, provided that the coefficients are bounded and can be computed deterministically and space-efficiently.] then any entry in the coefficient vector $\bfc$ can be computed in deterministic $O(\log{d})$ space;

* If $f$ is a piecewise-smooth function, then any entry in the coefficient vector $\bfc$ can be computed in bounded-error randomized $O(\log{d})$ space.

Furthermore, for any $(1,a,0)$-bitstring indexed encoding $U$ of $A=\tilde{\Pi} U \Pi$, acting on $s+a$ qubits where $a(n) \leq s(n)$, and any $P_d$ with $d\leq 2^{O(s(n))}$, we can implement the quantum singular value transformation $P_d^{\SV}(A)$ that acts on $O(s(n))$ qubits by using $O(d^2\|\bfc\|_1)$ queries to $U$.

We remark that we can apply <Ref> to general forms of the projected unitary encoding $U$ with orthogonal projectors $\Pi$ and $\tilde{\Pi}$, as long as such an encoding meets the conditions: (1) The basis of $\Pi$ and $\tilde{\Pi}$ admits a well-defined order; (2) Both controlled-$\Pi$ and controlled-$\tilde{\Pi}$ admit computationally efficient implementation. We note that bitstring indexed encoding defined in <Ref> trivially meets the first condition, and a sufficient condition for the second condition is that the corresponding subsets $S$ and $\tilde{S}$ have space-efficient set membership.

Specifically, we elaborate on three main technical contributions that culminate in our space-efficient quantum singular value transformations (<Ref>):

* We provide deterministic space-efficient polynomial approximations for bounded functions (<Ref>), including the sign function (<Ref>). Our approach leads to a simple proof of space-efficient error reduction for unitary quantum computations (<Ref>).

* We present bounded-error randomized space-efficient polynomial approximations for piecewise-smooth functions (<Ref>), such as the normalized logarithmic function (<Ref>).

* We propose QSVT implementations using Chebyshev interpolation polynomials (<Ref>), including those for the sign function (<Ref>) and the normalized logarithmic function (<Ref>).

§.§ Space-efficient bounded polynomial approximations

We provide a systematic approach for constructing space-efficient polynomial approximations of real-valued piecewise-smooth functions, which is a space-efficient counterpart of Corollary 23 in [50]. It is worth mentioning that our algorithm (<Ref>) is deterministic for continuous functions that are bounded on the interval $[-1,1]$. However, for general piecewise-smooth functions, we only introduce a randomized algorithm (<Ref>). In addition, please refer to <Ref> as a brief introduction to Chebyshev polynomials and Chebyshev interpolation.

§.§.§ Bounded functions

We propose a space-efficient algorithm for computing the coefficients of a polynomial approximation with high accuracy for bounded functions. Our approach uses Chebyshev interpolation and numerical integration, building upon the methodology outlined in Lemma 2.10 of [77] with meticulous analysis.

Consider a continuous function $f$, and let $\hat{P}^{(f)}_d$ be a degree-$d$ polynomial with the same parity as $f$, such that $\max_{x\in[-1,1]} \!|f(x)-\hat{P}^{(f)}_d \!(x)| \leq \epsilon$, where $f$ is bounded with $\max_{x\in[-1,1]} |f(x)| \leq B$. By using Chebyshev interpolation, we can obtain another degree-$d$ polynomial $P^{(f)}_d$ that has the same parity as $\hat{P}^{(f)}_d$ and satisfies $\max_{x\in[-1,1]} |f(x)-P^{(f)}_d(x)| \leq O(\epsilon \log {d})$. This polynomial $P^{(f)}_d$ is defined as a linear combination of Chebyshev polynomials $T_k(\cos \theta) = \cos(k \theta)$:

\[P^{(f)}_d(x)=\frac{c_0}{2}+\sum_{k=1}^d c_k T_k(x) \text{ where } c_k := \frac{2}{\pi} \int_{-\pi}^0 F_k(\theta) \dtheta \text{ and } F_k(\theta):=\cos(k\theta)f(\cos{\theta}).\]

If the integrand $F_k(\theta)$ satisfies $\max_{\xi\in [-\pi,0]} |F_k''(\xi)| \leq O(d^\gamma)$ for some constant $\gamma$, then any entry of the coefficient vector $\bfc=(c_0,\cdots,c_d)$ can be computed in deterministic time $O(d^{(\gamma+1)/2}\epsilon^{-1/2} t(\ell))$ and space $O(\log(d^{\gamma+1} \epsilon^{-1}B))$, where evaluating $F(\theta)$ in $\ell$-bit precision is in deterministic time $t(\ell)$ and space $O(\ell)$ for $\ell=O(\log(d^{(\gamma+1)/2}\epsilon^{-3/2}))$.
Furthermore, the coefficient vector $\bfc$ has a norm bounded by $\|\bfc\|_1 \leq O(Bd)$.

To apply Chebyshev interpolation to a bounded continuous function $f(x)$, we begin with a degree-$d$ polynomial $\hat{P}^{(f)}_d$ such that $\max_{x\in[-1,1]} |f(x)-\hat{P}^{(f)}_d(x)| \leq \epsilon$. By utilizing <Ref>, we can construct a degree-$d$ Chebyshev interpolation of $f(x)$ denoted as $P^{(f)}_d$. This interpolation is expressed as $P^{(f)}_d = c_0/2 + \sum_{k=1}^d c_k T_k$, where $c_k = \frac{2}{\pi}\int_{-\pi}^{0} F_k(\theta) \dtheta$ and $F_k(\theta):=\cos(k \theta) f(\cos{\theta})$, and additionally satisfies the error bound: $\max_{x \in [-1,1]} \left|f(x) - P^{(f)}_d(x)\right| \leq O(\epsilon \log d)$.

*Computing the coefficients.
It is left to compute the coefficients $c_k$ for $0 \leq k \leq d$. We can estimate the numerical integration using the composite trapezium rule, as described in <cit.>.
The application of this method yields the following result:

\begin{equation}
\label{eq:integration-summations}
\int_{-\pi}^{0} \!F_k(x) \dx
\approx \frac{\pi}{m} \Big( \frac{F_k(x_0)}{2} + \sum_{l=1}^m F_k(x_l) + \frac{F_k(x_m)}{2}  \Big)
\text{ where } x_l:=-\pi+\frac{\pi l}{m} \text{ for } l=0,1,\cdots,m.
\end{equation}

Moreover, we know the upper bound on the numerical errors for computing the coefficient $c_k$:

\begin{equation}
\label{eq:integration-errors}
\varepsilon_{d,k}^{(f)}:=\sum_{l=1}^m \Big| \int_{x_{i-1}}^{x_i} F_k(x)\dx - \frac{\pi}{2m} \cdot \left( F_k(x_{i-1}) + F_k(x_i) \right) \Big| \leq \frac{\pi^3}{12m^2} \max_{\xi\in[-\pi,\pi]}\left|F_k''(\xi)\right|.
\end{equation}

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=1}^d \varepsilon^{(f)}_{d,k} \leq \epsilon$.
Plugging the assumption $|F_k''(x)| \leq O(d^{\gamma})$ into <Ref>, by choosing an appropriate value of $m=O(\epsilon^{-1/2}d^{(\gamma+1)/2})$, we establish that $\varepsilon^{(f)}_d \leq O(d^{\gamma+1}/m^2) \leq O(\epsilon)$. Moreover, to guarantee that the accumulated error is $O(\epsilon)$ in <Ref>, we need to evaluate the integrand $F(\theta)$ with $\ell$-bit precision, where $\ell=O(\log{(m/\epsilon)})=O(\log(\epsilon^{-3/2}d^{(\gamma+1)/2}))$.
In addition, note that $c_k=\frac{2}{\pi}\int_{-\pi}^{0} F_k(\theta) \dtheta \leq 2\cdot \max_{x\in[-1,1]} |f(x)| \leq 2B$, we know that the coefficient vector $\bfc$ satisfies $\|\bfc\|_1 = \sum_{k=0}^d |c_i| \leq O(Bd)$.

*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

\[\max\!\big\{O(\log{m}),O\big(\log\tfrac{m}{\epsilon}\big),\log\|\bfc\|_{\infty}\big\}
\leq O\big(\!\max\!\big\{ \!\log\!\big(\epsilon^{-\frac{3}{2}}d^{-\frac{\gamma+1}{2}}\big),\log B \big\} \big)
\leq O\big(\log\!\big(\epsilon^{-\frac{3}{2}}d^{-\frac{\gamma+1}{2}}B\big)\big).\]

Here, $\|\bfc\|_{\infty} = \max\limits_{0 \leq k \leq d} \frac{2}{\pi} |\int_{-\pi}^0 \cos(k\theta) f(\cos{\theta}) \dtheta| \leq \max\limits_{0 \leq k \leq d} \max\limits_{-\pi \leq \theta \leq 0} O(|f(\cos\theta)|) \leq O(B)$, and the last inequality is due to the fact that $\Theta(\max\{\log A, \log B\}) = \Theta(\log(AB))$ for any $A,B > 0$.

It is worth noting that evaluating a large family of functions, called holonomic functions, with $\ell$-bit precision requires only deterministic $O(\ell)$ space:

Holonomic functions encompass several commonly used functions,[For a more detailed introduction, please refer to <cit.>.] such as polynomials, rational functions, sine and cosine functions (but not other trigonometric functions such as tangent or secant), exponential functions, logarithms (to any base), the Gaussian error function, and the normalized binomial coefficients. In [25, 69], these works have demonstrated that evaluating a holonomic function with $\ell$-bit precision is achievable in deterministic time $\tilde{O}(\ell)$ and space $O(\ell)$. Prior works achieved the same time complexity, but with a space complexity of $O(\ell\log{\ell})$.

We now present an example of bounded functions, specifically the sign function.

For any $\delta,\epsilon>0$, there is an explicit odd polynomial $P_d^{\sign}:=\tfrac{c_0}{2}+\sum_{k=1}^d c_k T_k \in \bbR[x]$ of degree $d\leq\tilde C_{\sign
}\delta^{-1}\log{\epsilon^{-1}}$, where $\tilde C_{\sign}$ is a universal constant.
Any entry of the coefficient vector $\bfc:=(c_0,\cdots,c_d)$ can be computed in deterministic time $\tilde{O}\big(\epsilon^{-1/2} d^{2}\big)$ and space $O(\log(\epsilon^{-1}d^4))$. Furthermore, the polynomial $P_d^{\sign}$ satisfies the following conditions:

\[\begin{aligned}
\forall x \in [-1,1] \setminus [-\delta,\delta],& \left|\sign(x)-P^{\sign}_d\!(x)\right| \leq C_{\sign} \epsilon\log{d}, \text{ where } C_{\sign} \text{ is a universal constant,}\\
\forall x \in [-1,1],& \left|P_d^{\sign}\!(x)\right| \leq 1.
\end{aligned}\]

Additionally, the coefficient vector $\bfc$ has a norm bounded by $\|\bfc\|_1 \leq \hat{C}_{\sign} \log d$, where $\hat{C}_{\sign}$ is another universal constant.
Without loss of generality. we assume that all constants $C_{\sign}$, $\hat{C}_{\sign}$, and $\tilde{C}_{\sign}$ are at least $1$.

We start from a degree-$d$ polynomial $\hat{P}_d^\sign$ that well-approximates $\sign(x)$.

For any $\delta > 0$, $x\in \bbR$, $\epsilon\in (0,\sqrt{2e\pi})$. Let $\kappa = \frac{2}{\delta}\log^{1/2}\left(\frac{\sqrt{2}}{\sqrt{\pi}\epsilon}\right)$, Then

\[g_{\delta,\epsilon}(x):=\erf(\kappa x) \text{ satisfies that } |g_{\delta,\epsilon}(x)| \leq 1 \text{ and } \max_{|x|\geq \delta/2} \left| g_{\delta,\epsilon}(x) - \sign(x) \right| \leq \epsilon.\]

Moreover, there is an explicit odd polynomial $\hat{P}_d^{\sign}\in\bbR[x]$ of degree $d=O(\sqrt{(\kappa^2+\log{\epsilon^{-1}})\log{\epsilon^{-1}}})$ such that $\max_{x\in[-1,1]} \left| \hat{P}_d^{\sign}(x)-\erf(\kappa x) \right| \leq \epsilon$

By applying <Ref>, we obtain a polynomial $\hat{P}^\sign_d$ that well approximates the function $\erf(\kappa x)$ where $\kappa=O(\delta^{-1}\sqrt{\log{\epsilon^{-1}}})$.
Consequently, this polynomial $\hat{P}^\sign_d$ has a degree of $d \leq \tilde{C}_{\sign} \delta^{-1}\log{\epsilon^{-1}}$, where $\tilde{C}_{\sign}$ is a universal constant.
Note that the Gaussian error function is bounded, namely $|\erf(\kappa x)| \leq 1$ for any $x$.
To utilize <Ref>, it suffices to upper bound $\max_{\xi \in [-\pi,0]}|F_k''(\xi)|$ for any $0 \leq k \leq d$, as specified in <Ref> and the proof is deferred to <Ref>.

Let $F_k(\theta):=\erf(\kappa \cos{\theta}) \cos(k\theta)$, $\max\limits_{0 \leq k \leq d}\max\limits_{\xi \in [-\pi,0]}|F_k''(\xi)| \leq \frac{2}{\sqrt{\pi}} \kappa + k^2 + \frac{4}{\sqrt{\pi}} \kappa^3 + \frac{4}{\sqrt{\pi}} k \kappa$.

Note that $\kappa \leq O(d)$ and $k \leq d$, <Ref> indicates that $\max_{\xi \in [-\pi,0]}|F_k''(\xi)| \leq O(d^3)$ for any $0 \leq k \leq d$. Hence, we result in an approximation polynomial $\tilde{P}_d^{\sign}$ by <Ref> satisfies that $\max_{x\in [-1,1]} |\erf(\kappa x)-\tilde{P}_d^{\sign}(x)| \leq O(\epsilon \log d)$, which additionally derives that

\[\max_{x\in[-1,1]} |\sign(x)-\tilde{P}^{\sign}_d(x)| \leq \epsilon + \max_{x\in[-1,1]} |\erf(\kappa x)-\tilde{P}^{\sign}_d(x)| \leq C_{\sign}\epsilon \log d.\]

Here, $C_{\sign}$ is a universal constant.
Moreover, we specify the bound of $\|\tilde{\bfc}^{\sign}\|_1$ in <Ref>, and the proof is  deferred to <Ref>:
[Implicit in <cit.>]factsignFuncCoefficientsBound

For the coefficient vector $\tilde{\bfc}^{\sign}$ corresponding to a degree-$d$ polynomial $\tilde{P}^{\sign}_d$, we have $\|\tilde{\bfc}^{\sign}\|_1 \leq \hat{C}_{\sign} \log d$ where $\hat{C}_{\sign}$ is a universal constant.

In addition, the coefficient vector $\tilde{\bfc}^{\sign}$ can be computed in deterministic space $O(\log(d\epsilon^{-1}))$. As the evaluation of the integrand $F(\theta)$ requires $\ell$-bit precision where $\ell=O(\log(\epsilon^{-3/2}d^{2}))$, together with <Ref>, $\tilde{\bfc}^{\sign}$ can be computed in deterministic time $\tilde{O}(\epsilon^{-1/2}d^{2})$.

Finally, we obtain that $|\tilde{P}_d^{\sign}(x)| \leq 1+\epsilon$ for any $x\in[-1,1]$ since $|\sign(x)|\leq 1$ for any $x$. We finish the proof by normalizing $\tilde{P}_d^{\sign}$, in particular, considering $P_d^{\sign}(x) := (1+\epsilon)^{-1} \tilde{P}_d^{\sign}$. It is evident to verify that $P_d^{\sign}$ is an odd polynomial that satisfies all desired requirements.

§.§.§ Piecewise-smooth functions

We present a randomized algorithm for constructing bounded polynomial approximations of piecewise-smooth functions, which can be seen as a space-efficient alternative to Corollary 23 in [50], as described in <Ref>. Our algorithm leverages <Ref> and <Ref>.

Consider a real-valued function $f\colon[-x_0-r-\delta, x_0+r+\delta] \rightarrow \bbR$ such that $f(x_0+x)=\sum_{l=0}^{\infty} a_l x^l$ for all $x \in [-r-\delta, r+\delta]$, where $x_0 \in [-1,1]$, $r\in(0,2]$, $\delta \in (0,r]$. Assume that $\sum_{l=0}^{\infty} (r+\delta)^l |a_l| \leq B$ where $B > 0$. Let $\epsilon \in (0,\frac{1}{2B}]$ such that $B > \epsilon$, then there is a polynomial $P\in\bbR[x]$ of degree $O(\delta^{-1} \log(\epsilon^{-1} B))$, such that any entry of the coefficient vector $\bfc^{(P)}$ can be computed in bounded-error randomized time $\tilde{O}(\max\{ (\delta')^{-5} \epsilon^{-2} B^2, d^2\epsilon^{-1/2} B \})$ and space $O(\log(d^4(\delta')^{-4}\epsilon^{-1}B))$ where $\delta':=\frac{\delta}{2(r+\delta)}$, such that

\[\begin{aligned}
\|f(x) - P(x)\|_{[x_0-r,x_0+r]} & \leq O(\epsilon \log{d}),\\
\|P(x)\|_{[-1,1]} & \leq O(\epsilon \log{d}) + \|f(x)\|_{[x_0-r-\delta/2,x_0+r+\delta/2]} \leq O(\epsilon \log{d}) + B,\\
\|P(x)\|_{[-1,1] \setminus [x_0-r-\delta/2, x_0+r+\delta/2]} & \leq O(\epsilon \log{d}).
\end{aligned}\]

Furthermore, the coefficient vector $\bfc^{(P)}$ of $P$ has a norm bounded by $\|\bfc^{(P)}\|_1 \leq O(Bd)$.

The main ingredient, and the primary challenge, for demonstrating <Ref> is to construct a low-weight approximation using Fourier series, as shown in Lemma 37 of [90], which requires computing the powers of sub-stochastic matrices in bounded space (<Ref>).

Let $0 < \delta,\epsilon < 1$ and $f\colon\bbR \rightarrow \bbR$ be a real-valued function such that $|f(x)-\sum_{k=0}^K a_k x^k| \leq \epsilon/4$ for all $x \in \calI_{\delta}$, the interval $\calI_{\delta}:=[-1+\delta,1-\delta]$ and $\|\bfa\|_1 \leq O(\max\{\epsilon^{-1},\delta^{-1}\})$. Then there is a coefficient vector $\bfc\in \bbC^{2M+1}$ such that

* For even functions, $\left| f(x) - \sum_{m=-M}^M c^{(\even)}_m \!\cos(\pi x m) \right| \leq \epsilon$ for any $x \in \calI_{\delta}$;

* For odd functions, $\left| f(x) - \sum_{m=-M}^M c^{(\odd)}_m \!\sin\!\left(\pi x \!\left(m\!+\!\frac{1}{2}\right) \right) \right| \leq \epsilon$ for any $x \in \calI_{\delta}$;

* Otherwise, $\Big| f(x) \!-\!\sum_{m=-M}^M \big(c^{(\even)}_m \!\cos(\pi x m) \!+\! c^{(\odd)}_m \!\sin\!\left(\pi x \!\left(m\!+\!\frac{1}{2}\right) \right)\big) \Big| \!\leq\! \epsilon$ for any $x \in \calI_{\delta}$.

Here $M:=\max\left(2\lceil \delta^{-1} \ln(4\|a\|_1\epsilon^{-1}) \rceil,0\right)$ and $\|\bfc\|_1 \leq \|\bfa\|_1$. Moreover, the coefficient vector $\bfc$ can be computed in bounded-error randomized time $\tilde{O}(\delta^{-5}\epsilon^{-2})$ and space $ O(\log(\delta^{-4}\epsilon^{-1}))$.

We begin by defining $\|f\|_{\infty}:=\sup\{|f(x)|: x \in [-1+\delta,1-\delta]\}$.
It is worth noting that the truncation error of $\sum_{k=0}^K a_k x^k$, as shown in <cit.>, 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 $\|\bfa\|_1 \geq \epsilon/2$.[This is because if $\|\bfa\|_1 < \epsilon/2$, then $\|f\|_{\infty} \leq \|f(x)-\sum_{k=0}^K a_k x^k\|_{\infty} + \|\sum_{k=0}^K a_k x^k \|_{\infty} \leq \epsilon/4+\|\bfa\|_1 < \epsilon$, implying that $M=0$ and $\bfc=0$.]

Construction of polynomial approximations.
Our construction involves three approximations, as described in Lemma 37 of [90]. We defer the detailed proofs of all three approximations to <Ref>.

The first approximation combines the assumed $\sum_{k=0}^K a_k x^k$ with $\arcsin(x)$'s Taylor series.
[First approximation]propositionfirstLowWeightApprox

Let $\hat{f}_1(x)\! := \!\sum_{k=0}^K a_k x^k$ such that $\|f-\hat{f}_1\|_{\infty} \leq \epsilon/4$. Then we know that $\hat{f}_1(x) = \sum_{k=0}^K a_k \sum_{l=0}^{\infty} b_l^{(k)} \sin^{l}\left(\frac{x \pi}{2}\right)$ where the coefficients $b_l^{(k)}$ satisfy that

\begin{equation}
\label{eq:logQSVT-recursive-formula}
b_l^{(k+1)}=\sum_{l'=0}^l b_{l'}^{(k)} b_{l-l'}^{(1)} \text{ where } b^{(1)}_l=\begin{cases}
0 & \text{ if } l \text{ is even,}\\
\binom{l-1}{ \frac{l-1}{2} } \frac{2^{-l+1}}{l}\cdot\frac{2}{\pi} & \text{ if } l \text{ is odd.}
\end{cases}
\end{equation}

Furthermore, the coefficients $\{b^{(k)}_l\}$  satisfies the following: (1) $\|\bfb^{(k)}\|_1=1$ for all $k\geq 1$; (2) $\bfb^{(k)}$ is entry-wise non-negative for all $k \geq 1$; (3) $b^{(k)}_l=0$ if $l$ and $k$ have different parities.

The second approximation truncates the series at $l=L$, and bounds the truncation error.
[Second approximation]propositionsecondLowWeightApprox

Let $\hat{f}_2(x):=\! \sum_{k=0}^K a_k \sum_{l=0}^L b_l^{(k)} \sin^l\!\left(\frac{x\pi}{2}\right)$ where $L:=\lceil \delta^{-2} \ln(4\|\bfa\|_1 \epsilon^{-1})\rceil$, then we have that $\|\hat{f}_1-\hat{f}_2\|_{\infty} \leq \epsilon/4$.

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 <Ref>.
[Third approximation]propositionthirdLowWeightApprox

Let $\hat{f}_3(x)$ be polynomial approximations of $f$ that depends on the parity of $f$ such that $\|\hat{f}_2\!-\!\hat{f}_3\| \!\leq\! \epsilon/2$ and $M\!=\!\lfloor \delta^{-1}\ln(4\|\bfa\|_1\epsilon^{-1}) \!\rfloor$, then we have

\[\begin{aligned}
\hat{f}_3^{(\even)}(x) &:= \textstyle\sum\limits_{k=0}^K a_k\! \sum\limits_{\hat{l}=0}^{L/2} (-1)^{\hat{l}} 2^{-2\hat{l}} b_{2\hat{l}}^{(k)} \!\! \sum\limits_{m'=\hat{l}-M}^{\hat{l}+M} \!\! (-1)^{m'} \tbinom{2\hat{l}}{m'} \cos(\pi x (m'-\hat{l})),\\
\hat{f}_3^{(\odd)}(x) &:= \textstyle\sum\limits_{k=0}^{K} a_k \!\!\!\!\sum\limits_{\hat{l}=0}^{(L-1)/2} \!\!\!(-1)^{\hat{l}+1} 2^{-2\hat{l}-1} b_{2\hat{l}+1}^{(k)} \!\!\!\!\!\sum\limits_{m'=\hat{l}+1-M}^{\hat{l}+1+M} \!\!\!\! (-1)^{m'} \tbinom{2\hat{l}+1}{m'} \sin\!\big(\pi x \big(m'-\hat{l}-\tfrac{1}{2}\big)\big).
\end{aligned}\]

Therefore, we have that $\hat{f}_3(x) := \hat{f}_3^{(\even)}(x)$ if $f$ is even, whereas $\hat{f}_3(x) := \hat{f}_3^{(\odd)}(x)$ if $f$ is odd. In addition, if $f$ is neither even or odd, then $\hat{f}_3(x):=\hat{f}^{(\even)}_3(x) + \hat{f}^{(\odd)}_3(x)$.

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:=m'-\hat{l}$ if $f$ is even and $m:=m'-\hat{l}-1$ if $f$ is odd. Moreover, the definition of $m$ depends on the parity of $l=2\hat{l}+1$[In particular, the summand in $\hat{f}_3(x)$ is $c_m^{(\even)} \cos(\pi x m) + c_m^{(\odd)} \sin\!\big(\pi x\big( m+\frac{1}{2}\big)\big)$ if $f$ is neither even nor odd. ] if $f$ is neither even nor odd. By applying this approach, we can derive the following:

\begin{equation}
\label{eq:low-weight-approx-rearranging-terms}
\begin{aligned}
&\hat{f}^{(\even)}_3(x) \!=\!\!\! \textstyle \sum\limits_{m=-M}^M \!\!\!\! c^{(\even)}_m \!\cos(\pi x m) \text{ where } c^{(\even)}_m\!:=\!(-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}^{(\odd)}_3(x) \!=\!\!\! \textstyle \sum\limits_{m=-M}^M \!\!\!\! c^{(\odd)}_m \!\sin\!\big(\pi x \big(m\!+\!\tfrac{1}{2}\big)\big) \text{ where } c^{(\odd)}_m\!:=\!(-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{aligned}
\end{equation}

We then notice that the rearrangement of terms in <Ref> can be directly applied to the definition of $\hat{f}_3(x)$ in <Ref>. As a consequence, we obtain the following bound on the accumulative error: $\|f\!-\!\hat{f}_3\|_{\infty} \leq \|f\!-\!\hat{f}_1\|_{\infty} + \|\hat{f}_1\!-\!\hat{f}_2\|_{\infty} + \|\hat{f}_2\!-\!\hat{f}_3\|_{\infty} \leq \epsilon$.
Additionally, we remark that $\|\bfc\|_1 \leq \|\bfa\|_1$, since $\|\bfb^{(k)}\|_1=1$ (see <Ref>) 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 <Ref>.

We now present a bounded-error randomized algorithm for estimating $b^{(k)}_l$. As $\bfb^{(1)}$ is entry-wise non-negative and $\sum_{i=1}^l b_i^{(1)} < \|\bfb^{(1)}\|_1=1$ following <Ref>, we can express the recursive formula in <Ref> as the matrix powering of a sub-stochastic matrix $B_1$:

\[
B_1^k := \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}
:= 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 <Ref>, 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 <Ref>. 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)$. Note 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 $\bfc$ 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})$.

Now we present the proof of <Ref>, which is a space-efficient and randomized algorithm for constructing bounded polynomial approximations of piecewise-smooth functions.

Our approach is based on Theorem 40 in [90] and Corollary 23 in [50]. Firstly, we obtain a Fourier approximation $\hat{f}(x)$ of the given function $f(x)$ by truncating it using <Ref>. 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 <Ref>.

Construction of a bounded function.
Let us begin by defining a linear transformation $L(x):=\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):=f(L^{-1}(y))$ and $b_l:=a_l(r+\delta)^l$, then it is evident that $g(y):=\sum_{l=0}^{\infty} b_ly^l$ for any $y\in[-1,1]$.

To construct a Fourier approximation by <Ref>, we need to bound the truncation error $\varepsilon_J^{(g)}$. We define $\delta':=\frac{\delta}{2(r+\delta)}$ and $J:=\lceil (\delta')^{-1} \log(12B\epsilon^{-1}) \rceil$. This ensures that the truncation error $\varepsilon_J^{(g)}:=\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)} = \Big|\sum_{j=J}^{\infty} b_jy^j\Big| \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} := \frac{\epsilon'}{4}. \]

Afterward, let $\hat{\bfb}:=(b_0,b_1,\cdots,b_{J-1})$, then we know that $\|\hat{\bfb}\|_1 \leq \|\bfb\|_1 \leq B$ by the assumption. Now we utilize <Ref> and obtain the Fourier approximation $\hat{g}(y)$:

\begin{equation}
\label{eq:smooth-funcs-Fourier-approxY}
\hat{g}(y) \!:=\! \begin{cases}
\sum_{m=-M}^M c_m^{(\even)} \cos(\pi ym), & \text{if } f \text{ is even}\\
\sum_{m=-M}^M c_m^{(\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^{(\even)} \!\cos(\pi ym) + c_m^{(\odd)} \!\sin\big(\pi y \big(m\!+\!\tfrac{1}{2}\big)\big)\Big), & \text{otherwise}
\end{cases}.
\end{equation}

By appropriately choosing $M=O\big( (\delta')^{-1}\!\log\big(\|\hat{\bfb}\|_1/\epsilon'\big)\big) = O\big( r \delta^{-1}\!\log\big(B/\epsilon\big) \big)$, we obtain that the vectors of coefficients $\bfc^{(\even)}$ and $\bfc^{(\odd)}$ satisfy $\|\bfc^{(\even)}\|_1 \leq \|\hat{\bfb}\|_1 \leq \|\bfb\|_1 \leq B$ and similarly $\|\bfc^{(\odd)}\|_1 \leq B$. Plugging $f(x)=g(L(x))$ into <Ref>, 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]$:

\begin{equation*}
\hat{f}(x) = \hat{g}\Big( \frac{x\!-\!x_0}{r\!+\!\delta} \Big) = \begin{cases}
\sum\limits_{m=-M}^M c_m^{(\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^{(\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^{(\even)} \!\!\cos\!\big(\pi m \big(\frac{x-x_0}{r+\delta}\big) \big) + c_m^{(\odd)} \sin\!\big(\pi \big(m+\tfrac{1}{2}\big) \big(\frac{x-x_0}{r+\delta}\big) \big), & \text{otherwise}
\end{cases}.
\end{equation*}

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}:=\epsilon/(3B)$ and $\tilde{\delta}:=\delta/4$. Moreover, $|R(x)|\leq 1$ for any $x \in [-1,1]$.
Similar to Lemma 29 in [50], $R(x)$ can be expressed as a linear combination of Gaussian error functions:

\begin{equation}
R(x)\!:=\! \tfrac{1}{2}\Big[ \erf\big( \kappa (x \! - \! x_0 \! + \! r \! + \! \delta') \big) \! - \! \erf \big( \kappa (x \! - \! x_0 \! - \! r \! - \! \delta') \big)\Big] \text{where } \kappa \!:=\! \tfrac{2}{\delta'} \! \log^{\frac{1}{2}} \! \tfrac{\sqrt{2}}{\sqrt{\pi} \epsilon'} \!=\! \tfrac{8}{\delta} \! \log^{\frac{1}{2}} \! \tfrac{\sqrt{18}B}{\sqrt{\pi}\epsilon}.
\end{equation}

Bounded polynomial approximation with Chebyshev interpolation.
We here present an algorithmic, space-efficient, randomized polynomial approximation method using Chebyshev interpolation to approximate the function $h(x):=\hat{f}(x) \cdot R(x)$. As suggested in <Ref>, we use an explicit polynomial approximation $\hat{P}(x)$ of the bounded function $h(x)$ of degree $d=O(\delta^{-1} \log(B\epsilon^{-1}))$ that satisfies the conditions specified in <Ref>.

Let $x_0\in [-1,1]$, $r\in(0,2]$, $\delta\in(0,r]$ and let $f\colon[-x_0-r-\delta, x_0+r+\delta] \rightarrow \bbR$ and be such that $f(x_0+x)\!:=\!\sum_{l=0}^{\infty} a_l x^l$ for all $x\in[-r\!-\!\delta,r\!+\!\delta]$. Suppose $B>0$ is such that $\sum_{l=0}^{\infty} (r+\delta)^l |a_l| \leq B$. Let $\epsilon \in \big(0,\!\frac{1}{2B}\big]$, there is a $\epsilon/3$-precise Fourier approximation $\tilde{f}(x)$ of $f(x)$ on the interval $[x_0\!-r\!+\!\delta/2, x_0\!+\!r\!+\!\delta/2]$, where $\hat{f}(x)\!:=\!\sum_{m=-M}^M\! \operatorname{Re}\!\Big[\tilde{c}_m e^{-\frac{\rmi \pi m}{2(r+\delta)} x_0} e^{\frac{\rmi \pi m}{2(r+\delta)} x}\Big]$ and $\|\tilde{\bfc}\|_1 \leq B$. We have a time-efficient polynomial $P^*\in\bbR[x]$ of degree $O(\delta^{-1}\log(B\epsilon^{-1}))$ s.t.

\begin{equation}\begin{aligned}
\label{eq:smooth-funcs-opt}
\|\hat{f}(x)R(x) - P^*(x)\|_{[x_0-r,x_0+r]} & \leq \epsilon,\\
\|P^*(x)\|_{[-1,1]} & \leq \epsilon + \|\hat{f}(x)R(x)\|_{[x_0-r-\delta/2,x_0+r+\delta/2]} \leq \epsilon + B,\\
\|P^*(x)\|_{[-1,1] \setminus [x_0-r-\delta/2, x_0+r+\delta/2]} & \leq \epsilon.
\end{aligned}\end{equation}

To utilize <Ref>, we need to bound the second derivative $\max_{\xi\in[-\pi,0]} |F_k''(\xi)|$, where the integrand $F_k(\cos\theta):=\cos(k\theta) h(\cos\theta)$ for any $0 \leq k \leq d$. We will calculate this upper bound directly in <Ref>, and the proof is deferred to <Ref>.

Consider the integrand $F_k(\theta) \!=\! \sum_{m=-M}^M \!\frac{c_m}{2} \big( H_{k,m}^{(+)} \!-\! H_{k,m}^{(-)} \big)$ for any function $f$ which is either even or odd. If $f$ is even, we have that $c_m=c_m^{(\even)}$ defined in <Ref>, and

\begin{equation}
\label{eq:smooth-funcs-derivative-even}
H_{k,m}^{(\pm)}(\theta) := \cos\!\Big( \pi m \Big( \frac{\cos{\theta} - x_0}{r+\delta} \Big) \Big) \cdot \cos(k\theta) \cdot \erf\!\Big(\kappa \Big( \cos{\theta} - x_0 \pm r \pm \frac{\delta}{4} \Big)\Big).
\end{equation}

Likewise, if $f$ is odd, we know that $c_m=c_m^{(\odd)}$ defined in <Ref>, and

\begin{equation}
\label{eq:smooth-funcs-derivative-odd}
H_{k,m}^{(\pm)}(\theta) := \sin\!\Big( \pi \Big(m+\frac{1}{2}\Big) \Big( \frac{\cos{\theta} - x_0}{r+\delta} \Big) \Big) \cdot \cos(k\theta) \cdot \erf\!\Big(\kappa \Big( \cos{\theta} - x_0 \pm r \pm \frac{\delta}{4} \Big)\Big).
\end{equation}

Moreover, the integrand is $F_k(\theta) \!=\! \sum_{m=-M}^M \!\Big(\frac{c^{(\even)}_m}{2} \big( \hat{H}_{k,m}^{(+)} \!-\! \hat{H}_{k,m}^{(-)} \big) + \frac{c^{(\odd)}_m}{2} \big( \tilde{H}_{k,m}^{(+)} \!-\! \tilde{H}_{k,m}^{(-)} \big)\Big)$ when $f$ is neither even nor odd, where $\hat{H}_{k,m}^{(\pm)}$ and $\tilde{H}_{k,m}^{(\pm)}$ follow from <Ref> and <Ref>, respectively.
Regardless of the parity of $f$, we have that the second derivative $F''_k(\theta) \leq O(Bd^3)$.

Together with <Ref>, we are ready to apply <Ref> to $h(x)=\hat{f}(x)R(x)$, resulting in a degree-$d$ polynomial $P(x)$. Since $P(x)$ is the minimax approximation of $P^*(x)$ by Chebyshev interpolation and satisfies <Ref>, we can define intervals $\calI_{\inter}:=[x_0-r,x_0+r]$ and $\calI_{\exter}:=[x_0-r-\delta/2, x_0+r+\delta/2]$ to obtain:

\begin{equation}
\label{eq:smooth-funcs-approxpoly-errors}
\begin{aligned}
\|f(x)-P(x)\|_{\calI_{\inter}} &\leq \|f(x)-h(x)\|_{\calI_{\inter}} + \|h(x)-P(x)\|_{\calI_{\inter}} \leq \epsilon + O(\epsilon \log d) = O(\epsilon \log d), \\
\|P(x)-0\|_{\calI_{\exter}} & \leq \|P(x)-h(x)\|_{\calI_{\exter}} + \|h(x)-0\|_{\calI_{\exter}} \leq O(\epsilon \log d) + O(\epsilon) \leq O(\epsilon \log d).
\end{aligned}
\end{equation}

We can achieve the desired error bound by observing that <Ref> implies $|P(x)|_{[-1,1]} \leq O(\epsilon \log d) + |P(x)|_{[-1,1] \setminus \calI_{\exter}} \leq O(\epsilon \log d) + B$. Moreover, we note that the norm of the coefficient vector $\bfc^{(P)}$ of the polynomial $P(x)$ is bounded by $|\bfc^{(P)}| \leq O(Bd) \cdot (1 + O(\epsilon \log{d})) = O(Bd)$, which follows directly from our utilization of <Ref>.

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 <Ref> 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 <Ref>. This construction can be implemented in deterministic time $\tilde{O}(d^2\epsilon^{-1/2}B)$ and space $O(\log(d^4\epsilon^{-1}B))$ since the integrand $F_k(\theta)$ is a product of a constant number of (compositions of) holonomic functions (<Ref>). 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} B \big\})$ and space $O(\log(d^4(\delta')^{-4}\epsilon^{-1}B))$.

With the aid of <Ref>, we can provide a space-efficient polynomial approximation to the normalized logarithmic function utilized in Lemma 11 of [41].

Let $\beta \in (0,1]$ and $\epsilon\in(0,1/2)$, there is an even polynomial $P$ of degree $d \leq \tilde C_{\ln} \beta^{-1} \log{\epsilon^{-1}}$ where $\tilde C_{\ln}$ is a universal constant such that

\[\begin{aligned}
\forall x \in [\beta,1],& \left| P(x) - \tfrac{\ln(1/x)}{2\ln(2/\beta)} \right| \leq C_{\ln} \epsilon \log{d}, \text{ where } C_{\ln} \text{ is a universal constant}, \\
\forall x \in [-1,1],& |P(x)| \leq 1.
\end{aligned}\]

Moreover, the coefficient vector $\bfc^{(P)}$ of $P$ has a norm bounded by $\|\bfc^{(P)}\|_1 \leq \hat{C}_{\ln} d$, where $\hat{C}_{\ln}$ is another universal constant. In addition, any entry of the coefficient vector $\bfc^{(P)}$ can be computed in bounded-error randomized time $\tilde{O}(\max\{\beta^{-5}\epsilon^{-2}, d^2\epsilon^{-1/2}\})$ and space $O(\log(d^4 \beta^{-4} \epsilon^{-1}))$.
Without loss of generality, we assume that all constants $C_{\ln}$, $\hat{C}_{\ln}$, and $\tilde{C}_{\ln}$ are at least $1$.

Consider the function $f(x):=\frac{\ln(1/x)}{2\ln(2/\beta)}$. We apply <Ref> to $f(x)$ by choosing the same parameters as in Lemma 11 of [41], specifically $\epsilon'=\epsilon/2$, $x_0=1$, $r=1-\beta$, $\delta=\beta/2$, and $B=1/2$.[As indicated in Lemma 11 of [41], since the Taylor series of $f(x)$ at $x=1$ is $\frac{1}{2\ln(2/\beta)} \sum_{l=1}^{\infty} \frac{(-1)^lx^l}{l}$, we obtain that $B=f\big(\frac{\beta}{2}-1\big)=\frac{1}{2\ln(2/\beta)} \sum_{l=1}^\infty \frac{(1-\beta/2)^l}{l} = -\frac{1}{2\ln(2/\beta)} \sum_{l=1}^{\infty} \frac{(-1)^{l-1}}{l} (\beta/2-1)^l = -\frac{1}{2\ln(2/\beta)}\ln\frac{\beta}{2} = \frac{1}{2}$.] This results in a space-efficient randomized polynomial approximation $\tilde{P}\in\bbR[x]$ of degree $d = O(\delta^{-1} \log(\epsilon^{-1} B)) \leq \tilde{C}_{\ln} \beta^{-1} \log{\epsilon^{-1}}$, where $\tilde{C}_{\ln}$ is a universal constant. By appropriately choosing $\eta \leq 1/2$ such that $C'_{\ln} \epsilon\log d = \eta/4$ for a universal constant $C'_{\ln}$, the approximation guarantees the following inequalities:

\begin{equation}
\label{eq:conditions-log}
\begin{aligned}
\|f(x)-\tilde{P}(x)\|_{[\beta,2-\beta]} & \leq C'_{\ln} \epsilon \log{d} = \tfrac{\eta}{4}\\
\|\tilde{P}(x)\|_{[-1,1]} &\leq B+C'_{\ln} \epsilon\log{d} \leq \tfrac{1}{2} + C'_{\ln} \epsilon\log{d} = \tfrac{1}{2}+\tfrac{\eta}{4}\\
\|\tilde{P}(x)\|_{[-1,\beta/2]} &\leq C'_{\ln} \epsilon \log {d} = \tfrac{\eta}{4}.
\end{aligned}
\end{equation}

Additionally, the coefficient vector $\bfc^{(\tilde{P})}$ of $\tilde{P}$ satisfies that $\|\bfc^{(\tilde{P})}\|_1 \leq O(Bd) \leq \hat{C}_{\ln} d$ where $\hat{C}_{\ln}$ is a universal constant.
Notice 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 <Ref> yields a bounded-error randomized algorithm that requires $O(\log(d^4 (\delta')^{-4} \epsilon^{-1} B)) = O(\log(d^4 \beta^{-4} \epsilon^{-1}))$ space and $\tilde{O}(\max\{(\delta')^{-5} \epsilon^{-2} B^2, d^2 \epsilon^{-1/2} B\}) = \tilde{O}(\max\{\beta^{-5}\epsilon^{-2}, d^2 \epsilon^{-1/2}\})$ time.

Furthermore, note that the real-valued function $f(x)$ only defines when $x>0$, then $\tilde{P}(x)$ is not an even polynomial in general. Instead, we consider $P(x):=(1+\eta)^{-1}(\tilde{P}(x)+\tilde{P}(-x))$ for all $x\in[-1,1]$.
Together with <Ref>, we have derived that:

\begin{equation}
\label{eq:log-polynomial-error}
\begin{aligned}
\|f(x)-P(x)\|_{[\beta,1]} &\leq \big\|f(x)-\tfrac{1}{1+\eta} \tilde{P}(x)\big\|_{[\beta,1]} + \big\|\tfrac{1}{1+\eta}\tilde{P}(-x)\big\|_{[\beta,1]}\\
&\leq \big\|f(x)- \tilde{P}(x)\big\|_{[\beta,1]} + \big\|\tilde{P}(x)-\tfrac{1}{1+\eta} \tilde{P}(x)\big\|_{[\beta,1]} + \big\|\tfrac{1}{1+\eta} \tilde{P}(-x)\big\|_{[\beta,1]}\\
%&\leq \tfrac{\eta}{2} + \tfrac{\eta}{1+\eta}\cdot \tfrac{1+\eta}{2} + \tfrac{1}{1+\eta}\cdot \tfrac{\eta}{2}\\
&\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}\\
&= \tfrac{\eta}{4} + \tfrac{\eta}{1+\eta} \cdot \tfrac{1+\eta}{4} + \tfrac{1}{1+\eta} \cdot \tfrac{\eta}{2}\\
&\leq \eta.\\
\end{aligned}
\end{equation}

Here, the last line owes to the fact that $\eta > 0$.
Consequently, <Ref> implies that $\|f(x)-P(x)\|_{[\beta,1]} \leq 4C'_{\ln} \epsilon \log{d} := C_{\ln} \epsilon \log{d}$ for another universal constant $C_{\ln}$.
Notice $P(x)$ is an even polynomial with $\deg(P) \leq \tilde{C}_{\ln} \beta^{-1} \log \epsilon^{-1}$, <Ref> yields that:

\[\begin{aligned}
\|P(x)\|_{[-1,1]} = \|P(x)\|_{[0,1]} \leq \|\tfrac{1}{1+\eta}\tilde{P}(x)\|_{[0,1]} + \|\tfrac{1}{1+\eta}\tilde{P}(x)\|_{[-1,0]}
\leq \tfrac{1}{1+\eta} \cdot \tfrac{1+\eta}{2} + \tfrac{1}{1+\eta} \cdot \tfrac{\eta}{2} \leq 1.
\end{aligned}\]

We now complete the proof by noticing $\eta \leq 1/2$.

§.§ Applying Chebyshev interpolation to bitstring indexed encodings

Equipped with space-efficient bounded polynomial approximations of piecewise-smooth functions, it suffices to implement Chebyshev interpolation on bitstring indexed encodings, as specified in <Ref>. The proof follows from combining <Ref> and <Ref>.

Let $A$ be an Hermitian matrix acting on $s$ qubits, and let $U$ be a $(1,a,\epsilon_1)$-bitstring indexed encoding of $A$ that acts on $s+a$ qubits. For any degree-$d$ polynomial $P_d(x)=\frac{c_0}{2}+\sum_{k=1}^d c_k T_k(x)$ where $d \leq 2^{O(s(n))}$ and $T_k$ is the $k$-th Chebyshev polynomial (of the first kind), equipped with an evaluation oracle $\Eval$ that returns $\hat{c}_k$ with precision $\varepsilon:=O(\epsilon_2^2/d)$, then we have a $(1,a',144d\sqrt{\epsilon_1}\|\bfc\|_1^2+36\epsilon_2\|\bfc\|_1)$-bitstring indexed encoding $V$ of $P_d(A)$ that acts on $s+a'$ qubits where $a':=a+\lceil \log{d} \rceil+3$.

This implementation requires $O(d^2\|\bfc\|_1)$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and $O(d^2\|\bfc\|_1)$ multi-controlled single-qubit gates.[As indicated in Figure 3(c) of [50] (see also Lemma 19 in [49]), we replace the single-qubit gates used in <Ref> with multi-controlled (or “multiply controlled”) single-qubit gates.] Moreover, we can compute the description of the resulting quantum circuit in deterministic time $\tilde{O}(d^2\|\bfc\|_1 \log(d/\epsilon_2))$ and space $O(\max\{s(n),\log(d/\epsilon_2^2)\})$footnote:tilde-O, also $O(d^2\|\bfc\|_1)$ oracle calls to $\Eval$ with precision $\varepsilon$.

Furthermore, our construction straightforwardly extends to any linear (possibly non-Hermitian) operator $A$ by simply replacing $P_d(A)$ with $P^{\SV}_d(A)$ defined in <Ref>.

As shown in <Ref>, we can implement the quantum singular value transformation $T_k(A)$ exactly for any Hermitian matrix that admits a bitstring indexed encoding, because we observe that the rotation angles corresponding to the $k$-th Chebyshev polynomials are either $\pi/2$ or $(1-k)\pi/2$, indicating that $T_k(0)=0$ for any odd $k$.
We then implement the QSVT corresponding to the Chebyshev interpolation polynomial $P_d(x) = \sum_{l=0}^{(d-1)/2} c_{2l+1} T_{2l+1}(x)$, as described in <Ref>, although the actual implementation results in a slightly different polynomial, $\hat{P}_d(x) = \sum_{l=0}^{(d-1)/2} \hat{c}_{2l+1} T_{2l+1}(x)$. However, we still have $\hat{P}_d(0)=0=P_d(0)$, indicating that the implementations in <Ref> preserve the parity.

We first demonstrate an approach, based on Lemma 3.12 in [77], that constructs Chebyshev polynomials of bitstring indexed encodings in a space-efficient manner.
[Chebyshev polynomials applied to bitstring indexed encodings]lemmaChebyshevPolynomialImplementation

Let $A$ be a linear operator acting on $s$ qubits, and let $U$ be a $(1,a,\epsilon)$-bitstring indexed encoding of $A$ that acts on $s+a$ qubits. Then, for the $k$-th Chebyshev polynomial (of the first kind) $T_k(x)$ of degree $k\leq 2^{O(s)}$, there exists a new $(1,a+1,4k\sqrt{\epsilon})$-bitstring indexed encoding $V$ of $T_k^{\SV}(A)$ that acts on $s+a+1$ qubits. This implementation requires $k$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and $k$ single-qubit gates.
Moreover, we can compute the description of the resulting quantum circuit in deterministic time $k$ and space $O(s)$.

Furthermore, consider $A':= \tilde{\Pi} U \Pi$, where $\tilde{\Pi}$ and $\Pi$ are the corresponding orthogonal projectors of the bitstring indexed encoding $U$. If $A$ and $A'$ satisfy the conditions $\|A-A'\| + \big\|\frac{A+A'}{2}\big\|^2 \leq 1$ and $\big\|\frac{A+A'}{2}\big\|^2 \leq \zeta$, then $V$ is a $\big(1,a+1,\frac{\sqrt{2}}{\sqrt{1-\zeta}}k\epsilon\big)$-bitstring indexed encoding of $T^{\SV}_k(A)$.

As specified in <Ref>, we first notice that we can derive the sequence of rotation angles corresponding to Chebyshev polynomials $T_k(x)$ by directly factorizing them.

Let $T_k \in \bbR[x]$ be the $k$-th Chebyshev polynomial (of the first kind). Consider the corresponding sequence of rotation angles  $\Phi\in\bbR^k$ such that $\phi_1:=(1-k)\pi/2$, and $\phi_j:=\pi/2$ for all $j\in[k] \setminus \{1\}$, then we know that $\prod_{j=1}^k \left[\begin{psmallmatrix} \exp(i\phi_j) & 0\\ 0 & \exp(-i\phi_j)\\ \end{psmallmatrix} \begin{psmallmatrix} x & \sqrt{1-x^2}\\ \sqrt{1-x^2} & -x\\ \end{psmallmatrix}\right] = \begin{psmallmatrix} T_k & \cdot\\ \cdot & \cdot \end{psmallmatrix}$.

Then we implement the quantum singular value transformation $T_k^{\SV}(A)$, utilizing an alternating phase modulation (<Ref>) with the aforementioned sequence of rotation angles, denoted by $V$.

Suppose $P\in\bbC[x]$ is a polynomial, and let $\Phi\in\bbR^n$ be the corresponding sequence of rotation angles. We can construct $P^{\rm (SV)}(\tilde{\Pi} U \Pi) = \begin{cases}
\tilde{\Pi} U_{\Phi} \Pi, & \text{if } n \text{ is odd}\\
\Pi U_{\Phi} \Pi, & \text{if } n \text{ is even}
\end{cases}$ with a single ancillary qubit.
Moreover, this implementation in <cit.> makes $k$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and single-qubit gates.

Owing to the robustness of QSVT (Lemma 22 in [49], full version of [50]), 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^{\SV}(U) - T_k^{\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 <cit.>, 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 <Ref>.

We then proceed by presenting a linear combination of bitstring indexed encodings, which adapts the LCU technique proposed by Berry, Childs, Cleve, Kothari, and Somma in [11], and incorporates a space-efficient state preparation operator.
We say that $P_{\bfy}$ is an $\epsilon$-state preparation operator for $\bfy$ if $P_{\bfy} \ket{\bar{0}}:= \sum_{i=1}^m \sqrt{\hat{y}_i} \ket{i}$ for some $\hat{\bfy}$ such that $\|\bfy/\|\bfy\|_1-\hat{\bfy}\|_1 \leq \epsilon$.

Given a matrix $A=\sum_{i=0}^{m-1} y_i A_i$ such that each linear operator $A_i$ $(1 \leq i \leq m)$ acts on $s$ qubits with the corresponding $(\|\bfy\|_1,a,\epsilon_1)$-bitstring indexed encoding $U_i$ acting on $s+a$ qubits associated with projections $\tilde{\Pi}_i$ and $\Pi_i$. Also each $y_i$ $(1 \leq i \leq m)$ can be expressed in $O(s(n))$ bits with an evaluation oracle $\Eval$ that returns $\hat{y}_i$ with precision $\varepsilon:=O(\epsilon_2^2/m)$. Then utilizing an $\epsilon_2$-state preparation operator $P_{\bfy}$ for $\bfy$ acting on $O(\log m)$ qubits, and a $(s+a+\lceil\log{m}\rceil)$-qubit unitary $W=\sum_{i=0}^{m-1} \ket{i}\bra{i} \otimes U_i + \big(I-\sum_{i=0}^{m-1} \ket{i}\bra{i}\big)\otimes I$, we can implement a $(\|\bfy\|_1,a+\lceil\log{m}\rceil,\epsilon_1 \|\bfy\|_1^2 + \epsilon_2  \|\bfy\|_1)$-bitstring indexed encoding of $A$ acting on $s + a + \lceil\log m\rceil$ qubits with a single use of $W$, $P_{\bfy}$, $P_{\bfy}^{\dagger}$.
In addition, the classical pre-processing can be implemented in deterministic time $\tilde{O}(m^2 \log(m/\epsilon_2))$ and space $O(\log(m/\epsilon_2^2))$,[It is noteworthy that we define $\tilde{O}(f):=O(f \poly\log(f))$. ] as well as $m^2$ oracle calls to $\Eval$ with precision $\varepsilon$.

For the $\epsilon_2$-state preparation operator $P_{\bfy}$ such that $P_{\bfy}\ket{\bar{0}}=\sum_{i=1}^m \sqrt{\hat{y}_i} \ket{i}$, we utilize a scheme introduced by Zalka [103] (also independently rediscovered in [46] and [62]). We make an additional analysis of the required classical computational complexity, and the proof can be found in <Ref>.
[Space-efficient state preparation, adapted from [103, 62, 46]]propositionrealStatePreparation

Given an $l$-qubit quantum state $\ket{\psi}:=\sum_{i=1}^m \sqrt{\hat{y}_i}\ket{i}$, where $l=\lceil \log{m}\rceil$ and $\hat{y}_i$ are real amplitudes associated with an evaluation oracle $\Eval(i,\varepsilon)$ that returns $\hat{y}_i$ up to accuracy $\varepsilon$ we can prepare $\ket{\psi}$ up to accuracy $\epsilon$ in deterministic time $\tilde{O}(m^2\log(m/\epsilon))$ and space $O(\log(m/\epsilon^2))$, together with $m^2$ evaluation oracle calls with precision $\varepsilon:=O(\epsilon^2/m)$.

Now consider the bitstring indexed encoding $\big(P_{\bfy}^{\dagger}\otimes I_s\big) W \big(P_{\bfy}\otimes I_s\big)$ of $A$ acting on $s+a+\lceil\log{m}\rceil$ qubits. Let $y'_i:=y_i/\|\mathbf{y}\|_1$, then we obtain the implementation error:

\[\begin{aligned}
& \big\| A - \|\bfy\|_1 \big(\ket{\bar{0}}\bra{\bar{0}}\otimes \tilde{\Pi}\big) \big(P_y^{\dagger}\otimes I_s\big) W \big(P_y\otimes I_s\big) \left(\ket{\bar{0}}\bra{\bar{0}}\otimes \Pi\right) \big\| \\
= & \big\| A- \textstyle \|\bfy\|_1 \sum_{i=0}^{m-1} \hat{y}_i \tilde{\Pi}_i U_i \Pi_i \big\| \\
\leq & \big\|A - \textstyle\|\bfy\|_1 \sum_{i=0}^{m-1} y'_i \tilde{\Pi}_i U_i \Pi_i \big\| + \|\bfy\|_1 \sum_{i=0}^{m-1} (y'_i-\hat{y}_i) \| \tilde{\Pi}_i U_i \Pi_i \| \\
\leq & \textstyle \|\bfy\|_1 \sum_{i=0}^{m-1} y'_i \| A_i-\tilde{\Pi}_i U_i \Pi_i\| + \epsilon_2 \|\bfy\|_1 \\
\leq & \epsilon_1 \|\bfy\|_1^2 + \epsilon_2  \|\bfy\|_1.
\end{aligned}\]

Here, the third line is due to the triangle inequality, the fourth line owes to <Ref>, and the fifth line is because $U_i$ is a $(1,a,\epsilon_1)$-bitstring indexed encoding of $A_i$ for $0 \leq i < m$.

To make the resulting bitstring indexed encoding from <Ref> with $\alpha = 1$, we need to perform a renormalization procedure to construct a new encoding with the desired $\alpha$.
We achieve this by extending the proof strategy outlined by Gilyen <cit.> for block-encodings to bitstring indexed encodings.
The renormalization procedure is provided in <Ref>, and the complete proof is available in <Ref>. Additionally, similar results have been established in <cit.> and <cit.>.

[Renormalizing bitstring indexed encoding]lemmaRenormalizingBitstringIndexedEncoding

Let $U$ be an $(\alpha, a, \epsilon)$-bitstring indexed encoding of $A$, where $\alpha > 1$ and $0 < \epsilon < 1$, and $A$ is a linear operator acting on $s(n)$ qubits. We can implement a quantum circuit $V$, serving as a normalization of $U$, such that $V$ is a $(1, a+2, 36\epsilon)$-bitstring indexed encoding of $A$. This implementation requires $O(\alpha)$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and $O(\alpha)$ single-qubit gates. Moreover, the description of the resulting quantum circuit can be computed in deterministic time $O(\alpha)$ and space $O(s)$.

Finally, we combine Lemma <ref> and Lemma <ref> to proceed with the proof of <Ref>.

By using <Ref>, we have $P_d(A)=\frac{c_0}{2}+\sum_{k=1}^d c_k T_k(A)$ where $T_k(A)$ corresponding to a $(1,a+1,4k\sqrt{\epsilon_1})$-bitstring indexed encoding $V_k$.
Employing <Ref>, we result in a $(\|\bfc\|_1, \hat{a}, 4k\sqrt{\epsilon_1}\|\bfc\|_1^2+\epsilon_2\|\bfc\|_1)$-bitstring indexed encoding $\hat{V}$ where $\hat{a}:=a+\lceil\log{d}\rceil+1$.
Moreover, by utilizing <Ref>, we obtain a $(1, a', 144k\sqrt{\epsilon_1}\|\bfc\|_1^2+36\epsilon_2\|\bfc\|_1)$-bitstring indexed encoding $V$ acts on $s+a'$ qubits where $a' := \hat{a}+2 = a+\lceil\log{d}\rceil+3$.
A direct calculation demonstrates that this implementation makes $\sum_{k=1}^d k \cdot O(\|\bfc\|_1)=O(d^2\|\bfc\|_1)$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, also $\sum_{k=0}^d k \cdot O(\|\bfc\|_1)=O(d^2\|\bfc\|_1)$ uses of multi-controlled single-qubit gates.
In addition, the descriptions of quantum circuits $\{V_k\}_{k=0}^d$ can be computed in $O(s(n))$ space and $\sum_{k=0}^d k \cdot O(\|\bfc\|_1)=O(d^2\|\bfc\|_1)$ time. Therefore, the description of the quantum circuit $V$ can be computed in deterministic time $\max\{\tilde{O}(d^2\|\bfc\|_1\log(d/\epsilon_2)),O(d^2\|\bfc\|_1)\} = \tilde{O}(d^2\|\bfc\|_1\log(d/\epsilon_2))$ and space $O(\max\{s(n), d/\epsilon_2^2\})$, as well as $O(d^2\|\bfc\|_1)$ oracle calls to $\Eval$ with precision $\varepsilon$.

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

§.§ Examples: the sign function and the normalized logarithmic function

In this subsection, we provide explicit examples that illustrate the usage of the space-efficient quantum singular value transformation (QSVT) technique. We define two functions:

\begin{equation*}
\label{eq:space-efficient-QSVT-examples}
\sign(x):={\small
\begin{cases}
1,& x > 0\\
-1,& x < 0\\
0,& x=0
\end{cases}}
\ln_{\beta}(x):= \frac{\ln(1/x)}{2\ln(2/\beta)}.
\end{equation*}

In particular, the sign function is a bounded function, and we derive the corresponding bitstring indexed encoding with deterministic space-efficient classical pre-processing in <Ref>. On the other hand, the logarithmic function is a piecewise-smooth function that is bounded by $1$, and we deduce the corresponding bitstring indexed encoding with randomized space-efficient classical pre-processing in <Ref>.

Let $A$ be an Hermitian matrix that acts on $s$ qubits, where $s(n) \geq \Omega(\log(n))$. Let $U$ be a $(1,a, \epsilon_1)$-bitstring indexed encoding of $A$ that acts on $s+a$ qubits.

Then, for any $d \leq 2^{O(s(n))}$ and $\epsilon_2 \geq 2^{-O(s(n))}$, we have an $\big(1, a+\lceil\log{d}\rceil+3, 144 \hat{C}_{\sign}^2 d\epsilon_1^{1/2}\log^2(d) + 36 \hat{C}_{\sign}\epsilon_2 \log(d))\big)$-bitstring indexed encoding $V$ of $P_d^{\sign}(A)$, where $P_d^{\sign}$ is a space-efficient bounded polynomial approximation of the sign function specified in <Ref>, and $\hat{C}_{\sign}$ is a universal constant.
This implementation requires $O(d^2\log{d})$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$,  $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and $O(d^2\log{d})$ multi-controlled single-qubit gatesfootnote:multi-controlled-gates. Moreover, we can compute the description of $V$ in deterministic time $\tilde{O}(\epsilon_2^{-1} d^{9/2})$ and space $O(s(n))$.

Furthermore, our construction straightforwardly extends to any non-Hermitian (but linear) matrix $A$ by simply replacing $P_d^{\sign}(A)$ with $P_{\sign,d}^{\SV}(A)$ defined in the same way as <Ref>.

In <Ref>, we can express $P_d^{\sign}(x)$ as $\frac{c_0}{2}+\sum_{k=1}^d c_k T_k(x)$, where $d=O(\delta^{-1}\log{\epsilon^{-1}})$. For all $x\in[-1,1] \setminus [-\delta,\delta]$, we have $|\sign(x)-P_d^{\sign}(x)| \leq O(\epsilon \log{d}):=\epsilon_2.$ To implement $\Eval$ with precision $\varepsilon$, we can compute the corresponding entry $c_i$ of the coefficient vector, which requires $O(\log(\varepsilon^{-1}d^4))=O(\log(\epsilon_2^{-2}d^5))$ space and $\tilde{O}(\varepsilon^{-1/2} d^2)=\tilde{O}(\epsilon_2^{-1} d^{5/2})$ time. Using <Ref>, we can conclude that $P_d^{\sign}$ has a $\big(1, a', 144dC^2_{\sign}\epsilon_1^{1/2} \log^2(d) + 36\hat{C}_{\sign}\epsilon_2\log{d}\big)$-bitstring indexed encoding $V$ that acts on $s+a'$ qubits, where $a':=a+\lceil\log{d}\rceil+3$ and $\|\bfc\|_1\leq \hat{C}_{\sign} \log{d}$.

Furthermore, the quantum circuit of $V$ makes $O(d^2\log{d})$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, and $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$ as well as $O(d^2\log{d})$ multi-controlled single-qubit gates.
We note that $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 $\Eval$ with precision $\varepsilon$ can be computed in $O(\log(\epsilon_2^{-2} d^5))$ space. Additionally, the time complexity for computing the description of $V$ is

\[ \max\{\tilde{O}(d^2 \log{d} \log(d/\epsilon_2)), d^2 \log{d} \cdot \tilde{O}(\epsilon_2^{-1} d^{5/2})\}= \tilde{O}(\epsilon_2^{-1} d^{9/2}). \qedhere\]

Let $A$ be an Hermitian matrix that acts on $s$ qubits, where $s(n) \geq \Omega(\log(n))$. Let $U$ be a $(1,a, \epsilon_1)$-bitstring indexed encoding of $A$ that acts on $s+a$ qubits.

Then, for any $d \leq 2^{O(s(n))}$, $\epsilon_2 \geq 2^{-O(s(n))}$, and $\beta \geq 2^{-O(s(n))}$, we have a $(1, a+\lceil\log{d}\rceil+3, 144\hat{C}_{\ln}\epsilon_1^{1/2}d^3 + 36\hat{C}_{\ln}\epsilon_2 d)$-bitstring indexed encoding $V$ of $P_d^{\ln}(A)$, where $P_d^{\ln}$ is a space-efficient bounded polynomial approximation of the normalized log function specified in <Ref>, and $\hat{C}_{\ln}$ is a universal constant.
This implementation requires $O(d^3)$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$,  $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$, and $O(d^3)$ multi-controlled single-qubit gatesfootnote:multi-controlled-gates. Moreover, we can compute the description of the resulting quantum circuit in bounded-error randomized time $\tilde{O}(\max\{\beta^{-5} \epsilon_2^{-4} d^5, \epsilon_2^{-1}d^{11/2}\})$ and space $O(s(n))$.

In <Ref>, we can express $P_d^{\ln}(x)$ as $\frac{c_0}{2}+\sum_{k=1}^d c_k T_k(x)$, where $d=O(\delta^{-1}\log{\epsilon^{-1}})$. For any $\ln_{\beta}(x)$, we have $|\ln_{\beta}(x)-P_d^{\ln}(x)| \leq O(\epsilon \log{d}):=\epsilon_2$ for all $x\in[\beta,1]$. To implement $\Eval$ with precision $\varepsilon$, we can compute the corresponding entry $c_i$ of the coefficient vector by a bounded-error randomized algorithm. This requires $O(\log(\varepsilon^{-1}d^4\beta^{-4}))=O(\log(\beta^{-4} \epsilon_2^{-2} d^5))$ 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.
Using <Ref>, we conclude that $P_d^{\ln}$ has a $(1, a', 144C^2_{\ln}\epsilon_1^{1/2}d^3 + 36\hat{C}_{\ln}\epsilon_2 d)$-bitstring indexed encoding $V$ that acts on $s+a'$ qubits, where $a':=a+\lceil\log{d}\rceil+3$ and $\|\bfc\|_1 \leq \hat{C}_{\ln} d$.

Furthermore, the quantum circuit of $V$ makes $O(d^3)$ uses of $U$, $U^{\dagger}$, $\textsc{C}_{\Pi}\textsc{NOT}$, and $\textsc{C}_{\tilde{\Pi}}\textsc{NOT}$ as well as $O(d^3)$ multi-controlled single-qubit gates.
We note that $d \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 $\Eval$ with precision $\varepsilon$ can be computed in $O(\log(\beta^{-4} \epsilon_2^{-2} d^5))$ space.
The time complexity for computing the description of $V$ is given by:

\begin{equation}
\label{eq:log-poly-time-complexity}
\max\{\tilde{O}(d^3 \log(d/\epsilon_2)), d^3 \cdot \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^5, \epsilon_2^{-1}d^{11/2}\}).
%\max\{\tilde{O}(d^2 \log(d/\epsilon_2)), d^2 \cdot \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{equation}

Finally, to guarantee that the probability that all $O(d^3)$ oracle calls to $\Eval$ succeed is at least $2/3$, we use a $(4\ln{d})$-time sequential repetition of $\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^3 \cdot 2\exp(-4\ln{d}) \geq 2/3$. We further note that the time complexity specified in <Ref> only increase by a $4\ln{d}$ factor.

§.§ Application: space-efficient error reduction for unitary quantum computations

We provide a unified space-efficient error reduction for unitary quantum computations. In particular, one-sided error scenarios (e.g., $\RQUL$ and $\coRQUL$) have been proven in [93], and the two-sided error scenario (e.g., $\BQUL{}$) has been demonstrated in [31].

Let $s(n)$ be a space-constructible function, and let $a(n)$, $b(n)$, and $l(n)$ be deterministic $O(s(n))$ space computable functions such that $a(n)-b(n) \geq 2^{-O(s(n))}$, we know that for any $l(n)\leq O(s(n))$, there is $d:=l(n)/{\max\{\sqrt{a}-\sqrt{b},\sqrt{1-b}-\sqrt{1-a}\}}$ such that