We can compose a state $\rho$ and a CPTP map $\mathcal{E}$ to prepare a new
state $\mathcal{E}(\rho)$. Similarly, we can compose a POVM ${\mathcal{M}}$
and a CPTP map ${{\mathcal{E}}}$ to compose a new POVM
${\mathcal{M}}\circ{{\mathcal{E}}}$ that is equivalent to first applying
${{\mathcal{E}}}$ then measure using ${\mathcal{M}}$. We refer to the states
that could be prepared by composing a finite sequence of CPTP maps
$\mathcal{E}_{y}$ acting on some initial state $\rho_{x}$ as states that could
be generated in ${\mathcal{W}}$.

###  J.1 Assumptions

We assume that we have found a linearly independent set of composed states
$\\{\rho_{1},\ldots,\rho_{K_{1}}\\}$ such that
$\mathrm{span}(\rho_{1},\ldots,\rho_{K_{1}})$ contains all states that can be
generated in ${\mathcal{W}}$, where $\mathrm{span}(\ldots)$ means all linear
combinations with real coefficients. This is equivalent to stating that for
any state $\rho$ that can be generated in ${\mathcal{W}}$, there exists a
unique set of coefficients $\alpha_{1},\ldots,\alpha_{K_{1}}\in\mathbb{R}$
satisfying

$\rho=\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}\rho_{k_{1}}.$ (333)

Because $\rho$ and $\rho_{k_{1}}$ for all $k_{1}\in\\{1,\ldots,K_{1}\\}$ are
quantum states, we have $\sum_{k_{1}}\alpha_{k_{1}}=1$. We consider $R_{1}>0$
to be a constant such that

$\sum_{k_{1}=1}^{K_{1}}|\alpha_{k_{1}}|\leq R_{1}$ (334)

for any quantum state $\rho$ in $\mathrm{span}(\rho_{1},\ldots,\rho_{K_{1}})$.

######  Remark 3.

$R_{1}<\infty$ because a finite-dimensional quantum state space is compact.

We also assume that we have found a set of composed POVM elements
$\\{M_{1},\ldots,M_{K_{2}}\\}$ such that
$\mathrm{span}(\rho_{1},\ldots,\rho_{K_{1}})\subseteq\mathrm{span}(M_{1},\ldots,M_{K_{2}})$.
This assumption implies that for any
$\alpha,\alpha^{\prime}\in\mathbb{R}^{K_{1}}$, if

$\forall
k_{2}\in\\{1,\ldots,K_{2}\\},\operatorname{tr}\left(M_{k_{2}}\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}\rho_{k_{1}}\right)=\operatorname{tr}\left(M_{k_{2}}\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}^{\prime}\rho_{k_{1}}\right),$
(335)

then $\alpha=\alpha^{\prime}$. In particular, we consider $R_{2}>0$ to be a
constant such that

$\left\lVert\alpha-\alpha^{\prime}\right\rVert_{1}\leq
R_{2}\sum_{k_{2}=1}^{K_{2}}\left|\operatorname{tr}\left(M_{k_{2}}\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}\rho_{k_{1}}\right)-\operatorname{tr}\left(M_{k_{2}}\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}^{\prime}\rho_{k_{1}}\right)\right|$
(336)

for any $\alpha,\alpha^{\prime}\in\mathbb{R}^{K_{1}}$.

######  Remark 4.

$R_{2}<\infty$ because the homogeneity of Eq. (336) enables maximization to
find $R_{2}$ over the compact space
$\left\lVert\alpha-\alpha^{\prime}\right\rVert_{1}=1$.

###  J.2 Learning a frame

We are now ready to present an efficient learning algorithm that can be used
to predict the extrinsic behavior of the world model $\mathcal{W}$. For each
$k_{2}=1,\ldots,K_{2}$, we consider the POVM element $M_{k_{2}}$ to be a unit
vector in a $K_{2}$-dimensional vector space,

$M_{k_{2}}\rightarrow\hat{e}_{k_{2}}.$ (337)

For each $k_{1}=1,\ldots,K_{1}$, we consider the state $\rho_{k_{1}}$ to be a
vector $w_{k_{1}}\in\mathbb{R}^{K_{2}}$,

$\rho_{k_{1}}\rightarrow
w_{k_{1}}\equiv\sum_{k_{2}=1}^{K_{2}}w_{k_{1},k_{2}}\hat{e}_{k_{2}},$ (338)

where $w_{k_{1},k_{2}}$ is an estimate for
$\operatorname{tr}(M_{k_{2}}\rho_{k_{1}})$, such that

$\mathrm{Pr}\left[\,\,|w_{k_{1},k_{2}}-\operatorname{tr}(M_{k_{2}}\rho_{k_{1}})|>\tilde{\epsilon}_{w}\,\,\right]\leq\delta.$
(339)

We can obtain an estimate for $w_{k_{1},k_{2}}$ with the above guarantee using
$\mathcal{O}(\log(1/\delta)/\tilde{\epsilon}_{w}^{2})$ experiments. We simply
prepare $\rho_{k_{1}}$ and measure the POVM associated to $M_{k_{2}}$, then
compute the average of the indicator function on whether the POVM element
$M_{k_{2}}$ is the outcome. Because the indicator function of an event is a
bounded random variable, Hoeffding’s inequality gives us the above rigorous
guarantee.

###  J.3 Learning states

For the initial states $\rho_{x}$ with $x\in\mathcal{X}$, we represent
$\rho_{x}$ as a $K_{1}$-dimensional real vector

$\rho_{x}\rightarrow
v_{x}\equiv\sum_{k_{1}=1}^{K_{1}}v_{x,k_{1}}\hat{e}_{k_{1}},$ (340)

where $v_{x}$ is an optimum of the following optimization problem

$\mathrm{OPT}(v_{x})=\min_{\begin{subarray}{c}\alpha\in\mathbb{R}^{K_{1}},\left\lVert\alpha\right\rVert_{1}\leq
R_{1},\\\
\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}=1\end{subarray}}\left\lVert\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}w_{k_{1}}-\sum_{k_{2}=1}^{K_{2}}v^{\prime}_{x,k_{2}}\hat{e}_{k_{2}}\right\rVert_{1},$
(341)

and $v^{\prime}_{x,k_{2}}$ is an estimate for
$\operatorname{tr}(M_{k_{2}}\rho_{x})$ by doing additional experiments, such
that

$\mathrm{Pr}\left[\,\,|v^{\prime}_{x,k_{2}}-\operatorname{tr}(M_{k_{2}}\rho_{x})|>\tilde{\epsilon}_{v}\,\,\right]\leq\delta.$
(342)

Because the above optimization is a convex optimization, one could solve for
$\alpha_{x}$ efficiently. The purpose of the optimization problem is to
project the vector $\sum_{k_{2}=1}^{K_{2}}v^{\prime}_{x,k_{2}}\hat{e}_{k_{2}}$
onto the space spanned by $v_{1},\ldots,v_{K_{1}}$. For a fixed
$\tilde{\epsilon}_{v},\delta>0$, the total number of experiments for learning
representations of the states is
$\mathcal{O}(K_{2}|\mathcal{X}|\log(1/\delta)/\tilde{\epsilon}^{2}_{v})$.

###  J.4 Learning CPTP maps

For the CPTP maps ${{\mathcal{E}}}_{y}$ with $y\in\mathcal{Y}$, we represent
${{\mathcal{E}}}_{y}$ as a $K_{1}\times K_{1}$ real matrix of the form

${{\mathcal{E}}}_{y}\rightarrow
A_{y}\equiv\sum_{k_{1}=1}^{K_{1}}\sum_{k_{1}^{\prime}=1}^{K_{1}}A_{y,k_{1},k_{1}^{\prime}}\hat{e}_{k_{1}}\hat{e}_{k_{1}^{\prime}}^{T},$
(343)

where for each fixed value of $k_{1}^{\prime}$, the $K_{1}$-dimensional vector
$A_{y,(\cdot),k_{1}^{\prime}}$ is an optimum of the following convex
optimization problem

$\mathrm{OPT}(A_{y,(\cdot),k_{1}^{\prime}})=\min_{\begin{subarray}{c}\alpha\in\mathbb{R}^{K_{1}},\left\lVert\alpha\right\rVert_{1}\leq
R_{1},\\\
\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}=1\end{subarray}}\left\lVert\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}w_{k_{1}}-\sum_{k_{2}=1}^{K_{2}}A^{\prime}_{y,k_{2},k_{1}^{\prime}}\hat{e}_{k_{2}}\right\rVert_{1},$
(344)

and $A^{\prime}_{y,k_{2},k_{1}^{\prime}}$ is an estimate for
$\operatorname{tr}(M_{k_{2}}{{\mathcal{E}}}_{y}(\rho_{k_{1}^{\prime}}))$ by
doing additional experiments, such that

$\mathrm{Pr}\left[\,\,|A^{\prime}_{y,k_{2},k_{1}^{\prime}}-\operatorname{tr}(M_{k_{2}}{{\mathcal{E}}}_{y}(\rho_{k_{1}^{\prime}}))|>\tilde{\epsilon}_{A}\,\,\right]\leq\delta.$
(345)

Similar to before, the purpose of the optimization is to project the vector
$\sum_{k_{2}=1}^{K_{2}}A^{\prime}_{y,k_{2},k_{1}^{\prime}}\hat{e}_{k_{2}}$ to
the space formed by $v_{1},\ldots,v_{K_{1}}$. For a fixed
$\tilde{\epsilon}_{A},\delta>0$, the total number of experiments for learning
representations of the CPTP maps is
$\mathcal{O}(K_{1}K_{2}|\mathcal{Y}|\log(1/\delta)/\tilde{\epsilon}^{2}_{A})$.

###  J.5 Learning POVMs

For the POVM elements $M_{zb}$ with $z\in\mathcal{Z},b\in\mathcal{B}$, we
represent $M_{zb}$ as a $K_{1}$-dimensional real vector

$M_{zb}\rightarrow
u_{zb}\equiv\sum_{k_{1}=1}^{K_{1}}u_{z,b,k_{1}}\hat{e}_{k_{1}},$ (346)

where $u_{z,b,k_{1}}$ is an estimate for
$\operatorname{tr}(M_{zb}\rho_{k_{1}})$ by doing additional experiments, such
that

$\mathrm{Pr}\left[\,\,|u_{z,b,k_{1}}-\operatorname{tr}(M_{zb}\rho_{k_{1}})|>\tilde{\epsilon}_{u}\,\,\right]\leq\delta.$
(347)

For a fixed $\tilde{\epsilon}_{u},\delta>0$, the total number of experiments
for learning representations of the POVMs is
$\mathcal{O}(K_{1}|\mathcal{Z}|\log(1/\delta)/\tilde{\epsilon}_{u}^{2})$. The
reason that we don’t need an extra factor of $|{\mathcal{B}}|$ is because when
we measure the POVM $\mathcal{M}_{z}$, we can simultaneously estimate
$c_{z,b,k_{1}}$ for all $b\in\mathcal{B}$.

###  J.6 Prediction procedure and rigorous guarantee

During the prediction phase, we predict the probability for obtaining an
outcome $b\in\mathcal{B}$ after running the experiment
$E=(x,y_{1},\ldots,y_{L},z)$ to be

$u_{zb}^{T}PA_{y_{L}}P\ldots PA_{y_{1}}v_{x},$ (348)

where $P$ is the projection to the convex set
$\\{\alpha\in\mathbb{R}^{K_{1}}|\sum_{k_{1}}\alpha_{k_{1}}=1,\left\lVert\alpha\right\rVert_{1}\leq
R_{1}\\}$. We now give a rigorous performance guarantee for this algorithm.

######  Theorem J.1 (Predicting extrinsic behaviors; Restatement of Theorem
4).

Assume that we have found a complete set of linearly independent states and
POVMs. Using the proposed algorithm, we can predict
$\operatorname{tr}(M_{zb}({{\mathcal{E}}}_{y_{L}}\circ\ldots\circ{{\mathcal{E}}}_{y_{1}})(\rho_{x}))$
to $\epsilon$ error for all
$x\in{\mathcal{X}},y_{1},\ldots,y_{L}\in{\mathcal{Y}},z\in{\mathcal{Z}},b\in{\mathcal{B}}$
using a total of

$\widetilde{\mathcal{O}}\left(\frac{|{\mathcal{X}}|+L^{2}|{\mathcal{Y}}|+|{\mathcal{Z}}|}{\epsilon^{2}}\right)$
(349)

experiments, where $\widetilde{\mathcal{O}}(\cdot)$ neglects logarithmic
factors and considers $K_{1},K_{2},R_{1},R_{2}$ to be constant.

###  J.7 Proof of Theorem J.1 — Step A. Representations of target outputs

From Eq. (333) and (334), $\forall x\in\mathcal{X}$, we can write $\rho_{x}$
as

$\rho_{x}=\sum_{k_{1}=1}^{K_{1}}v^{*}_{x,k_{1}}\rho_{k_{1}},$ (350)

for some $K_{1}$-dimensional vector $v^{*}_{x}$ with $\left\lVert
v^{*}_{x}\right\rVert_{1}\leq R_{1}$. Similarly, Eq. (333) and (334) shows
that for any $k_{1}^{\prime}\in\\{1,\ldots,K_{1}\\}$, we can write
${{\mathcal{E}}}_{y}(\rho_{k_{1}^{\prime}})$ as

${{\mathcal{E}}}_{y}(\rho_{k_{1}^{\prime}})=\sum_{k_{1}=1}^{K_{1}}A^{*}_{y,k_{1},k_{1}^{\prime}}\rho_{k_{1}},$
(351)

for some $K_{1}$-dimensional vector $A^{*}_{y,(\cdot),k_{1}^{\prime}}$ with
$\left\lVert A^{*}_{y,(\cdot),k_{1}^{\prime}}\right\rVert_{1}\leq R_{1}$.
Using this representation, for an experiment specified by
$x\in{\mathcal{X}},y_{1},\ldots,y_{L}\in{\mathcal{Y}},z\in{\mathcal{Z}}$, the
probability to obtain the measurement outcome $b\in{\mathcal{B}}$ can be
written as

$\operatorname{tr}(M_{zb}({{\mathcal{E}}}_{y_{L}}\circ\ldots\circ{{\mathcal{E}}}_{y_{1}})(\rho_{x}))=\sum_{k_{1}=1}^{K_{1}}(A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x})_{k_{1}}\operatorname{tr}(M_{zb}\rho_{k_{1}})=(u^{*}_{zb})^{T}A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x},$ (352)

where we let $u^{*}_{z,b,k_{1}}\equiv\operatorname{tr}(M_{zb}\rho_{k_{1}})$
and $u^{*}_{zb}=\sum_{k_{1}}u^{*}_{z,b,k_{1}}\hat{e}_{k_{1}}$.

###  J.8 Proof of Theorem J.1 — Step B. Error analysis for the learned
representations

We begin by comparing the two vectors $v_{x}^{*}$ and $v_{x}$, where $v_{x}$
is the representation learned from experiments; see Eq. (340). We can bound
the difference as follows,

$\displaystyle\left\lVert v_{x}^{*}-v_{x}\right\rVert_{1}$ $\displaystyle\leq
R_{2}\sum_{k_{2}=1}^{K_{2}}\left|\operatorname{tr}(M_{k_{2}}\rho_{x})-\sum_{k_{1}=1}^{K_{1}}v_{x,k_{1}}\operatorname{tr}(M_{k_{2}}\rho_{k_{1}})\right|$
(353) $\displaystyle\leq
R_{2}\sum_{k_{2}=1}^{K_{2}}\left(\left|v^{\prime}_{x,k_{2}}-\sum_{k_{1}=1}^{K_{1}}v_{x,k_{1}}w_{k1,k2}\right|+\tilde{\epsilon}_{v}+\left\lVert
v_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right)$ (354)
$\displaystyle=R_{2}\mathrm{OPT}(v_{x})+R_{2}K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right),$ (355) $\displaystyle\leq
R_{2}K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v^{*}_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right)+R_{2}K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right),$ (356) $\displaystyle\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right),$ (357)

with probability at least $1-(K_{2}+1)\delta$. The first line follows from Eq.
(336) and (350). The second line follows from Eq. (339), (342), and the union
bound. The third line follows from Eq. (341). The fourth line follows from
considering $\alpha=v^{*}_{x}$ in the optimization problem given at Eq. (341),
and utilizing the following bounds,

$\displaystyle\left\lVert\sum_{k_{1}=1}^{K_{1}}v^{*}_{x,k_{1}}w_{k_{1}}-\sum_{k_{2}=1}^{K_{2}}v^{\prime}_{x,k_{2}}\hat{e}_{k_{2}}\right\rVert_{1}$
(358)
$\displaystyle\leq\sum_{k_{2}=1}^{K_{2}}\left|\sum_{k_{1}=1}^{K_{1}}v^{*}_{x,k_{1}}\operatorname{tr}(M_{k_{2}}\rho_{k_{1}})-\operatorname{tr}(M_{k_{2}}\rho_{x})\right|+K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v^{*}_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right)$ (359)
$\displaystyle=\sum_{k_{2}=1}^{K_{2}}\left|\operatorname{tr}(M_{k_{2}}\rho_{x})-\operatorname{tr}(M_{k_{2}}\rho_{x})\right|+K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v^{*}_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right)=K_{2}\left(\tilde{\epsilon}_{v}+\left\lVert
v^{*}_{x}\right\rVert_{1}\tilde{\epsilon}_{w}\right).$ (360)

The last line follows from $\left\lVert v_{x}^{*}\right\rVert_{1},\left\lVert
v_{x}\right\rVert_{1}\leq R_{1}$.

We can compare $A^{*}_{y,k_{1},k_{1}^{\prime}}$ and
$A_{y,k_{1},k_{1}^{\prime}}$ by employing the same analysis and replacing Eq.
(350) with (351), Eq. (340) with (343), Eq. (342) with (345), and Eq. (341)
with (344). For all $y\in\mathcal{Y},k_{1}^{\prime}\in\\{1,\ldots,K_{1}\\}$,
the analysis shows that the following,

$\left\lVert
A^{*}_{y,(\cdot),k_{1}^{\prime}}-A_{y,(\cdot),k_{1}^{\prime}}\right\rVert_{1}\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right),$ (361)

happens with probability at least $1-(K_{2}+1)\delta$. And recall from Eq.
(347), we have $|u_{z,b,k_{1}}-u^{*}_{z,b,k_{1}}|\leq\tilde{\epsilon}_{u}$
with probability at least $1-\delta$. Together, with probability at least
$1-|{\mathcal{X}}|(K_{2}+1)\delta-|{\mathcal{Y}}|K_{1}(K_{2}+1)\delta-|{\mathcal{Z}}||{\mathcal{B}}|\delta=1-((|{\mathcal{X}}|+K_{1}|{\mathcal{Y}}|)(K_{2}+1)+|{\mathcal{Z}}||{\mathcal{B}}|)\delta$,
we have

$\displaystyle\sum_{k_{1}=1}^{K_{1}}\left|v^{*}_{x,k_{1}}-v_{x,k_{1}}\right|$
$\displaystyle\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right),$
$\displaystyle\forall x\in{\mathcal{X}},$ (362)
$\displaystyle\sum_{k_{1}=1}^{K_{1}}\left|A^{*}_{y,k_{1},k_{1}^{\prime}}-A_{y,k_{1},k_{1}^{\prime}}\right|$
$\displaystyle\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right),$
$\displaystyle\forall y\in{\mathcal{Y}},\,\forall
k_{1}^{\prime}\in\\{1,\ldots,K_{1}\\},$ (363)
$\displaystyle\left|u^{*}_{z,b,k_{1}}-u_{z,b,k_{1}}\right|$
$\displaystyle\leq\tilde{\epsilon}_{u},$ $\displaystyle\forall
z\in{\mathcal{Z}},b\in{\mathcal{B}},\,\forall k_{1}\in\\{1,\ldots,K_{1}\\}.$
(364)

This provides a set of error bounds for the learned representations.

###  J.9 Proof of Theorem J.1 — Step C. Error analysis for the prediction

We will now analyze the difference between the prediction and the true answer.
We first define a linear function mapping a $K_{1}$-dimensional vector
$\alpha$ to a matrix

$\rho(\alpha)=\sum_{k_{1}=1}^{K_{1}}\alpha_{k_{1}}\rho_{k_{1}}.$ (365)

Because $\rho_{k_{1}}$ is a quantum state, we have

$\left\lVert\rho(\alpha)\right\rVert_{1}\leq\sum_{k_{1}=1}^{K_{1}}\left|\alpha_{k_{1}}\right|\left\lVert\rho_{k_{1}}\right\rVert_{1}=\left\lVert\alpha\right\rVert_{1}.$
(366)

Note that $\left\lVert\rho(\alpha)\right\rVert_{1}$ is the trace norm for a
matrix, while $\left\lVert\alpha\right\rVert_{1}$ is a vector one-norm. For an
experiment specified by
$x\in{\mathcal{X}},y_{1},\ldots,y_{L}\in{\mathcal{Y}},z\in{\mathcal{Z}}$, the
difference between the probability for obtaining $b\in{\mathcal{B}}$ and the
predicted probability is

$\displaystyle\left|u_{zb}^{T}PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x}-(u^{*}_{zb})^{T}A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x}\right|$ (367)
$\displaystyle\leq\max_{k_{1}}\left|u_{z,b,k_{1}}-u^{*}_{z,b,k_{1}}\right|\left\lVert
PA_{y_{L}}P\ldots PA_{y_{1}}v_{x}\right\rVert_{1}$ (368)
$\displaystyle+|\operatorname{tr}\left(M_{zb}\rho(PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x})\right)-\operatorname{tr}\left(M_{zb}\rho(A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x})\right)|$ (369)
$\displaystyle\leq\tilde{\epsilon}_{u}R_{1}+\left\lVert\rho(PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x})-\rho(A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x})\right\rVert_{1}.$ (370)

The first inequality is a telescoping sum with a triangle inequality. The
second inequality follows from Eq. (364) and the fact that $\left\lVert
M_{zb}\right\rVert_{\infty}\leq 1$.

We will now analyze the second term in the above equation. We will prove that

$\displaystyle\left\lVert\rho(PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x})-\rho(A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x})\right\rVert_{1}$ (371) $\displaystyle\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right)+2LR_{1}R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right)$
(372)

by induction on $L$. For the base case $L=0,$ from Eq. (362) and Eq. (366), we
see that

$\left\lVert\rho(v_{x})-\rho(v^{*}_{x})\right\rVert_{1}\leq\left\lVert
v_{x}-v^{*}_{x}\right\rVert_{1}\leq
2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right).$ (373)

Suppose that the claim holds for $L-1$. Then

$\displaystyle\left\lVert\rho(PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x})-\rho(A^{*}_{y_{L}}\ldots
A^{*}_{y_{1}}v^{*}_{x})\right\rVert_{1}$ (374)
$\displaystyle\leq\left\lVert\rho(PA_{y_{L}}(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x}))-\rho(A^{*}_{y_{L}}(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x}))\right\rVert_{1}$ (375)
$\displaystyle+\left\lVert\rho(A^{*}_{y_{L}}(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x}))-\rho(A^{*}_{y_{L}}(A^{*}_{y_{L-1}}\ldots
A^{*}_{y_{1}}v^{*}_{x}))\right\rVert_{1}$ (376) $\displaystyle\leq\left\lVert
PA_{y_{L}}(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x})-A^{*}_{y_{L}}(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x})\right\rVert_{1}$ (377)
$\displaystyle+\left\lVert\mathcal{E}_{y_{L}}\big{(}\rho(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x}-A^{*}_{y_{L-1}}\ldots
A^{*}_{y_{1}}v^{*}_{x})\big{)}\right\rVert_{1}$ (378)
$\displaystyle\leq\sum_{k_{1}=1}^{K_{1}}\left(\max_{k_{1}^{\prime}}\left|PA_{y_{L},k_{1},k_{1}^{\prime}}-A^{*}_{y_{L},k_{1},k_{1}^{\prime}}\right|\sum_{k_{1}^{\prime}=1}^{K_{1}}\left|(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x})_{k_{1}^{\prime}}\right|\right)$ (379)
$\displaystyle+\left\lVert\rho(PA_{y_{L-1}}\ldots
PA_{y_{1}}v_{x}-A^{*}_{y_{L-1}}\ldots A^{*}_{y_{1}}v^{*}_{x})\right\rVert_{1}$
(380) $\displaystyle\leq
2R_{1}R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right)$
(381)
$\displaystyle+2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right)+2(L-1)R_{1}R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right)$
(382)
$\displaystyle=2R_{2}K_{2}\left(\tilde{\epsilon}_{v}+R_{2}\tilde{\epsilon}_{w}\right)+2LR_{1}R_{2}K_{2}\left(\tilde{\epsilon}_{A}+R_{2}\tilde{\epsilon}_{w}\right).$
(383)

The first inequality follows from the triangle inequality and the linearity of
$\rho(\alpha)$. The second inequality follows from the action of
$\mathcal{E}_{y}$ given in Eq. (351). The third inequality uses two basic
inequalities:
$\left\lVert(A-A^{\prime})x\right\rVert\leq\sum_{i}(\max_{j}|(A-A^{\prime})_{i}j|\sum_{j}x_{j}),\forall
A,A^{\prime}\in\mathbb{R}^{k\times k},x\in\mathbb{R}^{k}$, and
$\left\lVert\mathcal{E}(X)\right\rVert_{1}\leq\left\lVert X\right\rVert_{1}$
for CPTP map $\mathcal{E}$ and Hermitian matrix $X$. The fourth inequality
uses the induction hypothesis, Eq. (363), and the fact that
$\sum_{k}|(Px)_{k}|\leq R_{1}$ for any $x\in\mathbb{R}^{K_{1}}$.

###  J.10 Proof of Theorem J.1 — Step D. Putting everything together

Together, we consider the following parameter choices,

$\displaystyle\frac{1}{\delta}$
$\displaystyle=100((|{\mathcal{X}}|+K_{1}|{\mathcal{Y}}|)(K_{2}+1)+|{\mathcal{Z}}||{\mathcal{B}}|),$
(384) $\displaystyle\frac{1}{\tilde{\epsilon}_{w}}$
$\displaystyle=\frac{16LR_{1}R_{2}^{2}K_{2}}{\epsilon},$ (385)
$\displaystyle\frac{1}{\tilde{\epsilon}_{v}}$
$\displaystyle=\frac{8R_{2}K_{2}}{\epsilon},$ (386)
$\displaystyle\frac{1}{\tilde{\epsilon}_{A}}$
$\displaystyle=\frac{8LR_{1}R_{2}K_{2}}{\epsilon},$ (387)
$\displaystyle\frac{1}{\tilde{\epsilon}_{u}}$
$\displaystyle=\frac{4R_{1}}{\epsilon},$ (388)

to ensure that with probability at least $0.99$, for any experiment specified
by $x\in{\mathcal{X}},y_{1},\ldots,y_{L}\in{\mathcal{Y}},z\in{\mathcal{Z}}$,
the difference between the actual probability for obtaining the measurement
outcome $b\in{\mathcal{B}}$ and the predicted probability is bounded above by
$\epsilon$,

$\left|u_{zb}^{T}PA_{y_{L}}P\ldots
PA_{y_{1}}v_{x}-\operatorname{tr}(M_{zb}({{\mathcal{E}}}_{y_{L}}\circ\ldots\circ{{\mathcal{E}}}_{y_{1}})(\rho_{x}))\right|\leq\epsilon.$
(389)

By aggregating the number of experiments for learning a frame, states, maps,
and POVMs, the total number of experiments is of order

$\displaystyle\frac{L^{2}R^{2}_{1}R_{2}^{4}K^{2}_{2}+|{\mathcal{X}}|R_{2}^{2}K_{2}^{3}+L^{2}|{\mathcal{Y}}|K_{1}K^{3}_{2}R^{2}_{1}R^{2}_{2}+|{\mathcal{Z}}|R_{1}^{2}K_{1}}{\epsilon^{2}}\log\left(K_{2}|{\mathcal{X}}|+K_{1}K_{2}|{\mathcal{Y}}|+|{\mathcal{Z}}||{\mathcal{B}}|\right)$
(390)
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{|{\mathcal{X}}|+L^{2}|{\mathcal{Y}}|+|{\mathcal{Z}}|}{\epsilon^{2}}\right),$
(391)

where $\widetilde{\mathcal{O}}(\cdot)$ neglects logarithmic contributions and
considers $K_{1},K_{2},R_{1},R_{2}$ to be constant.

##  APPENDIX K Related work

In this appendix, we present the connection of the theory developed in this
work and existing works. We will refer to basic concepts developed in some of
the previous appendices. In particular, Appendix A on the definition of world
models, Appendix C on the definition of model classes and learning intrinsic
descriptions, and Appendix I on the definition of predicting extrinsic
behaviors.

###  K.1 Gate set tomography

The most relevant literature to the theory of world models developed in this
work is gate set tomography. Here we provide a brief review on gate set
tomography. We refer the readers to two comprehensive reviews on gate set
tomography greenbaum2015introduction ; nielsen2020gate . Ref.
greenbaum2015introduction  gives the basic concepts and nielsen2020gate
provides both the fundamental ideas and recent progress on gate set
tomography. An experimental demonstration of gate set tomography is given in
blume2017demonstration . An open-sourced software for gate set tomography has
been developed in erik_2021_5546759 .

The main goal of gate set tomography (GST) is to characterize how quantum
processes and logical gates affect the qubits in the device. This is closely
related to the task of quantum process tomography (QPT). However, in quantum
process tomography, one assumes perfect state preparations and perfect POVM
measurements. The key differences between GST and QPT are: (1) the lack of
assumption on perfect states and measurements; (2) the need to benchmark
multiple quantum processes (gates) at once. Because GST does not assume the
ability to prepare perfect states and measurements, existing protocols learn
the relation between different gates instead of the intrinsic physical
description of each gate. This problem is referred to as gauge freedom in GST.

When we vectorize state and POVM element as $\mathrm{vec}(\rho_{x})$ and
$\mathrm{vec}(M_{zb})$ and write the CPTP maps ${{\mathcal{E}}}_{y}$ as a
matrix $A_{y}$, then we have

$\operatorname{tr}(M_{zb}{{\mathcal{E}}}_{y}(\rho_{x}))=\mathrm{vec}(M_{zb})^{T}A_{y}\mathrm{vec}(\rho_{x})=(M^{-1}\mathrm{vec}(M_{zb}))^{T}(MA_{y}M^{-1})(M\mathrm{vec}(\rho_{x})).$
(392)

The following transformation is known as a gauge transformation

$\displaystyle\mathrm{vec}(\rho_{x})$ $\displaystyle\rightarrow
M\mathrm{vec}(\rho_{x}),$ (393) $\displaystyle A_{y}$
$\displaystyle\rightarrow MA_{y}M^{-1},$ (394)
$\displaystyle\mathrm{vec}(M_{zb})$ $\displaystyle\rightarrow
M^{-1}\mathrm{vec}(M_{zb}),$ (395)

which is parameterized by an invertible matrix $M$. Most existing GST
protocols are designed to learn the vectorization and matricization up the the
gauge freedom, specified by the matrix $M$. Due to the gauge $M$, it has been
difficult to provide a fully rigorous statistical analysis of GST. The key
problem is that the gauge freedom makes it challenging to define errors in
GST. And we are not aware of a rigorous proof showing the required number of
experiments to perform GST up to certain error.

We begin with a summary of the difference between the theory on learning world
models developed in this work and the existing literature on gate set
tomography nielsen2020gate . According to the review nielsen2020gate , GST is
tomography of a novel entity, which is not the individual description of each
gate, but some form of relations between the gates. Based on our theory, we
can formalize this novel entity as a non-physical model capable of predicting
the extrinsic behaviors of the quantum device under the following assumption:
one can (efficiently) find a complete basis of states and POVMs by composing
existing states, gates, and measurements. Without this assumption, Theorem 3
shows that learning the extrinsic behavior can be extremely inefficient. And
under this assumption, Theorem 4 provides a rigorous algorithm, that shares
many common aspects with GST, for predicting extrinsic behaviors that improves
significantly upon the worst case complexity given in Theorem 3.

In contrast, learning intrinsic physical descriptions of the operations in the
device is significantly more challenging than performing GST. In certain
scenarios, it is impossible to learn the intrinsic descriptions to arbitrary
accuracy as shown in Theorem 6. However, we show that it is possible in many
natural scenarios. We can learn the intrinsic description up to any accuracy
when the world model has an unknown pure state and a universal set of unknown
gates (Theorem 2). Hence, being “informationally complete” for GST is easier
than being “informationally complete” for learning intrinsic descriptions.

We now present several questions that illustrate the difference between the
theory on learning world models developed in this work and gate set
tomography.

##### Is equivalence up to a gauge transformation in GST the same as weak
indistinguishability?

No. When two world models are related by the gauge transformation defined in
GST, it is true that the two world models are weakly indistinguishable, i.e.,
no experiments can distinguish the two world models. However, there are pairs
of weakly indistinguishable world models that are not related by a gauge
transformation. One such example has been presented in the main text. Consider
the following two distinct physical realities in a single-qubit system,

$\displaystyle\mathcal{W}^{A}_{\mathrm{HT}}:\quad\rho^{A}_{0}$
$\displaystyle=I/2,$ $\displaystyle\mathcal{E}^{A}_{H}(\rho)$
$\displaystyle=H\rho H^{\dagger},$ $\displaystyle\mathcal{E}^{A}_{T}(\rho)$
$\displaystyle=T\rho T^{\dagger},$ $\displaystyle\mathcal{M}^{A}_{0}$
$\displaystyle=\\{\lvert 0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert\\},$ (396)
$\displaystyle\mathcal{W}^{B}_{\mathrm{HT}}:\quad\rho^{B}_{0}$
$\displaystyle=I/2,$ $\displaystyle\mathcal{E}^{B}_{H}(\rho)$
$\displaystyle=I/2,$ $\displaystyle\mathcal{E}^{B}_{T}(\rho)$
$\displaystyle=I/2,$ $\displaystyle\mathcal{M}^{B}_{0}$
$\displaystyle=\\{\lvert 0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert\\},$ (397)

with actions $\mathcal{X}=\\{0\\},\mathcal{Y}=\\{H,T\\},\mathcal{Z}=\\{0\\}$.
Because $\mathcal{E}^{A}_{H}\neq\mathcal{E}^{A}_{T}$ but
$\mathcal{E}^{B}_{H}=\mathcal{E}^{B}_{T}$, it is impossible that the two world
models are related by a gauge transformation. However, as we have discussed in
the main text, the two world models cannot be distinguished by any experiment,
hence they are weakly indistinguishable. Together, we see that gauge
equivalence as defined in GST implies weak indistinguishability, but two
devices that are weakly indistinguishable need not be gauge equivalent in GST.
This means the set of relations defined by gauge equivalence in GST is a
subset of the relations defined by weakly indistinguishable world models.

##### Can we always learn a world model up to gauge transformation?

No. While GST removes the assumption on perfect state preparations and
measurements, GST still require assumptions to work. It is not true that we
can always learn a world model up to a gauge transformation using existing GST
protocols. This is already evident in the above example. The two world models
$\mathcal{W}^{A}_{\mathrm{HT}},\mathcal{W}^{B}_{\mathrm{HT}}$ are not related
by a gauge transformation, but they are weakly indistinguishable. Hence by
Proposition E.2, we cannot learn to distinguish the two world models from
experiments.

##### Is equivalence up to a gauge transformation in GST the same as strong
indistinguishability (i.e. equivalence in our framework)?

No. As Theorem A.8 has shown, equivalent world models are related by unitary
or anti-unitary transformation. But two world models related by the gauge
transformation defined in GST may not be related by unitary or anti-unitary
transformation. For example, consider two $d$-dimensional world models over
the action spaces
$\mathcal{X}=\\{\sigma\\}_{\sigma:\mathrm{state}},\mathcal{Y}=\\{U\\}_{U\in\mathrm{SU}(d)},\mathcal{Z}=\\{0\\}$
and outcome space ${\mathcal{B}}=\\{1,\ldots,d\\}$:
$\mathcal{W}^{A}=\left(\\{\rho^{A}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}^{A}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}^{A}_{z}\\}_{z\in\mathcal{Z}}\right)$,
where

$\displaystyle\rho^{A}_{\sigma}$
$\displaystyle=(1-\epsilon)\sigma+\epsilon\frac{I}{d},$
$\displaystyle\forall\sigma:\mathrm{state},$ (398)
$\displaystyle\mathcal{E}^{A}_{U}(\rho)$ $\displaystyle=U\rho U^{\dagger},$
$\displaystyle\forall U\in\mathrm{SU}(d),$ (399)
$\displaystyle\mathcal{M}^{A}_{0}$ $\displaystyle=\left\\{\lvert
b\rangle\\!\langle b\rvert\right\\}_{b=1,\ldots,d},$ (400)

and
$\mathcal{W}^{B}=\left(\\{\rho^{B}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}^{B}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}^{B}_{z}\\}_{z\in\mathcal{Z}}\right)$,
where

$\displaystyle\rho^{B}_{\sigma}$ $\displaystyle=\sigma,$
$\displaystyle\forall\sigma:\mathrm{state},$ (401)
$\displaystyle\mathcal{E}^{B}_{U}(\rho)$ $\displaystyle=U\rho U^{\dagger},$
$\displaystyle\forall U\in\mathrm{SU}(d),$ (402)
$\displaystyle\mathcal{M}^{B}_{0}$ $\displaystyle=\left\\{(1-\epsilon)\lvert
b\rangle\\!\langle b\rvert+\epsilon\frac{I}{d}\right\\}_{b=1,\ldots,d},$ (403)

We can see that $\mathcal{W}^{A}$ has depolarized initial states, while
$\mathcal{W}^{B}$ has depolarized measurements. The two world models are not
related by a unitary or anti-unitary transformation, hence they describe
distinct physical realities. However, it is not hard to show that the two
world models are related by a gauge transformation $M$.

##### Are two gauge-equivalent devices always physically the same?

No. We can have two noisy devices with depolarization noise happening in the
states or in the measurements; see the above example of $\mathcal{W}^{A}$ and
$\mathcal{W}^{B}$. The two devices are gauge equivalent. But these two noise
processes are not physically the same. And hence the two devices are not
physically the same. The inability to distinguish the two world models
$\mathcal{W}^{A}$ and $\mathcal{W}^{B}$ is due to the lack of sufficiently
informative actions. This is similar to the case when one performs quantum
state tomography with computational basis measurements. A coherent
$\lvert+\rangle\\!\langle+\rvert$ state is indistinguishable from a maximally
mixed state $I/2$ under computational basis measurements. However, the two
states are not physically the same. The indistinguishability arises not from
being physically the same, but from the lack of sufficiently useful actions.

##### How does gauge equivalence defined in GST relate to our theory of world
models?

Suppose that we have a $d$-dimensional world model $\mathcal{W}$, and assume
we can identify a set of (composed) states and a set of (composed) POVM
elements, such that both sets span the entire $d$-dimensional quantum state
space. Then every world model $\mathcal{W}^{\prime}$ that is weakly
indistinguishable from $\mathcal{W}$ is related by a gauge transformation.
Hence, under this assumption, we can equate weak indistinguishability in our
framework and gauge equivalence in GST. The assumption is critical and has
been explicitly or implicitly assumed in existing GST protocols
nielsen2020gate . A similar assumption is made in Theorem 4 (restated in
Theorem J.1) to establish the existence of an efficient algorithm for learning
extrinsic behaviors.

###  K.2 Quantum state/process/measurement tomography

The settings studied in quantum state, process, and measurement tomography are
special cases of our theory. In quantum state tomography, we are learning a
world model such that the CPTP maps and POVM measurements are perfect. Quantum
state tomography focuses on learning an unknown quantum state $\rho$ to high
accuracy, usually in trace norm or fidelity — see e.g. hradil1997quantum ;
gross2010quantum ; blume2010optimal ; banaszek2013focus  and references
therein. Recently, there have also been works investigating how learning
theory can be used to provide new insights into quantum state tomography
aaronson2018online ; quek2021private ; buadescu2021improved ;
huang2020predicting . In quantum measurement tomography d2003quantum , we are
learning a world model such that the state preparations and the the CPTP maps
are perfect. The goal of quantum measurement tomography is to learn the
descriptions of the POVMs. Finally, in quantum process tomography
mohseni2008quantum , we are learning a world model such that the state
preparations and the POVM measurements are perfect. The purpose of quantum
process tomography is to learn the full description of some unknown quantum
processes. A subset of quantum processes that have been actively studied
recently are the Pauli channels harper2020efficient ; flammia2020efficient ;
flammia2021pauli , which are often considered to be a good description of the
noise in quantum computers.

##  APPENDIX L Quantum advantage with noisy devices that cannot be fully
learned

###  L.1 Setting

We are given an $(2n)$-qubit device with unknown operations.

####  L.1.a State preparation and measurements

We can prepare an unknown product state given by

$\rho_{1}\otimes\ldots\otimes\rho_{2n}.$ (404)

We can perform an unknown product measurement given by a POVM with $2^{2n}$
outcomes,

$\left\\{\bigotimes_{i=1}^{2n}M^{(i)}_{B_{i}}\right\\}_{B\in\\{0,1\\}^{2n}},$
(405)

where $M^{(i)}_{B_{i}},\forall i=1,\ldots,2n$ are $2\times 2$ positive-
semidefinite matrices.

####  L.1.b Operations

In the device, we can apply layers of non-overlapping single- and two-qubit
gates. We consider the $2n$ qubits to be represented by an $n\times 2$ grid.
The grid coordinate of the $i$-th qubit ($i$ from $1$ to $n$) is $(\lceil
i/2\rceil,i\,\,\mathrm{mod}\,\,2)$. Single-qubit gates can be applied at every
grid point. But two-qubit gates can only be applied at edges on the $n\times
2$ grid. Each single-qubit gate is an unknown CPTP map on the corresponding
single qubit. And each two-qubit gate is an unknown CPTP map on the
corresponding two qubits. The unknown CPTP map implemented by each gate may
depend on the presence or absence of all the other gates applied at the same
layer.

Finally, we assume that we can load some unknown $n$-qubit quantum state
$\rho$ on the $n$ qubits in the left hand side of the $n\times 2$ grid.
Suppose $\sigma$ is the quantum state on the $2n$ qubits. After loading
$\rho$, the state on the $2n$ qubits becomes
$\rho\otimes\operatorname{tr}_{\mathrm{left\,\,side}}(\sigma)$.

###  L.2 Algorithm for partially learning the device

In this section, we will partially learn some of the operations in the unknown
quantum device. We will obtain some descriptions that are useful for using the
quantum device to achieve advantage in performing entangled data analysis. The
descriptions do not fully characterize the device. But the lack of full
characterization enables us to work under a more general setting.

####  L.2.a Experiments and loss functions: Single-qubit

We perform an optimization to find nine single-qubit gates for every qubit,
denoted as $g_{i,k}$ for all $i=1,\ldots,2n,k=0,\ldots,8$, by minimizing a
loss function. In particular, after choosing $g_{i,k}$, we conduct the
following experiments.

We consider the same single-qubit gates on the left hand side and the right
hand side of the $n\times 2$ qubit grid. For each of
$k_{1},k_{1}^{\prime}\in\\{0,\ldots,5\\},k_{2},k_{2}^{\prime}\in\\{6,7,8\\}$,
we prepare the unknown product state $\rho_{1}\otimes\ldots\otimes\rho_{2n}$,
apply a layer of single-qubit gates, followed by another layer of single-qubit
gates, then measure using the unknown product measurement. In the first layer
of the single-qubit gates, we apply $g_{i,k_{1}}$ for qubit $i$ on the left
and apply $g_{i,k_{1}^{\prime}}$ for qubit $i$ on the right. In the second
layer of the single-qubit gates, we apply $g_{i,k_{2}}$ for qubit $i$ on the
left and apply $g_{i,k_{2}^{\prime}}$ for qubit $i$ on the right. For each
$k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime}$ and each qubit $i$, we estimate
the probability for obtaining the outcome $b\in\\{0,1\\}$, denoted as
$\hat{p}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b}$. From a total of
$\mathcal{O}(\log(n/\delta)/\eta_{0}^{2})$ such experiments, the estimate
$\hat{p}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b}$ is equal to the true
probability up to $\eta_{0}$ error for all
$k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b$ with a probability at least
$1-\delta$. We now define a loss function based on the estimated values,

$\eta_{1}=\max_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b}\left|\hat{p}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b}-f(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b)\right|.$
(406)

The function $f(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b)$ is defined as
follows. For qubit $i$ on the left, we have

$f(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b)=\begin{cases}1/2&\lfloor
k_{1}/2\rfloor\neq(k_{2}-6)\\\ 1&\lfloor
k_{1}/2\rfloor=(k_{2}-6),\,\,k_{1}\equiv b\,(\mathrm{mod}2)\\\ 0&\lfloor
k_{1}/2\rfloor=(k_{2}-6),\,\,k_{1}\not\equiv b\,(\mathrm{mod}2)\\\
\end{cases}$ (407)

For qubit $i$ on the right, we have

$f(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b)=\begin{cases}1/2&\lfloor
k_{1}^{\prime}/2\rfloor\neq(k_{2}^{\prime}-6)\\\ 1&\lfloor
k_{1}^{\prime}/2\rfloor=(k_{2}^{\prime}-6),\,\,k_{1}^{\prime}\equiv
b\,(\mathrm{mod}2)\\\ 0&\lfloor
k_{1}^{\prime}/2\rfloor=(k_{2}^{\prime}-6),\,\,k_{1}^{\prime}\not\equiv
b\,(\mathrm{mod}2)\\\ \end{cases}$ (408)

We optimize over the selection of gates such that the loss function $\eta_{1}$
is as small as possible.

####  L.2.b Rigorous guarantee: Single-qubit

Given an estimation error $\eta_{0}$ and the loss function $\eta_{1}$, we can
approximately learn the following states and measurements. We combine the
first layer of single-qubit gates determined by $k_{1},k_{1}^{\prime}$ and the
unknown product state to create a new set of product states, denoted as

$\rho^{(k_{1},k_{1}^{\prime})}_{1}\otimes\ldots\otimes\rho^{(k_{1},k_{1}^{\prime})}_{2n},$
(409)

for all $k_{1},k_{1}^{\prime}\in\\{0,1,2,3,4,5\\}$. We also combine the last
layer of single-qubit gates determined by $k_{2},k_{2}^{\prime}$ and the
unknown product measurement to create a new set of product measurements,

$\left\\{\bigotimes_{i=1}^{2n}M^{(i,k_{2},k_{2}^{\prime})}_{B_{i}}\right\\}_{B\in\\{0,1\\}^{2n}},$
(410)

for all $k_{2},k_{2}^{\prime}\in\\{6,7,8\\}$. We have the following
characterization.

######  Lemma L.1 (Single-qubit stabilizer states).

For any $i=1,\ldots,2n$, there exists a unitary or anti-unitary transformation
$U_{i}$ on qubit $i$, such that the following holds for any
$k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},b$. For qubit $i$ on the left, we
have

$\displaystyle\left\lVert\rho_{i}^{(k_{1},k_{1}^{\prime})}-U_{i}\sigma_{k_{1}}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}),$
(411) $\displaystyle\left\lVert
M^{(i,k_{2},k_{2}^{\prime})}_{b}-U_{i}\sigma_{2(k_{2}-6)+b}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}).$
(412)

For qubit $i$ on the right, we have

$\displaystyle\left\lVert\rho_{i}^{(k_{1},k_{1}^{\prime})}-U_{i}\sigma_{k_{1}^{\prime}}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}),$
(413) $\displaystyle\left\lVert
M^{(i,k_{2},k_{2}^{\prime})}_{b}-U_{i}\sigma_{2(k_{2}^{\prime}-6)+b}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}),$
(414)

where the pure states $\sigma_{x}$ for $x=0,\ldots,5$ are given by

$\lvert 0\rangle\\!\langle 0\rvert,\,\,\lvert 1\rangle\\!\langle
1\rvert,\,\,\lvert+\rangle\\!\langle+\rvert,\,\,\lvert-\rangle\\!\langle-\rvert,\,\,\lvert
y+\rangle\\!\langle y+\rvert,\,\,\lvert y-\rangle\\!\langle y-\rvert.$ (415)

###### Proof.

Without loss of generality, we consider qubit $i$ on the left hand side of the
$n\times 2$ grid. The proof is the same for qubits on the right side except
that we need to swap $k_{1}\leftrightarrow k_{1}^{\prime},k_{2}\leftrightarrow
k_{2}^{\prime}$. From the estimate
$\hat{p}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b}$ and the definition
of the loss function $\eta_{1}$,

$\left|\operatorname{tr}\left(M^{(i,k_{2},k_{2}^{\prime})}_{b}\rho_{i}^{(k_{1},k_{1}^{\prime})}\right)-f(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},i,b)\right|\leq\eta_{0}+\eta_{1},$
(416)

for all $k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},b$. The above defines an
approximate geometry that can be used to infer the underlying operations. This
technique is used in Appendix D.5 to learn general $d$-dimensional systems.

For a fixed choice of $k_{1}^{\prime},k_{2}^{\prime}$, we have six matrices
for $\rho_{i}^{(k_{1},k_{1}^{\prime})}$ and six matrices for
$M^{(i,k_{2},k_{2}^{\prime})}_{b}$ corresponding to different $k_{1},k_{2}$
and $b$. Now, given $q=0,1,2$. We denote the two matrices
$\rho_{i}^{(k_{1},k_{1}^{\prime})}$ associated to $k_{1}=2q+0,2q+1$ as
$\rho_{0},\rho_{1}$, denote the two matrices
$M^{(i,k_{2},k_{2}^{\prime})}_{b}$ associated to $k_{2}=q$ and $b=0,1$ as
$M_{0},M_{1}$, and define $\eta=\eta_{0}+\eta_{1}$. We have the following
inequalities from Eq. (416),

$\operatorname{tr}(M_{0}\rho_{0})\geq
1-\eta,\,\,\,\operatorname{tr}(M_{0}\rho_{1})\leq\eta,\,\,\,\operatorname{tr}(M_{1}\rho_{0})\leq\eta,\,\,\,\operatorname{tr}(M_{1}\rho_{1})\geq
1-\eta.$ (417)

Using the fact that $M_{0},M_{1},\rho_{0},\rho_{1}$ are positive-semidefinite,
$M_{0}+M_{1}=I,$ and
$\operatorname{tr}(\rho_{0})=\operatorname{tr}(\rho_{1})=1$, there exists two
orthogonal pure states
$\lvert\psi_{0}\rangle\\!\langle\psi_{0}\rvert,\lvert\psi_{1}\rangle\\!\langle\psi_{1}\rvert$
and a constant $C>0$, such that

$\displaystyle\left\lVert
M_{0}-\lvert\psi_{0}\rangle\\!\langle\psi_{0}\rvert\right\rVert_{1}$
$\displaystyle\leq C\eta,$ $\displaystyle\,\,\left\lVert
M_{1}-\lvert\psi_{1}\rangle\\!\langle\psi_{1}\rvert\right\rVert_{1}$
$\displaystyle\leq C\eta,$ (418)
$\displaystyle\left\lVert\rho_{0}-\lvert\psi_{0}\rangle\\!\langle\psi_{0}\rvert\right\rVert_{1}$
$\displaystyle\leq C\eta,$
$\displaystyle\,\,\left\lVert\rho_{1}-\lvert\psi_{1}\rangle\\!\langle\psi_{1}\rvert\right\rVert_{1}$
$\displaystyle\leq C\eta.$ (419)

Hence, we know that the six matrices for $\rho_{i}^{(k_{1},k_{1}^{\prime})}$
are approximately pure states. Then we can use the approximate geometry given
in Eq. (416) over pairs of distinct $q$ to show that there exists a constant
$C^{\prime}>0$ and a unitary or anti-unitary transformation
$U_{i,k_{1}^{\prime},k_{2}^{\prime}}$ such that

$\displaystyle\left\lVert\rho_{i}^{(k_{1},k_{1}^{\prime})}-U_{i,k_{1}^{\prime},k_{2}^{\prime}}\sigma_{k_{1}}U_{i,k_{1}^{\prime},k_{2}^{\prime}}^{-1}\right\rVert_{1}\leq
C^{\prime}\eta,$ (420) $\displaystyle\left\lVert
M^{(i,k_{2},k_{2}^{\prime})}_{b}-U_{i,k_{1}^{\prime},k_{2}^{\prime}}\sigma_{2(k_{2}-6)+b}U_{i,k_{1}^{\prime},k_{2}^{\prime}}^{-1}\right\rVert_{1}\leq
C^{\prime}\eta,$ (421)

where the pure states $\sigma_{x}$ for $x=0,\ldots,5$ are given by

$\sigma_{x}=\lvert 0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert,\lvert+\rangle\\!\langle+\rvert,\lvert-\rangle\\!\langle-\rvert,\lvert
y+\rangle\\!\langle y+\rvert,\lvert y-\rangle\\!\langle y-\rvert,$ (422)

respectively.

We see that $U_{i,k_{1}^{\prime},k_{2}^{\prime}}$ depends on
$k_{1}^{\prime},k_{2}^{\prime}$. The last step is to show that we can actually
choose a single unitary or anti-unitary transformation $U_{i}$. Consider
$U_{i}=U_{i,k_{1}^{\prime}=0,k_{2}^{\prime}=6}$. For all $x=0,\ldots,5$, we
have

$\displaystyle\left\lVert
U_{i,k_{1}^{\prime},k_{2}^{\prime}}\sigma_{x}U_{i,k_{1}^{\prime},k_{2}^{\prime}}^{-1}-U_{i}\sigma_{x}U_{i}^{-1}\right\rVert_{1}$
(423) $\displaystyle\leq\left\lVert
U_{i,k_{1}^{\prime},k_{2}^{\prime}}\sigma_{x}U_{i,k_{1}^{\prime},k_{2}^{\prime}}^{-1}-U_{i,0,k_{2}^{\prime}}\sigma_{x}U_{i,0,k_{2}^{\prime}}^{-1}\right\rVert_{1}+\left\lVert
U_{i,0,k_{2}^{\prime}}\sigma_{x}U_{i,0,k_{2}^{\prime}}^{-1}-U_{i,0,6}\sigma_{x}U_{i,0,6}^{-1}\right\rVert_{1}$
(424) $\displaystyle\leq\left\lVert
U_{i,k_{1}^{\prime},k_{2}^{\prime}}\sigma_{x}U_{i,k_{1}^{\prime},k_{2}^{\prime}}^{-1}-\rho_{i}^{(x,k_{1}^{\prime})}\right\rVert_{1}+\left\lVert\rho_{i}^{(x,k_{1}^{\prime})}-U_{i,0,k_{2}^{\prime}}\sigma_{x}U_{i,0,k_{2}^{\prime}}^{-1}\right\rVert_{1}$
(425) $\displaystyle+\left\lVert
U_{i,0,k_{2}^{\prime}}\sigma_{x}U_{i,0,k_{2}^{\prime}}^{-1}-M^{(i,k_{2},\lfloor
x/2\rfloor+6)}_{x\,\mathrm{mod}\,2}\right\rVert_{1}+\left\lVert
M^{(i,k_{2},\lfloor
x/2\rfloor+6)}_{x\,\mathrm{mod}\,2}-U_{i,0,6}\sigma_{x}U_{i,0,6}^{-1}\right\rVert_{1}$
(426) $\displaystyle\leq 2C^{\prime}\eta+2C^{\prime}\eta=4C^{\prime}\eta.$
(427)

The second-to-last inequality follows from Eq. (420) and (421). Together, we
have

$\displaystyle\left\lVert\rho_{i}^{(k_{1},k_{1}^{\prime})}-U_{i}\sigma_{k_{1}}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}),$
(428) $\displaystyle\left\lVert
M^{(i,k_{2},k_{2}^{\prime})}_{b}-U_{i}\sigma_{2(k_{2}-6)+b}U_{i}^{-1}\right\rVert_{1}\leq\mathcal{O}(\eta_{0}+\eta_{1}),$
(429)

This concludes the proof. ∎

####  L.2.c Experiments and loss functions: Two-qubit

We also perform another layer of optimization to find two two-qubit gates for
every pair of corresponding qubits on the left and right, i.e., qubit
$i=2\ell-1,2\ell$, where $\ell=1,\ldots,n$. We denote the two two-qubit gates
as $g^{(2)}_{\ell,s}$ and $g^{(2)}_{\ell,e}$ for each $\ell=0,\ldots,n$.
Similar to before, after choosing $g^{(2)}_{\ell,s}$ and $g^{(2)}_{\ell,e}$,
we conduct the following set of experiments.

For each of
$k_{1},k_{1}^{\prime}\in\\{0,\ldots,5\\},k_{2},k_{2}^{\prime}\in\\{6,7,8\\},x\in\\{s,e\\}$,
we prepare the unknown product state $\rho_{1}\otimes\ldots\otimes\rho_{2n}$,
apply a layer of single-qubit gates, a layer of two-qubit gates, followed by
another layer of single-qubit gates, then measure using the unknown product
measurement. In the first layer of the single-qubit gates, we apply
$g_{i,k_{1}}$ for qubit $i$ on the left and apply $g_{i,k_{1}^{\prime}}$ for
qubit $i$ on the right. In the middle layer of two-qubit gates, we apply
$g^{(2)}_{\ell,x}$ on qubit $2\ell-1$ on the left and qubit $2\ell$ on the
right. In the other layer of the single-qubit gates, we apply $g_{i,k_{2}}$
for qubit $i$ on the left and apply $g_{i,k_{2}^{\prime}}$ for qubit $i$ on
the right. For each $k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime}$ and each pair
of qubits $2\ell-1,2\ell$, we estimate the probability for obtaining the two
bits $b,b^{\prime}\in\\{0,1\\}$ as the outcome, denoted as
$\hat{p}^{(2)}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}$.
From a total of $\mathcal{O}(\log(n/\delta)/\eta_{0}^{2})$, the estimate
$\hat{p}^{(2)}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}$
is equal to the true probability up to $\eta_{0}$ error for all
$k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}$ with a
probability at least $1-\delta$. We now define another loss function based on
the estimated values,

$\eta_{2}=\max_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}\left|\hat{p}^{(2)}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}-h(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,b,b^{\prime})\right|.$
(430)

The function $h(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,b,b^{\prime})$ is
defined as follows.

$\displaystyle h(k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,b,b^{\prime})$
$\displaystyle=\operatorname{tr}\left((\rho^{\mathrm{(out)}}_{k_{2},b}\otimes\rho^{\mathrm{(out)}}_{k_{2}^{\prime},b^{\prime}})U_{x}(\rho^{\mathrm{(in)}}_{k_{1}}\otimes\rho^{\mathrm{(in)}}_{k_{1}^{\prime}})U_{x}^{\dagger}\right),$
(431) $\displaystyle\rho^{\mathrm{(in)}}_{k_{1}}$
$\displaystyle=\sigma_{k_{1}},$ (432)
$\displaystyle\rho^{\mathrm{(out)}}_{k_{2},b}$
$\displaystyle=\sigma_{2(k_{2}-6)+b},$ (433)
$\displaystyle\sigma_{0},\ldots,\sigma_{5}$ $\displaystyle=\lvert
0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert,\lvert+\rangle\\!\langle+\rvert,\lvert-\rangle\\!\langle-\rvert,\lvert
y+\rangle\\!\langle y+\rvert,\lvert y-\rangle\\!\langle y-\rvert,$ (434)
$\displaystyle U_{s},U_{e}$ $\displaystyle=\mathrm{SWAP},\mathrm{BELL},$ (435)

where $\mathrm{SWAP}$ and $\mathrm{BELL}$ are two-qubit unitaries,
$\mathrm{SWAP}$ swaps the left and right qubits, $\mathrm{BELL}=(H\otimes
I)\,\,\mathrm{CNOT}$, $\mathrm{CNOT}$ is controlled on the same qubit that the
Hadamard $H$ acts on. The entangling operation $\mathrm{BELL}$ followed by
computational basis measurement is one way to perform Bell measurement.

####  L.2.d Rigorous guarantee: Two-qubit

Next, using the bound on the estimation error $\eta_{0}$ and the loss function
$\eta_{2}$, we can approximately learn the entangling operations. We can write
the middle layer of two-qubit gates as

${{\mathcal{E}}}_{\ell=1,x}\otimes\ldots\otimes{{\mathcal{E}}}_{\ell=n,x},$
(436)

for $x\in\\{s,e\\}$, where ${{\mathcal{E}}}_{\ell,x}$ acts on two qubits,
$2\ell-1$ and $2\ell$.

######  Lemma L.2 (SWAP and Bell measurement).

For each qubit $i=1,\ldots,2n$, consider the unitary or anti-unitary
transformation $U_{i}$ on qubit $i$ given in Lemma L.1.

$\displaystyle\left\lVert{{\mathcal{E}}}_{\ell,s}(\cdot)-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}(\cdot)(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}\right\rVert_{1\rightarrow 1}$ (437)
$\displaystyle\leq\mathcal{O}(\eta_{0}+\eta_{1}+\eta_{2}),$ (438)
$\displaystyle\left\lVert{{\mathcal{E}}}_{\ell,e}(\cdot)-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{BELL}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}(\cdot)(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{BELL}^{\dagger}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}\right\rVert_{1\rightarrow 1}$ (439)
$\displaystyle\leq\mathcal{O}(\eta_{0}+\eta_{1}+\eta_{2}),$ (440)

where $\left\lVert{{\mathcal{E}}}\right\rVert_{1\rightarrow
1}=\max_{\left\lVert
X\right\rVert_{1}=1}\left\lVert{{\mathcal{E}}}(X)\right\rVert_{1}$.

###### Proof.

We prove this lemma for $\mathrm{SWAP}$. The proof for $\mathrm{BELL}$ is
basically the same. We begin by defining the following notations.

$\displaystyle\rho^{(in)}$
$\displaystyle=(\sigma_{k_{1}}\otimes\sigma_{k_{1}^{\prime})}),$ (441)
$\displaystyle\rho^{(out)}$
$\displaystyle=(\sigma_{2(k_{2}-6)+b}\otimes\sigma_{2(k_{2}^{\prime}-6)+b^{\prime}}),$
(442) $\displaystyle\rho^{(in,U)}$
$\displaystyle=(U_{2\ell-1}\sigma_{k_{1}}U_{2\ell-1}^{-1})\otimes(U_{2\ell}\sigma_{k_{1}^{\prime}}U_{2\ell}^{-1}),$
(443) $\displaystyle\rho^{(out,U)}$
$\displaystyle=(U_{2\ell-1}\sigma_{2(k_{2}-6)+b}U_{2\ell-1}^{-1})\otimes(U_{2\ell}\sigma_{2(k_{2}^{\prime}-6)+b^{\prime}}U_{2\ell}^{-1}),$
(444) $\displaystyle\sigma_{0},\ldots,\sigma_{5}$ $\displaystyle=\lvert
0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert,\lvert+\rangle\\!\langle+\rvert,\lvert-\rangle\\!\langle-\rvert,\lvert
y+\rangle\\!\langle y+\rvert,\lvert y-\rangle\\!\langle y-\rvert.$ (445)

We can use triangle inequality in Eq. (430) to show that

$\displaystyle\left|\operatorname{tr}\left(\left(M^{2\ell-1,k_{2},k_{2}^{\prime}}_{b}\otimes
M^{2\ell,k_{2},k_{2}^{\prime}}_{b^{\prime}}\right){{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)-\operatorname{tr}\left(\rho^{(out)}\mathrm{SWAP}\left(\rho^{(in)}\right)\mathrm{SWAP}\right)\right|$
(446)
$\displaystyle\leq\left|\operatorname{tr}\left(\left(M^{2\ell-1,k_{2},k_{2}^{\prime}}_{b}\otimes
M^{2\ell,k_{2},k_{2}^{\prime}}_{b^{\prime}}\right){{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)-\hat{p}^{(2)}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}\right|$
(447)
$\displaystyle+\left|\hat{p}^{(2)}_{k_{1},k_{1}^{\prime},k_{2},k_{2}^{\prime},x,\ell,b,b^{\prime}}-\operatorname{tr}\left(\rho^{(out)}\mathrm{SWAP}\left(\rho^{(in)}\right)\mathrm{SWAP}\right)\right|$
(448) $\displaystyle\leq\eta_{0}+\eta_{2}.$ (449)

Then from triangle inequality and Lemma L.1, we have

$\displaystyle\left|\operatorname{tr}\left(\left(M^{2\ell-1,k_{2},k_{2}^{\prime}}_{b}\otimes
M^{2\ell,k_{2},k_{2}^{\prime}}_{b^{\prime}}\right){{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)-\operatorname{tr}\left(\rho^{(out,U)}{{\mathcal{E}}}_{\ell,s}\left(\rho^{(in,U)}\right)\right)\right|$
(450)
$\displaystyle\leq\left|\operatorname{tr}\left(\left(M^{2\ell-1,k_{2},k_{2}^{\prime}}_{b}\otimes
M^{2\ell,k_{2},k_{2}^{\prime}}_{b^{\prime}}\right){{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)-\operatorname{tr}\left(\rho^{(out,U)}{{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)\right|$
(451)
$\displaystyle+\left|\operatorname{tr}\left(\rho^{(out,U)}{{\mathcal{E}}}_{\ell,s}\left(\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}\right)\right)-\operatorname{tr}\left(\rho^{(out,U)}{{\mathcal{E}}}_{\ell,s}\left(\rho^{(in,U)}\right)\right)\right|$
(452)
$\displaystyle\leq\left\lVert\left(M^{2\ell-1,k_{2},k_{2}^{\prime}}_{b}\otimes
M^{2\ell,k_{2},k_{2}^{\prime}}_{b^{\prime}}\right)-\rho^{(out,U)}\right\rVert_{1}+\left\lVert\rho^{k_{1},k_{1}^{\prime}}_{2\ell-1}\otimes\rho^{k_{1},k_{1}^{\prime}}_{2\ell}-\rho^{(in,U)}\right\rVert_{1}$
(453) $\displaystyle\leq\mathcal{O}(\eta_{0}+\eta_{1}).$ (454)

Hence, by another triangle inequality, we obtain

$\displaystyle\left|\operatorname{tr}\left(\rho^{(out,U)}{{\mathcal{E}}}_{\ell,s}\left(\rho^{(in,U)}\right)\right)-\operatorname{tr}\left(\rho^{(out)}\mathrm{SWAP}\left(\rho^{(in)}\right)\mathrm{SWAP}\right)\right|\leq\mathcal{O}(\eta_{0}+\eta_{1}+\eta_{2}).$
(455)

Because every $(2\times 2)\times(2\times 2)$ Hermitian matrix can be written
as a linear combination of $\sigma_{i}\otimes\sigma_{j},\forall
i,j\in\\{0,1,\ldots,5\\}$, we have the following bound by triangle inequality,

$\displaystyle\left\lVert{{\mathcal{E}}}_{\ell,s}(\cdot)-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}(\cdot)(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}\right\rVert_{1\rightarrow 1}$ (456)
$\displaystyle\leq\mathcal{O}(\eta_{0}+\eta_{1}+\eta_{2}).$ (457)

This concludes the proof. ∎

######  Remark 5.

If $\eta_{0}+\eta_{1}+\eta_{2}$ is smaller than some constant, then
$U_{2\ell-1}$ and $U_{2\ell}$ must be both unitary or both anti-unitary, which
can be shown by a proof by contradiction.

####  L.2.e Putting everything together

When the quantum device is designed perfectly, the loss functions vanish,
i.e., $\eta_{1}=\eta_{2}=0$. However, when the quantum device is subject to
some unknown noise, the loss functions $\eta_{1},\eta_{2}$ will be small but
non-zero. Here, we show that when we perform sufficiently many experiments to
estimate the loss functions and we find the loss functions to be small, then
we can guarantee that the underlying physical operations satisfy a certain
form.

From now on, we assume that $\eta_{0}+\eta_{1}+\eta_{2}$ are small enough such
that there exists $\epsilon>0$ and a set of unitary or anti-unitary
transformations $U_{i},\forall i=1,\ldots,2n$ satisfying the following
constraints. For all $\ell=1,\ldots,n$,
$k_{1},k_{1}^{\prime}\in\\{0,\ldots,5\\}$, and
$k_{2},k_{2}^{\prime}\in\\{6,7,8\\}$, we have

$\displaystyle\left\lVert\rho_{2\ell-1}^{(k_{1},k_{1}^{\prime})}\otimes\rho_{2\ell}^{(k_{1},k_{1}^{\prime})}-(U_{2\ell-1}\sigma_{k_{1}}U_{2\ell}^{-1})\otimes(U_{2\ell}\sigma_{k_{1}^{\prime}}U_{2\ell}^{-1})\right\rVert_{1}$
$\displaystyle\leq\epsilon,$ (458)
$\displaystyle\sum_{b,b^{\prime}\in\\{0,1\\}}\left\lVert
M^{(2\ell-1,k_{2},k_{2}^{\prime})}_{b}\otimes
M^{(2\ell,k_{2},k_{2}^{\prime})}_{b^{\prime}}-(U_{2\ell-1}\sigma_{2(k_{2}-6)+b}U_{2\ell}^{-1})\otimes(U_{2\ell}\sigma_{2(k_{2}^{\prime}-6)+b^{\prime}}U_{2\ell}^{-1})\right\rVert_{1}$
$\displaystyle\leq\epsilon,$ (459)

where the pure states $\sigma_{x}$ for $x=0,\ldots,5$ are given by

$\lvert 0\rangle\\!\langle 0\rvert,\,\,\lvert 1\rangle\\!\langle
1\rvert,\,\,\lvert+\rangle\\!\langle+\rvert,\,\,\lvert-\rangle\\!\langle-\rvert,\,\,\lvert
y+\rangle\\!\langle y+\rvert,\,\,\lvert y-\rangle\\!\langle y-\rvert.$ (460)

And we also have

$\displaystyle\left\lVert{{\mathcal{E}}}_{\ell,s}-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}(\cdot)(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{SWAP}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}\right\rVert_{1\rightarrow 1}\leq\epsilon,$ (461)
$\displaystyle\left\lVert{{\mathcal{E}}}_{\ell,e}-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{BELL}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}(\cdot)(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{BELL}^{\dagger}(U_{2\ell-1}\otimes
U_{2\ell})^{-1}\right\rVert_{1\rightarrow 1}\leq\epsilon,$ (462)

where $\mathrm{SWAP}$ and $\mathrm{BELL}$ are two-qubit unitaries,
$\mathrm{SWAP}$ swaps the left and right qubits, $\mathrm{BELL}=(H\otimes
I)\,\,\mathrm{CNOT}$, and
$\left\lVert{{\mathcal{E}}}\right\rVert_{1\rightarrow 1}=\max_{\left\lVert
X\right\rVert_{1}=1}\left\lVert{{\mathcal{E}}}(X)\right\rVert_{1}$.

###  L.3 Task description and quantum advantage

We focus on the task of predicting many incompatible properties in unknown
physical systems studied in huang2021information ; chen2021exponential ;
huang2021quantum . We consider an unknown physical system described by an
$n$-qubit separable state $\rho$. Recall that a separable state is a classical
probability mixture over product states. The goal is to learn to predict
properties about $\rho$.

We compare two experimental settings: conventional experiments and quantum-
enhanced experiments. In _conventional experiments_ , the physicist could
perform any POVM measurement on the unknown state $\rho$ to gather classical
data. Based on the measurement data, the physicist could adaptively choose the
next measurement on $\rho$ to obtain more data. After many rounds of
measurements, the physicist combines all measurement outcomes to form a model
about the unknown state $\rho$. In _quantum-enhanced experiments_ , the
physicist could load multiple copies of the unknown state $\rho$ to a quantum
computing system. The physicist can then use the quantum computer to perform
quantum data analysis to learn a model about the unknown state $\rho$. After
learning a model of $\rho$, we will ask the physicist to predict properties of
$\rho$.

We assume that the conventional experiments are perfect. All the POVM
measurement could be chosen arbitrarily and are not subject to any noise. In
contrast, we consider quantum-enhanced experiments to base only on the noisy
and unknown quantum device that we partially learned in Appendix L.2. Despite
the imperfection of quantum-enhanced experiments, we can still demonstrate a
large quantum advantage.

######  Theorem L.3 (Advantage with noisy quantum device; Restatement of
Theorem 7).

Given $n>0$. Suppose $\epsilon$ is the error on each two-qubit operation in
the noisy quantum device. There exists a distribution over unknown $n$-qubit
separable states $\rho$ and properties, such that quantum-enhanced experiments
using the noisy quantum device only require
$N_{\mathrm{Q}}=\mathcal{O}((1/(1-4\epsilon))^{2n})$ experiments to predict
accurately, while noiseless conventional experiments require
$N_{\mathrm{C}}=\Omega(2^{n})$ experiments. This yields a separation of
$N_{\mathrm{C}}=\Omega(N_{\mathrm{Q}}^{a}),$ where
$a=-\log(2)/(2\log(1-4\epsilon))=\mathcal{O}(\epsilon)$.

###  L.4 A class of states and properties

For certain states and properties, conventional experiments can be very
powerful. For example, classical shadow tomography huang2020predicting ;
huang2022learning  is a class of conventional experiments based on randomized
measurements that can be used to make accurate prediction for many properties.
Here, we give an example where there is a large separation between
conventional experiments with perfect measurements and noisy quantum-enhanced
experiments. We consider a distribution over the unknown $n$-qubit separable
states $\rho$ and the properties as follows.

With probability $1/(4^{n}-1)$, we sample a Pauli observable
$P\in\\{I,X,Y,Z\\}^{\otimes n}\setminus\\{I^{\otimes n}\\}$. Then with
probability $1/2$, we consider the unknown state $\rho$ to be the maximally
mixed state $I/2^{n}$. With probability $1/4$, we consider the unknown state
$\rho$ to be

$\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)\left(\frac{I+0.9P}{2^{n}}\right)\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right).$
(463)

With probability $1/4$, we consider the unknown state $\rho$ to be

$\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)\left(\frac{I-0.9P}{2^{n}}\right)\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right).$
(464)

The property we would like to predict is the absolute value of the expectation
value of

$O=\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)P\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right).$
(465)

We tell the learning algorithm both the Pauli observable $P$ and the above
observable $O$. When $\rho=I/2^{n}$, the property is equal to zero. However,
when $\rho$ is an alternative state that is not $I/2^{n}$, the property is
equal to $0.9$. Hence, making accurate prediction in this task is equivalent
to distinguishing whether $\rho$ is the maximally mixed state $I/2^{n}$.

####  L.4.a Characterization of the probability distribution

Both the states $I/2^{n}$ and $(I\pm 0.9P)/2^{n}$ are separable states and can
be represented as a classical probability distribution over tensor products of
the single-qubit stabilizer states

$S=\big{\\{}\lvert 0\rangle\\!\langle 0\rvert,\,\lvert 1\rangle\\!\langle
1\rvert,\,\lvert+\rangle\\!\langle+\rvert,\,\lvert-\rangle\\!\langle-\rvert,\,\lvert
y+\rangle\\!\langle y+\rvert,\,\lvert y-\rangle\\!\langle y-\rvert\big{\\}}.$
(466)

The physical system $\rho$ is a classical probability mixture over tensor
products of $U_{2\ell-1}\sigma_{\ell}U_{2\ell-1}^{-1}$ for $\ell=1,\ldots,n$,
where $\sigma_{\ell}$ is a single-qubit stabilizer state. Hence, we have

$\rho=\sum_{\sigma_{\ell}\in
S,\forall\ell=1,\ldots,n}p(\sigma_{1},\ldots,\sigma_{n})(U_{1}\sigma_{1}U_{1}^{-1})\otimes\ldots\otimes(U_{2n-1}\sigma_{n}U_{2n-1}^{-1}).$
(467)

There are multiple distinct probability distributions that lead to the same
state $\rho$. Here, we consider the following classical distribution based on
the chosen Pauli observable $P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes n}\\}$ for the ease of analysis.

  * •

$\rho$ is the maximally mixed state: For each $\ell=1,\ldots,n$, we consider
the following. If $P_{\ell}=I,X,Y$, we choose $\sigma_{\ell}$ from the uniform
distribution over $\lvert 0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert$. If $P_{\ell}=Z$, we choose $\sigma_{\ell}$ from the uniform
distribution over
$\lvert+\rangle\\!\langle+\rvert,\lvert-\rangle\\!\langle-\rvert$.

  * •

$\rho$ is a locally rotated $(I\pm 0.9P)/2^{n}$: The state $(I\pm 0.9P)/2^{n}$
is equal to the uniform mixture of the maximally mixed state and the state
$(I\pm P)/2^{n}$. With probability $0.1$, we prepare $\rho$ the same way as
the maximally mixed state given above. With probability $0.9$, we prepare
$\rho$ as $(I\pm P)/2^{n}$. For each $\ell=1,\ldots,n$, we consider the
following. If $P_{\ell}=I$, we choose a $\sigma_{\ell}$ to be a uniform
distribution over $\lvert 0\rangle\\!\langle 0\rvert,\lvert 1\rangle\\!\langle
1\rvert$. If $P_{\ell}\neq I$, we choose $\sigma_{\ell}$ to be one of the
eigenstates of $P_{\ell}$. When $P_{\ell}$ is not the last non-identity Pauli
operator, we choose $\sigma_{\ell}$ uniformly at random. When $P_{\ell}$ is
the last non-identity Pauli operator, we choose $\sigma_{\ell}$
deterministically based on the choice of $\sigma_{\ell^{\prime}}$ for
$\ell^{\prime}<\ell$ where $P_{\ell^{\prime}}$ is not an identity. The
determinisitic choice satisfies a parity constraint given by the state $(I\pm
P)/2^{n}$.

Other choices of the classical probability distribution that give rise to the
same state would yield exactly the same result but the analysis could be
slightly more complex.

###  L.5 Upper bound for noisy quantum-enhanced experiments

We provide a sample complexity upper bound for quantum-enhanced experiments
using the noisy quantum device that we partially learned. The quantum-enhanced
experiment we implement loads in two copies of the physical system $\rho$ and
performs an entangled measurement across the two copies.

####  L.5.a Detailed procedure

In the noisy quantum-enhanced experiments, we utilize the noisy quantum device
and repeat the following for $N_{\mathrm{Q}}/2$ times.

  1. 1.

Prepare the initial product state followed by a layer of single-qubit gates
$g_{i,0}$ for all qubit $i=1,\ldots,2n$.

  2. 2.

Load the physical system $\rho$ into the left hand side of the $n\times 2$
grid.

  3. 3.

Apply the entangling layer
${{\mathcal{E}}}_{\ell=1,s}\otimes\ldots\otimes{{\mathcal{E}}}_{\ell=n,s}$,
which is approximately equal to applying SWAP gates between left and right
side of the $n\times 2$ grid from Eq. (461).

  4. 4.

Load the physical system $\rho$ into the left hand side of the $n\times 2$
grid again.

  5. 5.

Apply the entangling layer
${{\mathcal{E}}}_{\ell=1,e}\otimes\ldots\otimes{{\mathcal{E}}}_{\ell=n,e}$,
which is approximately equal to rotating the pairs of qubits into a Bell basis
from Eq. (462).

  6. 6.

Apply a layer of single-qubit gates $g_{i,6}$ for all qubit $i=1,\ldots,2n$.
Then measure using the unknown product measurement.

  7. 7.

Store the measurement outcome as $b_{t,i},\forall i=1,\ldots,2n$ for the
$t$-th experiment.

After the $N_{\mathrm{Q}}/2$ experiments using $N_{\mathrm{Q}}$ copies of the
physical system $\rho$, when we are given a Pauli observable
$P\in\\{I,X,Y,Z\\}^{\otimes n}$, we compute the following,

$\Xi\equiv\frac{2}{N_{\mathrm{Q}}}\sum_{t=1}^{N_{\mathrm{Q}}/2}\prod_{\ell=1}^{n}\bra{\beta(b_{t,2\ell-1},b_{t,2\ell})}P_{\ell}\otimes
P_{\ell}\ket{\beta(b_{t,2\ell-1},b_{t,2\ell})},$ (468)

where $\ket{\beta(x,y)}$ is the Bell state,

$\ket{\beta(x,y)}=\left(\frac{\ket{0,y}+(-1)^{x}\ket{1,1-y}}{\sqrt{2}}\right).$
(469)

To understand what is happening, consider $U_{i}=I,\forall i$. When all the
operations are perfect, the quantum-enhanced experiment is equivalent to
storing two copies of $\rho$ in the $2n$ qubits and measuring every pair of
corresponding qubits in the Bell basis. The Bell basis simultaneously
diagonalizes $P\otimes P$ for all $P\in\\{I,X,Y,Z\\}^{\otimes n}$. Hence, we
can simultaneously predict $\operatorname{tr}((P\otimes
P)(\rho\otimes\rho))=\operatorname{tr}(P\rho)^{2}$ for all the Pauli
observables.

####  L.5.b Noise analysis

We analyze how noise affects the quantum-enhanced experiments. Suppose the
first sample of $\rho$ is

$(U_{1}\sigma^{A}_{1}U_{1}^{-1})\otimes\ldots\otimes(U_{2n-1}\sigma^{A}_{n}U_{2n-1}^{-1}),$
(470)

and the second sample of $\rho$ is

$(U_{1}\sigma^{B}_{1}U_{1}^{-1})\otimes\ldots\otimes(U_{2n-1}\sigma^{B}_{n}U_{2n-1}^{-1}).$
(471)

Let us focus on a pair of qubits $2\ell-1,2\ell$ for $\ell=1,\ldots,n$. From
Eq. (458), after the first two steps, the pair of qubits is in a state
$\rho^{(2\ell-1,2\ell),a}$ with

$\left\lVert\rho^{(2\ell-1,2\ell),a}-(U_{2\ell-1}\sigma^{A}_{\ell}U_{2\ell-1}^{-1})\otimes(U_{2\ell}\lvert
0\rangle\\!\langle 0\rvert U_{2\ell}^{-1})\right\rVert_{1}\leq\epsilon.$ (472)

After the third and fourth step, the pair of qubits is now in a state
$\rho^{(2\ell-1,2\ell),b}$ with

$\left\lVert\rho^{(2\ell-1,2\ell),b}-(U_{2\ell-1}\sigma^{B}_{\ell}U_{2\ell-1}^{-1})\otimes(U_{2\ell}\sigma^{A}_{\ell}U_{2\ell}^{-1})\right\rVert_{1}\leq
2\epsilon$ (473)

using Eq. (461). After the fifth step, the two-qubit state is now
$\rho^{(2\ell-1,2\ell),c}$. From Eq. (462), we have

$\left\lVert\rho^{(2\ell-1,2\ell),c}-(U_{2\ell-1}\otimes
U_{2\ell})\mathrm{BELL}(\sigma^{B}_{\ell}\otimes\sigma^{A}_{\ell})\mathrm{BELL}^{\dagger}(U_{2\ell-1}^{-1}\otimes
U_{2\ell}^{-1})\right\rVert_{1}\leq 3\epsilon.$ (474)

In the sixth and seventh step, we measure the two-qubit state
$\rho^{(2\ell-1,2\ell),c}$ with a two-qubit product POVM. The two-qubit
product POVM is given by

$\\{M_{0}^{(2\ell-1,6,6)}\otimes
M_{0}^{(2\ell,6,6)},M_{0}^{(2\ell-1,6,6)}\otimes
M_{1}^{(2\ell,6,6)},M_{1}^{(2\ell-1,6,6)}\otimes
M_{0}^{(2\ell,6,6)},M_{1}^{(2\ell-1,6,6)}\otimes M_{1}^{(2\ell,6,6)}\\},$
(475)

where the approximation error is given in Eq. (459).

We now combine with the classical post-processing in Eq. (468). Given a Pauli
observable $P\in\\{I,X,Y,Z\\}^{\otimes n}$. For each experiment, we can show
that we are measuring the two-qubit state $\rho^{(2\ell-1,2\ell),c}$ with an
observable

$O^{(2\ell-1,2\ell)}\equiv\sum_{x,y\in\\{0,1\\}}\bra{\beta(x,y)}P_{\ell}\otimes
P_{\ell}\ket{\beta(x,y)}M_{x}^{(2\ell-1,6,6)}\otimes M_{y}^{(2\ell,6,6)}.$
(476)

The observable $O^{(2\ell-1,2\ell)}$ differs from the ideal observable

$\sum_{x,y\in\\{0,1\\}}\bra{\beta(x,y)}P_{\ell}\otimes
P_{\ell}\ket{\beta(x,y)}(U_{2\ell-1}\lvert x\rangle\\!\langle x\rvert
U_{2\ell-1}^{-1})\otimes(U_{2\ell}\lvert y\rangle\\!\langle y\rvert
U_{2\ell}^{-1})$ (477)

by at most $\epsilon$ error in $\left\lVert\cdot\right\rVert_{\infty}$. Using
the triangle inequality, we have

$\left|\operatorname{tr}\left(O^{(2\ell-1,2\ell)}\rho^{(2\ell-1,2\ell),c}\right)-\sum_{x,y}\bra{\beta(x,y)}P_{\ell}\otimes
P_{\ell}\ket{\beta(x,y)}\bra{\beta(x,y)}(\sigma^{B}_{\ell}\otimes\sigma^{A}_{\ell})\ket{\beta(x,y)}\right|\leq
4\epsilon.$ (478)

Because the Bell basis simultaneously diagonalizes $\\{I\otimes I,X\otimes
X,Y\otimes Y,Z\otimes Z\\}$, we have

$\sum_{x,y}\bra{\beta(x,y)}P_{\ell}\otimes
P_{\ell}\ket{\beta(x,y)}\bra{\beta(x,y)}(\sigma^{B}_{\ell}\otimes\sigma^{A}_{\ell})\ket{\beta(x,y)}=\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell}).$
(479)

Recall that there exists a CPTP map ${{\mathcal{E}}}_{\ell}$ such that
$\rho^{(2\ell-1,2\ell),c}={{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})$.
Hence, we have

$\left|\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)-\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})\right|\leq
4\epsilon.$ (480)

Furthermore, when $P_{\ell}=I$, we have

$\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)=\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})=1.$
(481)

The two characterizations above will be crucial for the sample complexity
analysis.

####  L.5.c Sample complexity analysis

We use the probability distribution given in Appendix L.4.a to analyze the
expectation value of $\Xi$ in Eq. (468). Combining with Eq. (467), we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\Xi]=\sum_{\begin{subarray}{c}\sigma^{A}_{\ell}\in
S,\\\
\forall\ell=1,\ldots,n\end{subarray}}\sum_{\begin{subarray}{c}\sigma^{B}_{\ell}\in
S,\\\
\forall\ell=1,\ldots,n\end{subarray}}p(\sigma^{A}_{1},\ldots,\sigma^{A}_{n})p(\sigma^{B}_{1},\ldots,\sigma^{B}_{n})\prod_{\ell=1}^{n}\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right).$
(482)

We separate the analysis into two cases.

  * •

$\rho$ is the maximally mixed state: We only consider $\sigma^{A},\sigma^{B}$
that appear with nonzero probability. For all $\ell=1,\ldots,n$, we consider
whether $P_{\ell}$ is equal to $I$. If $P_{\ell}\neq I$, then we have
$\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})=0$,
hence

$|\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)|\leq
4\epsilon$ (483)

from Eq. (480). If $P_{\ell}=I$, from Eq. (481), we have

$\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)=1.$
(484)

Together, we have

$\left|\prod_{\ell=1}^{n}\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)\right|\leq(4\epsilon)^{\\#(P_{\ell}\neq
I)},$ (485)

where $\\#(P_{\ell}\neq I)$ is the number of $P_{\ell},\forall\ell=1,\ldots,n$
that is not equal to identity $I$. Therefore we conclude that

$|\operatorname*{{\mathbb{E}}}[\Xi]|\leq(4\epsilon)^{\\#(P_{\ell}\neq I)}.$
(486)

  * •

$\rho$ is a locally rotated $(I\pm 0.9P)/2^{n}$: There is a probability of
$0.19$ such that at least one of $\sigma^{A},\sigma^{B}$ is sampled according
to the distribution for the maximally mixed state. The same analysis as the
case for maximally mixed state shows that we have

$\left|\prod_{\ell=1}^{n}\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)\right|\leq(4\epsilon)^{\\#(P_{\ell}\neq
I)}.$ (487)

For a probability of $0.81$, we have both $\sigma^{A}$ and $\sigma^{B}$ are
sampled according to the probability distribution for $(I\pm P)/2^{n}$ defined
in Appendix L.4.a. We focus on $\sigma^{A}$ and $\sigma^{B}$ that occur with
non-zero probability. We consider all $\ell=1,\ldots,n$. We again separate
into two cases: $P_{\ell}\neq I$ and $P_{\ell}=I$.

    * –

If $P_{\ell}\neq I$, then we have
$\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})\in\\{1,-1\\}$.
If
$\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})=1$,
then

$\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)\geq
1-4\epsilon$ (488)

from Eq. (480). In contrast, if
$\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})=-1$,
then

$\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)\leq-1+4\epsilon.$
(489)

    * –

If $P_{\ell}=I$, from Eq. (481), we have

$\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)=1.$
(490)

Furthermore, the parity constraint in the probability distribution over
$\sigma^{A},\sigma^{B}$ given in Appendix L.4.a shows that

$\prod_{\ell=1}^{n}\operatorname{tr}(P_{\ell}\sigma^{A}_{\ell})\operatorname{tr}(P_{\ell}\sigma^{B}_{\ell})=1.$
(491)

Hence, we have

$\prod_{\ell=1}^{n}\operatorname{tr}\left(O^{(2\ell-1,2\ell)}{{\mathcal{E}}}_{\ell}(\sigma^{A}_{\ell}\otimes\sigma^{B}_{\ell})\right)\geq(1-4\epsilon)^{\\#(P_{\ell}\neq
I)}.$ (492)

Combining with Eq. (487), we can conclude that

$\operatorname*{{\mathbb{E}}}[\Xi]\geq 0.81(1-4\epsilon)^{\\#(P_{\ell}\neq
I)}-0.19(4\epsilon)^{\\#(P_{\ell}\neq I)}.$ (493)

Recall from Eq. (468), $\Xi$ is the average over $N_{\mathrm{Q}}/2$
independent random variables bounded between $[-1,1]$. Hence, by Hoeffding’s
inequality, we need

$N_{\mathrm{Q}}=\mathcal{O}(\log(1/\delta)/\tilde{\epsilon}^{2})$ (494)

to estimate $\operatorname*{{\mathbb{E}}}[\Xi]$ to $\tilde{\epsilon}$ error
with probability at least $1-\delta$. In order to distinguish between $\rho$
being the maximally mixed state or not, we need to estimate
$\operatorname*{{\mathbb{E}}}[\Xi]$ to an error of at most

$0.81(1-4\epsilon)^{\\#(P_{\ell}\neq I)}-0.19(4\epsilon)^{\\#(P_{\ell}\neq
I)}-(4\epsilon)^{\\#(P_{\ell}\neq I)}.$ (495)

For $\epsilon$ less than a constant and $n$ sufficiently large, the above
function is minimized at $\\#(P_{\ell}\neq I)=n$. In order to predict
accurately with a probability at least $0.99$, the sample complexity for the
noisy quantum-enhanced experiment is

$N_{\mathrm{Q}}=\mathcal{O}\left(\frac{1}{(1-4\epsilon)^{2n}}\right).$ (496)

This concludes the proof for the first part of Theorem L.3.

###  L.6 Lower bound for noiseless conventional experiments

We give a sample complexity lower bound for conventional experiments based on
adaptive POVM measurements. We do not assume the presence of any noise in
conventional experiments. The proof uses techniques proposed in
huang2021information ; huang2021quantum ; chen2021exponential . In particular,
the proof is closely related to one of the proofs in huang2021quantum  up to
minor changes. We present a concise proof here for completeness.

A learning algorithm using noiseless conventional experiments is a rooted
tree. At every node, we perform a POVM on $\rho$. Based on the POVM outcome,
we move to a child node of the node. Because a rank-$1$ POVM
$\\{w_{b}\lvert\psi_{b}\rangle\\!\langle\psi_{b}\rvert\\}_{b}$ is always at
least as powerful as general POVM huang2021information ; chen2021exponential ,
we will only consider rank-$1$ POVMs. After $N_{\mathcal{C}}$ experiments, we
arrive at a leaf node of the tree at depth $N_{\mathcal{C}}$. Depending on the
unknown physical state $\rho$, the probability distribution over the leaf
nodes will be different. We write the probability distribution as

$p_{\rho}(\ell)=\prod_{t=1}^{N_{\mathrm{C}}}w_{t}\bra{\psi_{t}}\rho\ket{\psi_{t}},\forall\ell:\mbox{leaf
nodes},$ (497)

where
$w_{1}\lvert\psi_{1}\rangle\\!\langle\psi_{1}\rvert,\ldots,w_{N_{\mathrm{C}}}\lvert\psi_{\mathrm{C}}\rangle\\!\langle\psi_{\mathrm{C}}\rvert$
are the POVM elements associated to the outcomes of the $N_{\mathrm{C}}$
measurements that ends up at the leaf node $\ell$.

After the experiments, we obtain a Pauli observable
$P\in\\{I,X,Y,Z\\}^{\otimes n}\setminus\\{I^{\otimes n}\\}$ and the assocaited
observable
$O=\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)P\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right).$
Suppose we can use the conventional experiments to classify between maximally
mixed state

$\rho_{\mathrm{mm}}=I/2^{n}$ (498)

and the alternative states

$\rho_{S,P}=\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)\left(\frac{I+S0.9P}{2^{n}}\right)\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right)$
(499)

under the knowledge of $P$ and $U_{i},\forall i$, where $S\in\\{\pm
1\\},P\in\\{I,X,Y,Z\\}^{\otimes n}\setminus\\{I^{\otimes n}\\}$. Then the
average total variation distance between the leaf node distribution of the
maximally mixed state and the alternative states $\rho_{s,P}$ must be greater
than a constant,

$\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\end{subarray}\setminus\\{I^{\otimes
n}\\}}\left[\,\frac{1}{2}\sum_{\ell:\mathrm{leaf}}\left|p_{\ell}(\rho_{\mathrm{mm}})-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}p_{\ell}\left(\rho_{S,P}\right)\right|\,\right]=\Omega(1).$ (500)

The expectation over $S\in\\{\pm 1\\}$ is in the inside because the knowledge
of $S$ is not revealed. On the other hand, the expectation over $P$ is on the
outside because the knowledge of $P$ is revealed.

We now upper bound the average total variation distance with
$N_{\mathcal{C}}$.

$\displaystyle\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\frac{1}{2}\sum_{\ell:\mathrm{leaf}}\left|p_{\ell}(\rho_{\mathrm{mm}})-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}p_{\ell}\left(\rho_{S,P}\right)\right|\,\right]$ (501)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\sum_{\ell:\mathrm{leaf}}\max\left(0,\,\,p_{\ell}(\rho_{\mathrm{mm}})-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}p_{\ell}\left(\rho_{S,P}\right)\right)\,\right]$ (502)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\sum_{\ell:\mathrm{leaf}}p_{\ell}(\rho_{\mathrm{mm}})\max\left(0,\,\,1-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}\frac{p_{\ell}\left(\rho_{S,P}\right)}{p_{\ell}(\rho_{\mathrm{mm}})}\right)\,\right].$
(503)

We lower bound the following term,

$\displaystyle\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}\frac{p_{\ell}\left(\rho_{S,P}\right)}{p_{\ell}(\rho_{\mathrm{mm}})}$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}\prod_{t=1}^{N_{\mathrm{C}}}\bra{\psi_{t}}\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}\right)\left(I+S0.9P\right)\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right)\ket{\psi_{t}}$
(504) $\displaystyle=\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}\prod_{t=1}^{N_{\mathrm{C}}}\left(1+0.9S\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}\right)$
(505)
$\displaystyle\geq\exp\left[\sum_{t=1}^{N_{\mathrm{C}}}\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}\log\left(1+0.9S\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}\right)\right]$
(506)
$\displaystyle=\exp\left[\frac{1}{2}\sum_{t=1}^{N_{\mathrm{C}}}\log\left(1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}\right)\right]$
(507)
$\displaystyle=\prod_{t=1}^{N_{\mathrm{C}}}\sqrt{1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}}.$
(508)

The second line is a definition of
$\ket{\tilde{\psi}_{t}}=\left(\bigotimes_{\ell=1}^{n}U_{2\ell-1}^{-1}\right)\ket{\psi_{t}}$.
The third line uses Jensen’s inequality. Hence, we can upper bound the average
total variation distance as

$\displaystyle\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\frac{1}{2}\sum_{\ell:\mathrm{leaf}}\left|p_{\ell}(\rho_{\mathrm{mm}})-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}p_{\ell}\left(\rho_{S,P}\right)\right|\,\right]$ (509)
$\displaystyle\leq\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\sum_{\ell:\mathrm{leaf}}p_{\ell}(\rho_{\mathrm{mm}})\max\left(0,\,\,1-\prod_{t=1}^{N_{\mathrm{C}}}\sqrt{1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}}\right)\,\right]$
(510)
$\displaystyle=\sum_{\ell:\mathrm{leaf}}p_{\ell}(\rho_{\mathrm{mm}})\left(1-\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\prod_{t=1}^{N_{\mathrm{C}}}\sqrt{1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}}\right).$
(511)

We can remove the $\max(0,\cdot)$ because
$1-\prod_{t=1}^{N_{\mathrm{C}}}\sqrt{1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}}\geq
0$. We bound the term,

$\displaystyle\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\prod_{t=1}^{N_{\mathrm{C}}}\sqrt{1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}}$
(512)
$\displaystyle\geq\exp\left[\frac{1}{2}\sum_{t=1}^{N_{\mathrm{C}}}\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\log\left(1-0.81\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}\right)\right]$
(513)
$\displaystyle\geq\exp\left[-1.215\sum_{t=1}^{N_{\mathrm{C}}}\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}\right]$
(514) $\displaystyle\geq
1-1.215\sum_{t=1}^{N_{\mathrm{C}}}\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}$ (515)
$\displaystyle=1-1.215\sum_{t=1}^{N_{\mathrm{C}}}\frac{1}{2^{n}+1}=1-\frac{1.215N_{\mathrm{C}}}{2^{n}+1}.$
(516)

The second line uses Jensen’s inequality. The third line uses
$\log(1-x)\geq-3x,\forall x\in[0,0.94]$. The fourth line uses $\exp(x)\geq
1+x,\forall x\in\mathbb{R}$. The last line uses

$\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes n}\\}\end{subarray}}P\otimes
P=\frac{2^{n}\mathrm{SWAP}-I\otimes I}{4^{n}-1},$ (517)

hence
$\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\bra{\tilde{\psi}_{t}}P\ket{\tilde{\psi}_{t}}^{2}=\frac{2^{n}-1}{4^{n}-1}=\frac{1}{2^{n}+1}$.
Combining with Eq. (500), we have

$\displaystyle\Omega(1)=$
$\displaystyle\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}P\in\\{I,X,Y,Z\\}^{\otimes
n}\setminus\\{I^{\otimes
n}\\}\end{subarray}}\left[\,\frac{1}{2}\sum_{\ell:\mathrm{leaf}}\left|p_{\ell}(\rho_{\mathrm{mm}})-\operatorname*{{\mathbb{E}}}_{S\in\\{\pm
1\\}}p_{\ell}\left(\rho_{S,P}\right)\right|\,\right]$ (518)
$\displaystyle\leq\sum_{\ell:\mathrm{leaf}}p_{\ell}(\rho_{\mathrm{mm}})\frac{1.215N_{\mathrm{C}}}{2^{n}+1}=\frac{1.215N_{\mathrm{C}}}{2^{n}+1}.$
(519)

Thus we arrive at the desired lower bound,

$N_{\mathrm{C}}=\Omega(2^{n}),$ (520)

which concludes the proof of Theorem L.3.

## References

  * (1) S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak.  Online learning of quantum states.  Advances in neural information processing systems, 31, 2018.
  * (2) D. Aharonov, J. Cotler, and X.-L. Qi.  Quantum algorithmic measurement.  Nature Communications, 13(1):1–9, 2022.
  * (3) A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar.  Sample-efficient learning of interacting quantum systems.  Nature Physics, 17:931–935, 2021.
  * (4) C. Bădescu and R. O’Donnell.  Improved quantum data analysis.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411, 2021.
  * (5) K. Banaszek, M. Cramer, and D. Gross.  Focus on quantum tomography.  New Journal of Physics, 15(12):125020, 2013.
  * (6) R. Blume-Kohout.  Optimal, reliable estimation of quantum states.  New Journal of Physics, 12(4):043034, 2010.
  * (7) R. Blume-Kohout, J. K. Gamble, E. Nielsen, K. Rudinger, J. Mizrahi, K. Fortier, and P. Maunz.  Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography.  Nature communications, 8(1):1–13, 2017.
  * (8) J. Bourgain and A. Gamburd.  A spectral gap theorem in SU$(d)$.  Journal of the European Mathematical Society, 14(5):1455–1511, 2012\.
  * (9) J. C. Bridgeman and C. T. Chubb.  Hand-waving and interpretive dance: an introductory course on tensor networks.  Journal of physics A: Mathematical and theoretical, 50(22):223001, 2017.
  * (10) R. Brieger, I. Roth, and M. Kliesch.  Compressive gate set tomography.  arXiv preprint arXiv:2112.05176, 2021.
  * (11) C. Brif, R. Chakrabarti, and H. Rabitz.  Control of quantum phenomena: past, present and future.  New Journal of Physics, 12(7):075008, 2010.
  * (12) S. Chen, J. Cotler, H.-Y. Huang, and J. Li.  Exponential separations between learning with and without quantum memory.  To appear in FOCS, 2021.
  * (13) S. Chen, J. Cotler, H.-Y. Huang, and J. Li.  A hierarchy for replica quantum advantage.  arXiv preprint arXiv:2111.05874, 2021.
  * (14) S. Chen, S. Zhou, A. Seif, and L. Jiang.  Quantum advantages for Pauli channel estimation.  arXiv preprint arXiv:2108.08488, 2021.
  * (15) C. Dankert, R. Cleve, J. Emerson, and E. Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1), Jul 2009.
  * (16) G. M. D’Ariano, M. G. Paris, and M. F. Sacchi.  Quantum tomography.  Advances in Imaging and Electron Physics, 128:206–309, 2003.
  * (17) C. M. Dawson and M. A. Nielsen.  The Solovay-Kitaev algorithm.  arXiv preprint quant-ph/0505030, 2005.
  * (18) J. Emerson, R. Alicki, and K. Życzkowski.  Scalable noise estimation with random unitary operators.  Journal of Optics B: Quantum and Semiclassical Optics, 7(10):S347–S352, sep 2005.
  * (19) S. Endo, S. C. Benjamin, and Y. Li.  Practical quantum error mitigation for near-future applications.  Physical Review X, 8(3):031027, 2018.
  * (20) Erik, L. Saldyt, Rob, tjproct, J. Gross, sserita, kmrudin, T. L. Scholten, colibri coruscans, kevincyoung, msarovar, coreyostrove, jordanh6, D. Nadlinger, L. N. Maurer, pyIonControl, and R. Blume-Kohout.  pygstio/pygsti: Version 0.9.10.  Zenodo, Oct. 2021.
  * (21) S. T. Flammia.  Averaged circuit eigenvalue sampling.  arXiv preprint arXiv:2108.05803, 2021.
  * (22) S. T. Flammia and R. O’Donnell.  Pauli error estimation via population recovery.  arXiv:2105.02885, 2021.
  * (23) S. T. Flammia and J. J. Wallman.  Efficient estimation of Pauli channels.  ACM Transactions on Quantum Computing, 1(1):1–32, 2020.
  * (24) I. Goodfellow, Y. Bengio, and A. Courville.  Deep Learning.  The MIT Press, 2016.
  * (25) D. Greenbaum.  Introduction to quantum gate set tomography.  arXiv preprint arXiv:1509.02921, 2015.
  * (26) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert.  Quantum state tomography via compressed sensing.  Physical review letters, 105(15):150401, 2010.
  * (27) M. Guţă, J. Kahn, R. Kueng, and J. A. Tropp.  Fast state tomography with optimal error bounds.  Journal of Physics A: Mathematical and Theoretical, 53(20):204001, 2020.
  * (28) J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu.  Sample-optimal tomography of quantum states.  IEEE Trans. Inf. Theory, 63(9):5628–5641, 2017.
  * (29) J. Haah, R. Kothari, and E. Tang.  Optimal learning of quantum Hamiltonians from high-temperature Gibbs states.  arXiv:2108.04842, 2021.
  * (30) R. Harper, S. T. Flammia, and J. J. Wallman.  Efficient learning of quantum noise.  Nature Physics, 16(12):1184–1188, 2020.
  * (31) A. W. Harrow, B. Recht, and I. L. Chuang.  Efficient discrete approximations of quantum gates.  Journal of Mathematical Physics, 43(9):4445–4451, 2002.
  * (32) J. Helsen, M. Ioannou, I. Roth, J. Kitzinger, E. Onorati, A. H. Werner, and J. Eisert.  Estimating gate-set properties from random sequences.  arXiv preprint arXiv:2110.13178, 2021.
  * (33) Z. Hradil.  Quantum-state estimation.  Physical Review A, 55(3):R1561, 1997.
  * (34) H.-Y. Huang.  Learning quantum states from their classical shadows.  Nature Reviews Physics, pages 1–1, 2022.
  * (35) H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, et al.  Quantum advantage in learning from experiments.  arXiv preprint arXiv:2112.00778, 2021.
  * (36) H.-Y. Huang, R. Kueng, and J. Preskill.  Predicting many properties of a quantum system from very few measurements.  Nat. Phys., 16:1050––1057, 2020.
  * (37) H.-Y. Huang, R. Kueng, and J. Preskill.  Information-theoretic bounds on quantum advantage in machine learning.  Phys. Rev. Lett., 126:190505, 2021.
  * (38) H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill.  Provably efficient machine learning for quantum many-body problems.  arXiv preprint arXiv:2106.12627, 2021.
  * (39) A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta.  Error mitigation extends the computational reach of a noisy quantum processor.  Nature, 567(7749):491–495, 2019.
  * (40) M. J. Kearns and U. V. Vazirani.  An introduction to computational learning theory.  MIT press, 1994.
  * (41) S. Kimmel, M. P. da Silva, C. A. Ryan, B. R. Johnson, and T. Ohki.  Robust extraction of tomographic information via randomized benchmarking.  Physical Review X, 4(1):011050, 2014.
  * (42) E. Knill.  Quantum computing with realistically noisy devices.  Nature, 434(7029):39–44, mar 2005.
  * (43) E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland.  Randomized benchmarking of quantum gates.  Physical Review A, 77(1):012307, 2008.
  * (44) E. Magesan, J. M. Gambetta, and J. Emerson.  Scalable and robust randomized benchmarking of quantum processes.  Physical review letters, 106(18):180504, 2011.
  * (45) E. Magesan, J. M. Gambetta, B. R. Johnson, C. A. Ryan, J. M. Chow, S. T. Merkel, M. P. Da Silva, G. A. Keefe, M. B. Rothwell, T. A. Ohki, et al.  Efficient measurement of quantum gate error by interleaved randomized benchmarking.  Physical review letters, 109(8):080505, 2012.
  * (46) S. T. Merkel, E. J. Pritchett, and B. H. Fong.  Randomized benchmarking as convolution: Fourier analysis of gate dependent errors.  Quantum, 5:581, nov 2021.
  * (47) M. Mohri, A. Rostamizadeh, and A. Talwalkar.  Foundations of machine learning.  The MIT Press, 2018.
  * (48) M. Mohseni, A. T. Rezakhani, and D. A. Lidar.  Quantum-process tomography: Resource analysis of different strategies.  Physical Review A, 77(3):032322, 2008.
  * (49) E. Nielsen, J. K. Gamble, K. Rudinger, T. Scholten, K. Young, and R. Blume-Kohout.  Gate set tomography.  arXiv preprint arXiv:2009.07301, 2020.
  * (50) R. O’Donnell and J. Wright.  Efficient quantum tomography.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899–912, 2016.
  * (51) R. O’Donnell and J. Wright.  Efficient quantum tomography ii.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 962–974, 2017.
  * (52) T. Proctor, K. Rudinger, K. Young, M. Sarovar, and R. Blume-Kohout.  What randomized benchmarking actually measures.  Physical review letters, 119(13):130502, 2017.
  * (53) Y. Quek, S. Arunachalam, and J. Smolin.  Private learning implies quantum stability.  Advances in Neural Information Processing Systems, 34, 2021.
  * (54) I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, and M. Kliesch.  Recovering quantum gates from few average gate fidelities.  Physical review letters, 121(17):170502, 2018.
  * (55) M. F. Sacchi.  Optimal discrimination of quantum operations.  Physical Review A, 71(6):062340, 2005.
  * (56) P. Selinger.  Efficient Clifford+T approximation of single-qubit operators.  arXiv preprint arXiv:1212.6253, 2012.
  * (57) A. Strikis, D. Qin, Y. Chen, S. C. Benjamin, and Y. Li.  Learning-based quantum error mitigation.  PRX Quantum, 2(4):040330, 2021.
  * (58) T. Surawy-Stepney, J. Kahn, R. Kueng, and M. Guta.  Projected least-squares quantum process tomography.  arXiv preprint arXiv:2107.01060, 2021.
  * (59) K. Temme, S. Bravyi, and J. M. Gambetta.  Error mitigation for short-depth quantum circuits.  Physical review letters, 119(18):180509, 2017.
  * (60) P. Varjú.  Random walks in compact groups.  Doc. Math., 18:1137–1175, 2013.
  * (61) L. Viola and E. Knill.  Random decoupling schemes for quantum dynamical control and error suppression.  Phys. Rev. Lett., 94:060502, Feb 2005.
  * (62) J. Wallman.  Randomized benchmarking with gate-dependent noise.  Quantum, 2:47, 2018.
  * (63) J. J. Wallman and J. Emerson.  Noise tailoring for scalable quantum computation via randomized compiling.  Physical Review A, 94(5):052325, 2016.
  * (64) Z. Webb.  The Clifford group forms a unitary 3-design.  arXiv preprint arXiv:1510.02769, 2015.
  * (65) E. Wigner.  Gruppentheorie und ihre anwendung auf die quantenmechanik der atomspektren.  1931\.
  * (66) H. M. Wiseman and G. J. Milburn.  Quantum measurement and control.  Cambridge university press, 2009.
  * (67) T. H. Yang, T. Vértesi, J.-D. Bancal, V. Scarani, and M. Navascués.  Robust and versatile black-box certification of quantum devices.  Physical review letters, 113(4):040401, 2014.
  * (68) H. Zhu, R. Kueng, M. Grassl, and D. Gross.  The Clifford group fails gracefully to be a unitary 4-design.  arXiv preprint arXiv:1609.08172, 2016.