From this we conclude that for such all-to-all perturbations, we have that

$$ \| (e^{t\mathcal{L}} - e^{t\mathcal{L}'}) (O) \| = \inf_{\delta>0} \mathcal{O}(n\tau(\delta tn + t^{D+1} \log^D(\delta^{-1}))) = \mathcal{O}(n\tau(t + t^{D+1} \log^D(n))), \quad (190) $$

where for the last bound we picked $\delta = n^{-1}$. Thus, we see that as long as $nt\tau \ll \epsilon$, our protocol still produces reliable results even under such global perturbations. Also note that our more refined perturbation bound using the LR-bound is quadratically better than the naive bound $n^2t\tau \ll \epsilon$ we directly obtain from observing that $\|\Delta\|_{+\infty \to +\infty} \le n^2$.

## B. Robustness to characterized SPAM errors

Let us consider how to adapt our protocol to the case where we have SPAM errors. We will model such errors by assuming we know quantum channels $T_P$ and $T_M$ that model the noise when preparing the state and the measurement and we assume that these channels are independent of the Pauli basis we are measuring or preparing.

In that case, the process shadow tomography would be estimating the value of

$$ 2^{-n} \operatorname{tr}(P_a(T_M \circ e^{t\mathcal{L}} \circ T_P)(P_b)) = 2^{-n} \operatorname{tr}(T_M^*(P_a)e^{t\mathcal{L}}(T_P(P_b))). \quad (191) $$

If the observable $T_M^*(P_a)$ is sufficiently local, i.e. it does not increase the support of $P_a$ significantly, then our previous results hold and we know that the function $f: t \mapsto 2^{-n} \operatorname{tr}(T_M^*(P_a)e^{t\mathcal{L}}(T_P(P_b)))$ will be well-approximated by a polynomial of low-degree. Thus, we can see that we can evaluate the derivative of the function at 0 exactly as before. However, now will get access to the equation:

$$ 2^{-n} \operatorname{tr}(T_M^*(P_a)\mathcal{L}(T_P(P_b))) = c_{a,b} \quad (192) $$

If the channels $T_M, T_P$ are sufficiently simple (i.e. approximately product), then it is possible to expand the expectation value in Eq. (192) efficiently and obtain a linear equation for the parameters of $\mathcal{L}$. Note, however, that these SPAM errors might decrease the condition number of the system of equations. Thus, it would be necessary to see how the condition number changes with the noise and then adjust the precision with which we estimate the derivative accordingly.

Let us exemplify this in a simple form of SPAM: local depolarizing noise. Let us assume that both $T_M$ and $T_P$ consist of $D_p^{\otimes n}$, where for some parameter $p$ $D_p(\rho) = p\rho + (1-p)\frac{I}{2}$. In this case, we see that $T_P(P_b) = p^{w(P_b)}P_b, T_M^*(P_a) = p^{w(P_a)}P_a$. Thus, in this case we see that the expectation values are rescaled by a factor $p^{w(P_a)+w(P_b)}$ and we can run exactly the same protocol, but now with a sampling overhead of $p^{2k}$ to learn $k$-local Hamiltonians. In conclusion, we see that for noise models like local depolarizing (or in fact any Pauli noise), it is easy to recover our original results with a mild sampling overhead by adjusting the linear systems.

Developing an analytical understanding of how the condition number changes for other important noise models like amplitude damping is beyond the scope of this work. But we once again emphasize that this is straightforward and efficient to do numerically.

## C. Robustness to unknown SPAM errors

In the last subsection we discussed how to deal with SPAM errors if they are well-characterized and independent of the measurement and state being prepared. Now we are going to discuss the case in which they are unknown and can potentially depend on the measurement and state we wish to prepare. We will show that the effect of SPAM errors will be local, in the sense that as long as the local SPAM rate is of order at most $\epsilon$, then the protocol still yields reliable results. For simplicity, we will consider SPAM errors that are modelled by single-qubit product quantum channels. However, our proof works analogously for channels with an approximately finite light-cone. That is, they map local observables to observables that are approximately local. More formally, in the SPAM-free setting, our protocol entails measuring states of the form:

$$ (\otimes_{i=1}^n V_i)e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(|0^n\rangle\langle0^n|), \quad (193) $$

where $U_i, V_i$ are single-qubit Pauli rotations. We then estimate local observables on such states. We will now model that instead we prepare the state

$$ (\otimes_{i=1}^n T_{i,V_i})(\otimes_{i=1}^n V_i)e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i})(|0^n\rangle\langle0^n|), \quad (194) $$
where $T_{i,U_i}$ and $R_{i,V_i}$ are single-qubit quantum channels that model the SPAM errors and can potentially depend on the gates we are implementing. We will now see that only local SPAM errors affect the performance of our protocol. But before that, let us discuss the sensitivity of the shadows protocol of Sec. 8 to noise. Suppose we wish to use the shadow protocol to estimate a pair of Paulis $P_a, P_b$ of respective weight $w_a, w_b$, i.e. we wish to estimate

$$2^{-n} \operatorname{tr} [P_b e^{t\mathcal{L}}(P_a)] . \qquad (195)$$

Then the protocol discussed in Sec. 8 consists of measuring an observable of $O_{a,b,\{V_i\},\{U_i\}}$ that depends on the state preparation and measurement unitaries, is supported only on the support of $P_b$ and such that $\|O_{a,b,\{V_i\},\{U_i\}}\| = 3^{w_a+w_b}/4$ over an ensemble of random states. Denoting by $B$ the support of $P_b$, we conclude that if for all possible $U_i, V_i$ we have

$$\| \operatorname{tr}_{B^c} [(\otimes_{i=1}^n T_{i,V_i})(\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i}) - (\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(|0^n\rangle\langle 0^n|)] \|_1 \le \tau, \qquad (196)$$

then by an application of Hölder's inequality, we have that the expectation value of the shadows protocol will deviate by at most $\tau 3^{w_a+w_b}/4$ from the ideal value. Although this exponential scaling of the sensitivity in the locality is undesirable, if the SPAM errors are very strong, we can also adopt the less efficient strategy of preparing each state for the isolation separately. As for that case we only need to measure a local observable of operator norm 1, we see that we avoid the exponential factor and the overall error in the estimation for the observable directly follows from Eq. (196) and corresponds to $\tau$.

Let us now show that $\tau$ does not scale with the system's size and only depends on the local noise rate:

**Proposition 9.1.** In the notations above, assume that for all $i, U_i, V_i$ we have that $\|R_{i,V_i} - \mathrm{id}\|_{\diamond}, \|T_{i,V_i} - \mathrm{id}\|_{\diamond} \le \tau$. Furthermore, assume that $\mathcal{L}$ satisfies a LR-bound like that of Eq. (81). Then for $t, w_a, w_b = \mathcal{O}(1)$ we have that:

$$\| \operatorname{tr}_{B^c} [(\otimes_{i=1}^n T_{i,V_i})(\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i}) - (\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(|0^n\rangle\langle 0^n|)] \|_1 = \mathcal{O}(\tau \operatorname{polylog}(\tau^{-1})). \quad (197)$$

In particular, under such a SPAM error we have that the process shadow protocol for Paulis $P_a, P_b$ will have an expectation value that is $\mathcal{O}(3^{w_a+w_b}\mathrm{poly}(w_a, w_b)\tau\mathrm{polylog}(\tau^{-1}))$ close to the SPAM-free setting.

*Proof.* the statement is equivalent to having for all $O_B$ supported on $B$ s.t. $\|O\| \le 1$ that

$$\operatorname{tr} [O_B [\otimes_{i=1}^n T_{i,V_i})(\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i}) - (\otimes_{i=1}^n V_i) e^{t\mathcal{L}}(\otimes_{i=1}^n U_i)(|0^n\rangle\langle 0^n|)]] = \mathcal{O}(\tau\operatorname{polylog}(\tau^{-1})). \quad (198)$$

First, note that we have that

$$\operatorname{tr} [O_B (\otimes_{i=1}^n T_{i,V_i})(\otimes_{i=1}^n V_i) e^{t\mathcal{L}} (\otimes_{i=1}^n U_i) (\otimes_{i=1}^n R_{i,V_i}) (|0^n\rangle\langle 0^n|)] = \qquad (199)$$

$$\operatorname{tr} [O_B (\otimes_{i \in B} T_{i,V_i})(\otimes_{i \in B} V_i) e^{t\mathcal{L}} (\otimes_{i=1}^n U_i) (\otimes_{i=1}^n R_{i,V_i}) (|0^n\rangle\langle 0^n|)] = \qquad (200)$$

$$\operatorname{tr} [O'_B e^{t\mathcal{L}} (\otimes_{i=1}^n U_i) (\otimes_{i=1}^n R_{i,V_i}) (|0^n\rangle\langle 0^n|)] + \epsilon_1, \qquad (201)$$

where $|\epsilon| \le w_b\tau$ and $O'_B$ is again an observable of operator norm at most 1 on $B$. Here we have used that all the unitaries and channels acting outside of $B$ will have a trivial effect. For those acting on $B$ we use our bound on the diamond distance to the identity channel. Now, by our LR bound we have that for times $t = \mathcal{O}(1)$, we can write $e^{t\mathcal{L}^*}(O'_B) = O_{t,B(t,r)} + X_{r,t}$, where $O_{t,B(t,r)}$ is an observable supported on a ball of size $tv + r$ around $B$ and $\|X_{r,t}\| \le \mathcal{O}(e^{-Cr})$. In particular, picking $r = \mathcal{O}(\log(\tau^{-1}))$ and as $t = \mathcal{O}(1)$ we get that $e^{t\mathcal{L}^*}(O'_B)$ is localized on a number of sites that is at most $w_b(vt + C \log(\tau^{-1}))^D$ up to an error $\epsilon$, where $D$ is the dimension of the lattice.

Thus:

$$\operatorname{tr} [O'_B e^{t\mathcal{L}} (\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i}) (|0^n\rangle\langle 0^n|)] = \operatorname{tr} [O'_{t,B(t,r)} (\otimes_{i=1}^n U_i)(\otimes_{i=1}^n R_{i,V_i}) (|0^n\rangle\langle 0^n|)] + \epsilon_2, \quad (202)$$

where $\epsilon_2 \le \tau$ by our choice of $r$. We can then follow the same procedure as before for the $T_{i,V_i}$ to conclude that only those channels on the support of $O'_{t,B(t,r)}$ contribute to the noise. Thus, we get an additional error of order $\mathcal{O}(\tau\operatorname{polylog}(\tau^{-1}))$. This concludes the proof. $\square$

Recall that for the protocols discussed here we have $w(P_a), w(P_b) = \mathcal{O}(1)$. Thus, we see that our protocol is robust to local, gate-dependent SPAM noise as long as the local noise rates are smaller than the target accuracy and the SPAM errors do not need to decrease with the system's size.
## Supplementary Note 10: Learning the structure of the interactions

In the main text we assumed that we know which qubits interact with which qubits, i.e. the interaction graph is known, and we only wish to recover the parameters of this interaction. However, a close inspection of the proof shows that we do not really require exact knowledge of the structure; all we need is the promise that the evolution satisfies a LR bound. Indeed, the only structure required for our proofs to go through is that the evolution of local observables can be well-approximated by that of truncated Lindbladian, and this remains true if the structure of the interactions is unknown, but the true evolution still satisfies a LR bound.

Thus, in this section we will discuss how to apply our protocol in the setting in which we expect the evolution to satisfy a LR bound, but we do not necessarily know all qubits that are coupled to each other. Discussing this setting in full detail and generality goes beyond the scope of this paper, so we will restrict to the case where there is no Lindblad term and we restrict to interaction acting on only two qubits.

Furthermore, we will make the assumption that we have a lower-bound on the strength of all the interactions that are non-zero. This is necessary to obtain bounds on the performance of the protocol, as if we don't have such a lower-bound it will in principle be necessary to measure expectation values with a very high precision to see their effect.

We will thus assume that our generator is of the form

$$ \mathcal{L}(X) = \sum_{(i,j) \in E} a_{\alpha} i[H_{\alpha}, X], \qquad (203) $$

where the (unknown) interaction graph $G = (V, E)$ is such that the evolution induced by $\mathcal{L}$ satisfies a LR bound as in Eq. (81), $1 \ge |a_{\alpha}| \ge \eta$ and $||H_{\alpha}|| \le 1$ and $H_{\alpha}$ is supported on at most 2 qubits.

**Proposition 10.1 (Learning the interaction graph).** Let $\mathcal{L}$ be a Lindbladian on n-qubits as described in Eq. (203) that satisfies a LR bound as in Eq. (81) and $1 \ge |a_{\alpha}| \ge \eta$. Suppose we can measure the expectation value of two-body Pauli observables in the time interval $[t_0, t_{\max}]$ under $\{e^{t\mathcal{L}}\}_{t_0 \le t \le t_{\max}}$ for

$$ t_0^{-1} = \mathcal{O}[\text{polylog}(\eta^{-1})] \qquad (204) $$

and $t_{\max} = 2 + t_0$. Then, measuring the evolution in Pauli bases on Pauli eigenstates under the evolution of $e^{t\mathcal{L}}$ for

$$ m = \mathcal{O}[\text{polylog}(\epsilon^{-1})] \qquad (205) $$

random times $\mathcal{O}(\eta^{-2} \log(n) \text{polylog}(\eta^{-1}))$ times each, is sufficient to obtain with probability of success at least 2/3 the list of the edges $E$.

*Proof.* The protocol is as follows: we first perform the process shadow tomography protocol for $m$ random times $t_i$ and measure the output $\mathcal{O}(\eta^{-2} \log(n)/\text{polylog}(\eta^{-1}))$ times for each $t_i$. Then, by a union bound, we will obtain the expectation value of all the $\mathcal{O}(n^4)$ pairs input and output 2-body Pauli strings up to precision $\eta/\text{polylog}(\eta^{-1})$ each with probability at least 2/3. Conditioning on the event that all of the estimates were correct, we can use our previous results to estimate the interaction strength for all 2-body Pauli terms up to precision $\eta/4$. We then set an edge between all qubits such that they have a 2-body interaction at least $\frac{3}{4}\eta$ in absolute value. By our assumption that all the interactions are at least $\eta$, we will then identify all interactions correctly. $\square$

Thus, we see that our protocol can also correctly identify the interactions as long as some LR-bound is given. To the best of our knowledge, this is the first protocol that does not necessarily require knowledge of the graph, just some assumptions on the locality. Furthermore, note that the sample complexity of this version of the protocol requires approximately the same number of samples as to estimate the values themselves. However, note that learning the graph is computationally more expensive. This is because we need to run $\mathcal{O}(n^2)$ polynomial interpolations to estimate all couplings, whereas when we are given the graph, the number of interpolation steps required is $\mathcal{O}(n)$.

[1] W. Zhang, N. Konstantinidis, K.A. Al-Hassanieh, and V.V. Dobrovitski. Modelling decoherence in quantum spin systems. *Journal of Physics: Condensed Matter*, 19(8):083202, 2007.

[2] V.V. Dobrovitski and H.A. De Raedt. Efficient scheme for numerical simulations of the spin-bath decoherence. *Physical Review E*, 67(5):056702, 2003.

[3] M. Ledoux. *The concentration of measure phenomenon*. Number 89. American Mathematical Soc., 2001.
[4] C.P. Slichter. *Principles of magnetic resonance*, volume 1. Springer Science & Business Media, 2013.

[5] R. Kubo, M. Toda, and N. Hashitsume. *Statistical physics II: nonequilibrium statistical mechanics*, volume 31. Springer Science & Business Media, 2012.

[6] J. Dalibard, Y. Castin, and K. Mølmer. Wave-function approach to dissipative processes in quantum optics. *Physical review letters*, 68(5):580, 1992.

[7] M.A. Nielsen and I. Chuang. Quantum computation and quantum information, 2002.

[8] M. B. Hastings. Locality in Quantum Systems. arXiv:1008. 5137 [math-ph, physics:quant-ph], August 2010. arXiv: 1008. 5137.

[9] D. Poulin. Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics. Phys. Rev. Let., 104(19):190401, May 2010.

[10] T. Barthel and M. Kliesch. Quasilocality and efficient simulation of markovian quantum dynamics. Phys. Rev. Let., 108(23):230504, 2012.

[11] M. Kliesch, C. Gogolin, and J. Eisert. Lieb-Robinson Bounds and the Simulation of Time-Evolution of Local Observables in Lattice Systems. In Volker Bach and Luigi Delle Site, editors, *Many-Electron Approaches in Physics, Chemistry and Mathematics*, pages 301–318. Springer International Publishing, Cham, 2014. Series Title: Mathematical Physics Studies.

[12] D. Kane, S. Karmalkar, and E. Price. Robust Polynomial Regression up to the Information Theoretic Limit. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 391–402, Berkeley, CA, October 2017. IEEE.

[13] W. Markoff and J. Grossmann. über Polynome, die in einem gegebenen Intervalle möglichst wenig von Null abweichen. *Mathematische Annalen*, 77(2):213–258, June 1916.

[14] T.M. Rassias and V. Gupta, editors. *Mathematical Analysis, Approximation Theory and Their Applications*. Number 111 in Springer Optimization and Its Applications. Springer International Publishing : Imprint: Springer, Cham, 1st ed. 2016 edition, 2016.

[15] J. Haah, R. Kothari, and E. Tang. Optimal learning of quantum Hamiltonians from high-temperature Gibbs states, 2021. arXiv:2108. 04842v1.

[16] E. H. Lieb and D. W. Robinson. The finite group velocity of quantum spin systems. Commun. Math. Phys, 28(3):251–257, sep 1972.

[17] M. Kliesch, C. Gogolin, and J. Eisert. Lieb-robinson bounds and the simulation of time-evolution of local observables in lattice systems. In *Many-Electron Approaches in Physics, Chemistry and Mathematics*, pages 301–318. Springer International Publishing, 2014.

[18] R. Sweke, J. Eisert, and M. Kastner. Lieb-robinson bounds for open quantum systems with long-ranged interactions. *Journal of Physics A: Mathematical and Theoretical*, 52(42):424003, 2019.

[19] T. S. Cubitt, A. Lucia, S. Michalakis, and D. Perez-Garcia. Stability of local quantum dissipative systems. Commun. Math. Phys, 337(3):1275–1315, 2015.

[20] T. Kuwahara and K. Saito. Strictly Linear Light Cones in Long-Range Interacting Systems of Arbitrary Dimensions. Phys. Rev. X, 10(3):031010, July 2020.

[21] B. Nachtergaele, A. Vershynina, and V. A. Zagrebnov. Lieb-robinson bounds and existence of the thermodynamic limit for a class of irreversible quantum dynamics. AMS Contemporary Mathematics, 552:161–175, 2011.

[22] Zhiyuan Wang and Kaden RA Hazzard. Tightening the lieb-robinson bound in locally interacting systems. PRX Quantum, 1(1):010303, 2020.

[23] J. Kunjummen, M.C. Tran, D. Carney, and J.M. Taylor. Shadow process tomography of quantum channels, 2021. arXiv:2110.03629v2.

[24] R. Levy, D. Luo, and B.K. Clark. Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers, 2021. arXiv:2110.02965v1.

[25] L. Devroye, M. Lerasle, G. Lugosi, and R.I. Oliveira. Sub-gaussian mean estimators. *The Annals of Statistics*, 44(6):2695–2725, 2016.