Proof. If \(P_1 = Q_1\) and \(P_2 = Q_2\), \[\E_R\left[\ntr\Big(\chi_{P_1, P_2}(R)^{\dagger} \cdot \chi_{Q_1, Q_2}(R)\Big)\right] = \E_R\left[\ntr(P_2 R P_1 \cdot Q_1 R Q_2)\right] = \E_R[\ntr(R R)] = 1.\] Otherwise, let us assume without loss of generality that \(P_1 \neq Q_1\). Then, \(P_1 Q_1\) is some nonidentity Pauli matrix, and a random Pauli \(R\) will commute with \(P_1 Q_1\) with probability \(1/2\) and anticommute with probability \(1/2\). Thus, half of the time, we have \[\ntr\Big(\chi_{P_1, P_2}(R)^{\dagger}\cdot \chi_{Q_1, Q_2}(R) \Big) = \ntr(P_2 R P_1 Q_1 R Q_2) = \ntr(P_2 P_1 Q_1 RR Q_2) = \ntr(P_2 P_1 Q_1 Q_2),\] and the other half of the time, we have \[\ntr\Big(\chi_{P_1, P_2}(R)^{\dagger}\cdot \chi_{Q_1, Q_2}(R) \Big) = \ntr(P_2 R P_1 Q_1 R Q_2) = -\ntr(P_2 P_1 Q_1 RR Q_2) = -\ntr(P_2 P_1 Q_1 Q_2).\] These two average out to zero, which completes the proof. ◻

Proof. By definition, \[\begin{align} \E_{R \sim \mathcal{P}_{S}}\left[\ntr\Big(\chi_{P_1, P_2}(R)^{\dagger} \cdot \chi_{Q_1, Q_2}(R)\Big)\right] &=\E_{R \sim \mathcal{P}_{S}}\left[\ntr(P_2 R P_1 Q_1 R Q_2)\right]\\ &= \E_{R \sim \mathcal{P}_{S}}\left[\ntr(P_2^S R P_1^S Q_1^S R Q_2^S)\right] \cdot \overline{\mathrm{tr}}(Q_1^{\overline{S}} Q_2^{\overline{S}})\\ &= \E_{R \sim \mathcal{P}_{S}}\left[\ntr\Big(\chi_{P_1^S, P_2^S}(R)^{\dagger} \cdot \chi_{Q_1^S, Q_2^S}(R)\Big)\right] \cdot \overline{\mathrm{tr}}(Q_1^{\overline{S}} Q_2^{\overline{S}}). \end{align}\] By 1, the expectation is \(1\) if \(Q_1^S = P_1^S\) and \(Q_2^S = P_2^S\) and 0 otherwise. In addition, the second term is \(1\) if \(Q_1^{\overline{S}} = Q_2^{\overline{S}}\) and 0 otherwise. This completes the proof. ◻

Proof. We drop the \((i)\) superscript from our Pauli matrices for notational convenience. We also write \(S\) for \(S_{\overline{P}}\) and \(s\) for \(s_{\overline{P}}\).

First, we consider the expectation of \(E^{(i)}_{P_1, P_2}\) conditioned on a fixed \(A,B\). If \(Z \neq \mathcal{P}_{}(P_2 R P_1)\), then \(E^{(i)}_{P_1, P_2}\) is set to 0, so the expectation is 0. Otherwise, we receive the measurement outcome \(\ket{B, w}\) with probability \[\tr\Big(\ketbra{B, w}{B,w} \cdot \Phi(\ketbra{A, v}{A,v})\Big).\] Thus, we can write the expectation as \[\begin{align} \E[E_{P_1, P_2}^{(i)} \mid A, B] &= \E_{v \in \{\pm 1\}^n}\sum_{w \in \{\pm 1\}^n} 4^s \cdot c(P_2 R P_1) \cdot \chi_{S_R}(v) \cdot \chi_{S_Z}(w)\cdot \tr\Big(\ketbra{B, w}{B,w} \cdot \Phi(\ketbra{A, v}{A,v})\Big)\\ &=2^{-n}4^s \cdot c(P_2 R P_1) \cdot\tr\Big(\Big(\sum_w \chi_{S_Z}(w) \cdot \ketbra{B, w}{B,w}\Big) \cdot \Phi(\sum_v \chi_{S_R}(v) \cdot\ketbra{A, v}{A,v}\Big)\Big)\\ &=2^{-n}4^s \cdot c(P_2 R P_1) \cdot\tr(Z \cdot \Phi(R)) \\ &=4^s\ntr(P_2 R P_1 \cdot \Phi(R)), \end{align}\] where we used [eq:eigen,eq:pauli-factor] in the last two steps. Now, note that as \(A\) varies uniformly over \(\mathcal{P}_{n}\), \(R\) varies uniformly over \(\mathcal{P}_{S}\). Furthermore, conditioned on the value of \(A\), we have \(Z = \mathcal{P}_{}(P_2 R P_1)\) with probability exactly \(1/4^s\). Hence, \[\E[E_{P_1, P_2}^{(i)}] = \E_{R\sim \mathcal{P}_{S_{\overline{P}}}}\left[\ntr(\chi_{P_1, P_2}(R)^{\dagger} \cdot \Phi(R))\right].\] This concludes the proof. ◻

Proof. Consider a fixed \(P_1\) and \(P_2\). Each \(E^{(i)}_{P_1, P_2}\) is an unbiased estimator for \(\widehat{\Phi}_{\mathsf{loc}}(P_1, P_2)\) which is bounded in magnitude by \(4^k\). As a result, Hoeffding’s inequality, applied to the real and imaginary parts of the estimator, implies that \[\Pr[|\widehat{E}_{P_1, P_2} - \widehat{\Phi}_{\mathsf{loc}}(P_1, P_2)| \geq \epsilon] \leq 4 e^{-4M \epsilon^2/16^k}.\] Now, the number of \(P_1, P_2 \in \mathcal{P}_{n}\) with \(s_{\overline{P}} \leq k\) is at most \(\binom{n}{k} \cdot 16^k \leq (16n)^k\). Hence, by the union bound, the probability that there exists an \(E_{P_1, P_2}\) with error more than \(\epsilon\) is at most \[(16n)^k \cdot 2 e^{-2M \epsilon^2/16^k} \leq \delta,\] by our choice of \(M\). This completes the proof. ◻

Proof. The pairs \(\overline{Q}\) which satisfy \(\overline{R}\succeq \overline{Q}\) and \(\overline{Q}\succeq \overline{P}\) are exactly those which (i) agree with \(\overline{P}\) on \(S_{\overline{P}}\), (ii) agree with \(\overline{R}\) on some subset \(T\) of \(S_{\overline{R}} \setminus S_{\overline{P}}\), and (iii) are identity on the remaining qubits in \(S_{\overline{R}}\). As \(\overline{R}\) is non-identity on every qubit in \(T\), we have \(s_{\overline{Q}} - s_{\overline{P}} = |T|\). Thus, \[\sum_{\substack{\overline{Q}: \overline{Q}\succeq \overline{P}\\\overline{R}\succeq \overline{Q}}} (-1)^{s_{\overline{Q}}-s_{\overline{P}}} = \sum_{T\subseteq S_{\overline{R}}\setminus S_{\overline{P}}}(-1)^{|T|} = \left\{\begin{array}{rl} 1 & \text{if \overline{R}= \overline{P}},\\ 0 & \text{otherwise}. \end{array}\right.\] This completes the proof. ◻

Proof. To see this, \[\begin{align} (V_k A_k x)_{\overline{P}} &= \sum_{\overline{Q}\succeq \overline{P}} (-1)^{s_{\overline{Q}}-s_{\overline{P}}}(A_kx)_{\overline{Q}}\\ &= \sum_{\overline{Q}\succeq \overline{P}} (-1)^{s_{\overline{Q}}-s_{\overline{P}}}\sum_{\overline{R}\succeq \overline{Q}}x_{\overline{R}}\\ &= \sum_{\overline{R}\succeq \overline{P}}x_{\overline{R}} \sum_{\substack{\overline{Q}: \overline{Q}\succeq \overline{P}\\\overline{R}\succeq \overline{Q}}} (-1)^{s_{\overline{Q}}-s_{\overline{P}}} = x_{\overline{P}}, \end{align}\] where the last step used 4. This completes the proof. ◻

Proof. To see this, note that \((V_k A_k x)_{P, I}\) is equal to \[\label{eq:real-big-sum} 2 (A_k x)_{P, I} + \sum_{\substack{Q, S_Q \subseteq S_P \\ Q \neq I, P}} \overline{c(PQ)}\cdot (A_k x)_{Q, \mathcal{P}_{}(PQ)} + \sum_{\substack{\overline{Q}\succeq (P, I)\\\overline{Q}\neq (P, I)}} (-1)^{s_{\overline{Q}}- s_{P}} (A_k x)_{\overline{Q}}- \sum_{\substack{\overline{Q}\succeq (I, P)\\\overline{Q}\neq (I, P)}} (-1)^{s_{\overline{Q}}- s_{P}} (A_k x)_{\overline{Q}}.\tag{19}\] Note that only the first term involves indexing \((A_k x)\) by a pair of Paulis, one of which is \(I\); the other terms always index by two non-identity Paulis. Hence, the first two terms are equal to \[\label{eq:first-two-combined} 2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}} -\sum_{Q \neq I} \overline{c(P Q)}\cdot x_{Q, \mathcal{P}_{}(PQ)} + \sum_{\substack{Q, S_Q \subseteq S_P \\ Q \neq I, P}} \overline{c(PQ)}\cdot \sum_{\overline{R}\succeq (Q, \mathcal{P}_{}(PQ))} x_{\overline{R}}.\tag{20}\] Note that in the second summation, the pair \((Q, \mathcal{P}_{}(PQ))\) has support equal to \(S_P\) and is identity outside of it. This means that \(\overline{R}\) is equal to \((Q, \mathcal{P}_{}(PQ))\) within \(S_P\), and \(R_1\) and \(R_2\) agree outside of \(S_P\). This means that (i) \(\overline{R}= (R_1, \mathcal{P}_{}(P R_1))\), (ii) \(c(P R_1) = c(P Q)\), and (iii) \(\overline{R}\) ranges over all possible pairs of this form, subject to \(R_1|_{S_P}\) not being \(I\) or \(P\). Hence, \[\begin{align} \eqref{eq:first-two-combined} & = 2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}} -\sum_{Q \neq I} \overline{c(P Q)}\cdot x_{Q, \mathcal{P}_{}(PQ)} + \sum_{R : R|_{S_P} \neq I, P} \overline{c(P R)} \cdot x_{R, \mathcal{P}_{}(PR)}\\ &=2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}} -\sum_{\substack{Q \neq I,\\Q|_{S_P} = I \text{ or }P}} \overline{c(P Q)}\cdot x_{Q, \mathcal{P}_{}(PQ)}\\ &=2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}} -\sum_{\substack{Q \neq I,\\Q|_{S_P} = I \text{ or }P}} x_{Q, PQ}\\&=2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}} - x_{P, I} - \sum_{\substack{Q \neq I,P\\Q|_{S_P} = I \text{ or }P}} x_{Q, PQ}, \end{align}\] where in the second-to-last line we use the fact that if \(Q_{S_P} = I\) or \(P\), then \(PQ\) is a Pauli, and so \(\mathcal{P}_{}(PQ) = PQ\) and \(c(PQ) = 1\). Now, the third term in 19 is equal to \[\begin{align} \sum_{\substack{\overline{Q}\succeq (P, I)\\\overline{Q}\neq (P, I)}} (-1)^{s_{\overline{Q}}- s_{P}} (A_k x)_{\overline{Q}} &= \sum_{\substack{\overline{Q}\succeq (P, I)\\\overline{Q}\neq (P, I)}} (-1)^{s_{\overline{Q}}- s_{P}} \sum_{\overline{R}\succeq \overline{Q}} x_{\overline{R}}\\ &= \sum_{\overline{Q}\succeq (P, I)} (-1)^{s_{\overline{Q}}- s_{P}} \sum_{\overline{R}\succeq \overline{Q}} x_{\overline{R}}- \sum_{\overline{R}\succeq (P, I)} x_{\overline{R}}. \end{align}\] The first of these terms is equal to \[\sum_{\overline{R}\succeq (P, I)} x_{\overline{R}} \sum_{\substack{\overline{Q}: \overline{Q}\succeq (P, I) \\ \overline{R}\succeq \overline{Q}}}(-1)^{s_{\overline{Q}}- s_{P}} = x_{P, I},\] by 4. Hence, the third term in 19 is equal to \[x_{P, I} - \sum_{\overline{R}\succeq (P, I)} x_{\overline{R}} = -\sum_{\substack{R \neq I, P,\\R|_{S_P} = P}} x_{R, PR}.\] Similarly, the fourth term in 19 is equal to \[\sum_{\substack{R \neq I, P,\\R|_{S_P} = I}} x_{R, PR}.\] Plugging everything back into 19 , we get that \[\begin{align} (V_k A_k x)_{P, I} &= 2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}}-x_{P, I} -\sum_{\substack{Q \neq I, P,\\Q|_{S_P} = I \text{ or }P}} x_{Q, PQ} -\sum_{\substack{R \neq I, P,\\R|_{S_P} = P}} x_{R, PR} +\sum_{\substack{R \neq I, P,\\R|_{S_P} = I}} x_{R, PR}\\ &= 2\sum_{\overline{Q}\succeq(P,I)}x_{\overline{Q}}-x_{P, I} -2\sum_{\substack{Q \neq I, P,\\Q|_{S_P} = P}} x_{Q, PQ}\\ &= 2 x_{P, I} - x_{P, I}\\ &= x_{P, I}, \end{align}\] where in the third step we used that if \(\overline{Q}= (Q, PQ)\) and \(Q|_{S_P} = P\), then \(\overline{Q}\succeq (P, I)\). This completes the proof. ◻

Proof. For \(P_1, P_2 \neq I\), we consider bounding the entry \[\begin{align} |(Ax)_{P_1, P_2}| &\leq \sum_{(Q_1, Q_2) \succeq (P_1, P_2)} |x_{Q_1, Q_2}|. \end{align}\] Note that \(|(A^{-1}x)_{P_1, P_2}|\) is also bounded by the same quantity, so the entirety of the following argument will work for it as well. We will now show an equivalent way to write this expression which allows us to derive our desired bound. For each set \(S \subseteq [k]\), we will construct a vector \(x^S\) as follows:

1. Initialize \(x^S_{P_1, P_2} = 0\) for all pairs of Paulis with \(s_{\overline{P}} \leq k\).

2. For each \(\overline{Q}= (Q_1, Q_2)\) with \(s_{\overline{Q}} \leq k\), consider the \(\ell \leq k\) qubits in which the Paulis are identical, and number them from \(1\) to \(\ell\).

3. For each \(i \in S\), set the \(i\)-th identical pair in \(Q_1\) and \(Q_2\) to the identity \(I\). Call the resulting Paulis \(R_1\) and \(R_2\). If there is some \(i \in S\) for which there is no corresponding identical pair (meaning that \(i > \ell\)), do not update \(x^S\).

4. Otherwise, update \(x^S_{R_1, R_2}\gets x^S_{R_1, R_2} + |x_{Q_1, Q_2}|\).

Note that for each \((Q_1, Q_2) \succeq (P_1, P_2)\), there is exactly one choice of \(S\) so that \((R_1, R_2) = (P_1, P_2)\). Thus, \[\begin{align} |(Ax)_{P_1, P_2}| \leq \sum_{(Q_1, Q_2) \succeq (P_1, P_2)} |x_{Q_1, Q_2}| = \sum_{S \subseteq [k]} (x^S)_{P_1, P_2}. \end{align}\] Moreover, \(x^S\) has the same locality properties as \(x\). In particular, \(\lonorm{x^S} \leq \lonorm{x}\). This gives the desired bounds. ◻

Proof. Let \(x\) be a vector such that \(\lonorm{x} \leq 1\). Let \(i \in [n]\). Then, we can bound the \(B_1\) norm of \((\overline{\Pi} A^{-1})x\) associated with site \(i \in [n]\) using 18 as \[\sum_{P:S_P \ni i} |(A^{-1} x)_{P, I}| \leq \sum_{P:S_P \ni i} \Big|2 x_{P, I} + \sum_{\substack{Q, S_Q \subseteq S_P \\ Q \neq I, P}} \overline{c(PQ)}\cdot x_{Q, \mathcal{P}_{}(PQ)} + \sum_{\substack{\overline{Q}\succeq (P, I)\\\overline{Q}\neq (P, I)}} (-1)^{s_{\overline{Q}}- s_{P}} x_{\overline{Q}}- \sum_{\substack{\overline{Q}\succeq (I, P)\\\overline{Q}\neq (I, P)}} (-1)^{s_{\overline{Q}}- s_{P}} x_{\overline{Q}}\Big|\] To understand this expression, note that the second term ranges over all \((Q, PQ)\) with \(S_Q \subseteq S_P\) and \(Q \neq I, P\); the third term ranges over all \((Q, PQ)\) where \(Q\) agrees with \(P\) on \(S_P\) (and arbitrary outside) and \(Q \neq P\); and the fourth term ranges over all \((Q, PQ)\) where \(Q\) agrees with \(I\) on \(S_P\) (and arbitrary outside) and \(Q \neq I\). Together, every term of the form \((Q, PQ)\) appears at most once, and \(Q = I\) and \(P\) both appear zero times. Hence, \[\begin{align} \sum_{P:S_P \ni i} |(A^{-1} x)_{P, I}| &\leq \sum_{P:S_P \ni i} \Big(2|x_{P, I}| + \sum_{Q \neq I, P} |x_{Q, \mathcal{P}_{}(PQ)}|\Big)\label{eq:gonna-cite}\\ &\leq \sum_{P:S_P \ni i} 2 |x_{P, I}| + \sum_{\substack{\overline{P}:i \in S_{\overline{P}},\\ P_1, P_2 \neq I}} |x_{\overline{P}}|\\ &\leq 2\lonorm{x}\\ &\leq 2. \end{align}\tag{21}\] As for \((\overline{\Pi} A) x\), the \(B_1\) norm associated with site \(i \in[n]\) is \[\begin{align} \sum_{P:S_P \ni i} |(A x)_{P, I}| & \leq \sum_{P:S_P \ni i} \Big(\sum_{\overline{Q}\succeq (P, I)} |x_{\overline{Q}}| + \frac{1}{2} \sum_{Q \neq I} |x_{Q, \mathcal{P}_{}(PQ)}|\Big)\\ &\leq \sum_{\overline{P}: i \in S_{\overline{P}}} |x_{P_1, P_2}| + \frac{1}{2} \sum_{\substack{\overline{P}:i \in S_{\overline{P}},\\ P_1, P_2 \neq I}}|x_{\overline{P}}|\\ &\leq 2 \lonorm{x}\\ &\leq 2. \end{align}\] Both of these held for all \(i \in [n]\), so this completes the proof. ◻

Proof. We prove the lemma by induction on \(\ell\). For the base case of \(\ell = 0\), we have \(\mathcal{L}^{\dagger \ell}(O) = O\). Then, consider \(\mathcal{G}_{S,\boldsymbol{a}}(O) = O\), i.e., \(\mathcal{G}_{\boldsymbol{a}}\) is the identity superoperator, for \(\boldsymbol{a} = \emptyset\). This satisfies the required conditions on its Fourier coefficients, because the only nonzero Fourier coefficient is \(\widehat{\mathcal{G}_{S,\boldsymbol{a}}}(I, I) = 1\). In addition, \(S_{I, I} = \emptyset = S_{\boldsymbol{a}}\). Moreover, \(\boldsymbol{a} \cup S\) is vacuously a cluster.

For the inductive step, suppose the result holds for \(\ell\). Then, \[\begin{align} \mathcal{L}_x^{\dagger\,\ell+1}(O) &= \mathcal{L}_x^{\dagger}(\mathcal{L}_x^{\dagger\ell}(O))\\ &= \sum_{\substack{P_1,P_2\\P_1 \neq I}} x_{P_1,P_2} \left(P_2 \mathcal{L}^{\dagger\ell}(O) P_1 - \frac{1}{2}\{P_2P_1, \mathcal{L}^{\dagger\ell}(O)\}\right)\\ &= 2^\ell \ell! \sum_{\substack{P_1,P_2\\P_1 \neq I}} \sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} x_{P_1,P_2} \cdot x^{\boldsymbol{a}} \left(P_2 \mathcal{G}_{S,\boldsymbol{a}}(O) P_1 - \frac{1}{2}\{P_2P_1, \mathcal{G}_{S,\boldsymbol{a}}(O)\}\right) \iver{\boldsymbol{a} \cup S \text{ is a cluster}}.\label{eq:is-a-cluster} \end{align}\tag{24}\] In the second line, we use the definition of \(\mathcal{L}^\dagger\). In the last line, we use the inductive hypothesis.

Now, suppose \(\boldsymbol{a}\) satisfies that \(\boldsymbol{a} \cup S\) is a cluster, and let us consider the corresponding term \[\begin{align} &2^\ell \ell!\cdot x_{P_1,P_2} \cdot x^{\boldsymbol{a}} \left(P_2 \mathcal{G}_{S,\boldsymbol{a}}(O) P_1 - \frac{1}{2}\{P_2P_1, \mathcal{G}_{S,\boldsymbol{a}}(O)\}\right) \iver{\boldsymbol{a} \cup S \text{ is a cluster}}\\ ={}&2^\ell \ell!\cdot x_{P_1,P_2} \cdot x^{\boldsymbol{a}} \left([\chi_{P_2, P_1} - \frac{1}{2}(\chi_{P_2 P_1, I} + \chi_{I, P_2 P_1})](\mathcal{G}_{S,\boldsymbol{a}}(O))\right) \iver{\boldsymbol{a} \cup S \text{ is a cluster}}.\label{eq:second-line} \end{align}\tag{25}\] This term corresponds to the new cluster \(\boldsymbol{b} = \boldsymbol{a} \cup \{S_{\overline{P}}\}\) inside \(\mathcal{L}_x^{\dagger\,\ell+1}(O)\). Indeed, note that \(x_{P_1, P_2} \cdot x^{\boldsymbol{a}} = x^{\boldsymbol{b}}\). The induction hypothesis tells us that \(\mathcal{G}_{S,\boldsymbol{a}}\) is a linear combination of terms of the form \(Q_1 O Q_2\) with \(\overline{Q}\subseteq S_{\boldsymbol{a}}\). Hence, 25 is a linear combination of terms of the form \[\label{eq:one-term} 2^\ell \ell! \cdot x_{P_1,P_2} \cdot x^{\boldsymbol{a}} \left([\chi_{P_2, P_1} - \frac{1}{2}(\chi_{P_2 P_1, I} + \chi_{I, P_2 P_1})](Q_1 O Q_2)\right) \iver{\boldsymbol{a} \cup S \text{ is a cluster}}.\tag{26}\] Note that this is in turn a linear combination of terms of the form \(Q_1' O Q_2'\) with \(S_{\overline{Q}'} \subseteq S_{\overline{Q}} \cup S_{\overline{P}} \subseteq S_{\boldsymbol{a}} \cup S_{\overline{P}} = S_{\boldsymbol{b}}\). Furthermore, note that since the total support of \(Q_1 O Q_2\) is contained in \(S_{\boldsymbol{a}} \cup S\), 26 is nonzero only if \(S_{\overline{P}}\) overlaps with \(S_{\boldsymbol{a}} \cup S\). Since we know that \(\boldsymbol{a} \cup S\) is a cluster, this is equivalent to \(S_{\boldsymbol{a}} \cup \{S_{\overline{P}}\} \cup S = S_{\boldsymbol{b}} \cup S\) being a cluster.

By the triangle inequality, the expression in 25 has Fourier weight at most \(2 \cdot 2^{\ell} \ell! = 2^{\ell+1} \ell!\). Now, we collect all the terms in the sum associated to the monomial \(x^{\boldsymbol{b}}\). There are at most \(\ell + 1\) of them, corresponding to the clusters formed by removing one element from \(\boldsymbol{a}\) along with the element removed. Hence, their total Fourier weight is at most \((\ell+1) \cdot 2^{\ell+1} \ell! = 2^{\ell + 1} (\ell+1)!\). This gives the desired bound by collecting the corresponding (matrix) coefficient and labeling it \(\mathcal{G}_{\boldsymbol{b}}(O)\). ◻

Proof. We first show ?? . Let \(r\) be an integer satisfying \(1 \leq r \leq k\). We begin with the following standard fact (Lemma 4 of mann2024algorithmic?): Let \(G = (V, E)\) be a multihypergraph with maximum degree at most \(g\) and rank at most \(k\); then the number of connected subgraphs (sets of edges) of size \(r\) containing a vertex \(v \in V\) in its support is at most \((eg(k-1))^r\). The analogous statement also holds for weighted graphs: let \(w_e\) be the nonnegative weight associated to hyperedge \(e\), and let \(g\) be now the weighted degree, \(\max_{i \in V} \sum_{e \ni i} \abs{w_e}\). Then \[\begin{align} \label{eq:multisuperhypergraphs} \sum_{S \subseteq E} \iver{S \text{ is a connected subgraph of size } r \text{ containing } v} \prod_{e \in S} w_e \leq (eg(k-1))^{r}. \end{align}\tag{27}\] To prove this, let us note that it suffices to prove this when the \(w_e\)’s are rational, by a continuity argument. But for rational \(w_e\)’s, we can multiply each \(w_e\) by a scalar such that the weights become integral, and then apply the unweighted statement to the analogous hypergraph.

To apply this to our setting, let \(G_x\) be the multihypergraph with the vertex set \(V = [n]\) and, for each Lindbladian term \(a \in [m]\), a hyperedge \(S_a\) with weight \(|x_a|\). Then 27 implies that for each vertex \(i \in [n]\), \[\begin{align} \label{eq:applied-to-Gx} \sum_{S \subseteq [m]} \iver{S \text{ is a connected subgraph in G_x of size } r \text{ containing } i} \prod_{a \in S} |x_a| \leq (eg(k-1))^{r}. \end{align}\tag{28}\] From there, we now consider clusters. For every subgraph \(S = \{a_1, \ldots, a_r\} \subseteq [m]\) of size \(r\), there are \(\binom{\ell-1}{r-1}\) ways to assign positive integer weights to the \(r\) elements of \(S\) which sum up to \(\ell\). Each of these corresponds to a unique cluster \(\boldsymbol{a}\) of cardinality \(|\boldsymbol{a}| = \ell\) consisting of \(r\) distinct elements; we write \(\boldsymbol{a} \sim S\) for a cluster formed in this manner. Moreover, since \(\lonorm{x} \leq g\), the weight \(x^{\boldsymbol{a}}\) of the cluster \(\boldsymbol{a}\) is at most the weight of the subgraph times \(g^{\ell - r}\). Therefore, we can bound the number of clusters using the number of subgraphs, giving \[\begin{align} \abs{Z_i(x)} &=\Big|\sum_{r=1}^\ell\sum_{S \subseteq [m]} \iver{S \text{ is a connected subgraph in G_x of size } r \text{ containing } i} \cdot \sum_{\boldsymbol{a} \sim S} x^{\boldsymbol{a}}\Big|\\ &\leq\sum_{r=1}^\ell\sum_{S \subseteq [m]} \iver{S \text{ is a connected subgraph in G_x of size } r \text{ containing } i} \cdot \sum_{\boldsymbol{a} \sim S} |x^{\boldsymbol{a}}|\\ &\leq\sum_{r=1}^\ell\sum_{S \subseteq [m]} \iver{S \text{ is a connected subgraph in G_x of size } r \text{ containing } i} \cdot \sum_{\boldsymbol{a} \sim S} \prod_{a \in S} |x_a| \cdot g^{\ell-r}\\ &=\sum_{r=1}^\ell\sum_{S \subseteq [m]} \iver{S \text{ is a connected subgraph in G_x of size } r \text{ containing } i} \cdot \prod_{a \in S} |x_a| \cdot g^{\ell - r} \binom{\ell-1}{r-1}\\ &=\sum_{r=1}^{\ell} (eg(k-1))^r \cdot g^{\ell - r}\binom{\ell-1}{r-1}\label{eq:plugged-in-awesome-bound}, \end{align}\tag{29}\] where we used 28 in the last step. Now, using the fact that \(\sum_{r=1}^{\ell} x^r \cdot \binom{\ell-1}{r-1} = x (x + 1)^{\ell-1} \leq (x + 1)^{\ell}\) for a nonnegative number \(x\), we have \[\eqref{eq:plugged-in-awesome-bound} = g^{\ell} \cdot \sum_{r=1}^{\ell} (e(k-1))^r \cdot \binom{\ell-1}{r-1} \leq g^{\ell} (e (k- 1) + 1)^{\ell} \leq g^{\ell} (ek)^{\ell}.\] This completes the proof. ◻

Proof. To begin, let us compute \[\partial_a Z_i(x) = \sum_{\substack{\boldsymbol{a} : a \in \boldsymbol{a},\\\abs{\boldsymbol{a}} = \ell}} x^{\boldsymbol{a}\setminus\{a\}} \iver{\boldsymbol{a} \text{ is a cluster from } i},\] where here the notation “\(\boldsymbol{a}\setminus\{a\}\)” refers to removing a single instance of \(a\) from \(\boldsymbol{a}\). Thus, if \(v\) is a vector satisfying \(\lonorm{v} \leq 1\), we have \[\sum_a v_a \partial_a Z_i(x) = \sum_a v_a \cdot \sum_{\substack{\boldsymbol{a} : a \in \boldsymbol{a},\\\abs{\boldsymbol{a}} = \ell}} x^{\boldsymbol{a}\setminus\{a\}} \iver{\boldsymbol{a} \text{ is a cluster from } i}.\] Note that the absolute value of this quantity is largest when \(x\) and \(v\) are nonnegative, and so we will henceforth make this assumption without loss of generality. Now, take \(u = \frac{\ell-1}{\ell}\frac{x}{g} + \frac{1}{\ell} v\), and notice that \(\lonorm{u} \leq 1\) by construction. Then \[\begin{align} Z_i(u) &= \sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} u^{\boldsymbol{a}} \iver{\boldsymbol{a} \text{ is a cluster from } i}\\ &= \sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} \Big(\frac{\ell-1}{\ell}\cdot \frac{x}{g} + \frac{1}{\ell}\cdot v\Big)^{\boldsymbol{a}} \iver{\boldsymbol{a} \text{ is a cluster from } i}.\label{eq:about-to-binomial} \end{align}\tag{30}\] Note that if \(\boldsymbol{a} = \{a_1, \ldots, a_{\ell}\}\), then we can expand \[\begin{align} \Big(\frac{\ell-1}{\ell}\cdot \frac{x}{g} + \frac{1}{\ell}\cdot v\Big)^{\boldsymbol{a}} &= \Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell} x^{\boldsymbol{a}} + \Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell-1} \cdot \frac{1}{\ell} \sum_{a \in \boldsymbol{a}}x^{\boldsymbol{a} \setminus\{a\}} v_a + \cdots \\ &\geq\Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell-1} \cdot \frac{1}{\ell} \sum_{a \in \boldsymbol{a}} x^{\boldsymbol{a} \setminus\{a\}} v_{a}. \end{align}\] Here, in the first step, we use the binomial formula to expand \((\frac{\ell-1}{\ell}\cdot \frac{x}{g} + \frac{1}{\ell}\cdot v)^{\boldsymbol{a}}\). In the second step, we use the fact that all the terms in this expansion are nonnegative (which follows from the fact that \(x\) is nonnegative), to lower bound the expression by only those terms which use a single coordinate of \(v\). Plugging this in to 30 , we have that \[\begin{align} Z_i(u) &\geq\sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} \Big(\Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell-1} \cdot \frac{1}{\ell} \sum_{a \in \boldsymbol{a}} x^{\boldsymbol{a} \setminus\{a\}} v_{a}\Big)\cdot \iver{\boldsymbol{a} \text{ is a cluster from } i}\\ &\geq\Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell-1} \cdot \frac{1}{\ell} \cdot \sum_a v_a \sum_{\substack{\boldsymbol{a} : a \in \boldsymbol{a},\\\abs{\boldsymbol{a}}=\ell}} x^{\boldsymbol{a} \setminus\{a\}} \iver{\boldsymbol{a} \text{ is a cluster from } i}\\ &= \Big(\frac{\ell-1}{\ell \cdot g}\Big)^{\ell-1} \cdot \frac{1}{\ell} \cdot \sum_a v_a \partial_a Z_i(x). \end{align}\] Rearranging, we have \[\sum_a v_a \partial_a Z_i(x) \leq \ell \Big(\frac{\ell}{\ell-1}\Big)^{\ell-1} g^{\ell - 1} \cdot Z_i(u) \leq \ell \Big(\frac{\ell}{\ell-1}\Big)^{\ell-1} g^{\ell - 1} \cdot (ek)^{\ell} \leq \ell (ek)^\ell e g^{\ell - 1}.\] In the second step, we used 12 and the fact that \(\lonorm{u}\leq 1\). This concludes the proof. ◻

Proof. We use 11 to expand out \(\mathcal{L}_x^{\dagger \ell}(P_2 R P_1)\) into a polynomial for every \(R \in \mathcal{P}_{S_{\overline{P}}}\): \[\begin{align} \E_{R \sim \mathcal{P}_{S_{\overline{P}}}}[\ntr(\mathcal{L}_x^{\dagger \ell}(P_2 R P_1)R)] &= 2^\ell \ell! \E_{R \sim \mathcal{P}_{S_{\overline{P}}}}\bracks[\Big]{\ntr\parens[\Big]{R \sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} x^{\boldsymbol{a}} \mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}(P_2RP_1) \iver{\boldsymbol{a} \cup S_{\overline{P}} \text{ is a cluster}}}} \\ &= 2^\ell \ell! \sum_{\boldsymbol{a} : \abs{\boldsymbol{a}} = \ell} x^{\boldsymbol{a}} \iver{\boldsymbol{a} \cup S_{\overline{P}} \text{ is a cluster}} \underbrace{\E_{R \sim \mathcal{P}_{S_{\overline{P}}}}\bracks[\Big]{\ntr\parens[\Big]{R \mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}(P_2 R P_1)}}}_{\triangleq \gamma_{\boldsymbol{a}}}, \end{align}\] where in the first equality, we used the fact that the support of \(P_2 R P_1\) is contained in \(S_{\overline{P}}\) to apply 11. The coefficients of this expansion can be bounded: \[\begin{align} \abs{\gamma_{\boldsymbol{a}}} \leq \sum_{Q_1, Q_2} \left|\widehat{\mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}}(Q_1, Q_2)\right| \E_{R \sim \mathcal{P}_{S_{\overline{P}}}}\bracks[\Big]{\abs[\Big]{\ntr\parens[\Big]{R \chi_{Q_1, Q_2}(P_2 R P_1)}}} \leq \sum_{Q_1, Q_2} \left|\widehat{\mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}}(Q_1, Q_2)\right| \leq 1, \end{align}\] where in the final inequality we use the bound on the Fourier weight of \(\mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}\). Moreover, because \(\mathcal{G}_{S_{\overline{P}}, \boldsymbol{a}}\) only acts on sites contained in \(S_{\boldsymbol{a}}\), \(\gamma_{\boldsymbol{a}}\) is only nonzero provided that \(S_{\boldsymbol{a}}\) does not merely overlap \(S_{\overline{P}}\), but contains it. This concludes the proof. ◻

Proof. Consider some \(v\) such that \(\lonorm{v} \leq 1\). Further consider some site \(i \in [n]\). Then, by 14, \[\begin{align} \sum_{a : S_{a} \ni i} \abs{(J^{(\ell)}(x) v)_a} &= \frac{1}{t}\sum_{a : S_a \ni i} \left|\sum_b v_b \partial_b E^{(\ell)}_a(x)\right|\\ &= 2^{\ell} \ell! \frac{1}{t}\sum_{a : S_{a} \ni i} \abs[\Big]{\sum_{b} v_b\partial_b \sum_{\boldsymbol{a} : |\boldsymbol{a}| = \ell} \gamma_{a, \boldsymbol{a}} x^{\boldsymbol{a}} \iver{\boldsymbol{a} \text{ is a cluster}} \iver{S_{\boldsymbol{a}} \supseteq S_{a}}} \\ &= 2^{\ell} \ell! \frac{1}{t}\sum_{a : S_{a} \ni i} \abs[\Big]{\sum_{b} v_b\partial_b \sum_{\boldsymbol{a} : |\boldsymbol{a}| = \ell} \gamma_{a, \boldsymbol{a}} x^{\boldsymbol{a}} \iver{\boldsymbol{a} \text{ is a cluster from i}} \iver{S_{\boldsymbol{a}} \supseteq S_{a}}} \\ &\leq 2^\ell \ell! \frac{1}{t}\sum_{a : S_{a} \ni i} \sum_{\boldsymbol{a} : |\boldsymbol{a}| = \ell} \sum_b \abs{v_b \partial_b x^{\boldsymbol{a}}} \iver{\boldsymbol{a} \text{ is a cluster from i}} \iver{S_{\boldsymbol{a}} \supseteq S_{a}} \\ &= 2^\ell \ell! \frac{1}{t}\sum_{\boldsymbol{a} : |\boldsymbol{a}| = \ell} \sum_b \abs{v_b \partial_b x^{\boldsymbol{a}}} \iver{\boldsymbol{a} \text{ is a cluster from i}} \sum_{a : S_{a} \ni i} \iver{S_{\boldsymbol{a}} \supseteq S_{a}} \\ &\leq 2^\ell \frac{1}{t} \binom{\ell(k-1)}{k-1} 16^k\ell! \sum_{\boldsymbol{a} : |\boldsymbol{a}| = \ell} \sum_b \abs{v_b \partial_b x^{\boldsymbol{a}}} \iver{\boldsymbol{a} \text{ is a cluster from i}} \\ &\leq 2^\ell \frac{1}{t} \binom{\ell(k-1)}{k-1}16^k e^2 k \ell! \ell (egk)^{\ell - 1}\\ &\leq 2^\ell \frac{1}{t}(16 e \ell)^k e^2 k \ell \cdot \ell! (egk)^{\ell-1} \end{align}\] In the second line, we use 14. In the third line, we use the fact that \(i \in S_a \subseteq S_{\boldsymbol{a}}\), and so \(\boldsymbol{a} \cup \{\{i\}\}\) is a cluster. In the fourth line, we use triangle inequality. In the fifth line, we move the order of the sums. The sixth line uses that a cluster with \(\ell\) elements has support size at most \(\ell(k-1)+1\), so the number of possible subsets \(S_a\) with \(k\) elements (but still containing \(i\)) is at most \(\binom{\ell(k-1)}{k-1}\), and the number of possible Paulis \(\overline{P}\) supported on \(S_a\) is at most \(16^k\). The seventh line uses 13. The last line uses that \(\binom{b}{c} \leq (be/c)^c\). Since this holds for all \(i\), we have the desired bound. ◻

Proof of 10. Let \(\overline{P}\) and \(\overline{Q}\) be \(k\)-local. Recall from 22 that \(E(x)\) can be written as \[\begin{align} E_{\overline{P}}(x) &= t (A x)_{\overline{P}} + \sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \E_{R\sim\mathcal{P}_{S_{\overline{P}}}}[\ntr(\mathcal{L}^\ell_x(R)P_2 R P_1)], \end{align}\] where \(A = A_k\) is the matrix defined in [not:A]. Thus, \(J(x) - A\) is given by \[J_{\overline{P},\overline{Q}}(x) - A_{\overline{P}, \overline{Q}} = \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \E_{R\sim \mathcal{P}_{S_{\overline{P}}}}[\partial_{x_{\overline{Q}}}\ntr(\mathcal{L}_x^\ell(R)P_2 R P_1)] = \sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} J^{(\ell)}_{\overline{P}, \overline{Q}}(x).\] Thus, using 15, we have \[\begin{align} \norm{J(x) - A}_{B_1 \to B_1} &\leq \sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \Vert J^{(\ell)}(x)\Vert_{B_1 \to B_1}\\ &\leq \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} 2^\ell k e^{k+2} \ell^k 16^k (\ell+1)! (egk)^{\ell - 1}\\ &= \frac{1}{t}\cdot 4e^{k+3}16^k k^2 gt^2 \sum_{\ell=2}^\infty (\ell +1) \ell^k (2egkt)^{\ell-2}\\ &\leq \frac{1}{t} \cdot 4e^{k+3}16^k k^2 gt^2 \sum_{\ell=1}^\infty (\ell +1) \ell^k 2^{-\ell+2}\\ &\leq \frac{1}{t} \cdot 32e^{k+3}16^k k^2 gt^2 \sum_{\ell=1}^\infty \frac{\ell^{k+1}}{2^\ell}\\ &\leq \frac{1}{t} \cdot 32e^{k+3}16^k k^2 gt^2 \cdot 2^{k+1}(k+1)!\\ &\leq \frac{1}{t} \cdot 2^{7k+12} gt^2 \cdot (k+3)!\\ &\leq gt \cdot (23k)!. \end{align}\] In the second line, we use 15. In the fourth line, we use \(t < 1/(4egk)\). In the fifth line, we use that \(\ell + 1 \leq 2\ell\) and enlarge the sum to include \(\ell = 1\). ◻

Proof. Consider \(f_{\overline{P}}:[0,1] \to \mathbb{C}\) defined by \(f_{\overline{P}}(s) \triangleq E_{\overline{P}}(\lambda+s\Delta)/t\). Then, by the Fundamental Theorem of Calculus, \[f_{\overline{P}}(1) - f_{\overline{P}}(0) = \int_0^1 \partial_s f_{\overline{P}}(s)\,ds.\] Expanding both sides and using \(\partial_s = \sum_{\overline{Q}} \Delta_{\overline{Q}} \partial_{\overline{Q}}\), we see that \[\mathcal{F}_{\overline{P}}(x) = \int_0^1 \sum_{\overline{Q}} \Delta_{\overline{Q}} J_{\overline{P},\overline{Q}}(\lambda+s\Delta)\,ds = \int_0^1 (J(\lambda+s\Delta) \Delta)_{\overline{P}}\,ds.\] Subtracting \((A\Delta)\) from both sides, we have \[\label{eq:ftc-f-lindblad} \mathcal{F}_{\overline{P}}(x) - (A\Delta)_{\overline{P}} = \int_0^1 ( (J(\lambda+s\Delta) - A)\Delta)_{\overline{P}}\,ds.\tag{34}\] Bounding the absolute value of this, we have \[\lonorm{\mathcal{F}(x) - (A\Delta)} \leq \int_0^1 \norm{J(\lambda + s\Delta) -A}_{B_1\to B_1}\lonorm{\Delta}\,ds \leq (23k)! 2g t \lonorm{\Delta},\] where in the last inequality, we used 10 applied to \(\lambda + s\Delta\), which has \(\lonorm{\lambda + s\Delta} \leq 2g\). ◻

Proof of 5. Let \(j \in \{0,\dots, T-1\}\). We prove this via induction on \(j\), where at each iteration, we maintain the invariants \[\begin{gather} \label{eq:inductive-hypo} \lonorm{x^{(j)} - \lambda} \leq \eps_j,\\ \deg(x^{(j)}) \leq 3 d. \end{gather}\tag{35}\] For the base case of \(j = 0\), recall that \(x^{(0)} = 0\) and \(\epsilon_0 = g\). Thus, we have \(\lonorm{x^{(0)} - \lambda} = \lonorm{\lambda} \leq g\). Moreover, it is vacuously true that \(\deg(x^{(0)}) \leq 3 d\).

For the inductive step, suppose that the inductive hypotheses hold at iteration \(j\). We will prove that they still hold at iteration \(j +1\). To simplify notation, we drop the iteration index. Let \(x\triangleq x^{(j)}\) denote the current iterate, \(x^+ \triangleq x^{(j+1)}\) the next iterate, \(\Delta \triangleq x - \lambda\) the error vector of the current iterate, \(\Delta^+ \triangleq x^+ -\lambda\) the error vector of the next iterate, \(\eps\triangleq \epsilon_j\) the current error, \(\epsilon^+ \triangleq \epsilon_{j+1} = \epsilon/2\) the desired error of the next iterate, and \(\tau \triangleq \tau_j\) the current threshold. (Note that setting \(\eps\triangleq \epsilon_j\) creates a notational conflict with the “\(\eps\)” used as input to this algorithm. However, in this proof we will only ever use the form \(\eps\) and never the latter input “\(\eps\)”.) We use \(y\) to denote the next iterate before rounding: \[x^+ = \operatorname{Round}_{\epsilon/(4d)}(y) \quad \text{ where } y \triangleq x - A^{-1}\operatorname{Round}_{\tau}\left(\widehat{\mathcal{F}}(x)\right).\] By the inductive hypothesis, \(x\) satisfies 35 . We will show that \(x^+\) satisfies the inductive hypotheses with error parameter \(\epsilon^+ = \epsilon / 2\). It will suffice to analyze the unrounded vector \(y\) and show that \[\label{eq:y-dist} \lonorm{y - \lambda} \leq \frac{\epsilon}{10}.\tag{36}\] To see why, we will first show that this implies all of the inductive hypotheses for \(x^+\) for error parameter \(\epsilon^+\).

Recall that the definition of approximate degree splits the superoperator \(\mathcal{L}_\lambda\) into two parts \(\mathcal{L}_\lambda = \mathcal{L}^{\mathrm{big}}_\lambda + \mathcal{L}^{\mathrm{small}}_\lambda\), where \(\lonorm{\mathcal{L}^{\mathrm{small}}_\lambda} < \epsilon/(100 \cdot 16^k)\), and minimizes \(\deg(\mathcal{L}^{\mathrm{big}}_\lambda)\). From here on, let \(\mathcal{L}^{\mathrm{big}}_\lambda, \mathcal{L}^{\mathrm{small}}_\lambda\) be the parts attained in this minimization, i.e., \[\mathcal{L}^{\mathrm{big}}_\lambda = \mathop{\mathrm{argmin}}_{\mathcal{L}^{\mathrm{big}}: \lonorm{\mathcal{L}_\lambda - \mathcal{L}^{\mathrm{big}}} < \epsilon/(100 \cdot 16^k)} \deg(\mathcal{L}^{\mathrm{big}}),\qquad \mathcal{L}^{\mathrm{small}}_\lambda = \mathcal{L}_\lambda - \mathcal{L}^{\mathrm{big}}_\lambda.\] As discussed in 2.1, without loss of generality, splitting the Lindbladian in this way simply selects a subset of the coefficients to include in either \(\mathcal{L}^{\mathrm{big}}_\lambda\) or \(\mathcal{L}^{\mathrm{small}}_\lambda\). In other words, if \(\lambda^{\mathrm{big}}\) are the coefficients of \(\mathcal{L}^{\mathrm{big}}_\lambda\) and \(\lambda^{\mathrm{small}}\) are the coefficients of \(\mathcal{L}^{\mathrm{small}}_\lambda\), then we may assume that the supports of \(\lambda^{\mathrm{big}}\) and \(\lambda^{\mathrm{small}}\) are disjoint. Let \(W^{\mathrm{big}}\) denote the set of pairs of Paulis which are nonzero in \(\lambda^{\mathrm{big}}\), and let \(W^{\mathrm{small}}\) denote the set of remaining pairs of Paulis.

Let \(\Pi_{\lambda^{\mathrm{big}}}\) denote the coordinate projection onto \(W^{\mathrm{big}}\), i.e., the indices of coefficients included in \(\mathcal{L}^{\mathrm{big}}_\lambda\), and let \(\Pi_{\lambda^{\mathrm{small}}}\) denote the projection onto \(W^{\mathrm{small}}\). Note that \(\Pi_{\lambda^{\mathrm{small}}} = I - \Pi_{\lambda^{\mathrm{big}}}\). For the first hypothesis in 35 , we can bound the contributions after projecting onto \(\Pi_{\lambda^{\mathrm{big}}}\) and \(\Pi_{\lambda^{\mathrm{small}}}\) separately: \[\begin{align} \lonorm{\Pi_{\lambda^{\mathrm{big}}}(x^+ - \lambda)} &\leq \lonorm{\Pi_{\lambda^{\mathrm{big}}}(x^+ - y)} + \lonorm{\Pi_{\lambda^{\mathrm{big}}}(y - \lambda)} \\ &\leq \norm{\Pi_{\lambda^{\mathrm{big}}}}_{\infty \to B_1} \infnorm{x^+ - y} + \lonorm{y - \lambda} \\ &\leq d \frac{\eps}{4 d} + \frac{\eps}{10} \\ &= \frac{7\epsilon}{20}. \end{align}\] In the second line, we use that, since \(\Pi_{\lambda^{\mathrm{big}}}\) is a coordinate projection, then \(\norm{\Pi_{\lambda^{\mathrm{big}}}}_{B_1 \to B_1} \leq 1\). In the third line, we use that \(d = \deg(\mathcal{L}^{\mathrm{big}}_\lambda)\) so that \(\norm{\Pi_{\lambda^{\mathrm{big}}}}_{\infty\to B_1} \leq d\). We also use that \(x^+ = \operatorname{Round}_{\epsilon/(4d)}(y)\) and 36 . For the \(\Pi_{\lambda^{\mathrm{small}}}\) part, let \(U_y \triangleq \{\overline{P}: |y_{\overline{P}}| \leq \epsilon/(4d) \}\), and define \(\Pi_{U_y}\) to be the coordinate projection onto this set. In this way, then \(x^+ = (I-\Pi_{U_y})y\) so that \[\begin{align} \Pi_{\lambda^{\mathrm{small}}}(x^+ - \lambda) = \Pi_{\lambda^{\mathrm{small}}}(I-\Pi_{U_y})y - \Pi_{\lambda^{\mathrm{small}}}\lambda &= \Pi_{\lambda^{\mathrm{small}}}(I-\Pi_{U_y})(y-\lambda) - \Pi_{\lambda^{\mathrm{small}}}\Pi_{U_y}\lambda\\ &= \Pi_{\lambda^{\mathrm{small}}}(I-\Pi_{U_y})(y-\lambda) - \Pi_{U_y}\Pi_{\lambda^{\mathrm{small}}}\lambda, \end{align}\] where in the last step we used the fact that \(\Pi_{U_y}\) and \(\Pi_{\lambda^{\mathrm{small}}}\) are coordinate projections and hence commute. Bounding the \(B_1\)-norm of this, we have \[\begin{align} \lonorm{\Pi_{\lambda^{\mathrm{small}}}(x^+ - \lambda)} &\leq \lonorm{\Pi_{\lambda^{\mathrm{small}}}(I - \Pi_{U_y})(y-\lambda)} + \lonorm{\Pi_{U_y}\Pi_{\lambda^{\mathrm{small}}}\lambda}\\ &\leq \norm{\Pi_{\lambda^{\mathrm{small}}}}_{B_1\to B_1}\norm{I-\Pi_{U_y}}_{B_1\to B_1}\lonorm{y-\lambda} + \norm{\Pi_{U_y}}_{B_1\to B_1}\lonorm{\Pi_{\lambda^{\mathrm{small}}} \lambda}\\ &\leq \frac{\eps}{10} + \frac{\eps}{100 \cdot 16^k}\label{eq:small-bound} \\ &\leq \frac{41\eps}{400}. \end{align}\tag{37}\] Here, we use that \(\norm{\Pi_{\lambda^{\mathrm{small}}}}_{B_1\to B_1}, \norm{\Pi_{U_y}}_{B_1\to B_1}, \norm{I - \Pi_{U_y}}_{B_1\to B_1} \leq 1\) (since they’re coordinate projections), 36 , and \(\lonorm{\mathcal{L}^{\mathrm{small}}_\lambda} \leq \epsilon/(100 \cdot 16^k)\). Combining these, we have \[\begin{align} \lonorm{x^+ - \lambda} &\leq \lonorm{\Pi_{\lambda^{\mathrm{big}}}(x^+ - \lambda)} + \lonorm{\Pi_{\lambda^{\mathrm{small}}}(x^+ - \lambda)} \leq \eps/2. \end{align}\] For the second hypothesis in 35 , note that \[\label{eq:deg-bound} \deg(x^+) \leq \deg(\Pi_{\lambda^{\mathrm{big}}} x^+) + \deg(\Pi_{\lambda^{\mathrm{small}}} x^+) \leq d + \deg(\Pi_{\lambda^{\mathrm{small}}} x^+),\tag{38}\] where the first inequality uses that \(I = \Pi_{\lambda^{\mathrm{big}}} + \Pi_{\lambda^{\mathrm{small}}}\). The second inequality uses that \(d = \deg(\mathcal{L}^{\mathrm{big}})\). To bound the second term, consider a fixed qubit \(i \in [n]\). Notice that \[\lonorm{\Pi_{\lambda^{\mathrm{small}}} x^+} \leq \lonorm{\Pi_{\lambda^{\mathrm{small}}} (x^+ - \lambda)} + \lonorm{\Pi_{\lambda^{\mathrm{small}}} \lambda} \leq \frac{\eps}{10} + \frac{2\eps}{100\cdot 16^k} \leq \frac{\epsilon}{2},\] where the last inequality uses 37 and \(\lonorm{\mathcal{L}^{\mathrm{small}}_\lambda} \leq \epsilon/(100\cdot 16^k)\). Then, because the overall \(B_1\)-norm of \(\Pi_{\lambda^{\mathrm{small}}} x^+\) is less than \(\epsilon/2\), the number of entries of \(\Pi_{\lambda^{\mathrm{small}}} x^+\) of magnitude at least \(\eps/(4d)\) (which, due to the rounding in \(x^+\), are the only nonzero entries in \(\Pi_{\lambda^{\mathrm{small}}} x^+\)) whose support contains a fixed qubit \(i\) is at most \(2d\). The degree of \(\Pi_{\lambda^{\mathrm{small}}} x^+\) is bounded by the number of elements of \(x^+\). Thus, together with 38 , \(\deg(x^+) \leq 3d\), so the second hypothesis in 35 is satisfied.

Now, it remains to prove 36 . We define two sets of coordinates. Define \[\begin{align} U_{\tau} &\triangleq \left\{(Q_1,Q_2): \left|\widehat{\mathcal{F}}_{Q_1,Q_2}(x)\right| \geq \tau\right\}, \\ V &\triangleq \left\{(Q_1,Q_2): (Ax)_{Q_1, Q_2} \neq 0 \text{ or } (A\lambda^{\mathrm{big}})_{Q_1, Q_2} \neq 0\right\}, \end{align}\] and let \(\Pi_{U_\tau}\) and \(\Pi_V\) be the coordinate projections onto \(U_\tau\) and \(V\), respectively. In particular, \(\Pi_{U_\tau} (\widehat{\mathcal{F}}(x)) = \operatorname{Round}_\tau(\widehat{\mathcal{F}}(x))\).

We can write \(y-\lambda\) in terms of these projectors: \[\begin{align} y - \lambda &= x - A^{-1} \Pi_{U_\tau} \left(\widehat{\mathcal{F}}(x)\right) - \lambda\\ &=\Delta - A^{-1} \Pi_{U_\tau} \left(\widehat{\mathcal{F}}(x)\right)\\ &=\Delta - A^{-1} \Pi_{U_\tau}\left(\mathcal{F}(x)\right) \underbrace{- A^{-1} \Pi_{U_\tau} \left(\eta(x)\right)}_{\triangleq \operatorname{err}_1} \\ &= \Delta - A^{-1} \Pi_{U_\tau} (A \Delta) + \underbrace{A^{-1} \Pi_{U_\tau}\left(A \Delta - \mathcal{F}(x)\right)}_{\triangleq \operatorname{err}_2} + \operatorname{err}_1 \\ &= \Delta - A^{-1} A \Delta + \underbrace{A^{-1}(I - \Pi_{U_\tau}) A \Delta}_{\triangleq \operatorname{err}_3} + \operatorname{err}_2 + \operatorname{err}_1 \\ &= \operatorname{err}_3 + \operatorname{err}_2 + \operatorname{err}_1.\label{eq:errs} \end{align}\tag{40}\] Thus, there are three forms of error we need to bound. The first error \(\operatorname{err}_1\) comes from only having approximate access to \(\widehat{\mathcal{F}}\) (as in 33 ). The second error \(\operatorname{err}_2\) comes from the impact of the higher-order terms of \(\mathcal{F}(x)\), which we bounded in 7. The third error \(\operatorname{err}_3\) comes from the rounding of each \(\widehat{\mathcal{F}}(x)\). In the following, we bound each error separately.

Now, we can bound each of the error terms in 40 . First, consider \(\operatorname{err}_1\), the error from the approximation to \(\widehat{\mathcal{F}}(x)\), which we can bound as follows. \[\lonorm{\operatorname{err}_1} = \left\|A^{-1} \Pi_{U_\tau} \eta(x)\right\|_{B_1} \leq \norm{A^{-1}}_{B_1 \to B_1}\norm{\Pi_{U_\tau}}_{\infty\to B_1} \norm{\eta(x)}_\infty \leq 4^k \frac{\epsilon}{30 \cdot 4^k \eta} \eta = \frac{\epsilon}{30},\] where we use 7, [claim:round-set], and 33 . In the last inequality, we also use our choice of \(\eta\).

Next, consider \(\operatorname{err}_2\), the error from the higher-order terms of \(\mathcal{F}(x)\). \[\begin{align} \lonorm{\operatorname{err}_2} &= \lonorm{A^{-1} \Pi_{U_\tau}(A \Delta - \mathcal{F}(x))} \\ &\leq \norm{A^{-1}}_{B_1 \to B_1}\norm{\Pi_{U_\tau}}_{B_1 \to B_1} \lonorm{(A \Delta - \mathcal{F}(x))} \\ &\leq 4^{k} c t \lonorm{\Delta}\\ &\leq 4^{k} c t \epsilon\\ &\leq \frac{\epsilon}{30}. \end{align}\] where \(c = (23k)! 2g\). In the third line, we use 7, \(\norm{\Pi_{U_\tau}}_{B_1\to B_1} \leq 1\) since \(\Pi_{U_\tau}\) is a coordinate projection, and 7. In the second to last line, we also use the inductive hypothesis that \(\lonorm{\Delta} \leq \epsilon\). In the last line, we use our choice of \(t\).

Finally, consider \(\operatorname{err}_3\), the error from rounding. We further break this error up into two parts, corresponding to whether the terms are in \(V\) or not. \[\begin{align} \lonorm{\operatorname{err}_3} &= \lonorm{A^{-1}(I - \Pi_{U_\tau})A \Delta}\\ &\leq \norm{A^{-1}}_{B_1 \to B_1}\lonorm{(I-\Pi_{U_\tau}) A \Delta}\\ &\leq 4^k\parens[\Big]{\lonorm{(I-\Pi_{U_\tau})(I - \Pi_V) A \Delta} + \lonorm{(I-\Pi_{U_\tau})\Pi_V A \Delta}}\\ &= 4^k\parens[\Big]{\lonorm{\underbrace{(I-\Pi_{U_\tau})(I - \Pi_V) A \Delta}_{\triangleq \operatorname{err}_4}} + \lonorm{\underbrace{\Pi_V (I-\Pi_{U_\tau}) A \Delta}_{\triangleq \operatorname{err}_5}}}, \end{align}\] where in the third line, we used 7, and in the fourth line, we used the fact that \(\Pi_V\) and \((I-\Pi_{U_\tau})\) are coordinate projections and hence commute.

To bound \(\operatorname{err}_4\), note that \[(I - \Pi_V) A \Delta = (I - \Pi_V) A (x - \lambda^{\mathrm{big}}) - (I - \Pi_V) A \lambda^{\mathrm{small}}= -(I - \Pi_V) A \lambda^{\mathrm{small}}\] by definition of \(V\). Then, we can bound \[\begin{align} \lonorm{\operatorname{err}_4} \leq \lonorm{(I - \Pi_V) A \lambda^{\mathrm{small}}} \leq 4^k \cdot \frac{\epsilon}{100\cdot 16^k} = \frac{\epsilon}{100\cdot 4^k}, \end{align}\] where in the first inequality, we use \(\norm{I-\Pi_{U_\tau}}_{B_1 \to B_1} \leq 1\). In the second inequality, we use \(\norm{I-\Pi_V}_{B_1\to B_1} \leq 1\), 7, and \(\lonorm{\mathcal{L}^{\mathrm{small}}_\lambda} \leq \epsilon/(100\cdot 16^k)\). To bound \(\operatorname{err}_5\), recall that for coordinates not in \(U_\tau\), \[\begin{align} \abs{\mathcal{F}_{Q_1, Q_2}(x)} \leq \abs{\widehat{\mathcal{F}}_{Q_1, Q_2}(x)} + \eta \leq \tau + \eta \leq 2\tau, \end{align}\] where we use that \(\eta \leq \tau\). Consequently, we can conclude that \[\begin{align} \lonorm{\operatorname{err}_5} &= \lonorm{\Pi_V (I - \Pi_{U_\tau}) A \Delta} \\ &\leq \lonorm{\Pi_V (I - \Pi_{U_\tau}) \mathcal{F}(x) } + c t \eps \\ &\leq \norm{\Pi_V}_{\infty \to B_1} \infnorm{(I - \Pi_{U_\tau}) \mathcal{F}(x)} + c t \eps\\ &\leq 4^k (4d) 2\tau + c t \eps\\ &\leq \frac{\epsilon}{50 \cdot 4^k}, \end{align}\] where \(c = (23k)! 2g\). In the second line, we use 7. In the fourth line, we use [claim:round-set] and 39 . In the last line, we use our choice of \(t\) and \(\tau\).

Overall, plugging the bounds on the three errors back into 40 , we have \[\begin{align} \lonorm{y - \lambda} &\leq \lonorm{\operatorname{err}_1} + \lonorm{\operatorname{err}_2} + \lonorm{\operatorname{err}_3} \\ &\leq \lonorm{\operatorname{err}_1} + \lonorm{\operatorname{err}_2} + 4^k(\lonorm{\operatorname{err}_4} + \lonorm{\operatorname{err}_5})\\ &\leq \frac{\epsilon}{30} + \frac{\epsilon}{30} + \frac{\epsilon}{100} + \frac{\epsilon}{50}\\ &\leq \frac{\epsilon}{10}, \end{align}\] as required. As discussed after 36 , this completes the proof. ◻

Proof of 4. This follows by instantiating 6 with our choice of \(t,\eta,\Gamma\). We have that \[\Gamma \leq \frac{\log(4/(t\eta))}{\log(1/(2ekgt))} = \mathcal{O}(C_k \log(dg/\epsilon)),\] where \(C_k\) is some constant that depends only on \(k\). Then, taking \(k = \mathcal{O}(1)\), the time complexity simplifies to the claimed quantity. ◻

Proof of 6. First, we can estimate the expectation values \(E_{\overline{P}}(\lambda)\) using our query access to \(e^{\mathcal{L}t}\). In particular, by 3, we can obtain estimates \(\widehat{E}_{P_1,P_2}(\lambda)\) such that \[|\widehat{E}_{P_1,P_2}(\lambda) - E_{P_1,P_2}(\lambda)| \leq \frac{t\eta}{2}\] with probability at least \(1-\delta\) using \(\Theta(C^k\log(n/\delta)/(t\eta)^2)\) queries to the evolution operator \(e^{\mathcal{L}t}\), for some absolute constant \(C > 0\). Because each query evolves for time \(t\), this corresponds to the stated total evolution time. It remains to show that we can obtain estimates \(\widehat{E}_{P_1,P_2}(x)\) such that \[\label{eq:e-hat} |\widehat{E}_{P_1,P_2}(x) - E_{P_1,P_2}(x)| \leq \frac{t\eta}{2}.\tag{41}\] To do so, consider Taylor expanding out \(e^{\mathcal{L}_xt}\) in the expression for \(E_{P_1,P_2}(x)\) up to degree \[\Gamma \triangleq \left\lceil \frac{\log(4/(t\eta))}{\log(1/(2ek{g}t))} - 1\right\rceil.\] In other words, we approximate \[\label{eq:e-hat-series} \widehat{E}_{P_1,P_2}(x) \triangleq \sum_{\ell=1}^\Gamma \frac{t^\ell}{\ell!}\E_{R\sim \mathcal{P}_{S_{\overline{P}}}}[\ntr(R \mathcal{L}_x^{\dagger \ell}(P_2 R P_1))].\tag{42}\] To show that this indeed satisfies 41 , by triangle inequality, we have \[|\widehat{E}_{P_1,P_2}(x) - E_{P_1,P_2}(x)| \leq \sum_{\ell=\Gamma + 1}^\infty \frac{t^\ell}{\ell!}\E_{R\sim\mathcal{P}_{S_{\overline{P}}}}[|\ntr(R \mathcal{L}_x^{\dagger \ell}(P_2 R P_1))|].\] We can bound each of these terms using 6: \[|\ntr(R \mathcal{L}^{\dagger \ell}(P_2 R P_1))| \leq \frac{1}{N}\norm{R}_{\tr} \norm{\mathcal{L}_x^{\dagger \ell}(P_2 R P_1)}_{\mathrm{op}} \leq \ell! (2ek{g})^\ell.\] Plugging back into the above, we get \[|\widehat{E}_{P_1,P_2}(x) - E_{P_1,P_2}(x)| \leq \sum_{\ell=\Gamma + 1}^\infty (2ek{g}t)^\ell = \frac{(2ek{g}t)^{\Gamma +1}}{1-2ek{g}t} \leq 2(2ek{g}t)^{\Gamma + 1} \leq \frac{t\eta}{2},\] where in the equality, we use the sum of a geometric series when \(2ek{g}t \leq 1\). In the second to last inequality, we use \(2e k{g}t < 1/2\). In the last inequality, we use our choice of \(\Gamma\).

We want to bound the time complexity of computing this truncated series expansion. The time complexity of such operations is analyzed in detail in haah2024learning?. The same analysis applies here because the Lindbladian for which we compute the series expansion has degree \(3d\). This is because, in the proof of 5, we maintain the invariant that \(x\) has degree \(3d\). Thus, the analysis in haah2024learning? for computing the series yields a time complexity of \[\mathcal{O}(kmd\log d + ed(1+e(d-1))^\Gamma(4^\Gamma + k)\poly(\Gamma)),\] where \(m\) is the number of terms in the Lindbladian. In addition, we have the time complexity from 1, which by 3, costs \(\mathcal{O}((Cn)^k \log(n/\delta)/(t\eta)^2)\) for an absolute constant \(C\). ◻

Proof. In this case, \[\lonorm{\lambda} = \max_{i \in [n]} \sum_{\overline{P}: S_{\overline{P}} \ni i} |\lambda_{\overline{P}}| \leq \max_{i \in [n]} |\{\overline{P}: S_{\overline{P}} \ni i\}| \leq d,\] where we use that every qubit interacts with at most \(d\) nonzero terms. Moreover, note that \(\deg_\epsilon(\lambda) \leq d\). We can decompose \(\mathcal{L}_\lambda = \mathcal{L}^{\mathrm{big}}_\lambda + \mathcal{L}^{\mathrm{small}}_\lambda\), where \(\mathcal{L}^{\mathrm{big}}_\lambda = \mathcal{L}_\lambda\) and \(\mathcal{L}^{\mathrm{small}}_\lambda = 0\). In this way, \(\lonorm{\mathcal{L}^{\mathrm{small}}_\lambda} = 0 < \epsilon\), and \(\deg_\epsilon(\mathcal{L}_\lambda) \leq \deg(\mathcal{L}_\lambda) = d\). Taking \(g = d\) in 1 gives the result. ◻

Proof. First, we can easily bound the local one-norm. Let \(i \in [n]\). Then, \[\sum_{\overline{P}: S_{\overline{P}} \ni i} |\lambda_{\overline{P}}| \leq 1,\] where in the inequality, we use ?? for \(j = i\). This holds for all \(i \in [n]\), so we see that \(\lonorm{\lambda} \leq 1\).

To bound the approximate degree, consider decomposing \(\mathcal{L}_\lambda = \mathcal{L}^{\mathrm{big}}_\lambda + \mathcal{L}^{\mathrm{small}}_\lambda\), where \(\mathcal{L}^{\mathrm{small}}\) is the part of \(\mathcal{L}_\lambda\) with coefficients indexed by \(\overline{P}\) such that \(\mathop{\mathrm{diam}}(S_{\overline{P}}) > r\), where \(r = 4\gamma(p\log(2(1+2\gamma)) + \log(100\cdot 16^k/\epsilon))\), i.e., \[\lambda^{\mathrm{small}}_{\overline{P}} \triangleq \lambda_{\overline{P}}\iver{\mathop{\mathrm{diam}}(S_{\overline{P}}) > r},\qquad \lambda^{\mathrm{big}}\triangleq \lambda - \lambda^{\mathrm{small}}.\] Then, if \(\lonorm{\lambda^{\mathrm{small}}} \leq \epsilon/(100\cdot 16^k)\), we have \(\deg_{\epsilon/(100\cdot 16^k)}(\mathcal{L}_\lambda) \leq \deg(\mathcal{L}^{\mathrm{big}})\). First, we show that \(\lonorm{\lambda^{\mathrm{small}}} \leq \epsilon/(100\cdot 16^k)\). Let \(i \in [n]\). Then, \[\begin{align} \sum_{\overline{P}: S_{\overline{P}} \ni i} |\lambda^{\mathrm{small}}_{\overline{P}}| &= \sum_{\substack{\overline{P}: S_{\overline{P}} \ni i\\\mathop{\mathrm{diam}}(S_{\overline{P}}) > r}} |\lambda_{\overline{P}}|\\ &\leq \sum_{\substack{j \in [n]\\\mathop{\mathrm{dist}}(i,j) \geq r/2}} \sum_{\substack{\overline{P}\\\{i,j\} \subseteq S_{\overline{P}}}}|\lambda_{\overline{P}}|\\ &\leq \sum_{\substack{j\in [n]\\\mathop{\mathrm{dist}}(i,j) \geq r/2}} e^{-\mathop{\mathrm{dist}}(i,j)/\gamma}\\ &= \sum_{\ell=r/2}^{\infty} \sum_{\substack{j\in[n]\\\mathop{\mathrm{dist}}(i,j)= \ell}} e^{-\ell/\gamma}\\ &\leq 2^p \sum_{\ell=r/2}^\infty \binom{p+\ell-1}{p-1} e^{-\ell/\gamma}\\ &\leq 2^p e^{-r/(4\gamma)} \sum_{\ell=0}^\infty \binom{p+\ell-1}{p-1} e^{-\ell/(2\gamma)}\\ &= 2^p e^{-r/(4\gamma)} (1-e^{-1/(2\gamma)})^{-p}\\ &\leq e^{-r/(4\gamma)}(2(1 +2\gamma))^p\\ &\leq \frac{\epsilon}{100\cdot 16^k}. \end{align}\] In the first line, we use the definition of \(\lambda^{\mathrm{small}}\). In the second line, we use that if \(i \in S_{\overline{P}}\) and \(\mathop{\mathrm{diam}}(S_{\overline{P}}) > r\), there must exist two points \(j, a \in S_{\overline{P}}\) such that \(\mathop{\mathrm{dist}}(j,a) > r\), by definition of diameter. Then, by triangle inequality, one of the two points \(j\) or \(a\), say \(j\), must satisfy \(\mathop{\mathrm{dist}}(i,j) \geq r/2\). In the third line, we use ?? . In the fifth line, we use [fact:volume-bounds]. In the sixth line, we use that \(\ell \geq r/2\) and expand the number of terms in the sum. In the seventh line, we use the identity \[\sum_{\ell=0}^\infty \binom{p+\ell-1}{p-1}x^\ell = (1-x)^{-p}\] for \(x = e^{-1/(2\gamma)}\). In the eighth line, we use \((1-e^{-1/(2\gamma)})^{-1} \leq 1+2\gamma\) and that \(p > 0\). In the last line, we use our choice of \(r\). Since this holds for any \(i \in [n]\), this completes the proof that \(\lonorm{\lambda^{\mathrm{small}}} \leq \epsilon/(100\cdot 16^k)\).

Now, we need to bound \(\deg_{\epsilon/(100\cdot 16^k)}(\mathcal{L}_\lambda) \leq \deg(\mathcal{L}^{\mathrm{big}})\). By definition of \(\lambda^{\mathrm{big}}\), for a given site \(i \in [n]\), if \(i \in S_{\overline{P}}\) and \(\lambda^{\mathrm{big}}_{\overline{P}} \neq 0\), then \(\mathop{\mathrm{diam}}(S_{\overline{P}}) \leq r\). By [fact:volume-bounds], there are at most \((2e r)^{pk}\) possible supports that satisfy this. This corresponds to at most \(16^k (2er)^{pk}\) possible Pauli terms \(\overline{P}\). Thus, \[d=\deg_{\epsilon/(100\cdot 16^k)}(\mathcal{L}_\lambda) \leq 16^k(2er)^{pk} \leq C_k(C \gamma p \log(1+\gamma) + k + \log(1/\epsilon))^{pk},\] where \(C > 0\) is an absolute constant, and \(C_k\) is a constant that depends only on \(k\). Plugging in these parameters to 1 gives the result. ◻

Proof. As in the quasi-local case, \(\lonorm{\lambda} \leq 1\). To bound the approximate degree, consider decomposing \(\mathcal{L}_\lambda = \mathcal{L}^{\mathrm{big}}_\lambda + \mathcal{L}^{\mathrm{small}}_\lambda\), where \(\mathcal{L}^{\mathrm{small}}\) is the part of \(\mathcal{L}_\lambda\) with coefficients indexed by \(\overline{P}\) such that \(\mathop{\mathrm{diam}}(S_{\overline{P}}) > r\), where \(r = \left(\frac{\epsilon(\gamma-p)}{100 \cdot 16^k \cdot 2^\gamma(2e)^p}\right)^{-1/(\gamma-p)}\), i.e., \[\lambda^{\mathrm{small}}_{\overline{P}} \triangleq \lambda_{\overline{P}}\iver{\mathop{\mathrm{diam}}(S_{\overline{P}}) > r},\qquad \lambda^{\mathrm{big}}\triangleq \lambda - \lambda^{\mathrm{small}}.\] We first show that \(\lonorm{\lambda^{\mathrm{small}}} < \epsilon/(100 \cdot 16^k)\). The calculation proceeds similarly to the quasi-local case, so we combine a few steps. Let \(i \in [n]\). Then, \[\begin{align} \sum_{\overline{P}: S_{\overline{P}} \ni i} |\lambda^{\mathrm{small}}_{\overline{P}}| &\leq \sum_{\substack{j\in[n]\\\mathop{\mathrm{dist}}(i,j) \geq r/2}} \sum_{\substack{\overline{P}\\\{i,j\} \subseteq S_{\overline{P}}}} |\lambda_{\overline{P}}|\\ &\leq \sum_{\substack{j\in[n]\\\mathop{\mathrm{dist}}(i,j) \geq r/2}} \frac{1}{\mathop{\mathrm{dist}}(i,j)^\gamma}\\ &= \sum_{\ell=r/2}^\infty \sum_{\substack{j\in[n]\\\mathop{\mathrm{dist}}(i,j) = \ell}} \frac{1}{\ell^\gamma}\\ &\leq 2^p e^{p-1}\sum_{\ell=r/2}^\infty \frac{(\ell+1)^{p-1}}{\ell^\gamma}\\ &\leq (4e)^p \sum_{\ell=r/2}^\infty \ell^{p-1-\gamma}\\ &\leq (4e)^p \int_{r/2-1}^\infty x^{p-1-\gamma}\,dx\\ &\leq (4e)^p \frac{r^{p-\gamma}}{2^{p-\gamma}(\gamma - p)}\\ &\leq \frac{\epsilon}{100\cdot 16^k}. \end{align}\] In the second line, we use ?? . In the fourth line, we use [fact:volume-bounds]. In the fifth line, we use that \(\ell + 1 \leq 2\ell\) for \(\ell \geq 1\). In the last line, we use our choice of \(r\).

Now, we need to bound \(\deg_{\epsilon/(100\cdot 16^k)}(\mathcal{L}_\lambda) \leq \deg(\mathcal{L}^{\mathrm{big}})\). By definition of \(\lambda^{\mathrm{big}}\), for a given site \(i \in [n]\), if \(i \in S_{\overline{P}}\) and \(\lambda^{\mathrm{big}}_{\overline{P}} \neq 0\), then \(\mathop{\mathrm{diam}}(S_{\overline{P}}) \leq r\). By [fact:volume-bounds], there are at most \((2e r)^{pk}\) possible supports that satisfy this. This corresponds to at most \(16^k (2er)^{pk}\) possible Pauli terms \(\overline{P}\). Thus, for \(\gamma - p = \Omega(1)\) and \(k,p = \mathcal{O}(1)\), we have \[d=\deg_{\epsilon/(100\cdot 16^k)}(\mathcal{L}_\lambda) \leq 16^k(2er)^{pk} = \mathcal{O}\left(\frac{2^\gamma}{\epsilon}\right)^{pk/(\gamma-p)}.\] Plugging into 1 gives the result. ◻

Proof. In this case, we can naively bound \(d\) as \[d \leq \deg(\mathcal{L}_\lambda) \leq 16^k\binom{n-1}{k-1} \leq 16^k n^{k-1}.\] Plugging this into 1 gives the result. ◻

Proof. As in the proof of 7, consider \(f_P: [0,1] \to \C\) defined by \(f_P(s) \triangleq E_P(\lambda + s\Delta)\). Then, by the Fundamental Theorem of Calculus, \[f_P(1) - f_P(0) = \int_0^1 \partial_s f_P(s)\,ds.\] Expanding both sides and using \(\partial_s = \sum_Q \Delta_Q \partial_Q\), we see that \[\mathcal{F}_P(x) = \int_0^1 \sum_Q \Delta_Q J_{P,Q}(\lambda + s\Delta)\,ds.\] Subtracting \(\Delta\) from both sides, we have \[\mathcal{F}_P(x) - \Delta_P = \int_0^1 \sum_Q \Delta_Q (J_{P,Q}(\lambda + s\Delta) - \delta_{P,Q})\,ds = \int_0^1 \sum_{Q \in S_H} \Delta_Q (J_{P,Q}(\lambda + s\Delta) -\delta_{P,Q})\,ds,\] where in the last equality, we use that \(\Delta_Q = 0\) unless \(Q \in S_H\). Taking the absolute value of both sides, we have \[\begin{align} |\mathcal{F}_P(x) - \Delta_P| &\leq \int_0^1 \sum_{Q \in S_H}|J_{P,Q}(\lambda + s\Delta) - \delta_{P,Q}| |\Delta_Q| \,ds\\ &\leq \int_0^1 \sum_{Q \in S_H}|J_{P,Q}(\lambda + s\Delta) - \delta_{P,Q}|\,ds \cdot \norm{\Delta}_\infty\\ &\leq c_{2g}t\norm{\Delta}_\infty. \end{align}\] In the last line, we use the bound on the Jacobian for \(\lambda + s\Delta\), where \(\lonorm{\lambda + s\Delta} \leq 2g\). This holds for all \(P \in \mathcal{P}_{k}\), so this gives the claim. The proof is the same for the Gibbs state case. ◻

Proof of 7. In this case, the proof is short. Let \(j \in \{0,\dots, T-1\}\). We prove this via induction on \(j\), where at each iteration, we maintain the invariants \[\label{eq:inductive-hypo-ham} \begin{gather} \norm{x^{(j)} - \lambda}_\infty \leq \epsilon_j,\\ |x^{(j)}_P| \leq 2|\lambda_P| \end{gather}\tag{44}\] For the base case of \(j = 0\), recall that \(x^{(0)} = 0\) and \(\epsilon_0 = 1\). Thus, we have \(\norm{x^{(0)} - \lambda}_\infty = \norm{\lambda}_\infty \leq 1\), as required. Moreover, \(|x_P^{(0)}| = 0 \leq 2|\lambda_P|\) is trivially satisfied.

For the inductive step, suppose that \(\norm{x^{(j)} - \lambda}_\infty \leq \epsilon_j\) and \(|x_P^{(j)}| \leq 2|\lambda_P|\). We prove that this holds for iteration \(j + 1\). For brevity, we drop the iteration index. Let \(x\triangleq x^{(j)}\) denote the current iterate, \(x^+ \triangleq x^{(j+1)}\) the next iterate, \(\Delta \triangleq x - \lambda\) the error vector of the current iterate, \(\Delta^+ \triangleq x^+ -\lambda\) the error vector of the next iterate, \(\eps\triangleq \epsilon_j\) the current error, and \(\epsilon^+ \triangleq \epsilon_{j+1} = \epsilon/2\) the desired error of the next iterate. We use \(y\) to denote the next iterate before rounding: \[x^+ \triangleq \operatorname{Round}_{\epsilon/4}(y),\qquad y \triangleq x - \widehat{\mathcal{F}}(x).\] Note that it suffices to show that \[\norm{y - \lambda}_\infty \leq \frac{\epsilon}{10}.\] This implies 44 with error parameter \(\epsilon^+\): \[\norm{x^+ - \lambda}_\infty \leq \norm{x^+ - y}_\infty + \norm{y - \lambda}_\infty \leq \frac{\epsilon}{4} + \frac{\epsilon}{10} \leq \frac{\epsilon}{2} = \epsilon^+.\] For the second hypothesis in 44 , consider a parameter indexed by a Pauli \(P\). Then, either the rounding kicks in so that \(x_P^+ = 0\), in which case the bound is immediate, or \(|y_P| > \epsilon/4\). In the latter case, by the reverse triangle inequality, then \[|\lambda_P| \geq |y_P| - \frac{\epsilon}{10} > \frac{3\epsilon}{20},\] so \[|x_P^+| = |y_P| \leq |\lambda_P| + \frac{\epsilon}{10} \leq 2|\lambda_P|,\] so that 44 holds. Thus, it suffices to show that \(\norm{y - \lambda}_\infty \leq \epsilon/10\). We show this as follows: \[y - \lambda = x - \widehat{\mathcal{F}}(x) - \lambda = \Delta - \mathcal{F}(x) \underbrace{-\eta(x)}_{\triangleq\mathrm{err}_1} = \Delta - \Delta + \underbrace{\left(\Delta - \mathcal{F}(x)\right)}_{\triangleq \mathrm{err}_2} + \mathrm{err}_1 = \mathrm{err}_2 + \mathrm{err}_1.\] Then, we can bound each of the errors as follows: \[\norm{\operatorname{err}_1}_\infty \leq \frac{\epsilon}{20}\] by the hypothesis of the theorem. Also, \[\norm{\operatorname{err}_2}_\infty = \norm{\Delta - \mathcal{F}(x)}_\infty \leq c_{2g}t\norm{\Delta}_\infty \leq \frac{\epsilon}{20},\] where we use the inductive hypothesis and 16. Note that the hypothesis of 16, that \(\Delta_P = 0\) unless \(P \in S_H\), holds because we maintain the invariant \(|x_P| \leq 2|\lambda_P|\). Putting everything together, \(\norm{y-\lambda}_\infty \leq \epsilon/10\), as required. The proof is the same in the Gibbs state case via 16. ◻

Proof of 8. We proceed as in the proof of 6. First, by 3, we can obtain estimates \(\widehat{E}_P(\lambda)\) such that \[|\widehat{E}_P(\lambda) - E_P(\lambda)| \leq \frac{t\epsilon}{40}\] for all \(k\)-local Paulis \(P\) with probability at least \(1-\delta\) using \(\Theta(C^k \log(n/\delta)/(t\epsilon)^2)\) queries to the time evolution operator \(e^{-\ii Ht}\), for some absolute constant \(C > 0\). This corresponds to a total time evolution of \(\Theta(C^k \log(n/\delta)/(t\epsilon^2)) = \Theta(C_k g\log(n/\delta)/\epsilon^2)\) for some constant \(C_k > 0\) that depends only on the locality \(k\). As in 6, we can obtain estimates \(\widehat{E}_P(x)\) such that \[|\widehat{E}_P(x) - E_P(x)| \leq \frac{t\epsilon}{40}\] also by Taylor expanding \(e^{-\ii Ht}\) up to degree \[\Gamma \triangleq \left\lceil \frac{\log(160/(t\epsilon))}{\log(1/(2ekgt))} - 1 \right\rceil,\] by the same analysis as before. This gives us an approximation of \(\mathcal{F}(x)\) up to \(\epsilon/20\) error. Moreover, the Jacobian bound needed in 7 is clearly implied by 17: \[\sum_{Q \in S_H}|J_{P,Q}(x) -\delta_{P,Q}| \leq \sum_Q |J_{P,Q}(x) - \delta_{P,Q}| = \norm{J(x) - I}_{\infty\to\infty} \leq c_g t.\] ◻

Proof. We prove this by induction on \(\ell\). For the base case of \(\ell=0\), the claim is clear because \([H,Q]_0 = Q\) so that \(\sum_T |d_T| = 1\) and \(\mathrm{supp}(Q) \leq k\). For the inductive step, suppose the result holds for \(\ell\). Then, \[[H,Q]_{\ell+1} = [H,[H,Q]_\ell] = \ii\sum_P \lambda_P [P, [H, Q]_\ell] = \ii\sum_P \lambda_P \sum_T d_{T,\ell}[P, T],\] where in the last equality we use the inductive hypothesis. By the inductive hypothesis, \(\mathrm{supp}(T) \leq k(\ell+1)\). Since \(|S_P| \leq k\), \(|\mathrm{supp}([P, T])| \leq k(\ell+2)\). We can bound the 1-norm of the Pauli coefficients. Note that \(\lambda_P d_{T,\ell}\) is only included when \([P, T] \neq 0\). \[\sum_T |d_{T,\ell+1}| \leq 2 \sum_P \sum_T |\lambda_P||d_{T,\ell}| \iver{T \text{ overlaps with } P}\] Let \(\mathrm{supp}(T) = \{i_1,\dots, i_{k(\ell+1)}\}\) (the argument also works for fewer qubits). Then, we can break up the sum over \(P\) according to whether \(P\) is supported on some qubit \(i_j\). \[\begin{align} \sum_T |d_{T,\ell+1}| &\leq 2 \sum_T |d_{T,\ell}| \left(\sum_{P : S_P \ni i_1} |\lambda_P| + \cdots + \sum_{P : S_P \ni i_{k(\ell+1)}}|\lambda_P|\right)\\ &\leq 2g k(\ell+1) \sum_T |d_{T,\ell}|\\ &\leq 2g k(\ell+1) \ell! (2kg)^\ell\\ &= (\ell+1)!(2kg)^{\ell+1}. \end{align}\] In the second line, we use that \(\lonorm{\lambda} \leq g\). In the third line, we use the inductive hypothesis. ◻

Proof. This is essentially the Leibniz rule, but we prove it for completeness. We proceed via induction. For the base case of \(\ell = 1\), \(\partial_{x_Q} [H(x), T] = [\partial_{x_Q} H(x), T] = [Q, T]\), which is clearly the same as the right-hand side (only the \(j = 0\) term survives and \(\ell - 1- j = 0\)). For the inductive case, suppose the claim holds for \(\ell\). \[\begin{align} \partial_{x_Q} [H(x), T]_{\ell+1} &= \partial_{x_Q} [H(x), [H(x), T]_\ell]\\ &= [\partial_{x_Q} H(x), [H(x), T]_\ell] + [H(x), \partial_{x_Q}[H(x), T]_\ell]\\ &= \ii [Q, [H(x), T]_\ell] + \ii \sum_{j=0}^{\ell-1} [H(x), [H(x), [Q, [H(x), T]_{\ell-1-j}]]_j]\\ &= \ii [Q, [H(x), T]_\ell] + \ii \sum_{j=1}^{\ell} [H(x), [Q, [H(x), T]_{\ell-j}]]_j\\ &= \ii \sum_{j=0}^\ell [H(x), [Q, [H(x), T]_{\ell-j}]]_j. \end{align}\] Here, the second line follows from the Leibniz rule. The third line follows by the inductive hypothesis. The fourth line follows by shifting the index \(j \to j+1\). ◻

Proof. Write \(A = \sum_{R \in \mathcal{P}_n} \alpha_R R\) and \(B = \sum_{S \in \mathcal{P}_n} \beta_S S\). Then, we have \[\sum_{b=1}^M \left|\ntr(A[E_b, B])\right| \leq \sum_{R,S} |\alpha_R| |\beta_S| \sum_{b=1}^M \left|\ntr(R[E_b,S])\right|.\] Thus, it suffices to show that, for any Paulis \(R,S\), \[\sum_{b=1}^M \left|\ntr(R[E_b,S])\right| \leq 2.\] Notice that \[[E_b, S] = \begin{cases} 0 & \text{if } [E_b, S] = 0\\ 2 \omega T & \text{if } [E_b, S] \neq 0 \end{cases},\] where \(T \in \mathcal{P}_n\) such that \(\omega T = E_bS\), where \(\omega \in \{\pm 1, \pm \ii\}\). Then, \[\ntr(R[E_b, S]) = \begin{cases} 0 & \text{if } [E_b, S] = 0\\ 2\omega \mathbb{1}\{T = R\} & \text{if } [E_b, S] \neq 0 \end{cases}.\] We claim that there can be only one \(b \in [M]\) such that \([E_b, S] \neq 0\) and \(T = R\). This means that only one \(b\) contributes to the sum over \(b\), so the result follows. This is true because for \([E_b, S] \neq 0\) and \(T = R\) to hold, \(E_b = \omega R S\) (since \(\omega T = E_b S\) when \([E_b,S] \neq 0\)). Thus, given \(R\) and \(S\), \(E_b\) is uniquely determined amongst the set of pairwise distinct (phaseless) Paulis. ◻

Proof of 17. Let \(x\) be such that \(\lonorm{x} \leq g\). Recall by the definition of \(\mathcal{F}_P\), \[\begin{align} \mathcal{F}_P(x) &= \frac{1}{t}E_P(x) - \frac{1}{t}E_P(\lambda)\\ &= \frac{1}{t}\E_{R\sim\mathcal{P}_{S_P}} [\ntr(e^{-\ii Ht} R e^{\ii Ht} RP)] - \frac{1}{t}E_P(\lambda)\\ &= \frac{1}{t}\E_{R\sim\mathcal{P}_{S_P}} [\ntr(R e^{\ii Ht} RP e^{-\ii Ht})] - \frac{1}{t}E_P(\lambda)\\ &= -\E_{R\sim \mathcal{P}_{S_P}}[\ntr(R[H(x),RP])] + \frac{1}{t}\sum_{\ell=2}^\infty \frac{(\ii t)^\ell}{\ell!} \E_{R\sim \mathcal{P}_{S_P}}[\ntr(R[H(x), RP]_\ell)] - \frac{1}{t}E_P(\lambda)\\ &= -\sum_Q x_Q \E_{R\sim\mathcal{P}_{S_P}}[\ntr(R[Q, RP])] + \frac{1}{t}\sum_{\ell=2}^\infty \frac{(\ii t)^\ell}{\ell!} \E_{R\sim \mathcal{P}_{S_P}}[\ntr(R[H(x), RP]_\ell)] - \frac{1}{t}E_P(\lambda)\\ &= -\sum_Q x_Q \left(\E_{R\sim\mathcal{P}_{S_P}}[\ntr(RQRP)] - \E_{R\sim\mathcal{P}_{S_P}}[\ntr(PQ)]\right) + \frac{1}{t}\sum_{\ell=2}^\infty \frac{(\ii t)^\ell}{\ell!} \E_{R\sim \mathcal{P}_{S_P}}[\ntr(R[H(x), RP]_\ell)] - \frac{1}{t}E_P(\lambda) \\ &= x_P + \frac{1}{t}\sum_{\ell=2}^\infty \frac{(\ii t)^\ell}{\ell!} \E_{R\sim \mathcal{P}_{S_P}}[\ntr(R[H(x), RP]_\ell)] - \frac{1}{t}E_P(\lambda), \end{align}\] where in the last line, we use 2. We highlight that, unlike in the Lindbladian setting, there is no confusion (in the sense of [sec:local-fourier,sec:local-lindblad-fourier]). This is what makes the analysis of the algorithm much simpler because the \(A\) matrix from [not:A] is now just the identity matrix. Then, the Jacobian is given by \[\label{eq:jacobian} J_{P,Q}(x) = \partial_{x_Q} \mathcal{F}_P(x) = \delta_{P,Q} + \frac{1}{t}\sum_{\ell=2}^{\infty} \frac{(\ii t)^\ell}{\ell!} \E_{R\sim\mathcal{P}_{S_P}} [\partial_{x_Q} \ntr(R[H(x),RP]_\ell)].\tag{45}\] Thus, the leading order term of the Jacobian is \(I\). It suffices to show that the higher order terms are small, i.e., \(\norm{J(x) - I}_{\infty \to \infty} \leq c_g t\). Recall that \(\norm{M}_{\infty\to\infty} = \sup_{\norm{x}_\infty \leq 1} \norm{Mx}_\infty\). Consider \(u = (u_1,\dots, u_M)\) such that \(\norm{u}_\infty \leq 1\). We will bound \(\norm{(J(x) - I)u}_\infty\). \[\begin{align} |((J(x) - I)u)_P| &= \left|\sum_Q (J(x) - I)_{P,Q} u_Q\right|\\ &= \frac{1}{t}\left|\sum_Q u_Q\left(\sum_{\ell=2}^\infty \frac{(\ii t)^\ell}{\ell!} \E_{R\sim\mathcal{P}_{S_P}}[\partial_{x_Q} \ntr(R[H(x),RP]_\ell)]\right)\right|\\ &\leq \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \left(\sum_Q \E_{R\sim \mathcal{P}_{S_P}}[\left|\partial_{x_Q} \ntr(R[H(x), RP]_\ell)\right|]\right), \end{align}\] where in the second line we use 45 , and in the third line, we use \(|u_Q| \leq 1\) and the triangle inequality. Now, using [claim:deriv-commutator], we can expand the derivative of the nested commutator: \[|((J(x) - I)u)_P| \leq \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \sum_{j=0}^{\ell-1} \sum_Q \E_{R\sim \mathcal{P}_{S_P}}\left[\left|\ntr(R[H(x), [Q, [H(x), RP]_{\ell-1-j}]]_j)\right|\right]\] To get this into the correct form to apply [claim:exp-sum], we can repeatedly use \(\tr(A[H,B]) = \tr([A,H]B)\). Thus, we have \[\begin{align} |((J(x) - I)u)_P| &\leq \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \sum_{j=0}^{\ell-1}\E_{R\sim\mathcal{P}_{S_P}}\left[\sum_Q \left|\ntr([R,H(x)]_j [Q, [H(x), RP]_{\ell-1-j}])\right|\right]\\ &\leq \frac{1}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \sum_{j=0}^{\ell-1} \E_{R\sim \mathcal{P}_{S_P}}[2\norm{[R, H(x)]_j}_{P,1} \norm{[H(x), RP]_{\ell-j-1}}_{P,1}]\\ &\leq \frac{2}{t}\sum_{\ell=2}^\infty \frac{t^\ell}{\ell!} \sum_{j=0}^{\ell-1} j! (2kg)^j (\ell-1-j)! (2kg)^{\ell-1-j}\\ &\leq \frac{2}{t} \sum_{\ell=2}^\infty t^\ell (2kg)^{\ell-1}\\ &= 2\sum_{\ell=1}^\infty (2kgt)^\ell\\ &= 2 \cdot \frac{2kgt}{1-2kgt}\\ &\leq t\cdot \frac{81kg}{20}. \end{align}\] In the second line, we use Claim [claim:exp-sum]. In the third line, we use 18, which can be applied because \(\lonorm{x} \leq g\). In the fourth line, we use that \[\sum_{j=0}^{\ell-1} j! (\ell-1-j)! = \sum_{j=0}^{\ell-1}(\ell-1)! \frac{1}{\binom{\ell-1}{j}} \leq (\ell-1)! \sum_{j=0}^{\ell-1} 1 = \ell!.\] In the fifth line, we shift the index \(\ell \to \ell-1\). In the sixth line, we use the sum of a geometric series when \(2kg t < 1\). Finally, in the last line, we use \(t < 1/(162kg)\). Thus, this implies that \(\norm{J(x) - I}_{\infty\to\infty} \leq c_gt\). ◻

Proof of 9. As with 8, we first need to obtain estimates \(\widehat{E}_P(\lambda)\) such that \[|\widehat{E}_P(\lambda) - E_P(\lambda)| \leq \frac{\beta \epsilon}{40}\] for all \(k\)-local Paulis \(P\). We can do so with probability at least \(1-\delta\) using \(\mathcal{O}(4^k\log(n/\delta)/(\beta\epsilon)^2)\) copies of the Gibbs state \(\rho_\beta\) via classical shadows HKP20?. Moreover, for \(k=\mathcal{O}(1)\), this has a classical runtime of \(\mathcal{O}(n^k\log(n/\delta)/(\beta\epsilon)^2)\). For our choice of \(\beta\), this corresponds to \(\mathcal{O}(d^{16}\log(n/\delta)/\epsilon^2)\) copies.

Also, we can obtain estimates \(\widehat{E}_P(x)\) such that \[|\widehat{E}_P(x) - E_P(x)| \leq \frac{\beta \epsilon}{40}\] by computing a truncated cluster expansion. The proof of Theorem 4.6 in haah2024learning? shows that this takes classical runtime \(\mathcal{O}(n^k\poly(d, \log(1/(\beta\epsilon))/\epsilon)\). This applies to our setting because we maintain the invariant in our algorithm that \(|x_P^{(j)}| \leq 2|\lambda_P|\). This means that \(\deg(x) \leq \deg(\lambda) \leq d\), which fits in the setting of haah2024learning?. This gives us an approximation of \(\mathcal{F}(x)\) up to \(\epsilon/20\) error. It remains to argue that the Jacobian bound holds. Consider the statement we want to prove: \[\sum_{Q \in S_H} |J_{P,Q}(x) - \delta_{P,Q}| \leq c_d \beta,\] for \(\deg(x) \leq d\). This closely resembles 19. Notice that \(Q \in S_H\), so since \(H\) has bounded degree, the graph with \(Q \in S_H\) as its vertices has degree at most \(d\). However, the key difference is that \(P\) can be any \(k\)-local Pauli and does not necessarily lie in this graph. Nevertheless, the graph with vertices consisting of \(S_H \cup \{P\}\) still has degree at most \(D = kd\). Thus, we can apply 19 with \(D = kd\) to obtain our claim with \(c_d = 50e^6(kd+1)^8\). This completes the proof. ◻