$\sum_{P:|P|=\kappa^{*}}\left|\alpha_{P}\right|^{r}=\sum_{i=1}^{n}\sum_{p\in\\{X,Y,Z\\}}\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
|P|=\kappa^{*},P_{\pi(i)}=p\end{subarray}}\left|\alpha_{P}\right|^{r}\mathds{1}[\alpha_{P}\neq
0]\mathds{1}[P_{\pi(j)}=I,\forall j>i].$ (115)

Holder’s inequality and $1/(d_{e}+1)=1-r/2$ allows us to obtain the following
upper bound on $\sum_{P:|P|=\kappa^{*}}\left|\alpha_{P}\right|^{r}$,

$\sum_{i=1}^{n}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{\pi(i)}\neq
I\end{subarray}}\alpha_{P}^{2}\right)^{r/2}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*}\end{subarray}}\mathds{1}[\alpha_{P}\neq
0]\mathds{1}[P_{\pi(i)}\neq I]\mathds{1}[P_{\pi(j)}=I,\forall
j>i]\right)^{1/(d_{e}+1)}.$ (116)

We can then use Lemma 6 to obtain

$\sum_{P:|P|=\kappa^{*}}\left|\alpha_{P}\right|^{r}\leq\sum_{i=1}^{n}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{\pi(i)}\neq
I\end{subarray}}\alpha_{P}^{2}\right)^{r/2}\left(c_{e}i^{d_{e}-1}\right)^{1/(d_{e}+1)}.$
(117)

Using $r-1=(d_{e}-1)/(d_{e}+1)\geq 0$, we have

$\sum_{P:|P|=\kappa^{*}}\left|\alpha_{P}\right|^{r}\leq
c_{e}^{1/(d_{e}+1)}\sum_{i=1}^{n}\left(i\sqrt{\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{\pi(i)}\neq
I\end{subarray}}\alpha_{P}^{2}}\right)^{r-1}\sqrt{\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{\pi(i)}\neq I\end{subarray}}\alpha_{P}^{2}}$ (118)

The choice of $\pi$ ensures Eq. (114), which gives rise to

$\sum_{P:|P|=\kappa^{*}}\left|\alpha_{P}\right|^{r}\leq
c_{e}^{1/(d_{e}+1)}\left(\sum_{i\in[n]}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{i}\neq
I\end{subarray}}\alpha_{P}^{2}\right)^{1/2}\right)^{r}.$ (119)

The claim follows from $1/(r(d_{e}+1))=1/(2d_{e})$. ∎

Together, we can obtain the $\ell_{r}$-norm lower bound for the expectation
value of the homogeneous $\kappa^{*}$-local Hamiltonian $H_{\kappa^{*}}$ on
the constructed product state
$\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)$.

######  Corollary 9.

From the definitions given in Section A.3, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\ket{\psi_{(\cdot,\cdot)}}}\operatorname*{{\mathbb{E}}}_{\sigma\in\\{\pm
1\\}^{\kappa^{*}}}\Big{|}\operatorname{tr}\left(H_{\kappa^{*}}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)\Big{|}$
$\displaystyle\geq\frac{\sqrt{2(\kappa^{*}!)}}{c_{e}^{1/(2d_{e})}(\kappa^{*})^{\kappa^{*}+1.5}\sqrt{6}^{\kappa^{*}}}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*}\end{subarray}}\left|\alpha_{P}\right|^{r}\right)^{1/r}$
(120)
$\displaystyle\geq\frac{\sqrt{2(k!)}}{c_{e}^{1/(2d_{e})}k^{k+1.5}\sqrt{6}^{k}}\left(\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*}\end{subarray}}\left|\alpha_{P}\right|^{r}\right)^{1/r}.$
(121)

###### Proof.

From Lemma 5, we have

$\operatorname*{{\mathbb{E}}}_{\ket{\psi_{(\cdot,\cdot)}}}\operatorname*{{\mathbb{E}}}_{\sigma\in\\{\pm
1\\}^{\kappa^{*}}}\Big{|}\operatorname{tr}\left(H_{\kappa^{*}}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)\Big{|}\geq\frac{\sqrt{2(\kappa^{*}!)}}{(\kappa^{*})^{\kappa^{*}+1.5}\sqrt{6}^{\kappa^{*}}}\sum_{i\in[n],p\in\\{X,Y,Z\\}}\sqrt{\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{i}=p\end{subarray}}\alpha_{P}^{2}}.$ (122)

By the elementary inequality $\sqrt{x}+\sqrt{y}+\sqrt{z}\geq\sqrt{x+y+z}$ for
nonnegative $x,y,z$,

$\sum_{i\in[n],p\in\\{X,Y,Z\\}}\sqrt{\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
|P|=\kappa^{*},P_{i}=p\end{subarray}}\alpha_{P}^{2}}\geq\sum_{i\in[n]}\sqrt{\sum_{p\in\\{X,Y,Z\\}}\sum_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\ |P|=\kappa^{*},P_{i}=p\end{subarray}}\alpha_{P}^{2}}.$ (123)

Combining with Lemma 7 and the fact that $k\geq\kappa^{*}$ yields the stated
result. ∎

####  A.4.4 Homogeneous to inhomogeneous through polynomial optimization

We need the following basic result from real analysis:

######  Lemma 8 (Markov brothers’ inequality, see e.g. p. 248 of [79]).

For any real polynomial $p(t)=\sum^{k}_{\kappa=1}a_{\kappa}x^{\kappa}$,

$|a_{\kappa}|\leq(1+\sqrt{2})^{k}\sup_{|t|\leq 1}|p(t)|$ (124)

for all $1\leq\kappa\leq k$.

Using Markov brothers’ inequality, we can show that performing the one-
dimensional polynomial optimization over $t$ achieves a good advantage over
$\alpha_{I}=\operatorname*{{\mathbb{E}}}_{\ket{\psi}:\mathrm{Haar}}\bra{\psi}H\ket{\psi}$.

######  Corollary 10.

From the definitions given in Section A.3, we have

$\Big{|}\operatorname{tr}\left(H\rho\left(t^{*};\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)-\alpha_{I}\Big{|}\geq\frac{1}{(1+\sqrt{2})^{k}}\Big{|}\operatorname{tr}\left(H_{\kappa^{*}}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)\Big{|}.$
(125)

###### Proof.

Recall that $H=\alpha_{I}I+\sum_{\kappa=1}^{k}H_{\kappa}$ from Eq. (55). We
can use the polarization identity given in Lemma 1 to see that the function
$f(t)=\operatorname{tr}\left(H\rho\left(t;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)$
is a polynomial,

$\operatorname{tr}\left(H\rho\left(t;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)=\alpha_{I}+\sum_{\kappa=1}^{k}\operatorname{tr}\left(H_{\kappa}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)t^{\kappa}.$
(126)

Recall that $t^{*}$ is chosen based on the optimization

$\max_{t\in[-1,1]}\left|\operatorname{tr}\Big{(}H\rho\left(t;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\Big{)}-\alpha_{I}\right|.$
(127)

By considering Lemma 8 with
$a_{\kappa}=\operatorname{tr}\left(H_{\kappa}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)$,
we have

$(1+\sqrt{2})^{k}\left|\operatorname{tr}\Big{(}H\rho\left(t^{*};\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\Big{)}-\alpha_{I}\right|\geq\left|\operatorname{tr}\left(H_{\kappa}\rho\left(1;\ket{\psi_{(\cdot,\cdot)}},\sigma\right)\right)\right|.$
(128)

This concludes the proof of this corollary. ∎

##  APPENDIX B Norm inequalities from approximate optimization algorithm

The approximate optimization algorithm described in the previous section is
not used directly in the ML algorithm, but used to derive norm inequalities,
i.e., inequalities relating different norms over Hermitian operators. An
important norm that we will use in the ML algorithms is the Pauli-$p$ norm
defined below. The Pauli-$p$ norm is equivalent to the vector-$p$ norm on the
Pauli coefficient of an observable $H$.

######  Definition 3 (Pauli-$p$ norm).

Given $H=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}\alpha_{P}P$ and $p\geq 1$. The
Pauli-$p$ norm of $H$ is

$\left\lVert
H\right\rVert_{\mathrm{Pauli},p}=\left(\sum_{P}|\alpha_{P}|^{p}\right)^{1/p}.$
(129)

Recall that the spectral norm $\left\lVert
H\right\rVert=\max_{\ket{\psi}}|\bra{\psi}H\ket{\psi}|=\max_{\rho}|\operatorname{tr}(H\rho)|$.
In this section, we will use the approximate optimization algorithm to derive
several norm inequalities relating the Pauli-$p$ norm
$\left\lVert\cdot\right\rVert_{\mathrm{Pauli},p}$ to the spectral norm
$\left\lVert\cdot\right\rVert$ for common classes of observables.

We begin with a well-known fact that equates the Frobenius norm and the
Pauli-$2$ norm. This proposition follows directly from the orthonormality of
the Pauli observables $\\{I,X,Y,Z\\}^{\otimes n}$.

######  Proposition 1 (Frobenius norm).

Given any $n$-qubit Hermitian operator $H$. We have

$\frac{1}{\sqrt{2^{n}}}\left\lVert H\right\rVert_{F}=\left\lVert
H\right\rVert_{\mathrm{Pauli},2}\leq\left\lVert H\right\rVert.$ (130)

###### Proof.

Let $n$ be the number of qubits $H$ act on and
$\lambda_{1},\ldots,\lambda_{2^{n}}$ be the eigenvalues of $O$. From the fact
that $\operatorname{tr}(PQ)=2^{n}\delta_{P=Q}$, we have

$\left\lVert
H\right\rVert_{F}^{2}=\operatorname{tr}(H^{2})=\sum_{P}|\alpha_{P}|^{2}2^{n}=2^{n}\left\lVert
H\right\rVert_{\mathrm{Pauli},2}^{2}.$ (131)

Since $\left\lVert
H\right\rVert_{F}^{2}=\sum_{i=1}^{2^{n}}|\lambda_{i}|^{2}\leq
2^{n}\max_{i}|\lambda_{i}|^{2}=2^{n}\left\lVert H\right\rVert^{2}_{\infty}$,
we have $\sum_{P}|\alpha_{P}|^{2}=\left\lVert
H\right\rVert_{F}^{2}/2^{n}\leq\left\lVert H\right\rVert^{2}_{\infty}$. ∎

We now utilize Theorem 5 to obtain the following useful norm inequality.

######  Theorem 9 (Norm inequality from Theorem 5).

Given an $n$-qubit $k$-local Hamiltonian $H$ with expansion
coefficient/dimension $c_{e},d_{e}$. Let $r=2d_{e}/(d_{e}+1)\in[1,2)$. We have

$\frac{1}{3}C(c_{e},d_{e},k)\left\lVert
H\right\rVert_{\mathrm{Pauli},r}\leq\left\lVert H\right\rVert,$ (132)

where
$C(c_{e},d_{e},k)=\frac{\sqrt{2(k!)}}{c_{e}^{1/(2d_{e})}k^{k+1.5+1/r}(\sqrt{6}+2\sqrt{3})^{k}}$
is the same as Theorem 5.

###### Proof.

Consider the Pauli representation $H=\sum_{P:|P|\leq k}\alpha_{P}P$. If we
consider $\rho=I/2^{n}$, then we have

$\left\lVert
H\right\rVert\geq\left|\operatorname{tr}(H)/2^{n}\right|\geq\left|\operatorname*{{\mathbb{E}}}_{\ket{\phi}:\mathrm{Haar}}\big{[}\bra{\phi}H\ket{\phi}\big{]}\right|=\left|\alpha_{I}\right|.$
(133)

If we consider the random product state $\ket{\psi}$ from Theorem 5, then we
have

$\operatorname*{{\mathbb{E}}}_{\ket{\psi}}\left|\bra{\psi}H\ket{\psi}-\operatorname*{{\mathbb{E}}}_{\ket{\phi}:\mathrm{Haar}}\big{[}\bra{\phi}H\ket{\phi}\big{]}\right|\geq
C(c_{e},d_{e},k)\left(\sum_{P\neq I}|\alpha_{P}|^{r}\right)^{1/r}.$ (134)

Using
$\operatorname*{{\mathbb{E}}}_{\ket{\phi}:\mathrm{Haar}}\big{[}\bra{\phi}H\ket{\phi}\big{]}=\alpha_{I}$
and
$\operatorname*{{\mathbb{E}}}_{\ket{\psi}}\left|\bra{\psi}H\ket{\psi}-\alpha_{I}\right|\leq\operatorname*{{\mathbb{E}}}_{\ket{\psi}}\left|\bra{\psi}H\ket{\psi}\right|+|\alpha_{I}|$,
we have

$\left\lVert
H\right\rVert\geq\operatorname*{{\mathbb{E}}}_{\ket{\psi}}\left|\bra{\psi}H\ket{\psi}\right|\geq
C(c_{e},d_{e},k)\left(\sum_{P\neq
I}|\alpha_{P}|^{r}\right)^{1/r}-\left|\alpha_{I}\right|.$ (135)

Next, we utilize the following inequality

$\max(x_{1},cx_{2}-x_{1})\geq\frac{c}{c+2}(x_{1}+x_{2}),\forall
x_{1},x_{2},c\geq 0,$ (136)

which can be shown by considering the two cases: $x_{1}\geq(c/2)x_{2}$ and
$x_{1}<(c/2)x_{2}$, as well as the lower bounds on $\left\lVert H\right\rVert$
to show that

$\left\lVert
H\right\rVert\geq\frac{C(c_{e},d_{e},k)}{C(c_{e},d_{e},k)+2}\left(\left|\alpha_{I}\right|+\left(\sum_{P\neq
I}|\alpha_{P}|^{r}\right)^{1/r}\right)\geq\frac{C(c_{e},d_{e},k)}{3}\left(\left|\alpha_{I}\right|+\left(\sum_{P\neq
I}|\alpha_{P}|^{r}\right)^{1/r}\right).$ (137)

The second inequality uses $k,c_{e},d_{e}\geq 1$, which implies
$C(c_{e},d_{e},k)\in[0,1]$. Finally, the inequality

$\left|\alpha_{I}\right|+\left(\sum_{P\neq
I}|\alpha_{P}|^{r}\right)^{1/r}\geq\left(\sum_{P}|\alpha_{P}|^{r}\right)^{1/r},$
(138)

can be used to establish the claim. ∎

Using Fact 1 and Fact 2 that characterize the expansion property for general
$k$-local Hamiltonians and bounded degree $k$-local Hamiltonians (i.e., each
qubit is acted on by at most $d$ of the $k$-qubit observables), we can
establish the following corollaries.

######  Corollary 11 (Norm inequality for $k$-local Hamiltonian).

Given an $n$-qubit $k$-local Hamiltonian $H$. We have

$\frac{1}{3}C(k)\left\lVert
H\right\rVert_{\mathrm{Pauli},\frac{2k}{k+1}}\leq\left\lVert H\right\rVert,$
(139)

where
$C(k)=\frac{\sqrt{2(k!)}}{2k^{k+1.5+(k+1)/(2k)}(\sqrt{6}+2\sqrt{3})^{k}}$ is
the same as Corollary 5.

######  Corollary 12 (Norm inequality for bounded-degree Hamiltonian).

Given an $n$-qubit $k$-local Hamiltonian $H$ with a bounded degree $d$. We
have

$\frac{1}{3}C(k,d)\left\lVert H\right\rVert_{\mathrm{Pauli},1}\leq\left\lVert
H\right\rVert,$ (140)

where
$C(k,d)=\frac{\sqrt{2(k!)}}{\sqrt{d}k^{k+2.5}(2\sqrt{6}+4\sqrt{3})^{k}}$.

##  APPENDIX C Sample-optimal algorithms for predicting bounded-degree
observables

In this section, we consider one of the most basic learning problems in
quantum information theory: predicting properties of an unknown $n$-qubit
state $\rho$. This has been studied extensively in the literature on shadow
tomography [57, 58] and classical shadows [46].

###  C.1 Review of classical shadow formalism

We recall the following definition and theorem from classical shadow
tomography [46] based on randomized Pauli measurements. Each randomized Pauli
measurement is performed on a single copy of $\rho$ and measures each qubit of
$\rho$ in a random Pauli basis ($X,Y$, or $Z$).

######  Definition 4 (Shadow norm from randomized Pauli measurements).

Given an $n$-qubit observable $O$. Let $\mathcal{U}$ be the distribution over
the tensor product of $n$ single-qubit random Clifford unitary, and
$\mathcal{M}^{-1}_{P}=\bigotimes_{i=1}^{n}\mathcal{M}^{-1}_{1}$ with
$\mathcal{M}^{-1}_{1}(A)=3A-\operatorname{tr}(A)I$. The shadow norm of $O$ is
defined as

$\left\lVert
O\right\rVert_{\mathrm{shadow}}=\max_{\sigma:\mathrm{state}}\left(\operatorname*{{\mathbb{E}}}_{U\sim\mathcal{U}}\sum_{b\in\\{0,1\\}^{n}}\bra{b}U\sigma
U^{\dagger}\ket{b}\bra{b}U\mathcal{M}^{-1}_{P}(O)U^{\dagger}\ket{b}^{2}\right)^{1/2}.$
(141)

######  Theorem 10 (Classical shadow tomography using randomized Pauli
measurements [46]).

Given an unknown $n$-qubit state $\rho$ and $M$ observables
$O_{1},\ldots,O_{M}$ with $B_{\mathrm{shadow}}=\max_{i\in[M]}\left\lVert
O_{i}\right\rVert_{\mathrm{shadow}}$. After $N$ randomized Pauli measurements
on copies of $\rho$ satisfying

$N=\mathcal{O}\left(\frac{\log(M)B_{\mathrm{shadow}}^{2}}{\epsilon^{2}}\right),$
(142)

we can estimate $\operatorname{tr}(O_{i}\rho)$ to $\epsilon$ error for all
$i\in[M]$ with high probability.

We can see that the sample complexity for predicting many properties of an
unknown quantum state $\rho$ depends on the shadow norm
$\left\lVert\cdot\right\rVert_{\mathrm{shadow}}$. The larger
$\left\lVert\cdot\right\rVert_{\mathrm{shadow}}$ is, the more experiments is
needed to estimate properties of $\rho$ accurately. From the original
classical shadow paper [46], we can obtain the following shadow norm bounds
for Pauli observables and for few-body observables.

######  Lemma 9 (Shadow norm for Pauli observables [46]).

For any $P\in\\{I,X,Y,Z\\}^{\otimes n}$, we have

$\left\lVert P\right\rVert_{\mathrm{shadow}}=3^{|P|/2}.$ (143)

######  Lemma 10 (Shadow norm for few-body observables [46]).

For any observable $O$ that acts nontrivially on at most $k$ qubits, we have

$\left\lVert O\right\rVert_{\mathrm{shadow}}\leq 2^{k}\left\lVert
O\right\rVert.$ (144)

Combining the above lemmas and Theorem 10, we can see that Pauli observables
and few-body observables can both be predicted efficiently under very few
number of randomized Pauli measurements.

###  C.2 Upper bound for predicting bounded-degree observables

Consider an $n$-qubit observable $O$ given as a sum of $k$-qubit observables
$O=\sum_{j}O_{j}$, where each qubit is acted on by at most $d$ of these
$k$-qubit observables ${}_{O}j$. We focus on $k=\mathcal{O}(1)$ and
$d=\mathcal{O}(1)$, and refer to such an observable as a bounded-degree
observable. These bounded-degree observables arise frequently in quantum many-
body physics and quantum information. For example, the Hamiltonian in a
quantum spin system can often be described by a geometrically-local
Hamiltonian, which is an instance of bounded-degree observables. For these
observables, the shadow norm is related to the Pauli-$1$ norm of the
observable,

$\left\lVert O\right\rVert_{\mathrm{shadow}}\leq\sum_{P:|P|\leq
k}|\alpha_{P}|\left\lVert P\right\rVert_{\mathrm{shadow}}\leq
3^{k/2}\sum_{P:|P|\leq k}|\alpha_{P}|=3^{k/2}\left\lVert
O\right\rVert_{\mathrm{pauli},1}.$ (145)

If we consider the norm inequality between $\ell_{1}$-norm and $\ell_{2}$-norm
and use the standard result relating Frobenius norm and spectral norm
(Proposition 1), we would obtain the following upper bound on shadow norm.

$\left\lVert O\right\rVert_{\mathrm{shadow}}\leq 3^{k/2}\left\lVert
O\right\rVert_{\mathrm{pauli},1}\leq(2\sqrt{3})^{k}\sqrt{nd}\left\lVert
O\right\rVert_{\mathrm{pauli},2}=\mathcal{O}\left(\sqrt{n}\left\lVert
O\right\rVert\right).$ (146)

Using Theorem 10, this shadow norm bound would give rise to a number of
measurements scaling as

$N=\mathcal{O}\left(\frac{n\log(M)B^{2}_{\infty}}{\epsilon^{2}}\right),$ (147)

where $B_{\infty}=\max_{i\in[M]}\left\lVert O_{i}\right\rVert_{\infty}$ is an
upper bound on the spectral norm $\left\lVert\cdot\right\rVert$. Due to the
linear dependence on the number $n$ of qubits in the unknown quantum state,
this scaling is not ideal. Furthermore, we will later show that this scaling
is actually far from optimal.

To improve the sample complexity, we will use the improved approximate
optimization algorithm presented in Appendix A, and the corresponding norm
inequality presented in Appendix B. Using the norm inequality relating
Pauli-$1$ norm and the spectral norm (Corollary 12), we can obtain the
following shadow norm bound.

######  Lemma 11 (Shadow norm for bounded-degree observables).

Given $k,d=\mathcal{O}(1)$ and an $n$-qubit observable $O$ that is a sum of
$k$-qubit observables, where each qubit is acted on by at most $d$ of these
$k$-qubit observables.

$\left\lVert O\right\rVert_{\mathrm{shadow}}\leq C\left\lVert O\right\rVert,$
(148)

for some constant $C>0$.

Combining the above lemma with Theorem 10 allows us to establish the following
theorem. Comparing to Eq. (147), the following theorem uses $n$ times fewer
measurements.

######  Theorem 11 (Classical shadow tomography for bounded-degree
observables).

Given an unknown $n$-qubit state $\rho$ and $M$ observables
$O_{1},\ldots,O_{M}$ with $B_{\infty}=\max_{i}\left\lVert
O_{i}\right\rVert_{\infty}$. Suppose each observable $O_{i}$ is a sum of few-
body observables $O_{i}=\sum_{j}O_{ij}$, where every qubit is acted on by a
constant number of the few-body observables $O_{ij}$. After $N$ randomized
Pauli measurements on copies of $\rho$ with

$N=\mathcal{O}\left(\frac{\log\big{(}\min(M,n)\big{)}B_{\infty}^{2}}{\epsilon^{2}}\right),$
(149)

we can estimate $\operatorname{tr}(O_{i}\rho)$ to $\epsilon$ error for all
$i\in[M]$ with high probability.

###### Proof.

The upper bound of $N=\mathcal{O}\left(\log(M)\max_{i\in[M]}\left\lVert
O_{i}\right\rVert_{\infty}^{2}/\epsilon^{2}\right)$ follows immediately from
Theorem 10 and Lemma 11. We can also establish an upper bound of
$N=\mathcal{O}\left(\log(n)\max_{i\in[M]}\left\lVert
O_{i}\right\rVert_{\infty}^{2}/\epsilon^{2}\right)$. To see this, consider the
task of predicting all $k$-qubit Pauli observables $P\in\\{I,X,Y,Z\\}^{\otimes
n}$ with $|P|\leq k$. There are at most $\mathcal{O}(n^{k})$ such Pauli
observables. To predict all of the $k$-qubit Pauli observables to
$\epsilon^{\prime}$ error under the unknown state $\rho$, we can combine
Theorem 10 and Lemma 9 to see that we only need

$N=\mathcal{O}\left(\log(n)\max_{i\in[M]}\left\lVert
O_{i}\right\rVert_{\infty}^{2}/(\epsilon^{\prime})^{2}\right)$ (150)

randomized Pauli measurements. Now, given any observable
$O_{i}=\sum_{P}\alpha_{P}P$ that is a sum of few-body observables
$O_{i}=\sum_{j}O_{ij}$, where every qubit is acted on by a constant number of
the few-body observables $O_{ij}$, we can predict
$\operatorname{tr}(O_{i}\rho)$ using the following identity

$\operatorname{tr}(O_{i}\rho)=\sum_{P:|P|\leq
k}\alpha_{P}\operatorname{tr}(P\rho),$ (151)

which incurs a prediction error of at most
$\sum_{P}|\alpha_{P}|\epsilon^{\prime}$. Using the norm inequality in
Corollary 12, we have

$\left\lVert O_{i}\right\rVert_{\mathrm{Pauli},1}=\sum_{P}|\alpha_{P}|\leq
C\left\lVert O_{i}\right\rVert,$ (152)

for a constant $C$. Hence, by setting $\epsilon^{\prime}=\epsilon/C$, we can
predict $O_{i}$ to $\epsilon$ error. Thus we can also establish an upper bound
of $N=\mathcal{O}\left(\log(n)\max_{i\in[M]}\left\lVert
O_{i}\right\rVert_{\infty}^{2}/\epsilon^{2}\right)$. The claim follows by
considering the corresponding prediction algorithm (use the standard classical
shadow when $M<n$, and use the above algorithm when $M\geq n$). ∎

###  C.3 Optimality of Theorem 11

Here we prove the following lower bound on the sample complexity of shadow
tomography for bounded-degree observables demonstrating that Theorem 11 is
optimal. The optimality holds even when we considered collective measurement
procedure on many copies of $\rho$. This is in stark contrast to other sets of
observables, such as the collection of high-weight Pauli observables, where
single-copy measurements (e.g., classical shadow tomography) require
exponentially more copies than collective measurements.

######  Theorem 12 (Lower bound for predicting bounded-degree observables).

Consider the following task. Given any unknown $n$-qubit state $\rho$ and any
$M$ observables $O_{1},\ldots,O_{M}$ with $B_{\infty}=\max_{i}\left\lVert
O_{i}\right\rVert$. Each observable $O_{i}$ is a sum of few-body observables
$O_{i}=\sum_{j}O_{ij}$, where every qubit is acted on by a constant number of
the few-body observables $O_{ij}$. We would like to estimate
$\operatorname{tr}(O_{i}\rho)$ to $\epsilon$ error for all $i\in[M]$ with high
probability by performing arbitrary collective measurements on $N$ copies of
$\rho$. The number of copies needs to be at least

$N=\Omega\left(\frac{\log\big{(}\min(M,n)\big{)}B_{\infty}^{2}}{\epsilon^{2}}\right),$
(153)

for any algorithm to succeed in this task.

To show Theorem 12, we show a lower bound for the following _distinguishing
task_ , from which the lower bound for shadow tomography will follow readily.
Given $i\in[n]$, let $P_{i}$ denote the $n$-body Pauli operator that acts as
$Z$ on the $i$-th qubit and trivially elsewhere, and define the mixed state

$\rho^{i}\triangleq\frac{1}{2^{n}}\left(I+\frac{\epsilon}{B_{\infty}}\cdot
P_{i}\right).$ (154)

We will show a lower bound for distinguishing whether $\rho$ is maximally
mixed or of the form $\rho^{i}$ for some $i$.

######  Lemma 12 (Lower bound for a distinguishing task).

Let $0\leq\epsilon\leq 1$ and $\delta\geq 2\epsilon$. Let $\mathcal{A}$ be an
algorithm that, given access to $N$ copies of a mixed state $\rho$ which is
either the maximally mixed state or $\rho^{i}$ for some $i\in[\min(M,n)]$,
correctly determines whether or not $\rho$ is maximally mixed with probability
at least $3/4$. Then $N=\Omega(\log(\min(M,n))B_{\infty}^{2}/\epsilon^{2})$.

###### Proof of Theorem 12.

Let $\mathcal{A}$ be an algorithm that solves the task in Theorem 12 to error
$\epsilon/3$. We can use this to give an algorithm for the task in Lemma 12:
applying $\mathcal{A}$ to the following $\min(M,n)$ observables,

$O_{1}\triangleq B_{\infty}P_{1},\quad\ldots,\quad O_{\min(M,n)}\triangleq
B_{\infty}P_{\min(M,n)},$ (155)

we can produce $\epsilon/3$-accurate estimates for $\operatorname{tr}(\rho
P_{j})$ for all $j\in[\min(M,n)]$. Note that if $\rho$ is maximally mixed,
$\operatorname{tr}(\rho O_{j})=0$ for all $j$, whereas if $\rho=\rho^{i}$,
then $\operatorname{tr}(\rho O_{j})=\epsilon\cdot\mathds{1}[i=j]$. In
particular, by checking whether there is a $j$ for which
$\operatorname{tr}(\rho P_{j})>2\epsilon/3$, we can determine whether $\rho$
is maximally mixed or equal to some $\rho^{i}$. The lower bound in Lemma 12
thus implies the lower bound in Theorem 12. ∎

For convenience, define $n^{\prime}\triangleq\min(M,n)$. Note that for any
$i\in[n]$, $(\rho^{i})^{\otimes N}$ is diagonal, so we can assume without loss
of generality that $\mathcal{A}$ simply makes $N$ independent measurements in
the computational basis. Proving Lemma 12 thus amounts to showing a lower
bound for a classical distribution testing task.

Note that the distribution $\pi^{i}$ over outcomes of a single measurement of
$\rho^{i}$ in the computational basis places

$\frac{1+(-1)^{x_{i}}\epsilon}{2^{n}}$ (156)

mass on each string $x\in\\{0,1\\}^{n}$. The distribution $\pi$ over outcomes
of a single measurement of the maximally mixed state in the computational
basis is uniform over all strings $x\in\\{0,1\\}^{n}$. The following basic
result in binary hypothesis testing lets us reduce proving Lemma 12 to upper
bounding

$d_{\rm TV}\left(\operatorname*{{\mathbb{E}}}_{i}[(\pi^{i})^{\otimes
N}],\pi^{\otimes N}\right).$ (157)

######  Lemma 13 (Le Cam’s two-point method [80]).

Let $p_{0},p_{1}$ be distributions over a domain $\Omega$ for which there
exists a distribution $D$ such that $d_{\rm TV}(p_{0},p_{1})<1/3$. Then there
is no algorithm $\mathcal{A}$ that maps elements of $\Omega$ to $\\{0,1\\}$
for which $\Pr_{x\sim p_{i}}[\mathcal{A}(x)=i]\geq 2/3$ for both $i=0,1$.

###### Proof of Lemma 12.

To bound the expression in Eq. (157), it suffices to bound the chi-squared
divergence $\chi^{2}(\operatorname*{{\mathbb{E}}}_{i}[(\pi^{i})^{\otimes
N}]\|\pi^{\otimes N})$ because for any distributions $p,q$, we have $d_{\rm
TV}(p,q)\leq 2\sqrt{\chi^{2}(p\|q)}$. For convenience, let us define the
likelihood ratio perturbation

$\eta^{i}(x)\triangleq\frac{\mathrm{d}\pi^{i}}{\mathrm{d}\pi}(x)-1=(-1)^{x_{i}}\epsilon$
(158)

and observe that for any $i,j\in[n]$,

$\operatorname*{{\mathbb{E}}}_{x\sim\pi}[\eta^{i}(x)\cdot\eta^{j}(x)]=\epsilon^{2}\cdot\mathds{1}[i=j].$
(159)

Also given strings $x^{1},\ldots,x^{N}\in\\{0,1\\}^{n}$ and $S\subseteq[N]$,
denote

$\eta^{i}(x^{S})\triangleq\prod_{j\in S}\eta^{i}(x_{j}).$ (160)

We then have the standard calculation, see e.g. [81, Lemma 22.1]:

$\displaystyle
1+\chi^{2}\left(\operatorname*{{\mathbb{E}}}_{i\sim[n^{\prime}]}[(\pi^{i})^{\otimes
N}]\|\pi^{\otimes N}\right)$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{x^{1},\ldots,x^{N}\sim\pi^{\otimes
N}}\left[\operatorname*{{\mathbb{E}}}_{i\sim[n^{\prime}]}\left[\prod^{N}_{j=1}(1+\eta^{i,t}(x^{j}))\right]^{2}\right]$
(161)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{i,i^{\prime}\sim[n^{\prime}]}\left[\operatorname*{{\mathbb{E}}}_{x^{1},\ldots,x^{N}\sim\pi^{\otimes
N}}\left[\sum_{S,T\subseteq[N]}\eta^{i}(x^{S})\eta^{i^{\prime}}(x^{T})\right]\right]$
(162)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{i,i^{\prime}\sim[n^{\prime}]}\left[\operatorname*{{\mathbb{E}}}_{x^{1},\ldots,x^{N}\sim\pi^{\otimes
N}}\left[\sum_{S\subseteq[N]}\eta^{i}(x^{S})\eta^{i^{\prime}}(x^{S})\right]\right]$
(163)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{i,i^{\prime}\sim[n^{\prime}]}\left[\operatorname*{{\mathbb{E}}}_{x^{1},\ldots,x^{N}\sim\pi^{\otimes
N}}\left[\prod^{N}_{j=1}(1+\eta^{i}(x^{j})\eta^{i^{\prime}}(x^{j}))\right]\right]$
(164)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{i,i^{\prime}\sim[n^{\prime}]}\left[(1+\operatorname*{{\mathbb{E}}}_{x\sim\pi}[\eta^{i}(x)\eta^{i^{\prime}}(x)])^{N}\right]$
(165)
$\displaystyle=\frac{1}{n^{\prime}}(1+\epsilon^{2})^{N}+\frac{n^{\prime}-1}{n^{\prime}}$
(166)

We conclude that

$\chi^{2}(\operatorname*{{\mathbb{E}}}_{i\sim[n^{\prime}]}[(\pi^{i})^{\otimes
N}]\|\pi^{\otimes N})\leq\frac{1}{n^{\prime}}((1+\epsilon^{2})^{N}-1),$ (167)

so for $N=c\log(n^{\prime})/\epsilon^{2}$ for sufficiently small constant
$c>0$, this quantity is less than $1/3$. By applying Lemma 13 to
$p_{0}=\pi^{\otimes N}$ and
$p_{1}=\operatorname*{{\mathbb{E}}}_{i\sim[n^{\prime}]}[(\pi^{i})^{\otimes
N}]$, we obtain the claimed lower bound. ∎

##  APPENDIX D Learning to predict an unknown observable

We begin with a definition of invariance for distribution over quantum states.

######  Definition 5 (Invariance under a unitary).

A probability distribution $\mathcal{D}$ over quantum states is invariant
under a unitary $U$ if the probability density remains unchanged after the
action of $U$, i.e.,

$f_{\mathcal{D}}(\rho)=f_{\mathcal{D}}(U\rho U^{\dagger})$ (168)

for any state $\rho$.

In this section, we will utilize the norm inequalities in Section B to give a
learning algorithm that achieves the following guarantee. The learning
algorithm can learn any unknown $n$-qubit observable $O^{\mathrm{(unk)}}$ even
if the scale $\left\lVert O^{\mathrm{(unk)}}\right\rVert$ is unknown. The mean
squared error
$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho)-\operatorname{tr}\left(O^{\mathrm{(unk)}}\rho\right)\right|^{2}$
scales quadratically with the scale of the unknown observable
$O^{\mathrm{(unk)}}$. We can see that the sample complexity $N$ has a quasi-
polynomial dependence on the error $\epsilon,\epsilon^{\prime}$ relative to
the scale of the unknown observable $O^{\mathrm{(unk)}}$, and only depends on
the system size $n$ and the failure probability $\delta$ logarithmically.

######  Theorem 13 (Learning to predict an unknown observable).

Given $n,\epsilon,\epsilon^{\prime},\delta>0$. Consider any unknown $n$-qubit
observable $O^{\mathrm{(unk)}}=\sum_{P}\alpha_{P}P$ and any unknown $n$-qubit
state distribution $\mathcal{D}$ that is invariant under single-qubit $H$ and
$S$ gates. Given training data
$\\{\rho_{\ell},\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\\}_{\ell=1}^{N}$
of size

$N=\log\left(\frac{n}{\delta}\right)\,\min\left(2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)},2^{\mathcal{O}(\log(\frac{1}{\epsilon})\log(n))}\right).$
(169)

Let $k=\lceil\log_{1.5}(1/\epsilon)\rceil$, $O^{\mathrm{(low)}}=\sum_{|P|\leq
k}\alpha_{P}P$ be the low-degree approximation of $O^{\mathrm{(unk)}}$, and
$r=\tfrac{2k}{k+1}\in[1,2)$. The algorithm can learn a function
$h(\rho)=\max(-\hat{\Theta},\min(\hat{\Theta},\operatorname{tr}(\hat{O}\rho)))$
for an observable $\hat{O}$ and a real number $\hat{\Theta}$ that achieves a
prediction error

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho)-\operatorname{tr}\left(O^{\mathrm{(unk)}}\rho\right)\right|^{2}\leq\left(\epsilon+\epsilon^{\prime}\left[\,1+\left(\tfrac{\left\lVert
O^{\mathrm{(low)}}\right\rVert}{\left\lVert
O^{\mathrm{(unk)}}\right\rVert}\right)^{r}\,\right]\right)\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}$ (170)

with probability at least $1-\delta$.

###  D.1 Low-degree approximation under mean squared error

In order to characterize the mean squared error
$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2})\rho$
between two observables $O_{1},O_{2}$, we need the following definition of a
modified purity for quantum states.

######  Definition 6 (Non-identity purity).

Given a $k$-qubit state $\rho$. The non-identity purity of $\rho$ is

$\gamma^{\star}(\rho)\triangleq\frac{1}{2^{k}}\sum_{Q\in\\{X,Y,Z\\}^{\otimes
k}}\operatorname{tr}(Q\rho)^{2}.$ (171)

Non-identity purity is bounded by purity,
$\gamma^{\star}(\rho)\leq\gamma(\rho)=\operatorname{tr}(\rho^{2})=\frac{1}{2^{k}}\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes
k}}\operatorname{tr}(Q\rho)^{2}$.

######  Lemma 14 (Mean squared error).

Given two $n$-qubit observables $O_{1},O_{2}$ with

$O_{1}-O_{2}=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}\Delta\alpha_{P}P,$ (172)

and a distribution $\mathcal{D}$ over quantum states that is invariant under
single-qubit $H$ and $S$ gates. We have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|^{2}=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{\star}\left(\rho_{\mathsf{dom}(P)}\right)\right]\left(\frac{2}{3}\right)^{|P|}\left|\Delta\alpha_{P}\right|^{2}.$
(173)

###### Proof.

Consider $U_{1},\ldots,U_{n}$ to be independent random single-qubit Clifford
unitaries. Because $\mathcal{D}$ is invariant under single-qubit Hadamard and
phase gates, $\mathcal{D}$ is invariant under any tensor product of single-
qubit Clifford unitaries. This implies that the distribution of the random
state $\rho$ is the same as the distribution of the random state
$(U_{1}\otimes\ldots\otimes U_{n})\rho(U_{1}\otimes\ldots\otimes
U_{n})^{\dagger}$. Using this fact, we expand the mean squared error as

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|^{2}$
(174)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname*{{\mathbb{E}}}_{U_{1},\ldots,U_{n}}\sum_{P,Q\in\\{I,X,Y,Z\\}^{\otimes
n}}\Delta\alpha_{P}\Delta\alpha_{Q}\operatorname{tr}\left(\left(\bigotimes_{i=1}^{n}U_{i}^{\dagger}P_{i}U_{i}\right)\otimes\left(\bigotimes_{i=1}^{n}U_{i}^{\dagger}Q_{i}U_{i}\right)(\rho\otimes\rho)\right).$
(175)

Using the unitary $2$-design property of random Clifford unitary and
$\mathrm{SWAP}=\frac{1}{2}\sum_{P\in\\{I,X,Y,Z\\}}P\otimes P$, we have

$\operatorname*{{\mathbb{E}}}_{U_{i}}\big{[}U_{i}^{\dagger}P_{i}U_{i}\otimes
U_{i}^{\dagger}Q_{i}U_{i}\big{]}=\begin{cases}I\otimes I,&P_{i}=Q_{i}=I,\\\
\frac{1}{3}\left(X\otimes X+Y\otimes Y+Z\otimes Z\right),&P_{i}=Q_{i}\neq
I,\\\ 0,&P_{i}\neq Q_{i}.\end{cases}$ (176)

We can now write the target value as

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|^{2}=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\frac{1}{3^{|P|}}\left|\Delta\alpha_{P}\right|^{2}\sum_{Q\in\\{X,Y,Z\\}^{\otimes|P|}}\operatorname{tr}(Q\rho_{\mathsf{dom}(P)})^{2}.$
(177)

The claim follows from Definition 6 on non-identity purity $\gamma^{\star}$. ∎

The following lemma tells us that the mean absolute error can be upper bounded
by the root mean squared error. Hence, both the mean absolute error and the
mean squared error are characterized by the $\ell_{2}$ distance between the
Pauli coefficients (as well as the average non-identity purity). Due to the
following relation, we will focus on the mean squared error throughout the
text.

######  Lemma 15 (Mean absolute error).

Given two $n$-qubit observables $O_{1},O_{2}$ with

$O_{1}-O_{2}=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}\Delta\alpha_{P}P,$ (178)

and a distribution $\mathcal{D}$ over quantum states that is invariant under
single-qubit $H$ and $S$ gates. We have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|\leq\left(\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{\star}\left(\rho_{\mathsf{dom}(P)}\right)\right]\left(\frac{2}{3}\right)^{|P|}\left|\Delta\alpha_{P}\right|^{2}\right)^{1/2}.$
(179)

###### Proof.

Jensen’s inequality gives

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|\leq\left(\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\right|^{2}\right)^{1/2}.$
(180)

Combining with Lemma 14 yields the stated result. ∎

From Lemma 14, we can construct a low-degree approximation by removing all
high-weight Pauli terms for any observable $O$. The approximation error decays
exponentially with the weight of the Pauli terms.

######  Corollary 13 (Low-degree approximation).

Given an $n$-qubit observable $O=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\alpha_{P}P$ and a distribution $\mathcal{D}$ over quantum states that is
invariant under single-qubit $H$ and $S$ gates. For $k>0$, consider
$O^{(k)}=\sum_{P:|P|<k}\alpha_{P}P$. We have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O\rho)-\operatorname{tr}(O^{(k)}\rho)\right|^{2}\leq\left(\frac{2}{3}\right)^{k}\left\lVert
O\right\rVert^{2}.$ (181)

###### Proof.

Using Lemma 14 and the fact that
$\gamma^{\star}(\varrho)\leq\gamma(\varrho)\leq 1$ for any state $\varrho$, we
have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(O\rho)-\operatorname{tr}(O^{(k)}\rho)\right|^{2}\leq\sum_{P:|P|\geq
k}\left(\frac{2}{3}\right)^{|P|}|\alpha_{P}|^{2}\leq\left(\frac{2}{3}\right)^{k}\sum_{P}|\alpha_{P}|^{2}.$
(182)

The norm inequality given in Prop. 1 establishes the claim. ∎

###  D.2 Tools for extracting and filtering Pauli coefficients

In order to learn the low-degree approximation of an arbitrary observable $O$,
we need to be able to extract the relevant $\alpha_{P}$. Furthermore, we will
impose criteria for filtering out uninfluential Pauli observables $P$ to
prevent them from increasing the noise and leading to a higher prediction
error.

####  D.2.1 Extracting Pauli coefficient

######  Lemma 16 (Extracting Pauli coefficient).

Given an $n$-qubit observable $O=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\alpha_{P}P$ and a distribution $\mathcal{D}$ over quantum states that is
invariant under single-qubit $H$ and $S$ gates. For any Pauli observable
$P\in\\{I,X,Y,Z\\}^{\otimes n}$, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\left(\frac{2}{3}\right)^{|P|}\alpha_{P}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)}).$
(183)

###### Proof.

Using the invariance of $\mathcal{D}$, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname*{{\mathbb{E}}}_{U_{1},\ldots,U_{n}}\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}\alpha_{Q}\operatorname{tr}\left(\left(\bigotimes_{i=1}^{n}U_{i}^{\dagger}P_{i}U_{i}\right)\otimes\left(\bigotimes_{i=1}^{n}U_{i}^{\dagger}Q_{i}U_{i}\right)(\rho\otimes\rho)\right).$
(184)

Using Eq. (176), we can rewrite the above expression as

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\frac{1}{3^{|P|}}\alpha_{P}\sum_{Q\in\\{X,Y,Z\\}^{\otimes|P|}}\operatorname{tr}(Q\rho_{\mathsf{dom}(P)})^{2}.$
(185)

The claim follows from the definition of the non-identity purity $\gamma^{*}$.
∎

For each Pauli observable $P\in\\{I,X,Y,Z\\}^{\otimes n}$, define the quantity
we can extract using the lemma to be

$x_{P}=\left(\frac{2}{3}\right)^{|P|}\alpha_{P}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)}).$
(186)

We can obtain an estimate $\hat{x}_{P}$ for $x_{P}$ by averaging
$\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)$ over the training data.
However, to obtain an estimate $\hat{\alpha}_{P}$ for $\alpha_{P}$, we need to
divide $\hat{x}$ by
$\left(\frac{2}{3}\right)^{|P|}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)})$.
The error in the estimate $\hat{\alpha}_{P}$ could be arbitrarily large if
$\left(\frac{2}{3}\right)^{|P|}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)})$
is close to zero. Hence, we present a filter in Section D.2.2 to handle this
issue. In addition to this filter, the norm inequalities given in Section B
show that most $\alpha_{P}$ would be close to zero. Hence, when $\alpha_{P}$
is small, we could simply set them to zero to avoid noise build-up. This gives
rise to the second filtering layer given in Section D.2.3.

####  D.2.2 Filtering small weight factor

The first filter sets the estimate $\hat{\alpha}_{P}$ to be zero when the
average non-identity purity
$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)})$
is close to zero. We define the weight factor for a Pauli observable $P$ to be

$\beta_{P}=\left(\frac{2}{3}\right)^{|P|}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\gamma^{*}(\rho_{\mathsf{dom}(P)}).$
(187)

The weight factor $\beta_{P}$ depends on the distribution $\mathcal{D}$, which
may be unknown. Hence, we can only obtain an estimate $\hat{\beta}_{P}$ for
$\beta_{P}$ by utilizing the training data. Recall from Lemma 16, we can only
obtain an estimate $\hat{x}_{P}$ for $x_{P}=\alpha_{P}\beta_{P}$. The mean
squared error (Lemma 14) shows that the contribution from error in
$\hat{\alpha}_{P}$ is

$\beta_{P}\left|\hat{\alpha}_{P}-\alpha_{P}\right|^{2}.$ (188)

The presence of $\beta_{P}$ in the mean squared error is very useful since it
counteracts the fact that we cannot estimate $\hat{\alpha}_{P}$ accurately
when $\beta_{P}$ is close to zero. The following lemma shows that estimates
for $\beta_{P}$ and $x_{P}$ are sufficient to perform filtering and achieve a
small mean squared error.

######  Lemma 17 (Filtering small weight factor).

Given $\tilde{\epsilon},\eta>0$. Consider $\alpha\in[-\eta,\eta]$, and
$\beta\in[0,1]$. Let $x=\alpha\beta\in[-\eta,\eta]$. Given estimates $\hat{x}$
and $\hat{\beta}$ with $|\hat{x}-x|<\eta\tilde{\epsilon}$ and
$|\hat{\beta}-\beta|<\tilde{\epsilon}$. If we define the estimate

$\hat{\alpha}=\begin{cases}0,&\hat{\beta}\leq 2\tilde{\epsilon},\\\
\hat{x}/\hat{\beta},&\hat{\beta}>2\tilde{\epsilon},\end{cases}$ (189)

then we have $\beta|\hat{\alpha}-\alpha|^{2}\leq 3\eta^{2}\tilde{\epsilon}$.

###### Proof.

Consider the first case of $\hat{\beta}\leq 2\tilde{\epsilon}$. We have

$\beta|\hat{\alpha}-\alpha|^{2}=\beta\alpha^{2}\leq\eta^{2}\beta\leq\eta^{2}\hat{\beta}+\eta^{2}\tilde{\epsilon}\leq
3\eta^{2}\tilde{\epsilon}.$ (190)

For the second case of $\hat{\beta}>2\tilde{\epsilon}$, we have
$\beta>\tilde{\epsilon}$. By applying triangle inequality, we have

$\left|\sqrt{\beta}\hat{\alpha}-\sqrt{\beta}\alpha\right|\leq\frac{\sqrt{\beta}}{\hat{\beta}}\left|\hat{x}-x\right|+\left|\sqrt{\beta}x\right|\left|\frac{1}{\hat{\beta}}-\frac{1}{\beta}\right|.$
(191)

The first term can be bounded as
$\frac{\sqrt{\beta}}{\hat{\beta}}\left|\hat{x}-x\right|\leq\eta\frac{\sqrt{\beta}}{\hat{\beta}}\tilde{\epsilon}$.
The second term can be bounded by the same expression

$\left|\sqrt{\beta}x\right|\left|\frac{1}{\hat{\beta}}-\frac{1}{\beta}\right|=\beta^{3/2}|\alpha|\frac{|\hat{\beta}-\beta|}{\hat{\beta}\beta}\leq\eta\frac{\sqrt{\beta}}{\hat{\beta}}\tilde{\epsilon}.$
(192)

Using the fact that $\sqrt{z+\tilde{\epsilon}}/z$ is monotonically decreasing
for $z>0$, we have

$\frac{\sqrt{\beta}}{\hat{\beta}}\tilde{\epsilon}\leq\frac{\sqrt{\hat{\beta}+\tilde{\epsilon}}}{\hat{\beta}}\tilde{\epsilon}\leq\sqrt{\frac{3}{4}\tilde{\epsilon}}.$
(193)

Together, $\left|\sqrt{\beta}\hat{\alpha}-\sqrt{\beta}\alpha\right|^{2}\leq
3\eta^{2}\tilde{\epsilon}$ and the claim is established. ∎

####  D.2.3 Filtering uninfluential Pauli observables

Consider a set $S\subseteq\\{I,X,Y,Z\\}^{\otimes n}$ that contains the Pauli
observables of interest. For example, we will later consider $S$ to be the set
of all few-body Pauli observables. Using the norm inequalities given in
Appendix B, we can filter out more $\alpha_{P}$ to achieve an improved mean
squared error. Below is the filtering lemma that combines both the filtering
of Pauli observables with a small weight factor (Lemma 17) and the filtering
of those with a small contribution (characterized by
$|x_{P}|/\beta_{P}^{1/2}$).

######  Lemma 18 (Filtering lemma).

Given $\tilde{\epsilon},\eta>0,$ and a set $S\subseteq\\{I,X,Y,Z\\}^{\otimes
n}$. Consider $\alpha_{P}\in[-\eta,\eta]$, $\beta_{P}\in[0,1]$,
$x_{P}=\alpha_{P}\beta_{P}\in[-\eta,\eta]$ for all $P\in S$. Suppose there
exists $A>0$ and $1\leq r<2$, such that

$\sum_{P\in S}|\alpha_{P}|^{r}\leq A^{r}.$ (194)

Given $\hat{x}_{P}$ and $\hat{\beta}_{P}$ with
$|\hat{x}_{P}-x_{P}|<\eta\tilde{\epsilon}$ and
$|\hat{\beta}_{P}-\beta_{P}|<\tilde{\epsilon}$ for all $P\in S$. If we define

$\hat{\alpha}_{P}=\begin{cases}0,&\hat{\beta}_{P}\leq 2\tilde{\epsilon},\\\
0,&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}\leq
2\eta\sqrt{\tilde{\epsilon}},\\\
\hat{x}_{P}/\hat{\beta}_{P},&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}},\end{cases}$
(195)

then we have $\sum_{P\in S}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
6A^{r}\eta^{2-r}\tilde{\epsilon}^{1-(r/2)}$. We also have
$\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
9\eta^{2}\tilde{\epsilon},\forall P\in S$.

###### Proof.

We first define $S^{u}\subseteq S$ to be the set of Pauli observables $P$ with
$\hat{\beta}_{P}>2\tilde{\epsilon},|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}}$.
The set $S^{u}$ contains all the unfiltered Pauli observables. We define
$S^{f}$ to be $S\setminus S^{u}$, which contains all the filtered Pauli
observables. We separate the contribution of $S^{u}$ and $S^{f}$ in the mean
squared error $\sum_{P\in S}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}$,

$\sum_{P\in S}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}=\sum_{P\in
S^{u}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}+\sum_{P\in
S^{f}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}.$ (196)

A key quantity for the analysis is
$\beta_{P}^{1/2}\alpha_{P}=x_{P}/\beta_{P}^{1/2}$. For Pauli $P$ with
$\hat{\beta}_{P}\leq 2\tilde{\epsilon}$, we have

$|\beta_{P}^{1/2}\alpha_{P}|\leq\eta\sqrt{\hat{\beta}_{P}+\tilde{\epsilon}}\leq\eta\sqrt{3\tilde{\epsilon}}.$
(197)

For Pauli $P$ with $\hat{\beta}_{P}>2\tilde{\epsilon}$, we have

$\left|\frac{\hat{x}_{P}}{\hat{\beta}_{P}^{1/2}}-\frac{x_{P}}{\beta_{P}^{1/2}}\right|\leq\frac{1}{\hat{\beta}_{P}^{1/2}}\left|\hat{x}_{P}-x_{P}\right|+|x_{P}|\left|\frac{1}{\hat{\beta}_{P}^{1/2}}-\frac{1}{\beta_{P}^{1/2}}\right|\leq\eta\sqrt{\frac{\tilde{\epsilon}}{2}}+\eta\left|\frac{\beta_{P}}{\hat{\beta}_{P}^{1/2}}-\beta_{P}^{1/2}\right|\leq\eta\sqrt{\tilde{\epsilon}}.$
(198)

The last inequality uses the fact that $\beta_{P}>\tilde{\epsilon}$,
$\hat{\beta}_{P}/\beta_{P}>2$, and hence

$\left|\frac{\beta_{P}}{\hat{\beta}_{P}^{1/2}}-\beta_{P}^{1/2}\right|=\frac{\left|\hat{\beta}_{P}-\beta_{P}\right|}{\hat{\beta}_{P}^{1/2}\left(1+\left(\frac{\hat{\beta}_{P}}{\beta_{P}}\right)^{1/2}\right)}\leq\frac{\sqrt{\tilde{\epsilon}}}{2+\sqrt{2}}.$
(199)

We are now ready to analyze the contributions of $S^{u}$ and $S^{f}$.

For the unfiltered Pauli observables (those in set $S^{u}$), we can use Lemma
17 to obtain

$\sum_{P\in S^{u}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
3\eta^{2}\tilde{\epsilon}|S^{u}|.$ (200)

Eq. (198) shows that for Pauli observable $P$ with
$\hat{\beta}_{P}>2\tilde{\epsilon}$ and
$|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}}$, we have
$|x_{P}|/\beta_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}}-\eta\sqrt{\tilde{\epsilon}}.$
We will use this fact to bound the size of the set $|S^{u}|$,

$|S^{u}|\leq\sum_{P\in
S^{u}}\frac{(|x_{P}|/\beta_{P}^{1/2})^{r}}{\left(2\eta\sqrt{\tilde{\epsilon}}-\eta\sqrt{\tilde{\epsilon}}\right)^{r}}=\frac{1}{\eta^{r}\tilde{\epsilon}^{r/2}}\sum_{P\in
S^{u}}|\alpha_{P}|^{r}\beta_{P}^{r/2}\leq\frac{1}{\eta^{r}\tilde{\epsilon}^{r/2}}\sum_{P\in
S}|\alpha_{P}|^{r}=\frac{A^{r}}{\eta^{r}\tilde{\epsilon}^{r/2}}.$ (201)

Together, we have the following upper bound,

$\sum_{P\in S^{u}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
3\eta^{2-r}A^{r}\tilde{\epsilon}^{1-(r/2)}.$ (202)

For the filtered Pauli observables (those in set $S^{f}$), we have

$\sum_{P\in S^{f}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}=\sum_{P\in
S^{f}}\left|\beta_{P}^{1/2}\alpha_{P}\right|^{r}\left|\beta_{P}^{1/2}\alpha_{P}\right|^{2-r}.$
(203)

There are two types of Pauli observables in $S^{f}$.

  1. 1.

For $P$ with $\hat{\beta}_{P}\leq 2\tilde{\epsilon}$, we have
$\left|\beta_{P}^{1/2}\alpha_{P}\right|\leq\eta\sqrt{3\tilde{\epsilon}}$ from
Eq. (197).

  2. 2.

For $P$ with $\hat{\beta}_{P}>2\tilde{\epsilon}$ and
$|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}\leq\eta 2\sqrt{\tilde{\epsilon}}$, we
have $\left|\beta_{P}^{1/2}\alpha_{P}\right|=|x_{P}|/\beta_{P}^{1/2}\leq
2\eta\sqrt{\tilde{\epsilon}}+\eta\sqrt{\tilde{\epsilon}}$ from Eq. (198).

Together, we have the following upper bound,

$\sum_{P\in
S^{f}}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq(3\eta\sqrt{\tilde{\epsilon}})^{2-r}\sum_{P\in
S^{f}}\beta_{P}^{r/2}\left|\alpha_{P}\right|^{r}\leq
A^{r}(3\eta\sqrt{\tilde{\epsilon}})^{2-r}\leq
3A^{r}\eta^{2-r}\tilde{\epsilon}^{1-(r/2)}.$ (204)

Combining the contribution of $S^{u}$ and $S^{f}$ yields

$\sum_{P\in S}\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
6A^{r}\eta^{2-r}\tilde{\epsilon}^{1-(r/2)}.$ (205)

Thus we have established the first statement of the lemma.

We now focus on the second statement of the lemma. For Pauli observable $P$
that satisfies the first and the third cases of Eq. (195), we can use Lemma 17
to obtain $\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq
3\eta^{2}\tilde{\epsilon}<9\eta^{2}\tilde{\epsilon}$. For the second case of
Eq. (195), we can use Eq. (198) to see that

$\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}=\left(\frac{x_{P}}{\beta_{P}^{1/2}}\right)^{2}\leq\left(\frac{|\hat{x}_{P}|}{\hat{\beta}_{P}^{1/2}}+\left|\frac{\hat{x}_{P}}{\hat{\beta}_{P}^{1/2}}-\frac{x_{P}}{\beta_{P}^{1/2}}\right|\right)^{2}\leq
9\eta^{2}\tilde{\epsilon}.$ (206)

Hence, for all $P\in S$, we have
$\beta_{P}|\hat{\alpha}_{P}-\alpha_{P}|^{2}\leq 9\eta^{2}\tilde{\epsilon}$. ∎

###  D.3 Learning algorithm

In this section, we present a learning algorithm satisfying the guarantee
given in Theorem 13. Consider the full training data
$\\{\rho_{\ell},y_{\ell}=\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\\}_{\ell=1}^{N}$
of size $N$. The learning algorithm splits the full data into a smaller
training set of size $N_{\mathrm{tr}}$ and a validation set of size
$N_{\mathrm{val}}$ with $N=N_{\mathrm{tr}}+N_{\mathrm{val}}$. The training set
is used to extract Pauli coefficients and perform filtering with a
hyperparameter $\eta$. The validation set is used to choose the best
hyperparameter $\eta$. We can set $N_{\mathrm{tr}}=(4/5)N$ and
$N_{\mathrm{val}}=(1/5)N$.

We consider two slightly different learning algorithms for the sample
complexity scaling of

$N=\log\left(\frac{n}{\delta}\right)\,2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)}\quad\mbox{and}\quad
N=\log\left(\frac{n}{\delta}\right)\,2^{\mathcal{O}(\log(\frac{1}{\epsilon})\log(n))}.$
(207)

We can simply look at which sample complexity is smaller and select the
corresponding learning algorithm.

We begin with the learning algorithm for achieve the sample complexity on the
left of Eq. (207). First, the algorithm computes the sample maximum over the
training set,

$\hat{\Theta}=\max_{\ell\in\\{1,\ldots,N_{\mathrm{tr}}\\}}\left|y_{\ell}\right|=\max_{\ell\in\\{1,\ldots,N_{\mathrm{tr}}\\}}\left|\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\right|\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert.$ (208)

to obtain a scale for the function value. Let $C(k)$ be the constant from
Corollary 11. We define

$\tilde{\epsilon}\triangleq\left(\frac{\epsilon^{\prime}}{12}\right)^{k+1}\left(\frac{C(k)}{3}\right)^{2k}.$
(209)

Next, we consider the following grid of hyperparameters,

$\eta\in\left\\{2^{0}\hat{\Theta},2^{1}\hat{\Theta},2^{2}\hat{\Theta}\ldots,2^{R}\hat{\Theta}\right\\},$
(210)

where $R=\log_{2}\lceil 1/\tilde{\epsilon}\rceil$. For each hyperparameter
$\eta$, the learning algorithm runs the following. The learning algorithm
considers every Pauli observable $P\in\\{I,X,Y,Z\\}^{\otimes n}$ with
$|P|\leq\log_{1.5}(1/\epsilon)$. We define the set that contains the Pauli
observables of interest,

$S=\left\\{P:|P|\leq\log_{1.5}(1/\epsilon)\right\\},$ (211)

and $k=\lceil\log_{1.5}(1/\epsilon)\rceil$. For each $P\in S$, the algorithm
computes

$\displaystyle\hat{x}_{P}$
$\displaystyle=\frac{1}{N_{\mathrm{tr}}}\sum_{\ell=1}^{N_{\mathrm{tr}}}\operatorname{tr}(P\rho_{\ell})y_{\ell},$
(212) $\displaystyle\hat{\beta}_{P}$
$\displaystyle=\frac{1}{N_{\mathrm{tr}}}\sum_{\ell=1}^{N_{\mathrm{tr}}}\operatorname{tr}(P\rho_{\ell})\operatorname{tr}(P\rho_{\ell}),$
(213)

using the training set
$\\{(\rho_{\ell},y_{\ell}=\operatorname{tr}(O^{\mathrm{unk}\rho_{\ell}}))\\}_{\ell=1}^{N_{\mathrm{tr}}}$.
By definition of $\hat{x}_{P}$ and $\hat{\Theta}$, we have

$\left|\hat{x}_{P}\right|\leq\hat{\Theta},\quad\forall P\in S.$ (214)

Then, for each $P\in S$, the algorithm computes

$\hat{\alpha}_{P}(\eta)=\begin{cases}0,&\hat{\beta}_{P}\leq
2\tilde{\epsilon},\\\
0,&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}\leq
2\eta\sqrt{\tilde{\epsilon}},\\\
\hat{x}_{P}/\hat{\beta}_{P},&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}|/\hat{\beta}_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}},\end{cases}$
(215)

The algorithm considers the function
$h(\rho;\eta)=\max(-\hat{\Theta},\min(\hat{\Theta},\operatorname{tr}(\hat{O}(\eta)\rho)))$,
where the observable $\hat{O}(\eta)$ is defined as follows,

$\hat{O}(\eta)=\sum_{P\in S}\hat{\alpha}_{P}(\eta)P.$ (216)

The best $\eta$ is selected using the validation set,

$\eta^{*}=\operatorname*{arg\,min}_{\eta\in\\{2^{0}\hat{\Theta},\ldots,2^{R}\hat{\Theta}\\}}\frac{1}{N_{\mathrm{val}}}\sum_{\ell=N_{\mathrm{tr}}+1}^{N_{\mathrm{tr}}+N_{\mathrm{val}}}\left|h(\rho_{\ell};\eta)-y_{\ell}\right|^{2}.$
(217)

The learning algorithm outputs $h(\rho;\eta^{*})$ as the learned function.

We now present the learning algorithm for achieving the sample complexity on
the right of Eq. (207). We define the set that contains the Pauli observables
of interest,

$S^{\prime}=\left\\{P:|P|\leq\log_{1.5}(2/\epsilon)\right\\},$ (218)

and $k^{\prime}=\lceil\log_{1.5}(2/\epsilon)\rceil$. For each $P\in
S^{\prime}$, the algorithm computes

$\displaystyle\hat{x}_{P}^{\prime}$
$\displaystyle=\frac{1}{N}\sum_{\ell=1}^{N}\operatorname{tr}(P\rho_{\ell})y_{\ell},$
(219) $\displaystyle\hat{\beta}_{P}^{\prime}$
$\displaystyle=\frac{1}{N}\sum_{\ell=1}^{N}\operatorname{tr}(P\rho_{\ell})\operatorname{tr}(P\rho_{\ell}),$
(220)

using the full dataset
$\\{(\rho_{\ell},y_{\ell}=\operatorname{tr}(O^{\mathrm{unk}\rho_{\ell}}))\\}_{\ell=1}^{N}$.
The algorithm uses the following hyperparameter

$\tilde{\epsilon}^{\prime}\triangleq\frac{\epsilon}{6n^{k^{\prime}}}.$ (221)

Then, for each $P\in S^{\prime}$, the algorithm computes

$\hat{\alpha}_{P}^{\prime}=\begin{cases}0,&\hat{\beta}_{P}^{\prime}\leq
2\tilde{\epsilon}^{\prime},\\\
\hat{x}_{P}^{\prime}/\hat{\beta}_{P}^{\prime},&\hat{\beta}_{P}^{\prime}>2\tilde{\epsilon}^{\prime}.\end{cases}$
(222)

The algorithm outputs the function
$h^{\prime}(\rho)=\operatorname{tr}(\hat{O}^{\prime}\rho)$, where the
observable $\hat{O}^{\prime}$ is defined as $\hat{O}^{\prime}=\sum_{P\in
S^{\prime}}\hat{\alpha}_{P}^{\prime}P.$

Here, we assume that $\operatorname{tr}(P\rho_{\ell})$ can be obtained from
the training data. However, for each $\operatorname{tr}(P\rho_{\ell})$, we
only need to be able to obtain an unbiased estimator for
$\operatorname{tr}(P\rho_{\ell})$ and for
$\operatorname{tr}(P\rho_{\ell})^{2}$. Recall that an unbiased estimator for
$a$ is a random variable with expectation value equal to $a$. For example, an
unbiased estimator for $\operatorname{tr}(P\rho_{\ell})^{2}$ can be obtained
by performing two quantum measurements on two individual copies of
$\rho_{\ell}$ using the observable $P$ and multiplying the results, or by
utilizing classical shadow formalism [46] and randomized measurement [47].

###  D.4 Rigorous performance guarantee

In this section, we prove that the learning algorithm presented in the last
section satisfies Theorem 13. We separate the proof for achieving the sample
complexity on the left and right of Eq. (207).

The proof for the sample complexity stated on the left of Eq. (207) consists
of three parts: (1) a characterization of the prediction error, (2) the
existence of a good hyperparamter $\eta^{\triangle}$ that achieves a small
prediction error, (3) the hyperparameter $\eta^{*}$ found through grid search
on the validation set has a small prediction error.

The proof for the sample complexity stated on the right of Eq. (207) is
simpler and is given at the end.

####  D.4.1 Characterization of the prediction error

We begin with a lemma about the sample maximum.

######  Lemma 19 (Sample maximum).

Given $1>\epsilon,\delta>0$. Consider an arbitrary real-valued random variable
$X$. Let $X_{1},\ldots,X_{N}$ be $N$ independent samples of $X$ with
$N=\lceil\log(1/\delta)/\epsilon\rceil$ and let $\hat{\Theta}=\max_{i}X_{i}$.
Then

$\Pr\left[X\leq\hat{\Theta}\right]\geq 1-\epsilon.$ (223)

with probability at least $1-\delta$.

###### Proof.

Recall that the cumulative distribution function is defined as
$F(\theta)=\Pr\left[X\leq\theta\right]$. We define the approximate maximum as
follows,

$\Theta\triangleq\inf_{\theta:F(\theta)\geq 1-\epsilon}\theta.$ (224)

Using the right-continuity of $F(\theta)=\Pr\left[X\leq\theta\right]$, we have

$F(\Theta)=\Pr\left[X\leq\Theta\right]\geq 1-\epsilon.$ (225)

Furthermore, from the definition of $\Theta$, we have

$\Pr\left[X\geq\Theta\right]\geq\epsilon.$ (226)

To see the above inequality, suppose that
$\Pr\left[X\geq\Theta\right]<\epsilon$. Then from the left-continuity of
$F^{\prime}(\theta)=\Pr\left[X\geq\theta\right]$, we can find
$\Theta^{\prime}<\Theta$, such that
$\Pr\left[X\geq\Theta^{\prime}\right]\leq\epsilon$. Thus, there exists
$\Theta^{\prime}<\Theta$ with $\Pr\left[X\leq\Theta^{\prime}\right]\geq
1-\epsilon$, which is a contradiction to the definition of $\Theta$. Together,
we have

$\Pr\left[X_{i}<\Theta,\forall i\in[N]\right]\leq(1-\epsilon)^{N}.$ (227)

By choosing $N=\lceil\log(1/\delta)/\epsilon\rceil$, we have

$\Pr\left[\max_{i}X_{i}\geq\Theta\right]\geq
1-(1-\epsilon)^{\log(1/\delta)/\epsilon}\geq 1-\delta.$ (228)

Thus with probability at least $1-\delta$, we have $\hat{\Theta}\geq\Theta$.
Using the monotonicity of $F(\theta)$, we have

$\Pr\left[X\leq\hat{\Theta}\right]=F(\hat{\Theta})\geq F(\Theta)\geq
1-\epsilon,$ (229)

which establishes this lemma. ∎

Using the above lemma, we can show that given a training set of size

$N_{\mathrm{tr}}\geq\frac{12\log(3/\delta)}{\epsilon^{\prime}},$ (230)

the real value $\hat{\Theta}\leq\left\lVert O^{\mathrm{(unk)}}\right\rVert$
obtained by the algorithm satisfies

$\Pr_{\rho\sim\mathcal{D}}\left[\left|\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|\leq\hat{\Theta}\right]\geq
1-\frac{\epsilon^{\prime}}{12}$ (231)

with probability at least $1-(\delta/3)$. Hence, with probability at least
$1-(\delta/3)$, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(\hat{O}(\eta)\rho)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}+\frac{\epsilon^{\prime}}{12}\left|\hat{\Theta}+\left\lVert
O^{\mathrm{(unk)}}\right\rVert\right|^{2}.$ (232)

Using Lemma 14 on mean squared error and Corollary 13 on low-degree
approximation, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}$
(233) $\displaystyle\leq\underbrace{(2/3)^{k}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}}_{\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\epsilon}+\sum_{P\in
S}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(\eta)-\alpha_{P}\right|^{2}+\frac{\epsilon^{\prime}}{3}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}$ (234)

with probability at least $1-(\delta/3)$.

Let us define the following variables,

$x_{P}\triangleq\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\alpha_{P},\quad\beta_{P}\triangleq\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|},\quad\forall
P\in S.$ (235)

Then, with probability at least $1-(\delta/3)$ over the sampling of the
training set, we have the following characterization of the prediction error
for all $\eta>0$,

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\epsilon\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\frac{\epsilon^{\prime}}{3}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\sum_{P\in
S}\beta_{P}\left|\hat{\alpha}_{P}(\eta)-\alpha_{P}\right|^{2}.$ (236)

We will utilize this form to show the existence of a good hyperparameter
$\eta^{\triangle}$.

####  D.4.2 Existence of a good hyperparamter $\eta^{\triangle}$

By considering the training set size to be

$N_{\mathrm{tr}}=\Omega\left(\frac{\log(1/\delta)}{\epsilon^{\prime}}+\frac{\log(|S|/\delta)}{\tilde{\epsilon}^{2}}\right),$
(237)

we can guarantee Eq. (236) with probability at least $1-(\delta/3)$.
Furthermore, utilizing Hoeffding’s inequality and union bound, we could also
guarantee that

$\left|\hat{x}_{P}-x_{P}\right|\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert\tilde{\epsilon},\quad\left|\hat{\beta}_{P}-\beta_{P}\right|\leq\tilde{\epsilon},\quad\forall
P\in S$ (238)

with probability at least $1-(\delta/3)$. The norm inequality given in
Corollary 11 shows that

$\sum_{P\in
S}\left|\alpha_{P}\right|^{r}\leq\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}$ (239)

for a constant given by

$C(k)=\frac{\sqrt{2(k!)}}{2k^{k+1.5+(k+1)/(2k)}(\sqrt{6}+2\sqrt{3})^{k}}.$
(240)

We now condition on the event that Eq. (236) and Eq. (238) both hold, which
happens with probability at least $1-(2/3)\delta$. We are now ready to define
the good hyperparameter $\eta^{\triangle}$.

Let hyperparameter $\eta^{\triangle}$ belonging to the grid in Eq. (210) be
defined as follows,

$\eta^{\triangle}=2^{\min\left(R,\left\lceil\log_{2}\left(\left\lVert
O^{\mathrm{(unk)}}\right\rVert/\hat{\Theta}\right)\right\rceil\right)}\hat{\Theta}.$
(241)

We separately consider two cases: (1) $\eta^{\triangle}=2^{R}\hat{\Theta}$,
(2) $\eta^{\triangle}<2^{R}\hat{\Theta}$. For the first case
$\eta^{\triangle}=2^{R}\hat{\Theta}$, we can use
$|\hat{x}_{P}|\leq\hat{\Theta}$ in Eq. (214) and the definition of $R$ to see
that

$\hat{\alpha}_{P}(\eta^{\triangle})=0,\quad\forall P\in S.$ (242)

Since $\eta^{\triangle}=2^{R}\hat{\Theta}$, we have
$R\leq\left\lceil\log_{2}\left(\left\lVert
O^{\mathrm{(unk)}}\right\rVert/\hat{\Theta}\right)\right\rceil$. This yields
$\eta^{\triangle}\leq 2\left\lVert O^{\mathrm{(unk)}}\right\rVert$, which
implies that

$\hat{\alpha}_{P}\left(2\left\lVert
O^{\mathrm{(unk)}}\right\rVert\right)=0,\quad\forall P\in S.$ (243)

Hence, the reconstructed Pauli coefficients $\hat{\alpha}_{P}(\cdot)$ are the
same for $\eta^{\triangle}$ and $2\left\lVert O^{\mathrm{(unk)}}\right\rVert$.
The filtering lemma given in Lemma 18 shows that

$\displaystyle\sum_{P\in
S}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(\eta^{\triangle})-\alpha_{P}\right|^{2}$
(244) $\displaystyle=\sum_{P\in
S}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}\left(2\left\lVert
O^{\mathrm{(unk)}}\right\rVert\right)-\alpha_{P}\right|^{2}$ (245)
$\displaystyle\leq 12\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2-r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}\tilde{\epsilon}^{1-(r/2)}.$ (246)

For the second case $\eta^{\triangle}<2^{R}\hat{\Theta}$, we have the
following bound on $\eta^{\triangle}$,

$\eta^{\triangle}=2^{\left\lceil\log_{2}\left(\left\lVert
O^{\mathrm{(unk)}}\right\rVert/\hat{\Theta}\right)\right\rceil}\hat{\Theta}\in\left[\left\lVert
O^{\mathrm{(unk)}}\right\rVert,2\left\lVert
O^{\mathrm{(unk)}}\right\rVert\right].$ (247)

The filtering lemma given in Lemma 18 shows that

$\displaystyle\sum_{P\in
S}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(\eta^{\triangle})-\alpha_{P}\right|^{2}$
$\displaystyle\leq
6(\eta^{\triangle})^{r}\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}\tilde{\epsilon}^{1-(r/2)}$ (248)
$\displaystyle\leq 12\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2-r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}\tilde{\epsilon}^{1-(r/2)}.$ (249)

In both case (1) and case (2), using the definition $r=2k/(k+1)$ and
$\tilde{\epsilon}=\left(\frac{\epsilon^{\prime}}{12}\right)^{k+1}\left(\frac{C(k)}{3}\right)^{2k}$,
we have

$\sum_{P\in
S}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(\eta^{\triangle})-\alpha_{P}\right|^{2}\leq\epsilon^{\prime}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2-r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}.$ (250)

Combining with Eq. (236), we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta^{\triangle})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\epsilon\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\frac{\epsilon^{\prime}}{3}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\epsilon^{\prime}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2-r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}$ (251)

with probability at least $1-(2/3)\delta$.

####  D.4.3 The prediction performance of the hyperparameter $\eta^{*}$

From the definition of $h(\rho;\eta)$, for any quantum state $\rho$, we have

$\left|h(\rho;\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho))\right|^{2}\leq\left|\hat{\Theta}+\left\lVert
O^{\mathrm{(unk)}}\right\rVert\right|^{2}\leq 4\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}$ (252)

Using Hoeffding’s inequality and union bound, we can show that given a
validation set of size

$N_{\mathrm{val}}=\Omega\left(\frac{\log(R/\delta)}{(\epsilon^{\prime})^{2}}\right),$
(253)

with probability at least $1-(\delta/3)$, we have

$\left|\frac{1}{N_{\mathrm{val}}}\sum_{\ell=N_{\mathrm{tr}}+1}^{N_{\mathrm{tr}}+N_{\mathrm{val}}}\left|h(\rho_{\ell};\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\right|^{2}-\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho))\right|^{2}\right|\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\frac{\epsilon^{\prime}}{3},$ (254)

for all $\eta\in\\{2^{0}\hat{\Theta},\ldots,2^{R}\hat{\Theta}\\}$. Using the
definition of $\eta^{*}$ and $\eta^{\triangle}$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta^{*})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho))\right|^{2}$
$\displaystyle\leq\frac{1}{N_{\mathrm{val}}}\sum_{\ell=N_{\mathrm{tr}}+1}^{N_{\mathrm{tr}}+N_{\mathrm{val}}}\left|h(\rho_{\ell};\eta^{*})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\right|^{2}+\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\frac{\epsilon^{\prime}}{3}$ (255)
$\displaystyle\leq\frac{1}{N_{\mathrm{val}}}\sum_{\ell=N_{\mathrm{tr}}+1}^{N_{\mathrm{tr}}+N_{\mathrm{val}}}\left|h(\rho_{\ell};\eta^{\triangle})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho_{\ell}))\right|^{2}+\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\frac{\epsilon^{\prime}}{3}$ (256)
$\displaystyle\leq\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta^{\triangle})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho))\right|^{2}+\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\frac{2\epsilon^{\prime}}{3}$ (257)

with probability at least $1-(\delta/3)$ over the sampling of the validation
set. Combining with Eq. (251) and employing union bound, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho;\eta^{*})-\operatorname{tr}(O^{\mathrm{(unk)}}\rho))\right|^{2}\leq\epsilon\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\epsilon^{\prime}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\epsilon^{\prime}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2-r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}$ (258)

with probability at least $1-\delta$, as claimed in Eq. (170).

Finally, by noting that $|S|=\mathcal{O}(n^{k})$ and
$k=\log_{1.5}(1/\epsilon)$ and recalling the definition of $\tilde{\epsilon}$
in Eq .(209) on the right-hand side of Eq. (237), we have

$\frac{\log(1/\delta)}{\epsilon^{\prime}}+\frac{\log(|S|/\delta)}{\tilde{\epsilon}^{2}}=\log\left(\frac{n}{\delta}\right)\left(\frac{1}{\epsilon^{\prime}}\right)^{k+1}2^{\mathcal{O}(k\log
k)}=\log\left(\frac{n}{\delta}\right)2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)}.$
(259)

So it suffices to have

$N_{\mathrm{val}}=\log\left(\frac{n}{\delta}\right)2^{\Omega\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)}.$
(260)

Furthermore, by noting that $R=\log_{2}\lceil
1/\tilde{\epsilon}\rceil=\mathcal{O}(k\log(\epsilon^{\prime})+k\log^{2}k)$ in
Eq. (253), we see that it suffices to have

$N_{\mathrm{val}}=\Omega\left(\frac{\log\log(\epsilon)+\log\log(\epsilon^{\prime})+\log(1/\delta)}{(\epsilon^{\prime})^{2}}\right).$
(261)

Recall that the full data size $N=N_{\mathrm{tr}}+N_{\mathrm{val}}$, and the
quantity in Eq. (261) is dominated by the one in Eq. (260), yielding one
argument in the minimum of the sample complexity claimed in Theorem 13.

####  D.4.4 Establishing sample complexity on the right of Eq. (207)

By considering the full dataset size to be

$N=\Omega\left(\frac{\log(|S^{\prime}|/\delta)}{(\tilde{\epsilon}^{\prime})^{2}}\right),$
(262)

Hoeffding’s inequality and union bound can be used to guarantee that

$\left|\hat{x}_{P}^{\prime}-x_{P}\right|\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert\tilde{\epsilon}^{\prime},\quad\left|\hat{\beta}_{P}^{\prime}-\beta_{P}\right|\leq\tilde{\epsilon}^{\prime},\quad\forall
P\in S^{\prime}$ (263)

with probability at least $1-\delta$. Using Lemma 17 on filtering small-weight
factor, we have

$\beta_{P}\left|\hat{\alpha}_{P}^{\prime}-\alpha_{P}\right|^{2}\leq
3\left\lVert O^{\mathrm{(unk)}}\right\rVert^{2}\tilde{\epsilon}^{\prime}.$
(264)

Using Lemma 14 on mean squared error and Corollary 13 on low-degree
approximation, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(\hat{O}^{\prime}\rho)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}$
$\displaystyle\leq(2/3)^{k}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\sum_{P\in
S^{\prime}}\beta_{P}\left|\hat{\alpha}_{P}^{\prime}-\alpha_{P}\right|^{2}$
(265) $\displaystyle\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\frac{\epsilon}{2}+3n^{k^{\prime}}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\tilde{\epsilon}^{\prime}.$ (266)

From the definition of $\tilde{\epsilon}^{\prime}$ in Eq. (221), we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|\operatorname{tr}(\hat{O}^{\prime}\rho)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\epsilon\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}.$ (267)

The sample complexity is

$N=\mathcal{O}\left(\frac{\log(|S^{\prime}|/\delta)}{(\tilde{\epsilon}^{\prime})^{2}}\right)=\log(n/\delta)\,2^{\mathcal{O}(\log(1/\epsilon)\log(n))},$
(268)

which completes the sample complexity claimed in Theorem 13.

##  APPENDIX E Learning quantum evolutions from randomized experiments

We recall the following definitions pertaining to classical shadows for
quantum states and quantum evolutions, based on randomized Pauli measurements
and random input states.

######  Definition 7 (Single-qubit stabilizer state).

We define

$\mathrm{stab}_{1}\triangleq\\{\ket{0},\ket{1},\ket{+},\ket{-},\ket{y+},\ket{y-}\\}$
(269)

to be the set of single-qubit stabilizer states.

We define randomized Pauli measurements as follows.

######  Definition 8 (Randomized Pauli measurement).

Given $n>0$. A randomized Pauli measurement on an $n$-qubit state is given by
a $6^{n}$-outcome POVM

$\mathcal{F}^{\mathrm{(Pauli)}}\triangleq\left\\{\frac{1}{3^{n}}\bigotimes_{i=1}^{n}\lvert
s_{i}\rangle\\!\langle
s_{i}\rvert\right\\}_{s_{1},\ldots,s_{n}\in\mathrm{stab}_{1}},$ (270)

which corresponds to measuring every qubit under a random Pauli basis
($X,Y,Z$). The outcome of $\mathcal{F}^{\mathrm{(Pauli)}}$ is an $n$-qubit
state $\ket{\psi}=\bigotimes_{i=1}^{n}\ket{s_{i}},$ where
$\ket{s_{i}}\in\mathrm{stab}_{1}$ is a single-qubit stabilizer state.

In the following, we define the classical shadow of a quantum state based on
randomized Pauli measurements. Classical shadows could also be defined based
on other randomized measurements [46].

######  Definition 9 (Classical shadow of a quantum state).

Given $n,N>0$. Consider an $n$-qubit state $\rho$. A size-$N$ classical shadow
$S_{N}(\rho)$ of quantum state $\rho$ is a random set given by

$S_{N}(\rho)\triangleq\left\\{\ket{\psi_{\ell}}\right\\}_{\ell=1}^{N},$ (271)

where $\ket{\psi_{\ell}}=\bigotimes_{i=1}^{n}\ket{s_{\ell,i}}$ is the outcome
of the $\ell$-th randomized Pauli measurement on a single copy of $\rho$.

We can generalize classical shadows from quantum states to quantum processes
by considering random product input states and randomized Pauli measurements.
A similar generalization has been studied in [33].

######  Definition 10 (Classical shadow of a quantum process).

Given an $n$-qubit CPTP map $\mathcal{E}$. A size-$N$ classical shadow
$S_{N}(\mathcal{E})$ of quantum evolution $\mathcal{E}$ is a random set given
by

$S_{N}(\mathcal{E})\triangleq\left\\{\ket{\psi^{\mathrm{(in)}}_{\ell}},\ket{\psi^{\mathrm{(out)}}_{\ell}}\right\\}_{\ell=1}^{N},$
(272)

where
$\ket{\psi^{\mathrm{(in)}}_{\ell}}=\bigotimes_{i=1}^{n}\ket{s^{\mathrm{(in)}}_{\ell,i}}$
is a random input state with
$\ket{s^{\mathrm{(in)}}_{\ell,i}}\in\mathrm{stab}_{1}$ sampled uniformly, and
$\ket{\psi^{\mathrm{(out)}}_{\ell}}=\bigotimes_{i=1}^{n}\ket{s^{\mathrm{(out)}}_{\ell,i}}$
is the outcome of performing randomized Pauli measurement on
$\mathcal{E}(\lvert\psi^{\mathrm{(in)}}_{\ell}\rangle\\!\langle\psi^{\mathrm{(in)}}_{\ell}\rvert)$.

After obtaining the outcome from $N$ randomized experiments, we can design a
learning algorithm that learns a model of the unknown CPTP map $\mathcal{E}$,
such that given an input state $\rho$ and an observable $O$, the algorithm
could predict $\operatorname{tr}(O\mathcal{E}(\rho))$. The rigorous guarantee
is given in the following theorem.

######  Theorem 14 (Learning to predict a quantum evolution).

Given $n,\epsilon,\epsilon^{\prime},\delta>0$. Consider any unknown $n$-qubit
CPTP map $\mathcal{E}$. Given a classical shadow $S_{N}(\mathcal{E})$ of
$\mathcal{E}$ obtained by $N$ randomized experiments with

$N=\log\left(\frac{n}{\delta}\right)\,\min\left(2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)},\,\,2^{\mathcal{O}\left(\log(1/\epsilon)\log(n)\right)}\right).$
(273)

With probability $\geq 1-\delta$, the algorithm learns a function $h$, s.t.
for any $n$-qubit state distribution $\mathcal{D}$ invariant under single-
qubit $H$ and $S$ gates, and any observable $O$ given as a sum of few-body
observables, where each qubit is acted on by $\mathcal{O}(1)$ of the few-body
observables,

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}\left(O\mathcal{E}(\rho)\right)\right|^{2}\leq\left(\epsilon+\epsilon^{\prime}\left[\tfrac{\left\lVert
O^{\mathrm{(\mathrm{low})}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{\frac{2\lceil\log_{1.5}(1/\epsilon)\rceil}{\lceil\log_{1.5}(1/\epsilon)\rceil+1}}\right)\left\lVert
O\right\rVert^{2}.$ (274)

Here, $O^{(\mathrm{low})}$ is the low-degree approximation of $O$ after
Heisenberg evolution under $\mathcal{E}$.

The scaling given in the main text corresponds to the additional assumption
that $\left\lVert O\right\rVert\leq 1$. By noting that
$\frac{2\lceil\log_{1.5}(1/\epsilon)\rceil}{\lceil\log_{1.5}(1/\epsilon)\rceil+1}\in[1,2)$,
we have

$\left[\tfrac{\left\lVert O^{\mathrm{(\mathrm{low})}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{\frac{2\lceil\log_{1.5}(1/\epsilon)\rceil}{\lceil\log_{1.5}(1/\epsilon)\rceil+1}}\left\lVert
O\right\rVert^{2}\leq\left\lVert
O^{\mathrm{(\mathrm{low})}}\right\rVert^{\frac{2\lceil\log_{1.5}(1/\epsilon)\rceil}{\lceil\log_{1.5}(1/\epsilon)\rceil+1}}\leq\max\left(\left\lVert
O^{\mathrm{(\mathrm{low})}}\right\rVert^{2},1\right).$ (275)

Theorem 1 follows by considering $\epsilon^{\prime}\rightarrow 0$.

###  E.1 Learning algorithm

Recall that a size-$N$ classical shadow $S_{N}(\mathcal{E})$ of the CPTP map
$\mathcal{E}$ is a set given by

$S_{N}(\mathcal{E})\triangleq\left\\{\ket{\psi^{\mathrm{(in)}}_{\ell}}=\bigotimes_{i=1}^{n}\ket{s^{\mathrm{(in)}}_{\ell,i}},\ket{\psi^{\mathrm{(out)}}_{\ell}}=\bigotimes_{i=1}^{n}\ket{s^{\mathrm{(out)}}_{\ell,i}}\right\\}_{\ell=1}^{N}.$
(276)

Given an observable $O$ that can be written as a sum of $\kappa$-qubit
observables, where each qubit is acted on by at most $d$ of the $\kappa$-qubit
observables with $\kappa,d=\mathcal{O}(1)$. We have

$O=\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes n}:|Q|\leq\kappa}a_{Q}Q,$ (277)

where $\sum_{Q:|Q|\leq\kappa}\mathds{1}[a_{Q}\neq 0]=\mathcal{O}(n)$. The
algorithm creates a dataset,

$\left\\{\rho_{\ell}=\lvert\psi^{\mathrm{(in)}}_{\ell}\rangle\\!\langle\psi^{\mathrm{(in)}}_{\ell}\rvert,\quad
y_{\ell}(O)=\sum_{Q:|Q|\leq\kappa}a_{Q}\operatorname{tr}\left(Q\bigotimes_{i=1}^{n}\left(3\lvert
s^{\mathrm{(out)}}_{\ell,i}\rangle\\!\langle
s^{\mathrm{(out)}}_{\ell,i}\rvert-I\right)\right)\right\\}_{\ell=1}^{N}$ (278)

from the classical shadow $S_{N}(\mathcal{E})$, which requires
$\mathcal{O}(nN)$ computational time. We also define the parameter

$\eta\triangleq\sum_{Q:|Q|\leq\kappa}|a_{Q}|=\left\lVert
O\right\rVert_{\mathrm{Pauli},1}$ (279)

based on the given observable $O$.

The sample complexity in Eq. (273) is the minimum of two arguments. Each of
the two corresponds to a hyperparameter setting for $k$ and
$\tilde{\epsilon}$. Let $C(k)$ be the function from Corollary 11 and $C(k,d)$
be the function from Corollary 12. The first hyperparameter setting considers

$k=\lceil\log_{1.5}(1/\epsilon)\rceil,\quad\tilde{\epsilon}=\left(\frac{\epsilon^{\prime}}{6\cdot
2^{k}}\right)^{k+1}\left(\frac{C(\kappa,d)}{3}\right)^{2}\left(\frac{C(k)}{3}\right)^{2k}.$
(280)

The second hyperparameter setting considers

$k=\lceil\log_{1.5}(2/\epsilon)\rceil,\quad\tilde{\epsilon}=\frac{\epsilon}{9\cdot
2^{k+1}\cdot n^{k}}\left(\frac{C(\kappa,d)}{3}\right)^{2}.$ (281)

For every Pauli observable $P\in\\{I,X,Y,Z\\}^{\otimes n}$ with $|P|\leq k$,
the algorithm computes

$\displaystyle\hat{x}_{P}(O)$
$\displaystyle=\frac{1}{N}\sum_{\ell=1}^{N}\operatorname{tr}(P\rho_{\ell})y_{\ell}(O),$
(282) $\displaystyle\hat{\beta}_{P}$
$\displaystyle=\left(\frac{1}{3}\right)^{|P|},$ (283)
$\displaystyle\hat{\alpha}_{P}(O)$
$\displaystyle=\begin{cases}0,&\hat{\beta}_{P}\leq 2\tilde{\epsilon},\\\
0,&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}(O)|/\hat{\beta}_{P}^{1/2}\leq
2\eta\sqrt{\tilde{\epsilon}},\\\
\hat{x}_{P}(O)/\hat{\beta}_{P},&\hat{\beta}_{P}>2\tilde{\epsilon},\,|\hat{x}_{P}(O)|/\hat{\beta}_{P}^{1/2}>2\eta\sqrt{\tilde{\epsilon}},\end{cases}$
(284)

which requires $\mathcal{O}(kN)$ time per Pauli observable $P$. Finally, given
an $n$-qubit state $\rho$, the algorithm outputs

$h(\rho,O)\triangleq\sum_{P:|P|\leq
k}\hat{\alpha}_{P}(O)\operatorname{tr}(P\rho),$ (285)

which uses a computational time of $\mathcal{O}(n^{k})$.

###  E.2 Rigorous performance guarantee

In this section, we prove that the learning algorithm presented in the last
section satisfies Theorem 14. The proof uses the tools presented in Section
D.2 and is similar to the proof of Theorem 13.

####  E.2.1 Definitions

For a given observable that is a sum of $\kappa$-qubit observables, where
$\kappa=\mathcal{O}(1)$ and each qubit is acted on by $d=\mathcal{O}(1)$ of
the $\kappa$-qubit observables, we can write

$O=\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes n}:|Q|\leq\kappa}a_{Q}Q.$ (286)

We define a few variables based on $O$ as follows. We consider the unknown
observable to be

$O^{(\mathrm{unk})}\triangleq\mathcal{E}^{\dagger}(O)\triangleq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\alpha_{P}(O)P,$ (287)

and the low-degree approximation of $O^{(\mathrm{unk})}$ to be

$O^{(\mathrm{low})}\triangleq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}:|P|\leq
k}\alpha_{P}(O)P.$ (288)

Then for all Pauli observables $P\in\\{I,X,Y,Z\\}^{\otimes n}$, we define

$x_{P}(O)\triangleq\left(\frac{1}{3}\right)^{|P|}\alpha_{P}(O),\quad\beta_{P}\triangleq\left(\frac{1}{3}\right)^{|P|}.$
(289)

We also define the standard $n$-qubit input state distribution
$\mathcal{D}^{0}$ to be the uniform distribution over the tensor product of
$n$ single-qubit stabilizer states. A nice property of $\mathcal{D}^{0}$ is
that for any state $\rho$ in the support of $\mathcal{D}^{0}$, the non-
identity purity for a subsystem $A$ of size $L$ is

$\gamma^{*}(\rho_{A})=\frac{1}{2^{L}}.$ (290)

Using this property and Lemma 16 on extracting Pauli coefficients, we have the
following identities

$x_{P}(O)=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\operatorname{tr}(P\rho)\operatorname{tr}\left(\mathcal{E}^{\dagger}(O)\rho\right),\quad\beta_{P}=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\operatorname{tr}(P\rho)^{2}=\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}.$
(291)

We are now ready to prove Theorem 14.

####  E.2.2 Prediction error under standard distribution $\mathcal{D}^{0}$
(first set of hyperparameters)

We begin the proof by considering the first set of hyperparameters
$k,\tilde{\epsilon}$ as given in Eq. (280). For a Pauli observable
$Q\in\\{I,X,Y,Z\\}^{\otimes n}$ with $|Q|\leq\kappa=\mathcal{O}(1)$, we
consider the random variable

$\hat{x}_{P}(Q)=\frac{1}{N}\sum_{\ell=1}^{N}\operatorname{tr}(P\rho_{\ell})y_{\ell}(Q)=\frac{1}{N}\sum_{\ell=1}^{N}\operatorname{tr}(P\rho_{\ell})\operatorname{tr}\left(Q\bigotimes_{i=1}^{n}\left(3\lvert
s^{\mathrm{(out)}}_{\ell,i}\rangle\\!\langle
s^{\mathrm{(out)}}_{\ell,i}\rvert-I\right)\right).$ (292)

Because $|Q|=\mathcal{O}(1)$, we have
$\left|\operatorname{tr}\left(Q\bigotimes_{i=1}^{n}\left(3\lvert
s^{\mathrm{(out)}}_{\ell,i}\rangle\\!\langle
s^{\mathrm{(out)}}_{\ell,i}\rvert-I\right)\right)\right|=\mathcal{O}(1)$ with
probability one. By considering the size of the classical shadow
$S_{N}(\mathcal{E})$ to be

$N=\Omega\left(\frac{\log(n^{k+\kappa}/\delta)}{\tilde{\epsilon}^{2}}\right),$
(293)

we can utilize Hoeffding’s inequality and union bound to guarantee that

$\left|\hat{x}_{P}(Q)-x_{P}(Q)\right|\leq\tilde{\epsilon},\quad\forall
P,Q\in\\{I,X,Y,Z\\}^{\otimes n},|P|\leq k,|Q|\leq\kappa$ (294)

with probability at least $1-\delta$. In the following proof, we will
condition on the above event.

Using triangle inequality, we have

$\left|\hat{x}_{P}(O)-x_{P}(O)\right|\leq\left\lVert
O\right\rVert_{\mathrm{Pauli},1}\tilde{\epsilon}=\eta\tilde{\epsilon},\quad\left|\hat{\beta}_{P}-\beta_{P}\right|=0,\quad\forall
P:|P|\leq k.$ (295)

The norm inequality given in Corollary 11 shows that

$\sum_{P:|P|\leq
k}\left|\alpha_{P}(O)\right|^{r}\leq\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}$ (296)

for the constant $C(k)$ defined in (5).

The filtering lemma given in Lemma 18 shows that

$\displaystyle\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}$
$\displaystyle\leq 6\eta^{2-r}\left(\frac{3}{C(k)}\right)^{r}\left\lVert
O^{\mathrm{(low)}}\right\rVert^{r}\tilde{\epsilon}^{1-(r/2)}.$ (297)

From the norm inequality and the constant $C(k,d)$ given in Corollary 12, we
have

$\eta=\left\lVert
O\right\rVert_{\mathrm{Pauli},1}\leq\frac{3}{C(\kappa,d)}\left\lVert
O\right\rVert.$ (298)

Combining with the definition of $\tilde{\epsilon}$ given in Eq. (280), we
have

$\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}\leq\left[\tfrac{\left\lVert
O^{\mathrm{(low)}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{r}\frac{\epsilon^{\prime}}{2^{k}}\cdot\left\lVert
O\right\rVert^{2}.$ (299)

Using Lemma 14 on mean squared error and Corollary 13 on low-degree
approximation, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left|h(\rho,O)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}$
(300) $\displaystyle\leq\underbrace{(2/3)^{k}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}}_{\leq\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}\epsilon}+\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}.$
(301)

Using the definition of $O^{\mathrm{(unk)}}$, we have
$O^{\mathrm{(unk)}}=\mathcal{E}^{\dagger}(O)$ and $\left\lVert
O^{\mathrm{(unk)}}\right\rVert\leq\left\lVert O\right\rVert$. Hence

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\left(\epsilon+\frac{\epsilon^{\prime}}{2^{k}}\left[\tfrac{\left\lVert
O^{\mathrm{(low)}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{r}\right)\left\lVert O\right\rVert^{2},$ (302)

which establishes a prediction error bound for distribution $\mathcal{D}^{0}$.

####  E.2.3 Prediction error under general distribution $\mathcal{D}$ (first
set of hyperparameters)

We now consider an arbitrary $n$-qubit state distribution $\mathcal{D}$
invariant under single-qubit $H$ and $S$ gates. Using Lemma 14 on mean squared
error and Corollary 13 on low-degree approximation, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}$
(303) $\displaystyle\leq\epsilon\left\lVert O\right\rVert^{2}+\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}.$
(304)

Recall that $\gamma^{*}(\rho_{\mathsf{dom}(P)})\leq 1$, hence

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\leq
2^{k}\left(\frac{1}{3}\right)^{|P|},\quad\forall P\in\\{I,X,Y,Z\\}^{\otimes
n},|P|\leq k.$ (305)

Furthermore, we have
$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}_{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}=(1/3)^{|P|}$.
Together, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\epsilon\left\lVert
O\right\rVert^{2}+2^{k}\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}.$
(306)

Combining the above with Eq. (299), we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\left(\epsilon+\epsilon^{\prime}\left[\tfrac{\left\lVert
O^{\mathrm{(low)}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{r}\right)\left\lVert O\right\rVert^{2},$ (307)

which is the prediction error under distribution $\mathcal{D}$.

####  E.2.4 Putting everything together (first set of hyperparameters)

From Eq. (280), we have set the parameter $\tilde{\epsilon}$ to be

$\tilde{\epsilon}=\left(\frac{\epsilon^{\prime}}{6}\right)^{k+1}\left(\frac{C(\kappa,d)}{3}\right)^{2}\left(\frac{C(k)}{3}\right)^{2k}.$
(308)

Furthermore, given the classical shadow $S_{N}(\mathcal{E})$ of size

$N=\mathcal{O}\left(\frac{\log(n^{k+\kappa}/\delta)}{\tilde{\epsilon}^{2}}\right)=\log\left(\frac{n}{\delta}\right)\,2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\left(\log\log(\frac{1}{\epsilon})+\log(\frac{1}{\epsilon^{\prime}})\right)\right)},$
(309)

we can guarantee that with probability at least $1-\delta$, the following
holds. For any observable $O$ that is a sum of $\kappa$-qubit observables,
where $\kappa=\mathcal{O}(1)$ and each qubit is acted on by $d=\mathcal{O}(1)$
of the $\kappa$-qubit observables, and any $n$-qubit state distribution
$\mathcal{D}$ invariant under single-qubit $H$ and $S$ gates, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\left(\epsilon+\epsilon^{\prime}\left[\tfrac{\left\lVert
O^{\mathrm{(low)}}\right\rVert}{\left\lVert
O\right\rVert}\right]^{r}\right)\left\lVert O\right\rVert^{2}.$ (310)

This establishes one of the argument for the sample complexity stated in
Theorem 14.

####  E.2.5 Prediction error under standard distribution $\mathcal{D}^{0}$
(second set of hyperparameters)

In the following proof, we consider the second set of hyperparameters
$k,\tilde{\epsilon}$ as given in Eq. (281). By considering the size of the
classical shadow $S_{N}(\mathcal{E})$ to be

$N=\Omega\left(\frac{\log(n^{k+\kappa}/\delta)}{\tilde{\epsilon}^{2}}\right),$
(311)

we can utilize Hoeffding’s inequality and union bound to guarantee that

$\left|\hat{x}_{P}(Q)-x_{P}(Q)\right|\leq\tilde{\epsilon},\quad\forall
P,Q\in\\{I,X,Y,Z\\}^{\otimes n},|P|\leq k,|Q|\leq\kappa$ (312)

with probability at least $1-\delta$. In the following proof, we will
condition on the above event. Using triangle inequality, we have

$\left|\hat{x}_{P}(O)-x_{P}(O)\right|\leq\left\lVert
O\right\rVert_{\mathrm{Pauli},1}\tilde{\epsilon}=\eta\tilde{\epsilon},\quad\left|\hat{\beta}_{P}-\beta_{P}\right|=0,\quad\forall
P:|P|\leq k.$ (313)

The filtering lemma given in Lemma 18 shows that

$\displaystyle\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}$
$\displaystyle\leq 9\eta^{2}\tilde{\epsilon}^{2}.$ (314)

From the norm inequality and the function $C(k,d)$ given in Corollary 12, we
have

$\eta=\left\lVert
O\right\rVert_{\mathrm{Pauli},1}\leq\frac{3}{C(\kappa,d)}\left\lVert
O\right\rVert.$ (315)

Combining with the definition of $\tilde{\epsilon}$ given in Eq. (281), we
have

$\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}\leq\frac{\epsilon}{2^{k+1}}\cdot\left\lVert
O\right\rVert^{2}.$ (316)

Using Lemma 14 on mean squared error and Corollary 13 on low-degree
approximation, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left|h(\rho,O)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}$
(317) $\displaystyle\leq(2/3)^{k}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}$
(318) $\displaystyle\leq\frac{\epsilon}{2}\left\lVert
O^{\mathrm{(unk)}}\right\rVert^{2}+\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}.$
(319)

Using the definition of $O^{\mathrm{(unk)}}$, we have
$O^{\mathrm{(unk)}}=\mathcal{E}^{\dagger}(O)$ and $\left\lVert
O^{\mathrm{(unk)}}\right\rVert\leq\left\lVert O\right\rVert$. Hence

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\frac{1}{2}\left(\epsilon+\frac{\epsilon}{2^{k}}\right)\left\lVert
O\right\rVert^{2},$ (320)

which establishes a prediction error bound for distribution $\mathcal{D}^{0}$.

####  E.2.6 Prediction error under general distribution $\mathcal{D}$ (second
set of hyperparameters)

We now consider an arbitrary $n$-qubit state distribution $\mathcal{D}$
invariant under single-qubit $H$ and $S$ gates. Using Lemma 14 on mean squared
error, Corollary 13 on low-degree approximation,
$k=\lceil\log_{1.5}(2/\epsilon)\rceil$, the fact that
$\gamma^{*}(\rho_{\mathsf{dom}(P)})\leq 1$, and
$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}_{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}=(1/3)^{|P|}$,
we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O^{\mathrm{(unk)}}\rho)\right|^{2}\leq\frac{\epsilon}{2}\left\lVert
O\right\rVert^{2}+2^{k}\sum_{P:|P|\leq
k}\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}^{0}}\left[\gamma^{*}(\rho_{\mathsf{dom}(P)})\right]\left(\frac{2}{3}\right)^{|P|}\left|\hat{\alpha}_{P}(O)-\alpha_{P}(O)\right|^{2}.$
(321)

Combining the above with Eq. (316), we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\epsilon\left\lVert
O\right\rVert^{2},$ (322)

which is the prediction error under distribution $\mathcal{D}$.

####  E.2.7 Putting everything together (second set of hyperparameters)

From Eq. (281), we have set the parameter $\tilde{\epsilon}$ to be

$\tilde{\epsilon}=\frac{\epsilon}{9\cdot 2^{k+1}\cdot
n^{k}}\left(\frac{C(\kappa,d)}{3}\right)^{2}.$ (323)

Furthermore, given the classical shadow $S_{N}(\mathcal{E})$ of size

$N=\mathcal{O}\left(\frac{\log(n^{k+\kappa}/\delta)}{\tilde{\epsilon}^{2}}\right)=\log\left(\frac{n}{\delta}\right)\,2^{\mathcal{O}\left(\log(\frac{1}{\epsilon})\log(n)\right)},$
(324)

we can guarantee that with probability at least $1-\delta$, the following
holds. For any observable $O$ that is a sum of $\kappa$-qubit observables,
where $\kappa=\mathcal{O}(1)$ and each qubit is acted on by $d=\mathcal{O}(1)$
of the $\kappa$-qubit observables, and any $n$-qubit state distribution
$\mathcal{D}$ invariant under single-qubit $H$ and $S$ gates, we have

$\operatorname*{{\mathbb{E}}}_{\rho\sim\mathcal{D}}\left|h(\rho,O)-\operatorname{tr}(O\mathcal{E}(\rho))\right|^{2}\leq\epsilon\left\lVert
O\right\rVert^{2}.$ (325)

This completes the proof of Theorem 14.

##  APPENDIX F Numerical details

In the numerical experiments, we consider the two classes of Hamiltonians,

$\displaystyle H$
$\displaystyle=\frac{1}{4}\sum_{i}(X_{i}X_{i+1}+Y_{i}Y_{i+1})+\frac{1}{2}\sum_{i}h_{i}Z_{i},$
(XY model) (326) $\displaystyle H$
$\displaystyle=\frac{1}{2}\sum_{i}X_{i}X_{i+1}+\frac{1}{2}\sum_{i}h_{i}Z_{i},$
(Ising model) (327)

where $h_{i}=0.5$ for the homogeneous Z field, and $h_{i}$ is sampled
uniformly at random from $[-5,5]$ for the disordered Z field. We solve for the
time-evolved properties using the Jordan-Wigner transform to map the spin
chains to a free fermion model and the technique described in [82] to solve
the free fermion model.

We consider the training set to be a collection of $N$ random product states
$\ket{\psi_{\ell}},\ell=1,\ldots,N$ and their associated measured properties
$y_{\ell}$ corresponding to measuring an observable $O$ after evolving under
$U(t)=\exp(-itH)$. The measured properties are averaged over $500$
measurements. Hence $y_{\ell}$ is a noisy estimate of the true expectation
value
$\operatorname{tr}(OU(t)\lvert\psi_{\ell}\rangle\\!\langle\psi_{\ell}\rvert
U(t)^{\dagger})$. We consider essentially the same ML algorithm as described
in Section III.1, but utilize a more sophisticated approach to enforce
sparsity in $\hat{\alpha}_{P}$. We also consider $\alpha_{P}$ for Pauli
operator $P$ that is geometrically local. For ease of analysis, we consider a
simple strategy of setting small values to zero. The standard approach that is
often used in practice is LASSO [72].

In the numerical experiments, we perform a simple grid search for the two
hyperparameters using two-fold cross-validation on the training set:

$\displaystyle k$ $\displaystyle=1,2,3,4,$ (328) $\displaystyle a$
$\displaystyle=2^{-15},2^{-14},2^{-13},\ldots,2^{-4},2^{-3},$ (329)

where $k$ corresponds to the maximum number of qubits that the Pauli operators
$P$ act on, and $a$ is a hyperparameter corresponding to the strength of the
$\ell_{1}$ regularization term in LASSO. In particular, the optimization
problem of LASSO is given by

$\min_{\hat{\alpha}_{P}}\frac{1}{2N}\sum_{\ell=1}^{N}\left|y_{\ell}-\sum_{P:|P|\leq
k}\hat{\alpha}_{P}\operatorname{tr}(P\lvert\psi_{\ell}\rangle\\!\langle\psi_{\ell}\rvert)\right|^{2}+a\sum_{P:|P|\leq
k}|\hat{\alpha}_{P}|,$ (330)

where $|P|$ is the number of qubits that the Pauli observable $P$ acts
nontrivially on. We then use the values $\hat{\alpha}_{P}$ found by the above
optimization to form a succinct approximate model

$\sum_{P:|P|\leq k}\hat{\alpha}_{P}P$ (331)

of the time-evolved observable $O(t)=U(t)^{\dagger}OU(t)$. Given a new initial
state $\rho$, we would predict the time-evolved property
$\operatorname{tr}(O(t)\rho)=\operatorname{tr}(OU(t)\rho U(t)^{\dagger})$
using

$\sum_{P:|P|\leq k}\hat{\alpha}_{P}\operatorname{tr}(P\rho).$ (332)

In addition to the figures given in the main text, Fig. 5 shows another
example for predicting a highly entangled initial state. Even though the ML
model is trained with random product states, it still performs very well on a
structured entangled initial state.

Figure 5:  _Visualization of ML model’s prediction for a highly-entangled
initial state $\rho=\lvert\psi\rangle\\!\langle\psi\rvert$._ We consider the
expected value of $Z_{i}(t)=e^{itH}Z_{i}e^{-itH}$, where $H$ corresponds to
the 1D 50-spin XY chain with a homogeneous $Z$ field. The initial state
$\ket{\psi}$ has a GHZ-like entanglement over the first $18$-spin chain and is
a product state with spins rotating clockwise over the latter $32$-spin chain.
To prepare $\ket{\psi}$ with 1D circuits, a depth of at least $\Omega(n)$ is
required. Even though the ML model is trained only on random product states (a
total of $N=10000$), it still performs accurately in predicting the highly-
entangled state over a wide range of evolution time $t$.