# Learning Properties of Quantum States
Without the I.I.D. Assumption

Omar Fawzi  Univ Lyon, Inria, ENS Lyon, UCBL, LIP, Lyon, France  Richard Kueng
Institute for Integrated Circuits, Johannes Kepler University Linz,
Altenberger Straße 69, Austria  Damian Markham  Sorbonne Université, CNRS,
LIP6, F-75005 Paris, France  Aadil Oufkir  Univ Lyon, Inria, ENS Lyon, UCBL,
LIP, Lyon, France  Institute for Quantum Information, RWTH Aachen University,
Aachen, Germany.

###### Abstract

We develop a framework for learning properties of quantum states beyond the
assumption of independent and identically distributed (i.i.d.) input states.
We prove that, given any learning problem (under reasonable assumptions), an
algorithm designed for i.i.d. input states can be adapted to handle input
states of any nature, albeit at the expense of a polynomial increase in copy
complexity. Furthermore, we establish that algorithms which perform non-
adaptive incoherent measurements can be extended to encompass non-i.i.d. input
states while maintaining comparable error probabilities. This allows us, among
others applications, to generalize the classical shadows of Huang, Kueng, and
Preskill to the non-i.i.d. setting at the cost of a small loss in efficiency.
Additionally, we can efficiently verify any pure state using Clifford
measurements, in a way that is independent of the ideal state. Our main
techniques are based on de Finetti-style theorems supported by tools from
information theory. In particular, we prove a new randomized local de Finetti
theorem that can be of independent interest.

##  1 Introduction

The advent of quantum technologies has led to a notable amount of tools for
quantum state and process learning. These are employed as tools within use
cases, but also to test applications and devices themselves. However, almost
all existing methods require the assumption that the devices or states being
tested are prepared in the same way over time—following an identical and
independent distribution (i.i.d.) [15, 16, 26, 27, 31, 33, 46, 44, 51, 58]. In
various situations, this assumption should not be taken for granted. For
instance, in time correlated noise, states and devices change in time in a
non-trivial way [14, 18, 19]. Moreover, in settings where we cannot trust the
devices or states - for example, originating from an untrusted, possibly
malicious manufacturer, or states are distributed over untrusted channels -
the assumption of i.i.d. state preparations can be exploited by malicious
parties to mimic good behaviour whilst corrupting the intended application.
Avoiding this assumption is crucial for various applications such as verified
quantum computation [36] or tasks using entangled states in networks [49],
such as authentication of quantum communication [6], anonymous communication
[9] or distributed quantum sensing [66]. At the core of these applications are
some verification procedures used to ensure trust, however they are all
catering for particular states or processes, with independent proofs and with
differing efficiencies.

The main contribution of this paper is to develop a framework to _extend
existing i.i.d. learning algorithms into a fully general (non-i.i.d.) setting
while preserving rigorous performance guarantees._ See Theorem 1.1 and Theorem
1.3 for the type of (informal) results we provide. The main technical
ingredient is a _new variant of the quantum de Finetti theorem_ for randomized
permutation invariant measurements. As a concrete example, we apply our
findings to the task of feature prediction with randomized measurements (‘
_classical shadows_ ’) [46, 39, 71]. We then apply these results to the
problem of state verification, allowing us to find the first explicit protocol
for verifying an arbitrary multiparty state, showing the power of these
techniques.

Figure 1:  _Illustration of general state learning algorithms:_ A learning
algorithm consumes $N-1$ copies of $\rho$ to construct a prediction $p$.
Success occurs if $p$ is (approximately) compatible with the remaining post-
measurement test copy.

###  1.1 Evaluating a learning algorithm

The first difficulty we face is to define what it means for a learning
algorithm to achieve some learning task on a non-i.i.d. state. In the i.i.d.
setting, a learning algorithm requests $N$ copies of an unknown quantum state
and is provided with the quantum state $\rho=\sigma^{\otimes
N}\in\left(\mathbb{C}^{d\times d}\right)^{\otimes N}$. Subsequently, the
learning algorithm makes predictions about a property of the quantum state
$\sigma$. This algorithm is evaluated by contrasting its predictions with the
actual property of the quantum state $\sigma$. In scenarios where the i.i.d.
assumption does not hold, the learning algorithm is presented with a quantum
state $\rho\in\left(\mathbb{C}^{d\times d}\right)^{\otimes N}$, which may be
non-i.i.d. and can even feature entanglement across different tensor factors.
In such cases, determining how to evaluate the algorithm becomes less
straightforward due to the absence of a fixed target or ideal state for
comparison. For this, we use the common idea in machine learning of separating
the data set (here the $N$ systems that will be denoted $A_{1},\dots,A_{N}$)
into a _training set_ used for estimation and a _test set_ used for
evaluation. We refer to Figure 1 for a visual illustration. This idea was
previously used in [16] in the context of quantum tomography.

The choice of which systems to train and test is random, which is equivalent
to assuming the systems $A_{1},\dots,A_{N}$ are randomly permuted and we fix
the training set to be $A_{1},\dots,A_{N-1}$ and the test set to be $A_{N}$.
The learning algorithm $\mathcal{B}$ is applied to the training set
$A_{1}\dots A_{N-1}$ and makes a prediction that we denote $p$ and we test
this prediction against the system $A_{N}$. The learning task will be
described by a family of sets $\textup{SUCCESS}_{\varepsilon}$ where
$\varepsilon$ should be seen as a precision parameter. The pair
$(p,\sigma)\in\textup{SUCCESS}_{\varepsilon}$ if prediction $p$ is correct for
the state $\sigma$ with precision $\varepsilon$. As an example, for the shadow
tomography problem with observables $O_{1},\dots,O_{M}$, we would have
$\bm{p}=(p_{1},\dots,p_{M})\in[0,1]^{M}$ and

$\textup{SUCCESS}_{\varepsilon}=\\{((p_{1},\dots,p_{M}),\sigma):\forall
i\in[M],|p_{i}-\mathrm{Tr}\left[O_{i}\sigma\right]|\leq\varepsilon\\}.$

We evaluate a learning algorithm $\mathcal{B}$ for the task described by
$\textup{SUCCESS}_{\varepsilon}$ on the input state $\rho^{A_{1}\dots A_{N}}$
as follows. The algorithm $\mathcal{B}$ takes as input the systems $A_{1}\dots
A_{N-1}$ and outputs a prediction, i.e., $p\in\mathcal{P}$. In other words,
$p$ follows the distribution $\mathcal{B}(\rho^{A_{1}\dots A_{N-1}})$, which
we write: $p\sim\mathcal{B}(\rho^{A_{1}\dots A_{N-1}})$. For an outcome $p$,
we write $\rho_{p}^{A_{N}}$ for the reduced state of $A_{N}$ of the state
$(\mathcal{B}\otimes\mathrm{id})(\rho^{A_{1}\dots A_{N}})$ conditioned on the
outcome of $\mathcal{B}$ being $p$. We let

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)=\mathbb{P}_{p\sim\mathcal{B}(\rho)}\left[\left(p,\rho_{p}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right].$
(1)

We make a few remarks about this definition. First, in the i.i.d. setting we
have that $\rho^{A_{N}}_{p}=\sigma$ for any $p\in\mathcal{P}$ and we recover
the usual definition of error probability. Second, note that it is essential
to consider the state of $A_{N}$ conditioned on the outcome $p$. One might be
tempted to replace $\rho^{A_{N}}_{p}$ with the marginal $\rho^{A_{N}}$ but
this would be both unachievable and undesirable. In fact, consider the simple
example $\rho=\frac{1}{2}(|0\rangle\\!\langle 0|^{\otimes
N}+|1\rangle\\!\langle 1|^{\otimes N})$ and we would like to estimate the
value of the observable $O=|1\rangle\\!\langle 1|$. Note that
$\mathbb{P}_{p\sim\mathcal{B}(\rho)}\left[\cdot\right]=\frac{1}{2}\mathbb{P}_{p\sim\mathcal{B}(|0\rangle\\!\langle
0|^{\otimes
N})}\left[\cdot\right]+\frac{1}{2}\mathbb{P}_{p\sim\mathcal{B}(|1\rangle\\!\langle
1|^{\otimes N})}\left[\cdot\right]$. As such, with the naive definition using
the marginal $\rho^{A_{N}}$ which is $\mathbb{I}/2$ in this case, the error
probability would be given by
$\frac{1}{2}\mathbb{P}_{p\sim\mathcal{B}(|0\rangle\\!\langle 0|^{\otimes
N})}\left[|\frac{1}{2}-p|>\varepsilon\right]+\frac{1}{2}\mathbb{P}_{p\sim\mathcal{B}(|1\rangle\\!\langle
1|^{\otimes N})}\left[|\frac{1}{2}-p|>\varepsilon\right]$. Clearly any good
learning algorithm should work for the i.i.d. states $|0\rangle\\!\langle
0|^{\otimes N}$, $|1\rangle\\!\langle 1|^{\otimes N}$ and this implies that
the error probability $\delta_{\mathcal{B}}(N,\rho,\varepsilon)$ is close to
$1$ for this choice of $\rho$. For this example, it is desirable that the
learning algorithm detects which of the two states $|0\rangle\\!\langle
0|^{\otimes N}$ or $|1\rangle\\!\langle 1|^{\otimes N}$ we have and this is
captured by the definition (1).

In order to be able to prove our results, we generalize the definition of a
learning algorithm by allowing it to output a classical register $c$ which can
be seen as calibration information. This register has an effect on the
definition of error probability, which becomes:

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)=\mathbb{P}_{\rho}\left[\left(p,\rho_{c,p}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right].$

|  |
---|---|---
Figure 2:  _Illustration for adapting a learning $\mathcal{A}$ designed for
i.i.d. inputs to general inputs:_ _(Left)_ Illustration of the learning
algorithm $\mathcal{B}$ used in Theorem 1.1 _(Right)_ Illustration of the
learning algorithm $\mathcal{B}$ used in Theorem 1.3. Note that in this case
$\mathcal{A}$ is a non-adaptive incoherent algorithm and $\mathcal{M}_{r}$
corresponds to the measurements applied by this algorithm.

###  1.2 Adapting a learning algorithm designed for i.i.d. inputs

Our first result transforms any learning algorithm $\mathcal{A}$ for the task
$\textup{SUCCESS}_{\varepsilon}$ to a learning algorithm $\mathcal{B}$ for the
same task without requiring the i.i.d. assumption at the cost of an increased
number of queries.

######  Theorem 1.1 (Informal).

Let $\varepsilon>0$ and $1\leq k<N/2$. Let $\mathcal{A}$ be a learning
algorithm designed for i.i.d. input states. There exists a learning algorithm
$\mathcal{B}$ taking arbitrary inputs on $N$ system and having an error
probability satisfying

$\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},2\varepsilon\right)\leq\sup_{\sigma\;:\;\rm{state}}\delta_{\mathcal{A}}\left(k,\sigma^{\otimes
k},\varepsilon\right)+\mathcal{O}\left(\sqrt{\frac{k^{3}d^{2}\log(d)}{N\varepsilon^{2}}}\right).$

Note that the evaluation of a learning algorithm is defined by first randomly
permuting the systems $A_{1}\dots A_{N}$ so we may assume that
$\rho^{A_{1}\dots A_{N}}$ is invariant under permutations. The first term in
the bound of Theorem 1.1 is the worst case error probability in the i.i.d.
setting. So, we can regard the parameter $k$ as the copy complexity within the
i.i.d. setting. Hence, in order to attain a low total error probability in the
non-i.i.d. setting, it is sufficient to take a total number of copies
$N=\Omega\left(k^{3}d^{2}\log(d)\right)$. This result shows in principle that
any learning algorithm designed for i.i.d. states can be transformed into one
for general states at an additional cost that is polynomial in the dimension
$d$.

The algorithm $\mathcal{B}$, illustrated in Figure 2 (Left), partitions the
training data into 3 parts. For that we choose a random number
($l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}$). The first part has
size $l-k$ and each system is measured using some fixed measurement
$\mathcal{M}_{\text{dist}}$ leading to an output string $\bm{w}$. The second
part is of size $k$ and we apply the learning algorithm $\mathcal{A}$ and
return this prediction. The third part consists of $N-l-1$ systems that are
not used by the learning algorithm.

To control the error probability of Algorithm $\mathcal{B}$, we use the de
Finetti theorem of [52, proof of Theorem 2.4] to obtain the approximation for
all $1\leq k<N/2$:

$\displaystyle\mathbb{E}_{l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\},\;\bm{w}\sim\mathcal{M}_{\text{dist}}^{\otimes(l-k)}\left(\rho^{A_{k+1}\cdots
A_{l}}\right)}\left[\left\|\rho_{\bm{w}}^{A_{1}\cdots
A_{k}}-\left(\rho_{\bm{w}}^{A_{1}}\right)^{\otimes k}\right\|_{1}\right]\leq
2\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}},$ (gF)

where $\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$ is the state conditioned on
observing the outcome $\bm{w}$ after measuring the quantum state
$\rho^{A_{k+1}\cdots A_{l}}$ with a fixed measurement device
$\mathcal{M}_{\text{dist}}^{\otimes(l-k)}$ (which should an informationally-
completely measurement satisfying a low-distortion property) and
$\rho_{\bm{w}}^{A_{1}}$ denotes the reduced quantum state derived by tracing
out the systems $A_{t}$ for $t>1$ from the quantum state
$\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$. Crucially, here the approximation of the
state $\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$ by the i.i.d. state
$\left(\rho_{\bm{w}}^{A_{1}}\right)^{\otimes k}$ is conducted using the one-
norm. This implies that any algorithm utilizing arbitrary measurement
strategies that necessitate i.i.d. input states can be generalized to the
non-i.i.d. setting at the cost of a new error probability bounded as in
Theorem 1.1. Unfortunately, for some tasks, the additional cost in Theorem 1.1
is prohibitive. For example, for classical shadows, we expect that the
dependence on the dimension $d$ be at most logarithmic.

An example of [10] shows that the dependency in the dimension can not be
lifted for a general de Finetti theorem with the one-norm approximation. On
the other hand, [17] reduced the dependency in the dimension for the LOCC
norm. Specifically, it is shown in [17] that for a permutation invariant state
$\rho^{A_{1}\cdots A_{N}}$ and $1\leq k<N$, there exists a probability measure
denoted as $\nu$, such that the following inequality holds:

$\displaystyle\sup_{\Lambda_{2},\dots,\Lambda_{k}}\left\|\mathrm{id}\otimes\Lambda_{2}\otimes\cdots\otimes\Lambda_{k}\left(\rho^{A_{1}\cdots
A_{k}}\right)-\int\mathop{}\\!\mathrm{d}\nu(\sigma)\sigma^{\otimes
k}\right\|_{1}\leq\sqrt{\frac{2k^{2}\log(d)}{N-k}},$ (lF)

where the maximization is over measurements channels111A measurement channel
corresponding to a measurement device
$\mathcal{M}=\\{M_{x}\\}_{x\in\mathcal{X}}$ is the quantum channel
$\Lambda(\rho)=\sum_{x\in\mathcal{X}}\mathrm{Tr}\left[M_{x}\rho\right]|x\rangle\\!\langle
x|$ where $\\{|x\rangle\\}_{x\in\mathcal{X}}$ is an orthonormal basis..
Initially, this might appear adequate for relaxing the assumption of i.i.d.
state preparations with a low overhead. However, the process of extending
algorithms from i.i.d. inputs to a mixture of i.i.d. states (not to mention
permutation-invariant states) is far from straightforward, particularly when
dealing with statements that require a correctness with high probability. To
address this difficulty, we use the same techniques from [17] and show a new
‘randomized’ local quantum de Finetti theorem.

######  Theorem 1.2 (Informal).

Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation invariant quantum state,
$\\{\Lambda_{r}\\}_{r\in\mathcal{R}}$ be a set of measurement channels and $q$
be a probability measure on $\mathcal{R}$. For all $1\leq k<N/2$, the
following inequality holds:

$\mathbb{E}_{(r_{1},\dots,r_{N})\sim q^{\otimes
N},l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}}\mathbb{E}_{\bm{w}}\left[\left\|\mathrm{id}\otimes\Lambda_{r_{2}}\otimes\dots\otimes\Lambda_{r_{k}}\left(\rho_{\bm{w}}^{A_{1}\cdots
A_{k}}-\left(\rho_{\bm{w}}^{A_{1}}\right)^{\otimes{k}}\right)\right\|_{1}\right]\leq\sqrt{\frac{4{k^{2}}\log(d)}{N}},$

where $\bm{w}$ is obtained by applying the channel
$\Lambda_{r_{k+1}}\otimes\cdots\otimes\Lambda_{r_{l}}$ to the systems
$A_{k+1}\cdots A_{l}$ of $\rho$.

Observe that our de Finetti theorem is weaker than the local de Finetti
theorem (lF)[17] in that the distribution of the measurement channels should
be permutation invariant (as opposed to arbitrary). However, our de Finetti
theorem is stronger than the local de Finetti theorem (lF) in that it
approximates the projection of the permutation invariant state to _exactly
i.i.d. states_ (instead of mixtures of i.i.d. states).
It is worth noting that the approximation error in Theorem 1.2 is
significantly smaller than the previous approximation error (gF). Notably, the
dependence on the local dimension $d$ is logarithmic, which implies that the
total number of copies $N$ only needs to scale as $\Omega(k^{2}\log(d))$, as
opposed to the more demanding $\Omega(k^{3}d^{2}\log(d))$. However, the
approximation of the state $\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$ by the i.i.d.
state $\left(\rho_{\bm{w}}^{A_{1}}\right)^{\otimes k}$ in the general one-norm
is no longer guaranteed. This assertion now holds only when applying
independent local measurement channels drawn from
$\\{\Lambda_{r}\\}_{r\in\mathcal{R}}$ according to the distribution $q$ on the
quantum state $\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$. For learning algorithms
that are non-adaptive and incoherent, this is enough to bound their error
probability and leads to the following theorem.

######  Theorem 1.3 (Informal).

Let $\varepsilon>0$ and $1\leq k<N/2$. Let $\mathcal{A}$ be a learning
algorithm designed for i.i.d. input states and performing non-adaptive
incoherent measurements. There is an algorithm $\mathcal{B}$ that takes as
input an arbitrary state on $N$ systems and possessing an error probability:

$\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},2\varepsilon\right)\leq\sup_{\sigma\;:\;\rm{state}}\delta_{\mathcal{A}}\left(k,\sigma^{\otimes
k},\varepsilon\right)+\mathcal{O}\left(\sqrt{\frac{k^{2}\log^{2}(N)\log(d)}{N\varepsilon^{2}}}\right).$

In terms of copy complexity, to ensure an error probability $\delta$, the
number of copies in the non-i.i.d. setting should be $N_{\rm{non-
iid}}=\Omega\left(\frac{\log(d)}{\delta^{2}\varepsilon^{2}}\cdot
k_{\,\rm{iid}}(\varepsilon,\delta)^{2}\log^{2}(k_{\,\rm{iid}}/\delta)\right)$
where $k_{\,\rm{iid}}(\varepsilon,\delta)$ is a sufficient number of copies
needed to achieve $\delta/2$ correctness in the i.i.d. setting with a
precision parameter $\varepsilon/2$.

The algorithm $\mathcal{B}$ is illustrated in Figure 2 (Right). Note that as
$\mathcal{A}$ is assumed to be incoherent and non-adaptive, it is described by
some measurements $\\{\mathcal{M}_{r}\\}_{r\in\mathcal{R}}$. The algorithm
$\mathcal{B}$ partitions the training data into 3 parts. We choose a random
number ($l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}$). The first
part has size $l-k$ and each system is measured using some measurement
$\mathcal{M}_{r}$, where $r$ is chosen at random. This step gives an output
string that we denote $\bm{w}$. The second part is of size $k$ and we apply
the learning algorithm $\mathcal{A}$ and return this prediction. The third
part consists of $N-l-1$ systems that are not used by the learning algorithm.
Besides this, Algorithm $\mathcal{B}$ returns also the outcomes $\bm{w}$ as
calibration data.

Many problems of learning properties of quantum states can be solved using
algorithms that perform non-adaptive incoherent measurements - that is,
measurements which are local on copies and chosen non-adaptively (see
Definition 2.5 for a formal definition). This includes state tomography [45],
shadow tomography using classical shadows [46], testing mixedness [43],
fidelity estimation [15], verification of pure states [31] among others. For
all these problems, we can apply Theorem 1.3 to extend these algorithms so
that they can operate even for non-i.i.d. input states (see Section 5). Here,
we present this extension for the classical shadows algorithms:

######  Corollary 1.4 (Informal).

Let $k\in[n]$ and $\\{O_{i}\\}_{i\in[M]}$ be $M$ (resp. $k$-local) observables
on an $n$-qubit system. There is an algorithm using Clifford (resp. Pauli)
measurements in the non-i.i.d. setting for predicting the expected values of
the observables $\\{O_{i}\\}_{i\in[M]}$ under the reduced test state to within
an additive error $\varepsilon$ with a probability at least $2/3$ and having a
copy complexity:

$\displaystyle N$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{n^{3}\max_{i\in[M]}\|O_{i}\|_{2}^{4}\log^{2}(3M)}{\varepsilon^{6}}\right)$
$\displaystyle\text{(Clifford)},$ $\displaystyle N$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{nk^{2}16^{k}\max_{i\in[M]}\|O_{i}\|^{4}_{\infty}\log^{2}(3M)}{\varepsilon^{6}}\right)$
$\displaystyle\text{(Pauli)},$

where $\tilde{\mathcal{O}}$ hides $\log\log(M)$ and $\log(1/\varepsilon)$
factors.

Notably, taking classical shadows techniques allows us to perform verification
in the non-i.i.d. setting [42] without even revealing or making assumptions on
the verified pure target state.

###  1.3 Application: verification of pure states

As an application of Theorem 1.3 and Corollary 1.4, we can show that _any_
$n$-qubit pure state can be verified with either
$\tilde{\mathcal{O}}\left(\frac{n}{\varepsilon^{6}}\right)$ Clifford
measurements (see Proposition 5.5) or
$\tilde{\mathcal{O}}\left(\frac{n^{3}16^{n}}{\varepsilon^{6}}\right)$ Pauli
measurements (see Proposition 5.6). In words, a verification algorithm should
accept only when the test set (post-measurement state) is $\varepsilon$-close
to the ideal state in fidelity. Our proposed algorithm offers two significant
advantages: (a) it does not rely on the assumption of i.i.d. state
preparations, and (b) it does not demand prior knowledge of the target pure
state during the data acquisition phase (that is, the measurements in the
algorithm are independent of the state we wish to verify).

Obtaining a statement beyond the i.i.d. assumption is particularly important
for cryptographic applications, verification of computation and network
settings. Notably, existing verification protocols in the non-i.i.d. setting
are _state-dependent_ , such as stabiliser states [21, 49, 40], weighted graph
states, hypergraph states [28], and Dicke states [37]. In contrast, our
protocol is _independent_ of the state to be verified. This not only adds to
its simplicity but also offers potential advantages in concealing information
from the measurement devices regarding the purpose of the test. This
‘blindness’ is a crucial aspect of many protocols for the verification of
computation [36], making this feature valuable in such contexts. Moreover, in
both network and computational settings, having a universal protocol
simplifies the management of verification steps in broader scenarios where
different states may be used for various applications.

The application of our results provides the first explicit protocol for
verifying _any_ multiparty quantum state, accompanied by clear efficiency
statements. However, this generality comes with certain costs in efficiency:
for local Pauli measurements, the scaling is exponential in the number of
qubits, and while the scaling for Clifford measurements is close to optimal,
they are non-local across copies. In addition, the scaling in the error
parameters is not optimal. Nevertheless, we see our results as a first proof-
of-principle showing that beyond i.i.d. learning is feasible in many settings
with performance guarantees that are comparable to the i.i.d. guarantees. We
expect that further work will improve the bounds we obtain both for the
general statements as well as using specificities of classes of learning
tasks. In addition, we believe that this work will contribute to the transfer
of techniques between the areas of learning theory and quantum verification.

###  1.4 Related work

#### De Finetti-style theorems.

The foundational de Finetti theorem, initially introduced by de Finetti [1],
states that exchangeable Bernoulli random variables behaves as a mixture of
i.i.d. Bernoulli random variables. Subsequently, this statement was quantified
and generalized to finite sample sizes and arbitrary alphabets by [3, 4]. This
theorem was further extended to quantum states. Initially, [2, 7] established
asymptotic generalizations, while [8, 10] presented finite approximations in
terms of one-norm. Later works improved these approximations for weaker norms:
[13, 17] achieved exponential improvements in the dimension dependence using
the one-way LOCC norm, initially for $k=2$ by [13], and subsequently for
general $k$ by [17]. In the mentioned works, the permutation-invariant state
was approximated by a mixture of i.i.d. states. [52] introduced an
approximation to i.i.d. states in terms of the one-norm. In this work, we
improve the dimension dependence of this approximation, employing a randomized
LOCC norm instead of the one-norm. Lastly, it is worth noting that
information-theoretic proofs for classical finite de Finetti theorems were
provided by [54, 61, 70].

#### State tomography.

In the i.i.d. setting, the copy complexity of the state tomography problem is
well-established: $\Theta(d^{2}/\varepsilon^{2})$ with coherent measurements
[26, 23], and $\Theta(d^{3}/\varepsilon^{2})$ with incoherent measurements
[27, 59], where $\varepsilon$ denotes the precision parameter. In the
non-i.i.d. setting, [16] introduced a formulation for the state tomography
problem and presented a result using confidence regions. This result pertains
to the asymptotic regime, specifically when the state can be represented as a
mixture of i.i.d. states. In this article, we build upon the formulation of
[16], and we discern between algorithms that return calibration information
and those that do not. Furthermore, we introduce a state tomography algorithm
with a finite copy complexity (in the non asymptotic regime). Finally, [12]
have also proposed non-i.i.d. tomography algorithms tailored for matrix
product states.

#### Shadow tomography.

The problem of shadow tomography is known to be solvable with a complexity
that grows poly-logarithmically with respect to both the dimension and the
number of observables, provided (almost) all i.i.d. copies can be coherently
measured [30, 33, 51]. However, if we seek to extend this result to the
non-i.i.d. setting using our framework, the copy complexity would be
polynomial in the dimension. In the case of incoherent measurements, classical
shadows [39, 38, 46, 56, 69, 64, 68, 65] offer efficient algorithms for
estimating properties of certain observable classes. Leveraging our findings,
these algorithms can be adapted to the non-i.i.d. setting while maintaining
comparable performance guarantees. Importantly, this extension retains
efficiency for the same class of observables. Finally, [60, 64] derived shadow
tomography results assuming receipt of independent (though not necessarily
identical) copies of states. However, it is worth noting that the assumption
of independence, which we overcome in this article, is necessary for their
analysis.

#### Verification of pure states.

In scenarios where the verifier receives independent or product states,
optimal and efficient protocols have been proposed by [31, 37, 48]. Recently,
considerable attention has been given to the verification of pure quantum
states in the adversarial scenario, where the received states can be
arbitrarily correlated and entangled [28, 32, 40, 42, 67, 72]. For instance,
[32] proposed efficient protocols for verifying the ground states of
Hamiltonians (subject to certain conditions) and polynomial-time-generated
hypergraph states. Meanwhile, [42] introduced protocols to efficiently verify
bipartite pure states, stabilizer states, and Dicke states. Noteworthy
attention has also been directed towards the verification of graph states [28,
42, 67, 72]. Furthermore, [62] studied device-independent verification of
quantum states beyond the i.i.d. assumption. Lastly, the verification of
continuous-variable quantum states in the adversarial scenario is studied in
[35, 53, 55]. Note that in all these cases the protocols depend explicitly on
the state in question.

###  1.5 Roadmap

We now outline the rest of this article. We first provide the necessary
notation and preliminaries in Section 2. This section is essential for a
complete understanding of the evaluation of an algorithm in the non-i.i.d.
setting and the distinction we make between general and non-adaptive
algorithms. Next, we state and prove our new randomized local de Finetti
theorem in Section 3. This section is self-contained and can be read directly.
In Section 4, we apply our de Finetti theorem (Theorem 3.1) to extend non-
adaptive algorithms to the non-i.i.d. setting. In Section 5, we apply the
results we obtained for non-adaptive algorithms (Theorem 4.1) to specific
examples, including classical shadows for shadow tomography (Section 5.1),
verification of pure states (Section 5.2), fidelity estimation (Section 5.3),
state tomography (Section 5.4), and testing the mixedness of states (Section
5.5). Finally, we show how to generalize any algorithm to the non-i.i.d.
setting in Section 6.

##  2 Notation and preliminaries

Let $[d]$ denote the set of integers from $1$ to $d$ and $[t,s]$ denote the
set of integers from $t$ to $s$. Hilbert spaces are denoted $A,B,...$ and will
be confused with the label of the corresponding systems. We let $d_{A}$ be the
dimension of the Hilbert space $A$. Let $\mathrm{L}(A)$ denote the set of
linear maps from $A$ to itself. A quantum state on $A$ is defined as

$\rho\in\mathrm{L}(A):\;\rho\succcurlyeq
0\;\text{and}\;\mathrm{Tr}\left[\rho\right]=1,$

where $\rho\succcurlyeq 0$ means that $\rho$ is positive semidefinite. The set
of quantum states on $A$ is denoted by $\mathrm{D}(A)$. For an integer $N\geq
2$, we denote the $N$-partite composite system by $A_{1}A_{2}\cdots
A_{N}=A_{1}\otimes A_{2}\otimes\dots\otimes A_{N}$. A classical-quantum state
is a bipartite states that can be written in the form:

$\rho^{XB}=\sum_{x\in\mathcal{X}}p_{x}|x\rangle\\!\langle
x|^{X}\otimes\rho^{B}_{x}$

for some orthonormal basis $\\{|x\rangle\\}_{x\in\mathcal{X}}$ of the space
$X$, where $\bm{p}=(p_{x})_{x\in\mathcal{X}}$ is a probability distribution
and for $x\in\mathcal{X}$, $\rho^{B}_{x}$ is a quantum state. It will also be
useful to see a classical quantum state
$\rho^{XB}\in\mathbb{C}^{\mathcal{X}}\otimes\mathrm{L}(B)$, i.e., as a vector
$(p_{x}\rho^{B}_{x})_{x\in\mathcal{X}}$ of operators acting on $B$. Note that
viewing $\rho^{XB}\in\mathbb{C}^{\mathcal{X}}\otimes\mathrm{L}(B)$ is more
appropriate when the classical system takes continuous values. In this case,
technically $\mathbb{C}^{\mathcal{X}}$ should be interpreted as the space
$L_{1}(\mathcal{X},\mu)$ with some measure $\mu$ on $\mathcal{X}$.
Quantum channels are linear maps
$\mathcal{N}:\mathrm{L}(A)\rightarrow\mathrm{L}(B)$ that can be written in the
form

$\forall\rho\in\mathrm{L}(A):\mathcal{N}(\rho)=\sum_{x\in\mathcal{X}}K_{x}\rho
K_{x}^{\dagger}$

where the Kraus operators $\\{K_{x}\\}_{x\in\mathcal{X}}$ are linear maps from
$A$ to $B$ and satisfy
$\sum_{x\in\mathcal{X}}K_{x}^{\dagger}K_{x}=\mathbb{I}_{d_{A}}$. Equivalently,
$\mathcal{N}$ is trace preserving and completely positive. The partial trace
$\mathrm{Tr}_{B}\left[.\right]$ is a quantum channel from $AB$ to $A$ defined
as

$\forall\rho\in\mathrm{L}(A)\otimes\mathrm{L}(B):\mathrm{Tr}_{B}\left[\rho\right]=\sum_{i=1}^{d_{B}}\left(\mathbb{I}^{A}_{d_{A}}\otimes\langle
i|^{B}\right)\,\rho\,\left(\mathbb{I}^{A}_{d_{A}}\otimes|i\rangle^{B}\right).$

For bipartite state $\rho^{AB}$, we denote the reduced state on $A$ by
$\rho^{A}=\mathrm{Tr}_{B}\left[\rho^{AB}\right]$. In general, for an
$N$-partite state $\rho^{A_{1}\cdots A_{N}}$ and for two integers $t\leq
s\in[N]$, we denote by $\rho^{A_{t}\cdots A_{s}}$ the quantum state obtained
by tracing out the systems $A_{i}$ for $i<t$ or $i>s$ of $\rho^{A_{1}\cdots
A_{N}}$, that is:

$\rho^{A_{t}\cdots A_{s}}=\mathrm{Tr}_{A_{1}\cdots A_{t-1}A_{s+1}\cdots
A_{N}}\left[\rho^{A_{1}\cdots A_{N}}\right].$

In the situation where all systems except one ($A_{t}$ for $t\in[N]$) are
traced out, we use the notation

$\mathrm{Tr}_{-A_{t}}\left[\rho\right]=\mathrm{Tr}_{A_{1}\cdots
A_{t-1}A_{t+1}\cdots A_{N}}\left[\rho^{A_{1}\cdots A_{N}}\right].$

A quantum channel $\Lambda$ with classical output system is called a
measurement channel, and is described by a POVM (positive operator-valued
measure)
$\\{M_{x}\\}_{x\in\mathcal{X}}\in\left(\mathrm{L}(A)\right)^{\mathcal{X}}$
where the measurement operators satisfy $M_{x}\succcurlyeq 0$ and
$\sum_{x\in\mathcal{X}}M_{x}=\mathbb{I}_{d_{A}}$. After performing the
measurement on a quantum state $\rho\in\mathrm{D}(A)$ we observe the outcome
$x\in\mathcal{X}$ with probability $\mathrm{Tr}\left[M_{x}\rho\right]$. The
measurement channel $\Lambda$ should be viewed as a linear map
$\Lambda:\mathrm{L}(A)\to\mathbb{C}^{\mathcal{X}}$ (preserving positivity and
normalization) defined by:

$\forall\rho\in\mathrm{L}(A):\;\Lambda(\rho)=(\mathrm{Tr}\left[M_{x}\rho\right])_{x\in\mathcal{X}}.$

For a measurement operator $0\preccurlyeq M_{x}\preccurlyeq\mathbb{I}$ acting
on $A$, we write $\rho$ conditioned on observing the outcome $x$ by:

$\rho^{B}_{x}=\frac{1}{\mathrm{Tr}\left[M_{x}\rho^{A}\right]}\;\mathrm{Tr}_{A}\left[\left(M_{x}\otimes\mathbb{I}^{B}\right)\cdot\rho^{AB}\right].$

We set $\rho^{B}_{x}$ to be any fixed density operator (e.g., maximally mixed)
if $\mathrm{Tr}\left[M_{x}\rho\right]=0$. The state $\rho$ and the measurement
$\Lambda$ define a probability measure
$\mathbb{P}_{\Lambda(\rho)}\left[.\right]$ on $\mathcal{X}$ by
$\mathbb{P}_{\Lambda(\rho)}\left[x\right]=\mathrm{Tr}\left[M_{x}\rho^{A}\right]$
and we will usually write $x$ to be a random variable following the measure
$\mathbb{P}_{\Lambda(\rho)}\left[.\right]$.

#### I.i.d. setting - input state.

A common assumption in the field of quantum learning is that the learning
algorithm is provided with $N$ independent and identically distributed
(i.i.d.) copies of the unknown quantum state.

######  Definition 2.1 (I.i.d. states).

Let $A_{1}\cong A_{2}\cong\cdots\cong A_{N}$ be $N$ isomorphic quantum
systems. An i.i.d. state refers to an $N$-partite quantum state
$\rho\in\mathrm{D}(A_{1}\cdots A_{N})$ that can be expressed as
$\rho=\sigma^{\otimes N}$ where $\sigma\in\mathrm{D}(A_{1})$ is a quantum
state.

An i.i.d. state possesses the characteristic of permutation invariance: if we
permute the arrangement of the constituent states $\sigma$, the overall state
$\rho=\sigma^{\otimes N}$ remains unchanged. It is important to note, however,
that not all quantum states exhibiting this property are i.i.d.. Let
$\mathfrak{S}_{N}$ be the permutation group of $N$ elements.

######  Definition 2.2 (Permutation invariant states).

For $\pi\in\mathfrak{S}_{N}$, let $C_{\pi}$ be the permutation operator
corresponding to the permutation $\pi$, that is:

$C_{\pi}|i_{1}\rangle\otimes\dots\otimes|i_{N}\rangle=|i_{\pi^{-1}(1)}\rangle\otimes\dots\otimes|i_{\pi^{-1}(N)}\rangle\;,\quad\forall
i_{1},\dots,i_{N}\in[d].$

A state $\rho\in\mathrm{D}(A_{1}\cdots A_{N})$ is permutation invariant if for
all $\pi\in\mathfrak{S}_{N}$ we have

$\rho^{A_{1}\cdots A_{N}}=C_{\pi}\,\rho^{A_{1}\cdots
A_{N}}\,C_{\pi}^{\dagger}.$

If $\rho$ is permutation invariant then for an operator $0\preccurlyeq
M_{x}\preccurlyeq\mathbb{I}$ acting on $A_{1}\cdots A_{t}$, the post-
measurement state $\rho^{A_{t+1}\cdots A_{N}}_{x}$ is also permutation
invariant. So we can define the reduced state conditioned on observing $x$ as:

$\rho_{x}^{A_{N}}=\mathrm{Tr}_{-A_{N}}\left[\rho^{A_{t+1}\cdots
A_{N}}_{x}\right]=\mathrm{Tr}_{-A_{j}}\left[\rho^{A_{t+1}\cdots
A_{N}}_{x}\right]=\rho_{x}^{A_{j}},\quad\forall j\in[t+1,N].$

#### Problems/tasks.

In this article, we consider problems of learning quantum states’ properties.
These problems can be formulated using a SUCCESS event:

######  Definition 2.3 (Success formulation of learning properties of quantum
states).

A quantum learning problem for states on the system $A$ is defined by: a set
$\mathcal{P}$ of possible predictions together with a set of successful
predictions SUCCESS $\subseteq\mathcal{P}\times\mathrm{D}(A)$. If
$(p,\sigma)\in\textup{SUCCESS}$, then $p$ is considered a correct prediction
for $\sigma$. Otherwise, it is considered incorrect.

Many problems have a precision parameter $\varepsilon$, we write in this case
$\textup{SUCCESS}_{\varepsilon}$ for the pairs $(p,\sigma)$ for which $p$ is a
correct prediction for $\sigma$ within precision $\varepsilon$.

We say that the property $\textup{SUCCESS}_{\varepsilon}$ satisfies the
robustness assumption whenever

$\displaystyle\forall(\sigma,\xi):\|\sigma-\xi\|_{1}\leq\varepsilon^{\prime}\;:\quad(p,\sigma)\in\textup{SUCCESS}_{\varepsilon}$
$\displaystyle\Rightarrow(p,\xi)\in\textup{SUCCESS}_{\varepsilon+\varepsilon^{\prime}}.$

######  Example 1.

We illustrate the SUCCESS set for the shadow tomography, full state
tomography, verification of a pure state, and testing mixedness problems:

  * •

Shadow tomography: For some family of $M$ observables $O_{1},\dots,O_{M}$
satisfying $0\preccurlyeq O_{i}\preccurlyeq\mathbb{I}$, the objective is to
estimate all their expectation values within an additive error $\varepsilon$.
In this case, a prediction is an $M$-tuple of numbers in $[0,1]$, i.e.,
$\mathcal{P}=[0,1]^{M}$ and the correct pairs are given by

$\displaystyle\textup{SUCCESS}_{\varepsilon}=\\{(\\{\mu_{1},\dots,\mu_{M}\\},\sigma)\;|\;\forall
1\leq i\leq
M:|\mu_{i}-\mathrm{Tr}\left[O_{i}\sigma\right]|_{1}\leq\varepsilon\\}\subset[0,1]^{M}\times\mathrm{D}(A).$

  * •

State tomography: The objective is to obtain a description of the full state.
In this case, a prediction is a description of a density operator, i.e.,
$\mathcal{P}=\mathrm{D}(A)$ and we have

$\displaystyle\textup{SUCCESS}_{\varepsilon}=\\{(\rho,\sigma)\;|\;\|\rho-\sigma\|_{1}\leq\varepsilon\\}\subset\mathrm{D}(A)\times\mathrm{D}(A).$

  * •

(Tolerant) verification of pure states: In this problem, the objective is to
output ‘$0$’ if the state we have is $\varepsilon$-close to $|\Psi\rangle$ and
output ‘$1$’ if it is $2\varepsilon$-far from $|\Psi\rangle$. In this case,
the prediction is a bit, i.e., $\mathcal{P}=\\{0,1\\}$ and notice that this is
a promise problem in the sense that there are inputs for which any output is
valid. For this reason, it is simpler to define the incorrect prediction
pairs:

$\displaystyle(\textup{SUCCESS}_{\varepsilon})^{c}=\left\\{\left(1,\sigma\right)|\langle\Psi|\sigma|\Psi\rangle\geq
1-\varepsilon\right\\}\cup\left\\{\left(0,\sigma\right)\;|\;\langle\Psi|\sigma|\Psi\rangle\leq
1-2\varepsilon\right\\}\subset\\{0,1\\}\times\mathrm{D}(A).$

  * •

(Tolerant) testing mixedness of quantum states: This problem is similar to the
previous one, except that we are testing if the state is maximally mixed or
not. In this case, we have

$\displaystyle(\textup{SUCCESS}_{\varepsilon})^{c}=\left\\{\left(1,\sigma\right)|\left\|\sigma-\tfrac{\mathbb{I}}{d}\right\|_{1}\leq\varepsilon\right\\}\cup\left\\{\left(0,\sigma\right)\;|\;\left\|\sigma-\tfrac{\mathbb{I}}{d}\right\|_{1}\geq
2\varepsilon\right\\}\subset\\{0,1\\}\times\mathrm{D}(A).$

Observe that all these problems, by the triangle inequality, satisfy the
robustness assumption.

Before specifying the algorithms we consider, let us first recall how one
could formulate a problem when the input state is non-i.i.d.

#### Non-i.i.d. setting - input state.

Given a learning problem defined by SUCCESS, in the usual setting, an
algorithm takes as an input an i.i.d. state $\rho^{A_{1}\cdots
A_{N}}=\sigma^{\otimes N}$ and outputs a prediction $p$. Then, we say that
this algorithm succeeds if $(p,\sigma)$ belongs to the SUCCESS set. In the
setting where the input state $\rho^{A_{1}\cdots A_{N}}$ is no longer an
i.i.d. state, it is not clear when the algorithm succeeds. In what follows, we
follow [16, 42] and present a way to evaluate algorithms with possibly
non-i.i.d. input states.

Consider a collection of $N$ finite dimensional quantum systems
$A_{1}\cong\cdots\cong A_{N}$. We denote the dimension of $A_{1}$ by $d$ (for
an $n$-qubit system $A_{1}$, we have $d=2^{n}$). This collection is shuffled
uniformly at random so that the state $\rho^{A_{1}\cdots
A_{N}}\in\mathrm{D}(A_{1}\cdots A_{N})$ is permutation invariant. We need to
form two sets:

  * •

Train set which consists of the first $N-1$ copies of the state. Some of these
copies are measured in order to construct the estimations necessary for the
learning task, and

  * •

Test set which consists of the last copy (the state on $A_{N}$) that is used
to ‘test’ the accuracy of the estimations deduced from the train set. This
copy should not be measured.

Since the state $\rho^{A_{1}\cdots A_{N}}$ can be entangled, it is possible
that we are in a situation the measurement we perform in the train set affects
the test set. On the other hand, the choice of measuring a copy or not can
also affect the test set. At the end, we compare the estimations from the
train set with only the copy of the test set. See Figure 3 for an illustration
(the distinction between algorithms with and without calibration output is
explained later).

Figure 3: A general algorithm for learning properties of quantum states in the
non-i.i.d. setting. Left (resp. Right) the algorithm is not (resp. is) allowed
to output side/calibration information $c$.

Note that in the i.i.d. setting, i.e., $\rho=\sigma^{\otimes N}$, the train
set will be of the form $\sigma^{\otimes N-1}$ and the test set of the form
$\sigma$ where we compare the estimations deduced from measuring the state
$\sigma$ with the test state $\sigma$. Thus we recover the usual setting. The
following example illustrates the importance of choosing the test state as the
post-measurement state.

######  Example 2.

Consider the following permutation invariant state

$\displaystyle\rho^{A_{1}\cdots
A_{N}}=\frac{1}{d}\sum_{i=1}^{d}|i\rangle\\!\langle i|^{\otimes N}.$

If we measure the first system $A_{1}$ with the canonical basis
$\mathcal{M}=\\{|i\rangle\\!\langle i|\\}_{i\in[d]}$, we observe $m\in[d]$
with probability $1/d$ and the state collapses to:

$\displaystyle\rho^{A_{2}\cdots A_{N}}_{m}=|m\rangle\\!\langle m|^{\otimes
N-1}.$

After this initial measurement, the state of the last system $A_{N}$ is always
equal to $|m\rangle\\!\langle m|$. Therefore, it is more appropriate to
compare the prediction to $\rho^{A_{N}}_{m}=|m\rangle\\!\langle m|$ rather
than the reduced measurement state
$\rho^{A_{N}}=\frac{1}{d}\sum_{i=1}^{d}|i\rangle\\!\langle
i|=\frac{\mathbb{I}}{d}.$

#### Algorithms.

In a general algorithm, the prediction can be an arbitrary quantum channel
from the train set to a prediction.

######  Definition 2.4 (General algorithm).

Let $A_{1}\cong A_{2}\cong\cdots\cong A_{N}$ be $N$ isomorphic quantum
systems. An algorithm for a learning problem with prediction set $\mathcal{P}$
is simply a measurement channel $\mathcal{B}:\mathrm{L}(A_{1}\cdots
A_{N-1})\rightarrow\mathbb{C}^{\mathcal{P}}$.

We will also be interested in a special class of learning algorithms: non-
adaptive incoherent algorithms that can only measure each system separately
and then apply an arbitrary classical post-processing function.

######  Definition 2.5 (Non-adaptive algorithm using $N$ copies).

Let $A_{1}\cong A_{2}\cong\cdots\cong A_{N}$ be $N$ isomorphic quantum
systems. For a non-adaptive algorithm, the prediction channel $\mathcal{B}$
should be of the form
$\mathcal{B}=\mathcal{D}\circ(\mathcal{M}_{1}\otimes\cdots\otimes\mathcal{M}_{N-1})$
where $\mathcal{M}_{i}:\mathrm{L}(A_{i})\to\mathbb{C}^{\mathcal{X}_{i}}$ are
measurement channels, and
$\mathcal{D}:\mathbb{C}^{\mathcal{X}_{1}}\otimes\cdots\otimes\mathbb{C}^{\mathcal{X}_{N-1}}\to\mathbb{C}^{\mathcal{P}}$
is an arbitrary post-processing channel.

#### Error probability.

We can assess an algorithm based on its probability of error, which represents
the likelihood that its outcomes do not satisfy the desired property for a
given test set or state.

######  Definition 2.6 (Error probability in the non-i.i.d. setting (no
calibration data)).

Let $N\geq 1$ be a positive integer, $A_{1}\cong A_{2}\cong\cdots\cong A_{N}$
be $N$ isomorphic quantum systems. Let $\rho^{A_{1}\cdots
A_{N}}\in\mathrm{D}(A_{1}\cdots A_{N})$. A learning algorithm
$\mathcal{B}:\mathrm{L}(A_{1}\dots A_{N-1})\to\mathbb{C}^{\mathcal{P}}$ has
error probability on $\rho$ given by:

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)=\mathbb{P}_{p\sim\mathcal{B}(\rho)}\left[\left(p,\rho_{p}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right],$

where $p$ follows the probability measure $\mathcal{B}(\rho^{A_{1}\dots
A_{N-1}})$ and we recall that $\rho_{p}^{A_{N}}$ is defined by conditioning on
the outcome $p$ of the measurement $\mathcal{B}$ on the systems $A_{1}\dots
A_{N-1}$ of $\rho$.

Note that if a learning algorithm outputs more information than simply the
prediction $p$, this may influence the post-measurement state that we are
comparing against and influence the error probability. This leads us to the
following definition which allows the learning algorithm to output auxiliary
information, which we refer to as ‘calibration’. See Figure 3 for an
illustration of algorithms without and with calibration information.

######  Definition 2.7 (Error probability in the non-i.i.d. setting with
calibration).

Let $N\geq 1$ be a positive integer, $A_{1}\cong A_{2}\cong\cdots\cong A_{N}$
be $N$ isomorphic quantum systems. Let $\rho^{A_{1}\cdots
A_{N}}\in\mathrm{D}(A_{1}\cdots A_{N})$. A learning algorithm with calibration
is given by a quantum channel $\mathcal{B}:\mathrm{L}(A_{1}\dots
A_{N-1})\to\mathbb{C}^{\mathcal{C}}\otimes\mathbb{C}^{\mathcal{P}}$. The error
probability of the algorithm on input $\rho$ is:

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)=\mathbb{P}_{(c,p)\sim\mathcal{B}(\rho)}\left[\left(p,\rho_{c,p}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right],$

where $(c,p)$ is a random variable having distribution
$\mathcal{B}(\rho^{A_{1}\dots A_{N-1}})$.

Note that, if $\rho$ is i.i.d., the conditioning on $c,p$ does not have any
effect on the post-measurement state and both Definitions 2.6 and 2.7 coincide
with the usual definition of the error probability.

The following example illustrates the possible difference that conditioning on
calibration data has.

######  Example 3.

We denote the weight of an element $\bm{x}\in\\{0,1\\}^{n}$ by
$|\bm{x}|=\sum_{i=1}^{n}x_{i}$. Let $\rho^{A_{1}\cdots
A_{N}}=\sum_{\bm{x}\in\\{0,1\\}^{n}}\frac{1}{2^{n}}|\bm{x}\rangle\\!\langle\bm{x}|^{\otimes
N}$ be a permutation invariant state. We want to predict the (average) weight
of the state. A possible algorithm $\mathcal{B}$ is to measure the first
system $A_{1}$ with the canonical basis
$\\{|\bm{x}\rangle\\!\langle\bm{x}|\\}_{\bm{x}\in\\{0,1\\}^{n}}$, observe
$\bm{x}\in\\{0,1\\}^{n}$ and return the prediction $p=|\bm{x}|$ and possibly
the calibration $c=\bm{x}$. The post-measurement state conditioned on the
prediction-related information $p$ is:

$\rho_{p}^{A_{N}}=\frac{1}{\binom{n}{p}}\sum_{\bm{y}\in\\{0,1\\}^{n}:|\bm{y}|=p}|\bm{y}\rangle\\!\langle\bm{y}|.$

On the other hand, the post-measurement state conditioned on the prediction
and calibration information is:

$\rho_{c,p}^{A_{N}}=|\bm{x}\rangle\\!\langle\bm{x}|.$

The states $\rho_{p}^{A_{N}}$ and $\rho_{c,p}^{A_{N}}$ are in general
different. Infact, we have, with probability at least $1-1/2^{n-1}$,
$\left\|\rho_{p}^{A_{N}}-\rho_{c,p}^{A_{N}}\right\|_{1}=2\left(1-1/\binom{n}{p}\right)\geq
2-2/n$.

We will initially present our findings using the error probability with
calibration as defined in Definition 2.7. Nonetheless, we are able to extend
algorithms to the non-i.i.d. setting using the error probability without
calibration as defined in Definition 2.6 for a wide range of learning problems
that can be formulated using a function with reasonable assumptions. We refer
to Appendix A for additional details.

We first state and prove a randomized local de Finetti theorem in Section 3.
We then concentrate on non-adaptive algorithms employing incoherent
measurements and illustrate how to extend their applicability to handle
non-i.i.d. input states. Later, in Section 6, we detail the process of
adapting any algorithm to function within the non-i.i.d. framework.

##  3 Randomized local de Finetti Theorem

In this section we state and prove a randomized local de Finetti theorem.

######  Theorem 3.1 (Randomized local de Finetti).

Let $1\leq k<N/2$. Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation-invariant
state and let $q^{N}$ be a permutation-invariant measure on $\mathcal{R}^{N}$.
Let $\\{\Lambda_{r}\\}_{r\in\mathcal{R}}$ be a set of measurement channels
with input system $A$ and output system $X$. Let
$l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}$,
$\bm{r}=(r_{1},\dots,r_{N})\sim q^{N}$ and $\bm{w}=(w_{l+1},\dots,w_{k+N/2})$
be the outcomes of measuring the systems $A_{l+1},\dots,A_{k+N/2}$ using the
measurements $\Lambda_{r_{l+1}},\dots,\Lambda_{r_{k+N/2}}$. The following
inequality holds:

$\displaystyle\mathbb{E}_{l,\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}\langle\bm{w}|\Bigg{(}\bigotimes_{i=l+1}^{k+N/2}\Lambda_{r_{i}}\Bigg{)}(\rho)|\bm{w}\rangle\left\|\mathrm{id}\otimes\Bigg{(}\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}\Bigg{)}\left(\rho_{l,\bm{r},\bm{w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{r},\bm{w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right]\leq\sqrt{\frac{4{k^{2}}\log(d)}{N}},$

where we defined the conditional state $\rho_{l,\bm{r,w}}$ as

$\rho^{A_{1}\cdots
A_{k+1}A_{N}}_{l,\bm{r},\bm{w}}=\frac{\mathrm{Tr}_{A_{k+2}\cdots
A_{N-1}}\left[\langle\bm{w}|(\Lambda_{r_{l+1}}\otimes\cdots\otimes\Lambda_{r_{k+N/2}})(\rho)|\bm{w}\rangle\right]}{\mathrm{Tr}\left[\langle\bm{w}|(\Lambda_{r_{l+1}}\otimes\cdots\otimes\Lambda_{r_{k+N/2}})(\rho)|\bm{w}\rangle\right]}.$

The proof is inspired by [17].

###### Proof.

Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation invariant state on
$A_{1}\cdots A_{N}$. The mutual information is defined as follows:

$\displaystyle\mathcal{I}(A_{1}:A_{2}:\dots:A_{N})_{\rho}=S(\rho^{A_{1}})+\dots+S(\rho^{A_{N}})-S(\rho^{A_{1}\cdots
A_{N}})$

where $S(\rho)=-\mathrm{Tr}\left[\rho\log(\rho)\right]$ is the Von Neumann
entropy of $\rho$. The mutual information of quantum-classical state
$\xi^{A_{1}\cdots A_{k}C}=\sum_{m}p_{m}\rho_{m}^{A_{1}\cdots
A_{k}}\otimes|m\rangle\\!\langle m|^{C}$ is defined as follows:

$\displaystyle\mathcal{I}(A_{1}:\dots:A_{k}|C)_{\xi}=\sum_{m}p_{m}\mathcal{I}(A_{1}:\dots:A_{k})_{\rho_{m}}.$

The chain rule implies:

$\displaystyle\mathcal{I}(A_{1}:\dots:A_{k}|C)_{\xi}=\mathcal{I}(A_{1}:A_{2}|C)_{\xi}+\mathcal{I}(A_{1}A_{2}:A_{3}|C)_{\xi}+\dots+\mathcal{I}(A_{1}\cdots
A_{k-1}:A_{k}|C)_{\xi}.$

Moreover, we can apply the data-processing inequality locally, for all quantum
channels ${\Gamma_{i}:\mathrm{L}(A_{i})\to\mathrm{L}(X_{i})}$, let
$\zeta=\Gamma_{1}\otimes\cdots\otimes\Gamma_{k}\otimes\mathrm{id}\left(\xi^{A_{1}\cdots
A_{k}C}\right)$ we have:

$\displaystyle\mathcal{I}(X_{1}:\dots:X_{k}|C)_{\zeta}\leq\mathcal{I}(A_{1}:\dots:A_{k}|C)_{\xi}.$

For every $\bm{r}=(r_{1},\dots,r_{N})$ define the state:

$\displaystyle\pi^{A_{1}X_{2}\dots
X_{N}}_{\bm{r}}=\mathrm{id}\otimes\Lambda_{r_{2}}\otimes\dots\otimes\Lambda_{r_{N}}\left(\rho^{A_{1}\cdots
A_{N}}\right).$

We have by the chain rule:

$\displaystyle\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}\left(A_{1}X_{2}\cdots X_{k}:X_{k+1}\cdots
X_{k+N/2}\right)_{\pi_{\bm{r}}}\right]$ $\displaystyle=\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{l=k+1}^{k+N/2}\mathcal{I}(A_{1}X_{2}\cdots
X_{k}:X_{l}|X_{l+1}\cdots X_{k+N/2})_{\pi_{\bm{r}}}\right].$ (2)

Then since the state $\rho^{A_{1}\cdots A_{N}}$ and the distribution $q^{N}$
are invariant under the permutation of the systems $k+1$ and $l$ we have for
all $k+1\leq l\leq k+N/2$:

$\mathbb{E}_{\bm{r}\sim q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots
X_{k}:X_{l}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right]=\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots X_{k}:X_{k+1}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right]$

hence:

$\displaystyle\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{l=k+1}^{k+N/2}\mathcal{I}(A_{1}X_{2}\cdots
X_{k}:X_{l}|X_{l+1}\cdots X_{k+N/2})_{\pi_{\bm{r}}}\right]$
$\displaystyle=\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{l=k+1}^{k+N/2}\mathcal{I}(A_{1}X_{2}\cdots
X_{k}:X_{k+1}|X_{l+1}\dots X_{k+N/2})_{\pi_{\bm{r}}}\right].$ (3)

Now using the data-processing inequality for the partial trace channel and the
fact that $\rho^{A_{1}\dots A_{N}}$ and $q^{N}$ are permutation invariant, we
obtain for all $2\leq i\leq k$ and $k+1\leq l\leq k+N/2$:

$\displaystyle\mathbb{E}_{\bm{r}\sim q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots
X_{k}:X_{k+1}|X_{l+1}\cdots X_{k+N/2})_{\pi_{\bm{r}}}\right]$
$\displaystyle\geq\mathbb{E}_{\bm{r}\sim q}\left[\mathcal{I}(A_{1}X_{2}\cdots
X_{i}:X_{k+1}|X_{l+1}\cdots X_{k+N/2})_{\pi_{\bm{r}}}\right]$
$\displaystyle=\mathbb{E}_{\bm{r}\sim q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots
X_{i}:X_{i+1}|X_{l+1}\cdots X_{k+N/2})_{\pi_{\bm{r}}}\right].$ (4)

Then we can apply the chain rule to get for all $k+1\leq l\leq k+N/2$:

$\displaystyle\sum_{i=2}^{k+1}\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots X_{i-1}:X_{i}|X_{l+1}\dots
X_{k+N/2})_{\pi_{\bm{r}}}\right]$ $\displaystyle=\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}:X_{2}:\cdots:X_{k+1}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right].$ (5)

Now, for each $k+1\leq l\leq k+N/2$, we introduce the notations
$\pi_{\bm{r},\bm{w}}$ for the states on conditioned on the systems
$(X_{l+1},\dots,X_{k+N/2})$ taking the value $\bm{w}$, and
$p_{\bm{r}}(\bm{w})$ for the probability of obtaining outcome $\bm{w}$. Hence
using Pinsker’s inequality then Cauchy Schwarz’s inequality, we obtain:

$\displaystyle\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}:X_{2}:\cdots:X_{k+1}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right]$ $\displaystyle=\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\mathcal{I}(A_{1}:X_{2}:\cdots:X_{k+1})_{\pi_{\bm{r},\bm{w}}}\right]$
$\displaystyle\geq\frac{1}{2}\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\left\|\pi_{\bm{r},\bm{w}}^{A_{1}X_{2}\cdots
X_{k+1}}-\pi_{\bm{r},\bm{w}}^{A_{1}}\otimes\pi_{\bm{r},\bm{w}}^{X_{2}}\otimes\cdots\otimes\pi_{\bm{r},\bm{w}}^{X_{k+1}}\right\|_{1}^{2}\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\left\|\Big{(}\mathrm{id}\otimes\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}\Big{)}(\rho_{l,\bm{r,w}}^{A_{1}A_{2}\cdots
A_{k}})-\rho_{l,\bm{r,w}}^{A_{1}}\otimes\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}(\rho_{l,\bm{r,w}}^{A_{i}})\right\|_{1}^{2}\right]$
$\displaystyle\geq\frac{1}{2}\left(\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\left\|\Big{(}\mathrm{id}\otimes\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}\Big{)}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right]\right)^{2}.$
(6)

Combining the (In)equalities (3), (3), (3), (3) and (3) we obtain:

$\displaystyle\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}\left(A_{1}X_{2}\cdots X_{k}:X_{k+1}\cdots
X_{k+N/2}\right)_{\pi_{\bm{r}}}\right]$
$\displaystyle\geq\frac{1}{k}\sum_{l=k+1}^{k+N/2}\sum_{i=2}^{k+1}\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}X_{2}\cdots X_{i-1}:X_{i}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right]$
$\displaystyle=\frac{N}{2k}\mathbb{E}_{l,\bm{r}\sim
q^{N}}\left[\mathcal{I}(A_{1}:X_{2}:\cdots:X_{k+1}|X_{l+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\right]$
$\displaystyle\geq\frac{N}{4k}\left(\mathbb{E}_{l,\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\left\|\Big{(}\mathrm{id}\otimes\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}\Big{)}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right]\right)^{2}.$

Since $\mathcal{I}(A_{1}X_{2}\cdots X_{k}:X_{k+1}\cdots
X_{k+N/2})_{\pi_{\bm{r}}}\leq\log(d^{k})=k\log(d)$ for all
$\bm{r}\in\mathcal{R}^{N}$, we obtain finally the desired inequality:

$\displaystyle\mathbb{E}_{l,\bm{r}\sim
q^{N}}\left[\sum_{\bm{w}}p_{\bm{r}}(\bm{w})\left\|\Big{(}\mathrm{id}\otimes\bigotimes_{i=2}^{k+1}\Lambda_{r_{i}}\Big{)}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right]$
$\displaystyle\quad\leq\sqrt{\frac{4k}{N}\cdot\mathbb{E}_{\bm{r}\sim
q^{N}}\left[\mathcal{I}\left(A_{1}X_{2}\cdots X_{k}:X_{k+1}\cdots
X_{k+N/2}\right)_{\pi_{\bm{r}}}\right]}$
$\displaystyle\quad\leq\sqrt{\frac{4k}{N}\cdot\sup_{\bm{r}\in\mathcal{R}^{N}}{\mathcal{I}\left(A_{1}X_{2}\cdots
X_{k}:X_{k+1}\cdots X_{k+N/2}\right)_{\pi_{\bm{r}}}}}$ (7)
$\displaystyle\quad\leq\sqrt{\frac{4k^{2}\log(d)}{N}}.$

∎

We illustrate Theorem 3.1 for a specific permutation invariant state and a
specific distribution of measurements.

######  Example 4.

Let the dimension be $d=2$. The quantum state we consider is

$\rho=\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\varphi)}|\varphi\rangle\\!\langle\varphi|^{\otimes
N}.$

The law of measurement devices is the Dirac delta distribution on the simple
POVM $\mathcal{M}=\\{|0\rangle\\!\langle 0|,|1\rangle\\!\langle 1|\\}$.
Observe that any Dirac delta distribution of measurement devices can be
reduced to this example because of the invariance of Haar measure by unitary
conjugation. Let $l\sim\operatorname{Unif}\\{1,\dots,\frac{N}{2}\\}$ be the
number of systems to be measured. For $\bm{w}\in\\{0,1\\}^{l}$, define
$M_{\bm{w}}=\bigotimes_{t=1}^{l}|w_{t}\rangle\\!\langle w_{t}|$. We can write
the post-measurement state as follows:

$\displaystyle\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}=\frac{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\varphi)}\;\langle\varphi|^{\otimes
l}M_{\bm{w}}\;|\varphi\rangle^{\otimes
l}|\varphi\rangle\\!\langle\varphi|^{\otimes
k}}{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\phi)}\;\langle\phi|^{\otimes
l}M_{\bm{w}}|\phi\rangle^{\otimes l}}.$

The measurement channel related to the POVM
$\mathcal{M}=\\{|0\rangle\\!\langle 0|,|1\rangle\\!\langle 1|\\}$ is :

$\displaystyle\Lambda(\rho)=\langle 0|\rho|0\rangle|0\rangle\\!\langle
0|+\langle 1|\rho|1\rangle|1\rangle\\!\langle 1|.$

If we apply the channel
$\mathrm{id}\otimes\Lambda_{2}\otimes\cdots\otimes\Lambda_{k}=\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda$
to the post-measurement state $\rho_{\bm{w}}^{A_{1}\cdots A_{k}}$ we obtain by
writing $|\phi\rangle=\begin{pmatrix}\alpha_{0}\\\ \alpha_{1}\end{pmatrix}$
and $p=|\alpha_{1}|^{2}$:

$\displaystyle\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda(\rho_{\bm{w}}^{A_{1}\cdots
A_{k}})$
$\displaystyle=\frac{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\varphi)}\langle\varphi|^{\otimes
l}M_{\bm{w}}|\varphi\rangle^{\otimes
l}|\varphi\rangle\\!\langle\varphi|\otimes\Lambda(|\varphi\rangle\\!\langle\varphi|)^{\otimes
k-1}}{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\phi)}\langle\phi|^{\otimes
l}M_{\bm{w}}|\phi\rangle^{\otimes l}}$
$\displaystyle=\frac{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\varphi)}(|\alpha_{0}|^{2})^{l-|\bm{w}|}(|\alpha_{1}|^{2})^{|\bm{w}|}\begin{pmatrix}|\alpha_{0}|^{2}&\alpha_{0}\bar{\alpha}_{1}\\\
\alpha_{1}\bar{\alpha}_{0}&|\alpha_{1}|^{2}\end{pmatrix}\otimes\begin{pmatrix}|\alpha_{0}|^{2}&0\\\
0&|\alpha_{1}|^{2}\end{pmatrix}^{\otimes
k-1}}{\int\mathop{}\\!\mathrm{d}{\mathrm{Haar}(\varphi)}(|\alpha_{0}|^{2})^{l-|\bm{w}|}(|\alpha_{1}|^{2})^{|\bm{w}|}}$
$\displaystyle=\frac{\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\int_{0}^{2\pi}\frac{1}{2\pi}\mathop{}\\!\mathrm{d}{\theta}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\begin{pmatrix}1-p&\sqrt{p(1-p)}e^{\mathbf{i}\theta}\\\
\sqrt{p(1-p)}e^{-\mathbf{i}\theta}&p\end{pmatrix}\otimes\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes
k-1}}{\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\int_{0}^{2\pi}\frac{1}{2\pi}\mathop{}\\!\mathrm{d}{\theta}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}}$
$\displaystyle=\frac{\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes
k}}{\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}}$
$\displaystyle=\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}.$

By tracing out all but the first system, we obtain an expression of the
reduced post-measurement state:

$\displaystyle\rho_{\bm{w}}^{A_{1}}$
$\displaystyle=\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}=\begin{pmatrix}1-\tfrac{|\bm{w}|+1}{l+2}&0\\\
0&\tfrac{|\bm{w}|+1}{l+2}\end{pmatrix}.$

Hence if we denote by $p_{\star}=\tfrac{|\bm{w}|+1}{l+2}$ we have:

$\displaystyle\left\|\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda(\rho_{\bm{w}}^{A_{1}\cdots
A_{k}})-\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda\left((\rho_{\bm{w}}^{A_{1}})^{\otimes
k}\right)\right\|_{1}$
$\displaystyle=\left\|\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left[\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right]\right\|_{1}.$

By Stirling’s approximation we have:

$\displaystyle\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\leq\frac{1}{\sqrt{2\pi|\bm{w}|(1-|\bm{w}|/l)}}\exp\left(-l\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}p\right)\right).$

Hence if
$S_{\varepsilon}=\left\\{p\in[0,1]:\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}p\right)>\varepsilon\right\\}$
we have by the triangle inequality:

$\displaystyle\left\|\int_{S_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left[\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right]\right\|_{1}$ $\displaystyle\leq
2\int_{S_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;\frac{(l+1)}{\sqrt{2\pi|\bm{w}|(1-|\bm{w}|/l)}}\exp\left(-l\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}p\right)\right)\leq\frac{2(l+1)e^{-l\varepsilon}}{\sqrt{2\pi|\bm{w}|(1-|\bm{w}|/l)}}.$

On the other hand, we have by the triangle and Pinsker’s inequalities:

$\displaystyle\left\|\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left[\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right]\right\|_{1}$
$\displaystyle\leq\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left\|\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right\|_{1}$
$\displaystyle\leq\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left\|\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-|\bm{w}|/l&0\\\
0&|\bm{w}|/l\end{pmatrix}^{\otimes k}\right\|_{1}$
$\displaystyle\quad+\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left\|\begin{pmatrix}1-|\bm{w}|/l&0\\\
0&|\bm{w}|/l\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right\|_{1}$
$\displaystyle\leq\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\sqrt{2D\left(\begin{pmatrix}1-|\bm{w}|/l&0\\\
0&|\bm{w}|/l\end{pmatrix}^{\otimes k}\bigg{\|}\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}\right)}$
$\displaystyle\quad+\sqrt{2D\left(\begin{pmatrix}1-|\bm{w}|/l&0\\\
0&|\bm{w}|/l\end{pmatrix}^{\otimes k}\bigg{\|}\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right)}$
$\displaystyle=\int_{S^{c}_{\varepsilon}}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\sqrt{2k\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}p\right)}+\sqrt{2k\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}p_{\star}\right)}$
$\displaystyle\leq\sqrt{2k\varepsilon}+\sqrt{2k\operatorname{KL}\left(\tfrac{|\bm{w}|}{l}\big{\|}\tfrac{|\bm{w}|+1}{l+2}\right)}\leq\sqrt{2k\varepsilon}+\sqrt{\frac{4k}{l}}.$

Therefore by the triangle inequality we deduce that:

$\displaystyle\left\|\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda(\rho_{\bm{w}}^{A_{1}\cdots
A_{k}})-\mathrm{id}\otimes\Lambda\otimes\cdots\otimes\Lambda\left((\rho_{\bm{w}}^{A_{1}})^{\otimes
k}\right)\right\|_{1}$
$\displaystyle=\left\|\int_{0}^{1}\mathop{}\\!\mathrm{d}{p}\;(l+1)\binom{l}{|\bm{w}|}(1-p)^{l-|\bm{w}|}p^{|\bm{w}|}\left[\begin{pmatrix}1-p&0\\\
0&p\end{pmatrix}^{\otimes k}-\begin{pmatrix}1-p_{\star}&0\\\
0&p_{\star}\end{pmatrix}^{\otimes k}\right]\right\|_{1}$
$\displaystyle\leq\frac{2(l+1)e^{-l\varepsilon}}{\sqrt{2\pi|\bm{w}|(1-|\bm{w}|/l)}}+\sqrt{2k\varepsilon}+\sqrt{\frac{4k}{l}}$
$\displaystyle\leq\frac{2}{(l+1)\sqrt{2\pi|\bm{w}|(1-|\bm{w}|/l)}}+\sqrt{\frac{2k\log\left((l+1)^{2}\right)}{l}}+\sqrt{\frac{4k}{l}}\leq\sqrt{\frac{9k\log\left(l+1\right)}{l}}$

where the last inequalities are achieved for
$\varepsilon=\frac{2}{l}\log\left(l+1\right)$. Now if we take the average
under $l\sim\operatorname{Unif}\\{1,\dots,\frac{N}{2}\\}$:

$\displaystyle\mathbb{E}_{l}\left[\left\|\mathrm{id}\otimes\Lambda^{\otimes
k-1}(\rho_{l,\bm{w}}^{A_{1}\cdots A_{k}})-\mathrm{id}\otimes\Lambda^{\otimes
k-1}\left((\rho_{l,\bm{w}}^{A_{1}})^{\otimes k}\right)\right\|_{1}^{2}\right]$
$\displaystyle\leq\frac{2}{N}\sum_{l=1}^{N/2}\frac{9k\log\left(l+1\right)}{l}$
$\displaystyle\leq\frac{18k\log^{2}(N)}{N}.$

Finally by Cauchy Schwarz’s inequality

$\displaystyle\mathbb{E}_{l}\left[\left\|\mathrm{id}\otimes\Lambda^{\otimes
k-1}(\rho_{l,\bm{w}}^{A_{1}\cdots A_{k}})-\mathrm{id}\otimes\Lambda^{\otimes
k-1}\left((\rho_{l,\bm{w}}^{A_{1}})^{\otimes k}\right)\right\|_{1}\right]$
$\displaystyle\leq\sqrt{\frac{18k\log^{2}(N)}{N}}.$

##  4 Non-adaptive algorithms in the non-i.i.d. setting

In this section, our emphasis is on problems related to learning properties of
quantum states (as defined in Definition 2.3) and algorithms that operate
through non-adaptive incoherent measurements (as defined in Definition 2.5).
We present a method to extend the applicability of these algorithms beyond the
constraint of i.i.d. input states.

Let $\text{SUCCESS}_{\varepsilon}$ define a property of quantum states. We
consider a fixed non-adaptive algorithm $\mathcal{A}$ that performs non-
adaptive measurements on the $N-1$ systems of the train set. Our approach
introduces a strategy $\mathcal{B}$ outlined in Algorithm 1 and illustrated in
Figure 4, which extends the functionality of the algorithm $\mathcal{A}$ to
encompass non-i.i.d. states. The input state, denoted as $\rho^{A_{1}\cdots
A_{N}}\in\mathrm{D}(A_{1}\cdots A_{N})$, is now an $N$-partite state that can
be entangled.

Since $\mathcal{A}$ is a non-adaptive algorithm, it performs measurements
using the measurements devices $\\{\mathcal{M}_{t}^{\mathcal{A}}\\}_{1\leq
t\leq k_{\mathcal{A}}}$. Let
$l\sim\operatorname{Unif}\left\\{k+1,\dots,k+\frac{N}{2}\right\\}$ (where
$k<N/2$ is related to the number of systems we will use for running
$\mathcal{A}$). For each $i\in[l]$, we choose
$r_{i}\in\operatorname{Unif}\\{1,\dots,k_{\mathcal{A}}\\}$ and we measure the
system $A_{i}$ using the measurement $\mathcal{M}^{\mathcal{A}}_{r_{i}}$.

To compute the prediction, Algorithm $\mathcal{B}$ considers the $k$ outcomes
$\bm{v}$ of measurements $\mathcal{M}_{r_{1}},\dots,\mathcal{M}_{r_{k}}$.
Provided $r_{1},\dots,r_{k}$ span the set $\\{1,\dots,k_{\mathcal{A}}\\}$, the
prediction algorithm of $\mathcal{A}$ is applied to the relevant systems (as
described in Algorithm 1). The coupon collector’s problem ensures that
$r_{1},\dots,r_{k}$ spans all elements in $\\{1,\dots,k_{\mathcal{A}}\\}$
before step $k=\mathcal{O}(k_{\mathcal{A}}\log(k_{\mathcal{A}}))$ with high
probability.

Algorithm 1 Predicting properties of quantum states in the non-i.i.d. setting-
Non-adaptive algorithms

The measurements $\\{\mathcal{M}_{t}^{\mathcal{A}}\\}_{1\leq t\leq
k_{\mathcal{A}}}$ of algorithm $\mathcal{A}$.

A permutation invariant state $\rho^{A_{1}\cdots A_{N}}$.

Adapt the algorithm $\mathcal{A}$ to non-i.i.d. inputs $\rho^{A_{1}\cdots
A_{N}}$.

Sample $l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}$ and
$(r_{1},\dots,r_{l})\overset{iid}{\sim}\operatorname{Unif}\\{1,\dots,k_{\mathcal{A}}\\}$

For $t=k+1,\dots,l$, apply $\mathcal{M}_{r_{t}}^{\mathcal{A}}$ to system
$A_{t}$ and obtain outcome
$\bm{w}\leftarrow\bigotimes_{t=k+1}^{l}\mathcal{M}_{r_{t}}^{\mathcal{A}}(\rho)$

For $t=1,\dots,k$, apply $\mathcal{M}_{r_{t}}^{\mathcal{A}}$ to system $A_{t}$
and obtain outcome
$\bm{v}\leftarrow\bigotimes_{t=1}^{k}\mathcal{M}_{r_{t}}^{\mathcal{A}}(\rho_{\bm{w}})$

For $t=1,\dots,k_{\mathcal{A}}$, let $s(t)\in[k]$ be the first integer such
that $r_{s(t)}=t$

Run the prediction of algorithm $\mathcal{A}$ to the measurement outcomes
$v_{s(1)},\dots,v_{s(k_{\mathcal{A}})}$ and obtain $p$

return $\left(l,\bm{r,w},p\right)$.

Figure 4: Illustration of Algorithm 1.

######  Theorem 4.1 (Non-adaptive algorithms in the non-i.i.d. setting).

Let $\varepsilon,\varepsilon^{\prime}>0$ and $k_{\mathcal{A}}<k<N/2$. Let
$\mathcal{A}$ be a non-adaptive algorithm suitable for i.i.d. input states and
performing measurements with $\\{\mathcal{M}_{t}^{\mathcal{A}}\\}_{1\leq t\leq
k_{\mathcal{A}}}$. Algorithm 1 has an error probability satisfying:

$\displaystyle\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon+\varepsilon^{\prime}\right)\leq\sup_{l,\bm{r,w}}\delta_{\mathcal{A}}\left(k_{\mathcal{A}},\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes
k_{\mathcal{A}}},\varepsilon\right)+k_{\mathcal{A}}e^{-{k}/k_{\mathcal{A}}}+\sqrt{\frac{4k^{2}\log(d)}{N}}+\sqrt{\frac{16k^{2}\log(d)}{N\varepsilon^{\prime
2}}}.$

######  Remark 4.2.

The first component of this upper bound essentially represents the error
probability of algorithm $\mathcal{A}$ when applied to an i.i.d. input state
$\sigma^{\otimes k_{\mathcal{A}}}$, where
$\sigma\in\\{\rho_{l,\bm{r,w}}^{A_{N}}\\}_{l,\bm{r,w}}$. Note that here we are
not required to control this error probability over all states but only over
the post-measurement states $\\{\rho^{A_{N}}_{l,\bm{r,w}}\\}_{l,\bm{r,w}}$.
The second component reflects the error of the coupon collector’s problem–some
of the measurements devices that algorithm $\mathcal{A}$ uses are not sampled
before step $k$. The third and fourth components consist of error terms that
account for the possibility of the input state $\rho^{A_{1}\cdots A_{N}}$
being non i.i.d..

######  Remark 4.3.

To achieve an error probability of at most $\delta$, one could start by
determining a value for $k_{\mathcal{A}}=k(\mathcal{A},\delta,\varepsilon)$
such that for all $l,\bm{r,w}$,
$\delta_{\mathcal{A}}\left(k_{\mathcal{A}},(\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k_{\mathcal{A}}},\varepsilon/2\right)\leq\delta/6$. Subsequently, we can
choose $k=k_{\mathcal{A}}\log(6k_{\mathcal{A}}/\delta)$ and the total number
of copies can be set to

$N=\frac{16^{2}\log(d)}{\delta^{2}\varepsilon^{2}}\cdot
k_{\mathcal{A}}^{2}\log^{2}(6k_{\mathcal{A}}/\delta).$

By doing this, we ensure that $\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)\leq\delta$.

######  Remark 4.4.

The third (resp. fourth) error terms of this upper bound can be improved to
$\sqrt{\frac{4k\sup_{\bm{r}}\mathcal{I}(\pi_{\bm{r}})}{N}}$ $\left(\text{resp.
}\sqrt{\frac{16k\sup_{\bm{r}}\mathcal{I}(\pi_{\bm{r}})}{N\varepsilon^{\prime
2}}}\right)$ through the same proof outlined in Theorem 3.1 (see Inequality
(3)). When the state $\rho^{A_{1}\cdots A_{N}}=\sigma^{\otimes N}$ is i.i.d.,
the mutual information
$\mathcal{I}(\pi_{\bm{r}})=\mathcal{I}\left(A_{1}X_{2}\cdots
X_{k}:X_{k+1}\cdots X_{k+N/2}\right)_{\pi_{\bm{r}}}$ becomes zero for all
local quantum channels
$\Lambda_{\bm{r}}=\mathrm{id}\otimes\Lambda_{r_{2}}\otimes\cdots\otimes\Lambda_{r_{k+N/2}}$.
Consequently, the third and fourth error terms vanish in the i.i.d. setting
and we recover the i.i.d. error probability, albeit with a minor loss:
substituting $\varepsilon$ with $\varepsilon+\varepsilon^{\prime}$ and
$k_{\mathcal{A}}$ with $k_{\mathcal{A}}\log(k_{\mathcal{A}}/\delta)$.

######  Remark 4.5.

In Algorithm 1, the initial stage of measuring systems $A_{k+1}\cdots A_{l}$
(corresponding to outcomes $\bm{w}$) can be thought as a projection phase,
while the subsequent stage involving measuring the systems $A_{1}\cdots A_{k}$
(corresponding to outcomes $\bm{v}$) can be regarded as a learning phase. Note
that we utilize only the outcomes $\bm{v}$ for the prediction component $p$;
however, the outcomes $\bm{w}$ hold significance in enabling the application
of the randomized de Finetti Theorem 3.1.

The remaining of this section is dedicated to the proof of Theorem 4.1.

###### Proof of Theorem 4.1.

Recall that we differentiate between $k_{\mathcal{A}}$ and $k$. The former is
the copy complexity of the non-adaptive algorithm $\mathcal{A}$ while the
latter is a parameter we use for the proof to ensure that all the measurement
devices used by the non-adaptive algorithm $\mathcal{A}$ are sampled. Let
$l\sim\operatorname{Unif}\\{k+1,\dots,k+N/2\\}$ and
$\bm{r}=(r_{1},\dots,r_{l})\overset{iid}{\sim}\operatorname{Unif}\\{1,\dots,k_{\mathcal{A}}\\}$.
Algorithm $\mathcal{B}$ applies measurement
$\mathcal{M}^{\mathcal{A}}_{r_{i}}$ to system $A_{i}$ for all $i\in[l]$.

Our proof strategy will be to approximate the reduced post-measurement state
$\rho_{l,\bm{r,w},p}^{A_{N}}$ by the reduced post-measurement state
$\rho_{l,\bm{r,w}}^{A_{N}}$. Then, we approximate the state
$\rho_{l,\bm{r,w}}^{A_{1}\cdots A_{k}}$ by the i.i.d. state
$\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes k}$ by using the de Finetti
Theorem 3.1.

More precisely, we write the error probability:

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon+\varepsilon^{\prime})$
$\displaystyle=\mathbb{P}_{l,\bm{r,w},p}\left[(p,\rho_{l,\bm{r,w},p}^{A_{N}})\notin\textup{SUCCESS}_{\varepsilon+\varepsilon^{\prime}}\right]$
$\displaystyle=\mathbb{P}_{l,\bm{r,w},p}\left[(p,\rho_{l,\bm{r,w},p}^{A_{N}})\notin\textup{SUCCESS}_{\varepsilon+\varepsilon^{\prime}}\;,\;\left\|\rho_{l,\bm{r,w},p}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\leq\varepsilon^{\prime}\right]$
$\displaystyle\quad+\mathbb{P}_{l,\bm{r,w},p}\left[(p,\rho_{l,\bm{r,w},p}^{A_{N}})\notin\textup{SUCCESS}_{\varepsilon+\varepsilon^{\prime}}\;,\;\left\|\rho_{l,\bm{r,w},p}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}>\varepsilon^{\prime}\right]$
$\displaystyle\leq\mathbb{P}_{l,\bm{r,w},p}\left[(p,\rho_{l,\bm{r,w}}^{A_{N}})\notin\textup{SUCCESS}_{\varepsilon}\right]+\mathbb{P}_{l,\bm{r,w},p}\left[\left\|\rho_{l,\bm{r,w},p}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}>\varepsilon^{\prime}\right]$
(8)

where we used the robustness condition for the problem defined by
$\text{SUCCESS}_{\varepsilon}$.

Let us start with the second term by relating the reduced post-measurement
state $\rho_{l,\bm{r,w},p}^{A_{N}}$ with $\rho_{l,\bm{r,w}}^{A_{N}}$. Note
that as $p$ is a function of $\bm{v}$, it suffices to bound the distance
between $\rho_{l,\bm{r,w}}^{A_{N}}$ and $\rho_{l,\bm{r,w,v}}^{A_{N}}$, which
is done in the following lemma.

######  Lemma 4.6.

We have for all $\varepsilon^{\prime}>0$:

$\displaystyle\mathbb{P}_{l,\bm{r},\bm{w,v}}\left[\left\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}>\varepsilon^{\prime}\right]\leq\sqrt{\frac{16{k^{2}}\log(d)}{N\varepsilon^{\prime
2}}}.$

###### Proof of Lemma 4.6.

We use the notation $M_{\bm{w}}=\bigotimes_{t=k+1}^{l}M^{t}_{w_{t}}$ and
$M_{\bm{v}}=\bigotimes_{t=1}^{k}M^{t}_{v_{t}}$ where
$\mathcal{M}_{r_{t}}^{\mathcal{A}}=\\{M_{x}^{t}\\}_{x\in\mathcal{X}}$ for
$t\in[N]$. We have:

$\displaystyle\left\|\mathcal{M}_{r_{1}}\otimes\dots\otimes\mathcal{M}_{r_{k}}\otimes\mathrm{id}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}$
$\displaystyle=\sum_{\bm{v}}\left\|\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[(M_{\bm{v}}\otimes\mathbb{I})\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right]\right\|_{1}$
$\displaystyle=\sum_{\bm{v}}\left\|\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}\right]-\mathrm{Tr}\left[M_{\bm{v}}\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}\right]\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}$

and similarly by the data processing inequality we have

$\displaystyle\left\|\mathcal{M}_{r_{1}}\otimes\dots\otimes\mathcal{M}_{r_{k}}\otimes\mathrm{id}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}$
$\displaystyle\geq\left\|\mathcal{M}_{r_{1}}\otimes\cdots\otimes\mathcal{M}_{r_{k}}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}\right)\right\|_{1}$
$\displaystyle=\sum_{\bm{v}}\left|\mathrm{Tr}\left[M_{\bm{v}}\left(\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}-\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}}\right)\right]\right|$
$\displaystyle=\sum_{\bm{v}}\left\|\mathrm{Tr}\left[M_{\bm{v}}\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}\right]\rho_{l,\bm{r,w}}^{A_{N}}-\mathrm{Tr}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}\right]\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}.$

So the triangle inequality implies:

$\displaystyle\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{v,w}}\mathrm{Tr}\left[(M_{\bm{v}}\otimes
M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{v,w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\mathrm{Tr}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}\right]\left\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{v,w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}\right]-\mathrm{Tr}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}\right]\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{v,w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}\right]-\mathrm{Tr}\left[M_{\bm{v}}\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}\right]\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle\quad+\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{v,w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\mathrm{Tr}\left[M_{\bm{v}}\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k}}\right]\rho_{l,\bm{r,w}}^{A_{N}}-\mathrm{Tr}\left[(M_{\bm{v}}\otimes\mathbb{I})\rho_{l,\bm{r,w}}\right]\rho_{l,\bm{r,w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle\leq
2\,\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\mathcal{M}_{r_{1}}\otimes\dots\otimes\mathcal{M}_{r_{k}}\otimes\mathrm{id}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right].$

On the other hand, we have by the randomized de Finetti Theorem 3.1:

$\displaystyle\mathbb{E}_{l,\bm{r}}\left[\sum_{\bm{w}}\mathrm{Tr}\left[(M_{\bm{w}}\otimes\mathbb{I})\rho\right]\left\|\mathcal{M}_{r_{1}}\otimes\dots\otimes\mathcal{M}_{r_{k}}\otimes\mathrm{id}\left(\rho_{l,\bm{r,w}}^{A_{1}\cdots
A_{k}A_{N}}-\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes{k+1}}\right)\right\|_{1}\right]\leq\sqrt{\frac{4{k^{2}}\log(d)}{N}}.$

Hence we can deduce the following inequality:

$\displaystyle\mathbb{E}_{l,\bm{r,w},p}\left[\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\|_{1}\right]\leq
2\sqrt{\frac{4{k^{2}}\log(d)}{N}}.$

Finally, the Markov’s inequality implies:

$\displaystyle\mathbb{P}_{l,\bm{r,w,v}}\left[\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\|_{1}>\varepsilon^{\prime}\right]\leq\frac{\mathbb{E}_{l,\bm{r,w,v}}\left[\|\rho_{l,\bm{r,w,v}}^{A_{N}}-\rho_{l,\bm{r,w}}^{A_{N}}\|_{1}\right]}{\varepsilon^{\prime}}\leq\sqrt{\frac{16{k^{2}}\log(d)}{N\varepsilon^{\prime
2}}}.$

∎

We now go back to (8) and consider the first term. Let us denote
$\mathcal{M}_{\bm{r}}=\otimes_{i=1}^{l}\mathcal{M}_{r_{i}}$ and $\mathcal{D}$
for the channel mapping the outcomes $\bm{v}$ and outputting a prediction $p$
(as described in Algorithm 1). We have

$\displaystyle\mathbb{P}_{l,\bm{r,w},p}\left[(p,\rho_{l,\bm{r,w}}^{A_{N}})\notin\textup{SUCCESS}_{\varepsilon}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{D}(\mathcal{M}_{\bm{r}}(\rho^{A_{1}\dots
A_{k}}_{l,\bm{r,w}}))}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{D}(\mathcal{M}_{\bm{r}}((\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k}))}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\right]+\sqrt{\frac{4{k^{2}}\log(d)}{N}}.$

using the randomized de Finetti Theorem 3.1. To relate

$\displaystyle\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{D}(\mathcal{M}_{\bm{r}}((\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k}))}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\right]$

to the behaviour of algorithm $\mathcal{A}$, we introduce the event that all
the measurement devices that algorithm $\mathcal{A}$ needs are sampled before
$k$:

$\displaystyle\mathcal{G}=\left\\{[k_{\mathcal{A}}]\subset\\{r_{t}\\}_{1\leq
t\leq k}\right\\}.$

The union bound implies:

$\displaystyle\mathbb{P}\left[\mathcal{G}^{c}\right]$
$\displaystyle=\mathbb{P}\left[\exists 1\leq s\leq
k_{\mathcal{A}}:s\notin\\{r_{t}\\}_{1\leq t\leq k}\right]$
$\displaystyle\leq\sum_{s=1}^{k_{\mathcal{A}}}\mathbb{P}\left[\forall 1\leq
t\leq k:r_{t}\neq
s\right]=k_{\mathcal{A}}\left(1-\frac{1}{k_{\mathcal{A}}}\right)^{k}\leq
k_{\mathcal{A}}e^{-k/k_{\mathcal{A}}}.$

Under $\mathcal{G}$ we let $s(t)\in[k]$ be the smallest integer such that
$r_{s(t)}=t$ for $t=1,\dots,k_{\mathcal{A}}$. Then

$\displaystyle\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{D}(\mathcal{M}_{\bm{r}}((\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k}))}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{D}(\mathcal{M}_{\bm{r}}((\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k}))}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\mathbf{1}\\{\mathcal{G}\\}\right]+\mathbb{P}\left[\mathcal{G}^{c}\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{r},\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{A}\left((\rho^{A_{N}}_{l,\bm{r,w}})^{\otimes
k_{\mathcal{A}}}\right)}\left[\left(p,\rho_{l,\bm{r,w}}^{A_{N}}\right)\notin\textup{SUCCESS}_{\varepsilon}\right]\right]+k_{\mathcal{A}}e^{-k/k_{\mathcal{A}}}$
$\displaystyle\leq\sup_{l,\bm{r,w}}\delta_{\mathcal{A}}\left(k_{\mathcal{A}},\left(\rho_{l,\bm{r,w}}^{A_{N}}\right)^{\otimes
k_{\mathcal{A}}},\varepsilon\right)+k_{\mathcal{A}}e^{-k/k_{\mathcal{A}}}.$

∎

##  5 Applications

In this section, we apply the non i.i.d. framework that we have developed in
Section 4 to address specific and concrete examples. These examples include
classical shadows for shadow tomography, the verification of pure states,
fidelity estimation, state tomography, and testing mixedness of states.

###  5.1 Classical shadows for shadow tomography

In the shadow tomography problem, we have $M\geq 1$ known observables denoted
as $O_{1},\dots,O_{M}$, with each observable satisfying $0\preccurlyeq
O_{i}\preccurlyeq\mathbb{I}$, along with $N$ incoherent copies of an unknown
quantum state $\sigma$. The objective here is to make estimations of the
expected values $\\{\mathrm{Tr}\left[O_{i}\sigma\right]\\}_{1\leq i\leq M}$
with a precision of at least $\varepsilon$ and a probability of at least
$1-\delta$. In their work, [46] have introduced two specific protocols known
as classical shadows, which employ Clifford and Pauli measurements to tackle
this problem. In their analysis, the authors crucially rely on the assumption
of input states being i.i.d., which is essential for the successful
application (concentration) of the median of means technique (estimator).
Given that both algorithms proposed by [46] are non-adaptive (as defined in
Definition 2.5), we can leverage Theorem 4.1 to extend the applicability of
these algorithms to encompass input states that are not i.i.d..

The initial algorithm employs measurements that follow either the Haar or
Clifford distributions. The Haar probability measure stands as the unique
invariant probability measure over the unitary (compact) group and is denoted
$\mathcal{L}_{\bf{Haar}}$. For the Clifford distribution, certain definitions
need to be introduced. We consider an $n$-qubit quantum system denoted as
$A\cong\mathbb{C}^{d}$ where $d=2^{n}$. First define the set of Pauli matrices
as follows:

$\mathbf{P}_{n}=\left\\{e^{\mathbf{i}\theta\pi/2}\sigma_{1}\otimes\dots\otimes\sigma_{n}\;\big{|}\;\theta=0,1,2,3,\;\sigma_{i}\in\\{\mathbb{I},X,Y,Z\\}\right\\}.$

Subsequently, the Clifford group is defined as the centralizer of the
aforementioned set of Pauli matrices:

$\displaystyle\mathbf{Cl}(2^{n})=\\{U\in\mathbb{U}_{d}:U\mathbf{P}_{n}U^{\dagger}=\mathbf{P}_{n}\\}.$

It is known [5, 11] that the Clifford group is generated by the Hadamard
$(H)$, phase $(S)$ and CNOT gates:

$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix},\;S=\begin{pmatrix}1&0\\\
0&i\end{pmatrix}\;\;\text{and}\;\;\rm{CNOT}=\begin{pmatrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{pmatrix}.$

Moreover, the Clifford group is finite (of order at most
$\exp\left(\mathcal{O}\left(n^{2}\right)\right)$) [11]. Sampling a Clifford
unitary matrix is given by selecting an element uniformly and randomly from
the Clifford group $\mathbf{Cl}(2^{n})$. We denote this distribution by
$\mathcal{L}_{\bf{Clifford}}$. Importantly, Clifford distribution is a
$3$-design [22, 24, 29], that is for all $s=0,1,2,3$:

$\displaystyle\mathbb{E}_{U\sim\mathcal{L}_{\bf{Clifford}}}\left[U^{\otimes{s}}\otimes\bar{U}^{\otimes{s}}\right]=\mathbb{E}_{U\sim\mathcal{L}_{\bf{Haar}}}\left[U^{\otimes{s}}\otimes\bar{U}^{\otimes{s}}\right].$

This property of the Clifford distribution has a significant implication:
unitaries distributed according to $\mathcal{L}_{\bf{Clifford}}$ or
$\mathcal{L}_{\bf{Haar}}$ distributions yield identical performance for the
classical shadows [46]. Now we can state the first result of [46]:

######  Theorem 5.1 ([46], rephrased).

Let $\\{O_{i}\\}_{i\in[M]}$ be $M$ observables. There is an algorithm for
predicting the expected values of the observables $\\{O_{i}\\}_{i\in[M]}$
under the state $\sigma$ to within $\varepsilon$ with an error probability
$\delta$. This algorithm performs i.i.d. measurements following the
distribution $\mathcal{L}_{\bf{Clifford}}$ (or $\mathcal{L}_{\bf{Haar}}$), and
it requires a total of i.i.d. copies of the state $\sigma$ satisfying:

$\displaystyle
N=\mathcal{O}\left(\frac{\max_{i\in[M]}\mathrm{Tr}\left[O_{i}^{2}\right]\log(M/\delta)}{\varepsilon^{2}}\right).$

Hence by Theorem 4.1 there is an algorithm $\mathcal{B}$ in the non-i.i.d.
setting with an error probability:

$\displaystyle\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon\right)\leq\sup_{\sigma\,:\;\text{state}}\delta_{\mathcal{A}}\left(k_{\mathcal{A}},\sigma^{\otimes
k_{\mathcal{A}}},\varepsilon/2\right)+k_{\mathcal{A}}e^{-{k}/k_{\mathcal{A}}}+\sqrt{\frac{4k^{2}\log(d)}{N}}+\sqrt{\frac{64k^{2}\log(d)}{N\varepsilon^{2}}}.$

By taking
$k_{\mathcal{A}}=\mathcal{O}\left(\frac{\max_{i\in[M]}\mathrm{Tr}\left[O_{i}^{2}\right]\log(M/\delta)}{\varepsilon^{2}}\right)$
as the complexity of classical shadows in the i.i.d. setting, we deduce that a
total number of copies sufficient to achieve $\delta$-correctness in the
non-i.i.d. setting is given by:

$\displaystyle
N=\mathcal{O}\left(\frac{k_{\mathcal{A}}^{2}\log^{2}(k_{\mathcal{A}}/\delta)\log(d)}{\delta^{2}\varepsilon^{2}}\right)=\mathcal{O}\left(\frac{\|O\|^{2}\log^{2}(M/\delta)\log^{2}(\|O\|\log(M/\delta)/\varepsilon\delta)\log(d)}{\delta^{2}\varepsilon^{6}}\right)$

where $\|O\|=\max_{i\in[M]}\mathrm{Tr}\left[O_{i}^{2}\right]$.

######  Proposition 5.2 (Classical shadows in the non-i.i.d.
setting–Clifford).

Let $\\{O_{i}\\}_{i\in[M]}$ be $M$ observables. There is an algorithm in the
non-i.i.d. setting for predicting the expected values of the observables
$\\{O_{i}\\}_{i\in[M]}$ under the post-measurement state to within
$\varepsilon$ with a copy complexity

$\displaystyle
N=\mathcal{O}\left(\frac{\max_{i\in[M]}\mathrm{Tr}\left[O_{i}^{2}\right]^{2}\log^{2}(M/\delta)\log^{2}\left(\max_{i\in[M]}\mathrm{Tr}\left[O_{i}^{2}\right]\log(M/\delta)/\varepsilon\delta\right)\log(d)}{\delta^{2}\varepsilon^{6}}\right).$

The algorithm is described in 1, where the non-adaptive algorithm/statistic
$\mathcal{A}$ is the classical shadows algorithm of [46] and the distribution
of measurements is $\mathcal{L}_{\bf{Clifford}}$ (or
$\mathcal{L}_{\bf{Haar}}$).

The second protocol introduced by [46] involves the use of Pauli measurements.
This is given by measuring using an orthonormal basis that corresponds to a
non-identity Pauli matrix. On the level of the unitary matrix, we can generate
this sample by taking $U=u_{1}\otimes\dots\otimes u_{N}$ where
$u_{1},\dots,u_{n}\overset{\text{i.i.d.\
}}{\sim}\operatorname{Unif}(\mathbf{Cl}(2))$. We denote this distribution by
$\mathcal{L}_{\bf{Pauli}}$. The classical shadows with Pauli measurement have
better performance for estimation expectations of local observables.

######  Theorem 5.3 ([46], rephrased).

Let $\\{O_{i}\\}_{i\in[M]}$ be $M$ $k$-local observables. There is an
algorithm for predicting the expected values of the observables
$\\{O_{i}\\}_{i\in[M]}$ under the state $\sigma$ to within $\varepsilon$ with
an error probability $\delta$. This algorithm performs i.i.d. measurements
following the distribution $\mathcal{L}_{\bf{Pauli}}$, and it requires a total
of i.i.d. copies of the state $\sigma$ satisfying:

$\displaystyle
N=\mathcal{O}\left(\frac{2^{2k}\max_{i\in[M]}\|O_{i}\|^{2}_{\infty}\log(M/\delta)}{\varepsilon^{2}}\right).$

Now, combining this theorem and Theorem 4.1, we obtain the following
generalization for estimating local properties in the non-i.i.d. setting.

######  Proposition 5.4 (Classical shadows in the non-i.i.d. setting–Pauli).

Let $\\{O_{i}\\}_{i\in[M]}$ be $M$ $k$-local observables. There is an
algorithm in the non-i.i.d. setting for predicting the expected values of the
observables $\\{O_{i}\\}_{i\in[M]}$ under the post-measurement state to within
$\varepsilon$ with an error probability $\delta$ and a copy complexity
satisfying:

$\displaystyle
N=\mathcal{O}\left(\frac{2^{4k}\max_{i\in[M]}\|O_{i}\|^{4}_{\infty}\log^{2}(M/\delta)\log^{2}(2^{2k}\log(M)/\varepsilon\delta)\log(d)}{\delta^{2}\varepsilon^{6}}\right).$

Recently, [56] provide protocols with depth-modulated randomized measurement
that interpolates between Clifford and Pauli measurements. Since their
algorithms are also non-adaptive, they can be generalized as well to the
non-i.i.d. setting using Theorem 4.1. Other classical shadows protocols [63,
68, 65, 69] could also be extended to the non-i.i.d. setting.

###  5.2 Verification of pure states

The verification of pure states is the task of determining whether a received
state precisely matches the ideal pure state or significantly deviates from
it. In this context, we will extend this problem to scenarios where we have
$M$ potential pure states represented as
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$, and our objective
is to ascertain whether the received state corresponds to one of these pure
states or is substantially different from all of them. The traditional problem
constitutes a special case with $M=1$. To formalize, a verification protocol
$\mathcal{B}$ satisfies:

  1. 1.

the completeness condition if it accepts, with high probability, upon
receiving one of the pure i.i.d. states
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|^{\otimes N}\\}_{1\leq i\leq M}$, i.e.,
for all $i\in[M]$, we have
$\mathbb{P}\left[\mathcal{B}\left(|\Psi_{i}\rangle\\!\langle\Psi_{i}|^{\otimes
N}\right)=0\right]\geq 1-\delta$. Here, the symbol ‘$0$’ represents the
outcome ‘Accept’ or the null hypothesis.

  2. 2.

the soundness condition if when the algorithm accepts, the quantum state
passing the verification protocol (post-measurement state conditioned on a
passing event) is close to one of the pure states
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ with high
probability, i.e.,

$\mathbb{P}_{\bm{x}}\left[\mathcal{B}\left(\rho^{A_{1}\cdots
A_{N}}\right)=0\,,\;\forall
i\in[M]:\langle\Psi_{i}|\rho_{\bm{x}}^{A_{N}}|\Psi_{i}\rangle<1-\varepsilon\right]\leq\delta.$

In this latter scenario, the protocol can receive a possibly highly entangled
state $\rho^{A_{1}\cdots A_{N}}$.

It is worth noting that in typical cases [28, 32, 40, 42, 67, 72], when
verifying a single pure state ($M=1$), the completeness and soundness
conditions are often formulated in terms of expectation rather than
probability. In this context, if $\Pi_{\text{Accept}}$ represents the event in
which the verification protocol accepts, the completeness condition is met
when the following inequality holds:

$\displaystyle\mathrm{Tr}\left[\Pi_{\text{Accept}}|\Psi\rangle\\!\langle\Psi|^{\otimes
N-1}\right]\geq 1-\varepsilon.$

Moreover, the soundness condition is met when the following inequality holds:

$\displaystyle\mathrm{Tr}\left[\Pi_{\text{Accept}}\otimes\left(\mathbb{I}-|\Psi\rangle\\!\langle\Psi|\right)\rho^{A_{1}\cdots
A_{N}}\right]\leq\varepsilon.$

We can indeed express our findings in terms of expectations for the task of
verifying one pure state, see Appendix B for more details. Here we prove the
following verification result with high probability.

######  Proposition 5.5 (Verification of pure states in the non-i.i.d.
setting–Clifford).

Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation invariant state. Let
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ be $M$ pure
states. There is an algorithm using Clifford measurements for verifying
whether the (post-measurement) state $\rho^{A_{N}}$ is a member of
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ or is at least
$\varepsilon$-far from them in terms of fidelity with a probability at least
$1-\delta$ and a number of copies satisfying

$\displaystyle
N=\mathcal{O}\left(\frac{\log^{2}(M/\delta)\log^{2}(\log(M)/\varepsilon\delta)\log(d)}{\delta^{2}\varepsilon^{6}}\right).$

###### Proof.

We can apply Proposition 5.2 to estimate the expectation of the observables
$\\{O_{i}=|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ under the
post-measurement state $\rho_{\bm{x}}^{A_{N}}$ to within $\varepsilon/4$ and
with a probability at least $1-\delta$ using a number of copies
$N=\mathcal{O}\left(\frac{\log^{2}(M/\delta)\log^{2}(\log(M)/\varepsilon\delta)\log(d)}{\delta^{2}\varepsilon^{6}}\right)$.
More concretely, we have $\\{\mu_{i}\\}_{1\leq i\leq M}$ satisfying:

$\displaystyle\mathbb{P}_{\bm{x}}\left[\forall
i\in[M]:\left|\mu_{i}-\mathrm{Tr}\left[|\Psi_{i}\rangle\\!\langle\Psi_{i}|\rho_{\bm{x}}^{A_{N}}\right]\right|\leq\varepsilon/4\right]\geq
1-\delta.$ (9)

Then, our proposed algorithm accepts if, and only if there is some $i\in[M]$
such that $\mu_{i}\geq 1-\varepsilon/2$. We can verify the completeness and
soundness conditions for this algorithm.

  1. 1.

Completeness. If the verifier receives one pure state of the form
$\rho^{A_{1}\cdots A_{N}}=|\Psi_{i}\rangle\\!\langle\Psi_{i}|^{\otimes N}$ for
some $i\in[M]$ then every post-measurement state is pure, i.e.,
$\rho_{\bm{x}}^{A_{N}}=|\Psi_{i}\rangle\\!\langle\Psi_{i}|$ and Inequality (9)
implies
$\mathbb{P}_{\bm{x}}\left[\left|\mu_{i}-1\right|\leq\varepsilon/2\right]=\mathbb{P}_{\bm{x}}\left[\left|\mu_{i}-\mathrm{Tr}\left[|\Psi_{i}\rangle\\!\langle\Psi_{i}|\rho_{\bm{x}}^{A_{N}}\right]\right|\leq\varepsilon/2\right]\geq
1-\delta$. Hence the algorithm accepts with a probability
$\mathbb{P}\left[\mathcal{B}(\rho)=0\right]\geq\mathbb{P}\left[\mu_{i}\geq
1-\varepsilon/2\right]\geq 1-\delta$. Observe that for this algorithm, we can
even relax the assumption that the input state is i.i.d.. For instance, we can
only ask that the input state is product $\rho^{A_{1}\cdots
A_{N}}=\bigotimes_{t=1}^{N}\sigma_{t}$ where for all $t\in[N]$,
$\langle\Psi_{i}|\sigma_{t}|\Psi_{i}\rangle\geq 1-\varepsilon/4$.

  2. 2.

Soundness. Here, we want to prove the following:

$\mathbb{P}_{\bm{x}}\left[\mathcal{B}\left(\rho^{A_{1}\cdots
A_{N}}\right)=0\,,\;\forall
i\in[M]:\langle\Psi_{i}|\rho_{\bm{x}}^{A_{N}}|\Psi_{i}\rangle<1-\varepsilon\right]\leq\delta.$

If $\mathcal{B}(\rho)=0$ then for some $j\in[M]$ we have $\mu_{j}\geq
1-\varepsilon/2$. Hence
$\langle\Psi_{j}|\rho_{\bm{x}}^{A_{N}}|\Psi_{j}\rangle<1-\varepsilon\Rightarrow\langle\Psi_{j}|\rho_{\bm{x}}^{A_{N}}|\Psi_{j}\rangle<\mu_{j}-\varepsilon/2$
therefore:

$\displaystyle\mathbb{P}_{\bm{x}}\left[\mathcal{B}\left(\rho^{A_{1}\cdots
A_{N}}\right)=0\,,\;\forall
i\in[M]:\langle\Psi_{i}|\rho_{\bm{x}}^{A_{N}}|\Psi_{i}\rangle<1-\varepsilon\right]$
$\displaystyle\leq\mathbb{P}_{\bm{x}}\left[\exists j\in[M]:\mu_{j}\geq
1-\varepsilon/2\,,\;\langle\Psi_{j}|\rho_{\bm{x}}^{A_{N}}|\Psi_{j}\rangle<1-\varepsilon\right]$
$\displaystyle\leq\mathbb{P}_{\bm{x}}\left[\exists
j\in[M]:\langle\Psi_{j}|\rho_{\bm{x}}^{A_{N}}|\Psi_{j}\rangle<\mu_{j}-\varepsilon/2\right]$
$\displaystyle\leq\mathbb{P}_{\bm{x}}\left[\exists
j\in[M]:\left|\mu_{j}-\mathrm{Tr}\left[|\Psi_{j}\rangle\\!\langle\Psi_{j}|\rho_{\bm{x}}^{A_{N}}\right]\right|>\varepsilon/2\right]$
$\displaystyle\leq\delta$

where we used Inequality (9).

∎

The above result uses Clifford measurements, which are non-local. If our
primary concern lies in verification with _local_ measurements, an alternative
approach would be to apply the non-i.i.d. shadow tomography result for local
measurements (proposition 5.4). Using the same analysis of this section, we
can prove the following proposition.

######  Proposition 5.6 (Verification of pure states in the non-i.i.d.
setting–Pauli).

Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation invariant state. Let
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ be $M$ pure
states. There is an algorithm using local (pauli) measurements for verifying
whether the (post-measurement) state $\rho^{A_{N}}$ is a member of
$\\{|\Psi_{i}\rangle\\!\langle\Psi_{i}|\\}_{1\leq i\leq M}$ or is at least
$\varepsilon$-far from them in terms of fidelity with a probability at least
$1-\delta$ and a number of copies satisfying

$\displaystyle
N=\mathcal{O}\left(\frac{n^{3}2^{4n}\log^{2}(M/\delta)\log^{2}(\log(M)/\varepsilon\delta)}{\delta^{2}\varepsilon^{6}}\right).$

#### Comparison with previous works on verification pure states.

The main contribution here compared to previous results is that we give the
first explicit protocol which works for all multipartite states. This stands
in contrast to previous protocols where the desired state must be a ground
state of a Hamiltonian satisfying certain conditions [32] or a graph state
[28, 40, 67, 72], or Dicke states [42]. However, the more efficient protocol
uses Clifford measurements, which are non-local. The Pauli measurement case is
local, but comes at a cost in scaling with number of systems.

We now go into more detail regarding the different scalings. The optimal copy
complexity, or scaling for the number of copies required, with the fidelity
error $\varepsilon$, is $1/\varepsilon$ [41, 42]. The scaling with the number
of systems $n$ depends on the protocol (e.g. for stabiliser states there are
protocols that do not scale with $n$, but know protocols for the W state
scales with $n$ [42]). Applying our results using Clifford (i.e. entangled
over the systems) gives scaling with $\varepsilon$ and $n$ as
$\tilde{\mathcal{O}}(n/\varepsilon^{6})$, and for random local Pauli scaling
(local) the scaling is $\tilde{\mathcal{O}}(n^{3}16^{n}/\varepsilon^{6})$. For
the Clifford protocol, then, we have similar scaling to optimal known for W
states (though with $\varepsilon$ scaling as $1/\varepsilon^{6}$ instead of
$1/\varepsilon$), but our protocol works for all states. The cost here is that
measurements are in non-local across each copy. However for certain
applications this is not an issue. For example verifying output of
computations, Clifford are reasonably within the sets of ‘easy’ gates, so we
have a close to optimal verification for all states that can be implemented.
In the case of random Paulis, where measurements are local on copies, we have
the same scaling with $\varepsilon$ but we get an exponential penalty of $n$
scaling in the error. Given the generality of our protocol to all states
though, it is perhaps not so surprising that we have a high dimensional cost.
Furthermore, depending on the situation, this scaling may not be the major
cost one cares about. Indeed, for small networks dimension will not be the
most relevant scaling. We can imagine many applications in this regime, for
example small networks of sensors [20, 66], or small highly secure
communication networks.

We also point out that we have not optimised over these numbers (rather we
were concerned with showing something that works for all states). It is highly
likely that these complexities can be improved and we expect that for
particular families of states one can find variants where the scaling in the
number of systems is polynomial or better. One perspective in this direction
coming directly from our results, is the observation that the protocols in the
framework of [31], which assume i.i.d. states, use random i.i.d. measurements,
therefore our theorem allows them to be applied directly to the non-i.i.d.
case. This allows us to take any protocol assuming i.i.d. states, and it works
for general (non-i.i.d.) sources with a small cost.

Lastly, our formulation is naturally robust to noise. Such robustness is an
important issue for any practical implementation, and indeed it has been
addressed for several of the protocols mentioned, for example [25, 40, 50,
72]. In terms of the completeness condition, we can easily make out statements
robust to noise. For instance, we can relax the requirement to only ask that
the input state is a product state $\rho^{A_{1}\cdots
A_{N}}=\bigotimes_{t=1}^{N}\sigma_{t}$ where for all $t\in[N]$,
$\langle\Psi_{i}|\sigma_{t}|\Psi_{i}\rangle\geq 1-\varepsilon/4$.

###  5.3 Fidelity estimation

The problem of direct fidelity estimation [15] consists of estimating the
fidelity $\langle\Psi|\rho|\Psi\rangle$ between the target known pure state
$|\Psi\rangle\\!\langle\Psi|$ and the unknown quantum state $\rho$ by
measuring independent copies of $\rho$. The algorithm of [15] proceeds by
sampling i.i.d. random Pauli matrices

$P_{1},\dots,P_{l}\sim\left\\{\frac{\langle\Psi|P|\Psi\rangle^{2}}{d}\right\\}_{P\in\\{\mathbb{I},X,Y,Z\\}^{\otimes
n}}$

where $l=\left\lceil 1/(\varepsilon^{2}\delta)\right\rceil$. Then for each
$i=1,\dots,l$, the algorithm measures the state $\rho$ with the POVM
$\mathcal{M}_{P_{i}}=\left\\{\frac{\mathbb{I}-P_{i}}{2},\frac{\mathbb{I}+P_{i}}{2}\right\\}$
$m_{i}$ times where $m_{i}$ is defined as

$\displaystyle
m_{i}=\left\lceil\frac{2\log(2/\delta)\delta}{\langle\Psi|P_{i}|\Psi\rangle^{2}}\right\rceil.$

The algorithm observes
$A_{i,j}\sim\left\\{\frac{1-\mathrm{Tr}\left[P_{i}\rho\right]}{2},\frac{1+\mathrm{Tr}\left[P_{i}\rho\right]}{2}\right\\}$
where $i\in\\{1,\dots,l\\}$ and $j\in\\{1,\dots,m_{i}\\}$. The estimator of
the fidelity is then given as follows

$\displaystyle
S=\frac{1}{l}\sum_{i=1}^{l}\frac{1}{m_{i}\langle\Psi|P_{i}|\Psi\rangle}\sum_{j=1}^{m_{i}}(2A_{i,j}-1).$

In general, [15] proved that the copy complexity satisfies:

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{l}m_{i}\right]\leq\left(1+\frac{12}{\varepsilon^{2}}+\frac{2d}{\varepsilon^{2}}\log(24)\right)$

to conclude that $|S-\langle\Psi|\rho|\Psi\rangle|\leq 2\varepsilon$ with
probability at least $5/6$. This algorithm is non-adaptive and performs
independent measurements from the set:

$\displaystyle\mathcal{M}_{P_{1},\dots,P_{l}}=\bigcup_{i=1}^{\left\lceil
12/\varepsilon^{2}\right\rceil}\left\\{\mathcal{M}_{P_{i}}\;\text{repeated}\;\left\lceil\frac{2\log(2/\delta)\delta}{\langle\Psi|P_{i}|\Psi\rangle^{2}}\right\rceil\;\text{times}\right\\}\;\text{where}\;P_{1},\dots,P_{l}\sim\left\\{\frac{\langle\Psi|P|\Psi\rangle^{2}}{d}\right\\}_{P\in\\{\mathbb{I},X,Y,Z\\}^{\otimes
n}}$

To extend this result to the non-i.i.d. setting, we apply Theorem 4.1 with the
set of POVMs $\mathcal{M}_{P_{1},\dots,P_{l}}$ and a copy complexity given by
$k_{\mathcal{A}}=\sum_{i=1}^{l}m_{i}=\sum_{i=1}^{\left\lceil
12/\varepsilon^{2}\right\rceil}\left\lceil\frac{\log(24)}{6\langle\Psi|P_{i}|\Psi\rangle^{2}}\right\rceil$.
Theorem 4.1 ensures that we can estimate the fidelity between the ideal state
$|\Psi\rangle\\!\langle\Psi|$ and the post-measurement state
$\rho^{A_{N}}_{\bm{w}}$ to within $3\varepsilon$ with probability at least
$5/6$ if the total number of copies $N$ satisfies:

$\displaystyle N=\frac{48^{2}\log(d)}{\varepsilon^{2}}\cdot
k_{\mathcal{A}}^{2}\log^{2}(18k_{\mathcal{A}}).$

By Markov’s inequality we have with probability at least $5/6$:

$\displaystyle k_{\mathcal{A}}\leq
6\,\mathbb{E}\left[\sum_{i=1}^{l}m_{i}\right]\leq
6\left(1+\frac{12}{\varepsilon^{2}}+\frac{2d}{\varepsilon^{2}}\log(24)\right)\leq\frac{12^{2}d}{\varepsilon^{2}}.$

Therefore, by the union bound, our non-i.i.d. algorithm is $1/3$-correct and
its complexity satisfies:

$\displaystyle N\leq\frac{48^{2}\cdot 12^{2}d^{2}\log^{2}(18\cdot
12^{2}d/\varepsilon^{2})\log(d)}{\varepsilon^{6}}=\mathcal{O}\left(\frac{d^{2}\log^{3}(d/\varepsilon)}{\varepsilon^{6}}\right).$

######  Proposition 5.7 (Fidelity estimation in the non-i.i.d. setting).

There is an algorithm in the non-i.i.d. setting for fidelity estimation with a
precision parameter $\varepsilon$, a success probability at least $2/3$ and a
copy complexity:

$\displaystyle
N=\mathcal{O}\left(\frac{d^{2}\log^{3}(d/\varepsilon)}{\varepsilon^{6}}\right).$

Moreover, [15] showed that for well-conditioned states
$|\Psi\rangle\\!\langle\Psi|$ satisfying for all
$P\in\\{\mathbb{I},X,Y,Z\\}^{\otimes n}$,
$|\langle\Psi|P|\Psi\rangle|\geq\alpha$ for some $\alpha>0$, the copy
complexity is bounded in expectation as follows:

$\displaystyle\mathbb{E}\left[k_{\mathcal{A}}\right]=\mathbb{E}\left[\sum_{i=1}^{l}m_{i}\right]=\mathcal{O}\left(\frac{\log(12)}{\alpha^{2}\varepsilon^{2}}\right).$

Similarly, by applying Theorem 4.1 and Markov’s inequality we can show the
following proposition.

######  Proposition 5.8 (Fidelity estimation in the non-i.i.d. setting–Well-
conditioned states).

Let $|\Psi\rangle$ be a well-conditioned state with parameter $\alpha>0$.
There is an algorithm in the non-i.i.d. setting for fidelity estimation with a
precision parameter $\varepsilon$, a success probability at least $2/3$ and a
copy complexity:

$\displaystyle
N=\mathcal{O}\left(\frac{\log^{3}(d/\alpha\varepsilon)}{\alpha^{4}\varepsilon^{6}}\right).$

###  5.4 State tomography

In the problem of state tomography, we are given $N$ copies of an unknown
quantum state $\sigma$ and the objective is to construct a (classical
description) of a quantum state $\hat{\sigma}$ satisfying
$\|\sigma-\hat{\sigma}\|_{1}\leq\varepsilon$ with a probability at least
$1-\delta$.

In the i.i.d. setting, a sufficient number of copies for state tomography in
the incoherent setting with a precision $\varepsilon$ and an error probability
$\delta$ is [27]:

$\displaystyle
k_{\mathcal{A}}=\mathcal{O}\left(\frac{d^{2}\log(1/\delta)}{\varepsilon^{2}}+\frac{d^{3}}{\varepsilon^{2}}\right).$

Hence by Theorem 4.1 there is an algorithm $\mathcal{B}$ in the non-i.i.d.
setting with an error probability:

$\displaystyle\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon\right)\leq\sup_{\sigma\,:\;\text{state}}\delta_{\mathcal{A}}\left(k_{\mathcal{A}},\sigma^{\otimes
k_{\mathcal{A}}},\varepsilon/2\right)+k_{\mathcal{A}}e^{-{k}/k_{\mathcal{A}}}+\sqrt{\frac{64k^{2}\log(d)}{N\varepsilon^{2}}}+\sqrt{\frac{4{k^{2}}\log(d)}{N}}$

So a total number of copies sufficient to achieve $\delta$-correctness in the
non-i.i.d. setting is:

$\displaystyle
N=\frac{256k_{\mathcal{A}}^{2}\log^{2}(6k_{\mathcal{A}}/\delta)\log(d)}{\delta^{2}\varepsilon^{2}}=\mathcal{O}\left(\frac{d^{4}\log^{2}(d/\delta\varepsilon)\log^{2}(1/\delta)\log(d)}{\delta^{2}\varepsilon^{6}}+\frac{d^{6}\log^{2}(d/\delta\varepsilon)\log(d)}{\delta^{2}\varepsilon^{6}}\right).$

######  Proposition 5.9 (State tomography in the non-i.i.d. setting).

There is an algorithm in the non-i.i.d. setting for state tomography with a
precision parameter $\varepsilon$, a success probability at least $1-\delta$
and a copy complexity:

$\displaystyle
N=\mathcal{O}\left(\frac{d^{4}\log^{5}(d/\delta\varepsilon)}{\delta^{2}\varepsilon^{6}}+\frac{d^{6}\log^{3}(d/\delta\varepsilon)}{\delta^{2}\varepsilon^{6}}\right).$

Observe that, unlike the statement of state tomography in the i.i.d. setting
[27], here we do not have an explicit dependency on the rank of the
approximated state. This can be explained by the fact that if the state
$\rho^{A_{1}\cdots A_{N}}$ is not i.i.d. then the post-measurement states
$\\{\rho^{A_{N}}_{\bm{x}}\\}_{\bm{x}}$ can have a full rank even if we start
with a pure input state $\rho^{A_{1}\cdots A_{N}}$. For instance, let
$\rho=|\Psi\rangle\\!\langle\Psi|$ where
$|\Psi\rangle=\frac{1}{\sqrt{d}}\sum_{i\in[d]}|i\rangle\otimes|i\rangle$ is
the maximally entangled state, and let
$X=\sum_{i\in[d]}\alpha_{i}|i\rangle\\!\langle i|$ be an observable. In this
case, we have $\operatorname{rank}\left(\rho^{A_{1}A_{2}}\right)=1$ and
$\operatorname{rank}\left(\rho^{A_{2}}_{\bm{x}}\right)=\operatorname{rank}\left(\sum_{i\in[d]}\frac{\alpha_{i}}{\|\alpha\|_{1}}|i\rangle\\!\langle
i|\right)=d$ if all the coefficients $\\{\alpha_{i}\\}_{i\in[d]}$ are non-
zero.

###  5.5 Testing mixedness of states

In the problem of testing mixedness of states, we are given an unknown quantum
state $\sigma$, which can either be $\frac{\mathbb{I}}{d}$ (null hypothesis)
or $\varepsilon$-far from it in the one-norm (alternate hypothesis). The
objective is to determine the true hypothesis with a probability of at least
$1-\delta$. However, this problem does not satisfy the robustness assumption
required in Definition 2.3. Due to this reason, we introduced the ‘tolerant’
version of this problem in Example 1. To the best of our knowledge, there is
no algorithm for the tolerant testing mixedness problem that outperforms the
tomography algorithm (naive testing by learning approach). Thus, in this
section, we concentrate on the standard (non-tolerant) formulation of testing
mixedness of states.

Under the null hypothesis, we assume that the learning algorithm is given the
i.i.d. state $\rho=\left(\frac{\mathbb{I}}{d}\right)^{\otimes N}$ and is
expected to respond with ‘$0$’ with a probability of at least $1-\delta$. On
the other hand, under the alternate hypothesis, the learning algorithm
receives a (potentially entangled) state $\rho^{A_{1}\cdots A_{N}}$. In this
scenario, the learning algorithm should output ‘$1$’ with a probability of at
least $1-\delta$ if the post-measurement state $\rho^{A_{N}}_{\bm{x}}$ is
$\varepsilon$-far from $\frac{\mathbb{I}}{d}$. In the i.i.d. case, a
sufficient number of copies for testing mixedness of states problem in the
incoherent setting with a precision parameter $\varepsilon$ and an error
probability $\delta$ is given by [43]:

$\displaystyle
k_{\mathcal{A}}=\mathcal{O}\left(\frac{\sqrt{d^{3}}\log(1/\delta)}{\varepsilon^{2}}\right).$

Hence by Theorem 4.1 222We can apply Theorem 4.1 only under the alternate
hypothesis where the robustness assumption holds. Under the null hypothesis,
the robustness assumption no longer holds; however, since we are assuming that
the input state is i.i.d., i.e.,
$\rho=\left(\frac{\mathbb{I}}{d}\right)^{\otimes N}$, we can directly apply
the result from [43] in this case. there is an algorithm $\mathcal{B}$ in the
non-i.i.d. setting with an error probability:

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)\leq\sup_{\sigma\,:\;\text{state}}\delta_{\mathcal{A}}\left(k_{\mathcal{A}},\sigma^{\otimes
k_{\mathcal{A}}},\varepsilon/2\right)+k_{\mathcal{A}}e^{-{k}/k_{\mathcal{A}}}+\sqrt{\frac{64k^{2}\log(d)}{N\varepsilon^{2}}}+\sqrt{\frac{4{k^{2}}\log(d)}{N}}$

So a total number of copies sufficient to achieve $\delta$-correctness in the
non-i.i.d. setting is:

$\displaystyle
N=\frac{256k_{\mathcal{A}}^{2}\log^{2}(6k_{\mathcal{A}}/\delta\varepsilon)\log(d)}{\delta^{2}\varepsilon^{2}}=\mathcal{O}\left(\frac{d^{3}\log^{2}(1/\delta)\log^{2}(d/\delta\varepsilon)\log(d)}{\delta^{2}\varepsilon^{6}}\right).$

######  Proposition 5.10 (Testing mixedness of quantum states in the
non-i.i.d. setting).

There is an algorithm in the non-i.i.d. setting for testing mixedness of
quantum states with a precision parameter $\varepsilon$, a success probability
at least $1-\delta$ and a copy complexity:

$\displaystyle
N=\mathcal{O}\left(\frac{d^{3}\log^{5}(d/\delta\varepsilon)}{\delta^{2}\varepsilon^{6}}\right).$

##  6 General algorithms in the non-i.i.d. setting

In this section, we present a general framework for extending algorithms
designed to learn properties of a quantum state using i.i.d. input states, to
general possibly entangled input states. The distinction from Section 4 lies
in the relaxation of the requirement for algorithms to be non-adaptive;
meaning, they can now involve adaptive measurements, potentially coherent or
entangled (see Definition 2.4). Coherent measurements are proved to be more
powerful than incoherent ones (let alone non-adaptive ones) for tasks such as
state tomography [26, 59], shadow tomography [33, 51, 57] and testing
mixedness of states [34, 58].

As we now consider general algorithms that encompass (possibly) coherent
measurements, a suitable candidate for the measurement device in the
projection phase (the $\bm{w}$ part in Algorithm 1) becomes less clear.
Furthermore, we require an approximation that excels under the more stringent
one-norm condition, particularly when addressing non-local (non product)
observables. To address this challenge, we adopt the approach outlined in
[52], utilizing any informationally complete measurement device. We will use
the measurement device $\mathcal{M}_{\text{dist}}$ having a low distortion
with side information, of [47]. It satisfies the following important property:
the application of the corresponding measurement channel
$\mathcal{M}_{\text{dist}}$ to the system $A_{2}$ does not diminish the
distinguishability between two bipartite states on $A_{1}A_{2}$ by a factor
greater than $2d_{A_{2}}$, wherein $d_{A_{2}}$ represents the dimension of
$A_{2}$. To be precise, the measurement channel $\mathcal{M}_{\text{dist}}$
satisfies the following inequality for all bipartite states
$\rho^{A_{1}A_{2}}$ and $\sigma^{A_{1}A_{2}}$:

$\displaystyle\left\|\rho^{A_{1}A_{2}}-\sigma^{A_{1}A_{2}}\right\|_{1}\leq
2d_{A_{2}}\,\left\|\mathrm{id}^{A_{1}}\otimes\mathcal{M}_{\text{dist}}^{A_{2}}\left(\rho^{A_{1}A_{2}}-\sigma^{A_{1}A_{2}}\right)\right\|_{1}.$

The measurement device $\mathcal{M}_{\text{dist}}$ will play a crucial role in
our algorithm. By applying this channel to a large fraction of the subsystems
of a quantum state, we can show that the post-measurement state behaves as an
i.i.d. state. Thus, we will be able to use the same algorithm on a small
number of the remaining systems.

For a learning algorithm $\mathcal{A}$ designed for i.i.d. inputs, we
construct the algorithm $\mathcal{B}$ explicitly described in Algorithm 2 and
illustrated in Figure 5.

Figure 5: Illustration of Algorithm 2. Algorithm 2 Predicting properties of
quantum states in the non-i.i.d. setting - General algorithms

Measurement $\mathcal{A}:\mathrm{L}(A_{1}\dots
A_{k})\to\mathbb{C}^{\mathcal{P}}$. A permutation invariant state
$\rho^{A_{1}\cdots A_{N}}$.

Adapt the algorithm $\mathcal{A}$ to non-i.i.d. inputs $\rho^{A_{1}\cdots
A_{N}}$.

Run algorithm $\mathcal{A}$ on systems $A_{1}\dots A_{k}$ and obtain outcome
$p\leftarrow\mathcal{A}(\rho)$

Sample $l\sim\operatorname{Unif}\\{k+1,\dots,k+\frac{N}{2}\\}$

Apply $\mathcal{M}_{\text{dist}}$ to each system $A_{k+1}$ to $A_{l}$ and
obtain outcome
$\bm{w}\leftarrow\mathcal{M}_{\text{dist}}^{\otimes(l-k)}(\rho)$

return $(l,\bm{w},p)$.

In the following theorem, we relate the error probability of Algorithm 2 with
the error probability of the algorithm $\mathcal{A}$.

######  Theorem 6.1 (General algorithms in the non-i.i.d. setting).

Let $\varepsilon,\varepsilon^{\prime}>0$ and $1\leq k<N/2$. Let $\mathcal{A}$
be a general algorithm. Algorithm 2 has an error probability satisfying:

$\displaystyle\delta_{\mathcal{B}}\left(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon+\varepsilon^{\prime}\right)$
$\displaystyle\leq\sup_{l,\bm{w}}\delta_{\mathcal{A}}\left(k,\left(\rho^{A_{N}}_{l,\bm{w}}\right)^{\otimes
k},\varepsilon\right)+12\sqrt{\frac{2k^{3}d^{2}\log(d)}{N\varepsilon^{\prime
2}}}+2\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}}.$

######  Remark 6.2.

To achieve an error probability of at most $\delta$, one could start by
determining a value for $k(\mathcal{A},\delta,\varepsilon)$ such that for all
$\bm{w}$, $\delta_{\mathcal{A}}\left(k,(\rho^{A_{N}}_{\bm{w}})^{\otimes
k},\varepsilon/2\right)\leq\delta/2$. Subsequently, the total number of copies
can be set to

$N=\frac{32\cdot 14^{2}d^{2}\log(d)}{\delta^{2}\varepsilon^{2}}\cdot
k(\mathcal{A},\delta,\varepsilon)^{3}.$

By doing this, we can ensure that $\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon)\leq\delta$.

In what follows we proceed to prove Theorem 6.1.

###### Proof of Theorem 6.1.

First, since we are using the informationally complete measurement device
$\mathcal{M}_{\text{dist}}$, we can relate the difference between post-
measurement states and the actual states. This along with an information
theoretical analysis using the mutual information show that measuring using
$\mathcal{M}_{\text{dist}}$ a sufficiently large number of times, transforms
the state approximately to an i.i.d. one. Infact, the proof of Theorem 2.4. of
[52] together with the distortion with side information measurement device
$\mathcal{M}_{\text{dist}}$ of [47] imply that for $k<N/2$:

######  Lemma 6.3 ([52], rephrased).

Let $\rho^{A_{1}\cdots A_{N}}$ be a permutation invariant state. For $k<N/2$,
we have

$\displaystyle\frac{2}{N}\sum_{l=k+1}^{k+N/2}\mathbb{E}_{w_{k+1},\dots,w_{l}}\left[\left\|\rho_{\bm{w}}^{A_{1}\cdots
A_{k}}-\left(\rho_{\bm{w}}^{A_{N}}\right)^{\otimes k}\right\|_{1}\right]\leq
2\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}}.$

where $\bm{w}=(w_{k+1},\dots,w_{l})$ is the outcome of measuring each of the
systems $A_{k+1}\dots A_{l}$ with the measurement $\mathcal{M}_{\text{dist}}$.

We write the error probability as

$\displaystyle\delta_{\mathcal{B}}(N,\rho^{A_{1}\cdots
A_{N}},\varepsilon+\varepsilon^{\prime})$
$\displaystyle=\mathbb{P}_{l,\bm{w},p}\left[(p,\rho^{A_{N}}_{l,\bm{w},p})\not\in\text{SUCCESS}_{\varepsilon+\varepsilon^{\prime}}\right]$
$\displaystyle=\mathbb{P}_{l,\bm{w},p}\left[(p,\rho^{A_{N}}_{l,\bm{w},p})\not\in\text{SUCCESS}_{\varepsilon+\varepsilon^{\prime}},\|\rho^{A_{N}}_{l,\bm{w},p}-\rho^{A_{N}}_{l,\bm{w}}\|_{1}\leq\varepsilon^{\prime}\right]$
$\displaystyle\quad+\mathbb{P}_{l,\bm{w},p}\left[(p,\rho^{A_{N}}_{l,\bm{w},p})\not\in\text{SUCCESS}_{\varepsilon+\varepsilon^{\prime}},\|\rho^{A_{N}}_{l,\bm{w},p}-\rho^{A_{N}}_{l,\bm{w}}\|_{1}>\varepsilon^{\prime}\right]$
$\displaystyle\leq\mathbb{P}_{l,\bm{w},p}\left[(p,\rho^{A_{N}}_{l,\bm{w}})\not\in\text{SUCCESS}_{\varepsilon}\right]+\mathbb{P}_{l,\bm{w},p}\left[\|\rho^{A_{N}}_{l,\bm{w},p}-\rho^{A_{N}}_{l,\bm{w}}\|_{1}>\varepsilon^{\prime}\right],$
(10)

where we use the robustness condition. Using Lemma 6.3 and the triangle
inequality, the first term can be bounded as follows:

$\displaystyle\mathbb{P}_{l,(p,\bm{w})\sim(\mathcal{A}\otimes\mathcal{M}_{\text{dist}}^{\otimes(l-k)})(\rho^{A_{1}\dots
A_{l}})}\left[(p,\rho^{A_{N}}_{l,\bm{w}})\not\in\text{SUCCESS}_{\varepsilon}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{A}(\rho_{l,\bm{w}}^{A_{1}\dots
A_{k}})}\left[(p,\rho^{A_{N}}_{l,\bm{w}})\not\in\text{SUCCESS}_{\varepsilon}\right]\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{w}}\left[\mathbb{P}_{p\sim\mathcal{A}\left((\rho_{l,\bm{w}}^{A_{N}})^{\otimes
k}\right)}\left[(p,\rho^{A_{N}}_{l,\bm{w}})\not\in\text{SUCCESS}_{\varepsilon}\right]\right]+2\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}}$
$\displaystyle\leq\sup_{l,\bm{w}}\delta_{\mathcal{A}}\left(k,\left(\rho_{l,\bm{w}}^{A_{N}}\right)^{\otimes
k},\varepsilon\right)+2\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}}$

For the second term of (10), we apply the following lemma:

######  Lemma 6.4.

Let $\varepsilon^{\prime}>0$, $1\leq k<N/2$ and
$l\sim\operatorname{Unif}\\{k+1,\dots,k+N/2\\}$. Let
$\bm{w}=(w_{k+1},\dots,w_{l})$ and $p$ be the outcomes of measuring the state
$\rho$ with the measurement $\mathcal{M}_{\text{dist}}^{\otimes(l-k)}$ on
systems $A_{k+1}\dots A_{l}$ and $\mathcal{A}$ on $A_{1}\dots A_{k}$. The
following inequality holds:

$\displaystyle\mathbb{P}_{l,\bm{w},p}\left[\|\rho_{l,\bm{w},p}^{A_{N}}-\rho^{A_{N}}_{l,\bm{w}}\|_{1}>\varepsilon^{\prime}\right]\leq
12\sqrt{\frac{2k^{3}d^{2}\log(d)}{N\varepsilon^{\prime 2}}}.$

###### Proof.

Denote by $\\{M_{p}\\}_{p}$ the elements of POVM corresponding to
$\mathcal{A}$. Lemma 6.3 together with the triangle inequality imply:

$\displaystyle\mathbb{E}_{l,\bm{w},p}\left[\|\rho_{l,\bm{w},p}^{A_{N}}-\rho^{A_{N}}_{l,\bm{w}}\|_{1}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\left\|\rho_{l,\bm{w},p}^{A_{N}}-\rho_{l,\bm{w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\left\|\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\rho_{l,\bm{w},p}^{A_{N}}-\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\rho_{l,\bm{w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle\leq\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\left\|\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\rho_{l,\bm{w},p}^{A_{N}}-\mathrm{Tr}\left[M_{p}(\rho_{l,\bm{w}}^{A_{N}})^{\otimes
k}\right]\rho_{l,\bm{w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle\quad+\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\left\|\mathrm{Tr}\left[M_{p}(\rho_{l,\bm{w}}^{A_{N}})^{\otimes
k}\right]\rho_{l,\bm{w}}^{A_{N}}-\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\rho_{l,\bm{w}}^{A_{N}}\right\|_{1}\right]$
$\displaystyle=\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\left\|\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[M_{p}\otimes\mathbb{I}\left(\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{w}}^{A_{N}}\right)^{\otimes
k+1}\right)\right]\right\|_{1}\right]$
$\displaystyle\quad+\mathbb{E}_{l,\bm{w}}\left[\sum_{p}\left|\mathrm{Tr}\left[M_{p}(\rho_{l,\bm{w}}^{A_{N}})^{\otimes
k}\right]-\mathrm{Tr}\left[M_{p}\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k}}\right]\right|\right]$ $\displaystyle\leq
2\,\mathbb{E}_{l,\bm{w}}\left[\left\|\rho_{l,\bm{w}}^{A_{1}\cdots
A_{k+1}}-\left(\rho_{l,\bm{w}}^{A_{N}}\right)^{\otimes
k+1}\right\|_{1}\right]$ $\displaystyle\leq
4\sqrt{\frac{2(k+1)^{3}d^{2}\log(d)}{N}}\leq
12\sqrt{\frac{2k^{3}d^{2}\log(d)}{N}},$

where we used the equality between states $\mathrm{Tr}_{A_{1}\cdots
A_{k}}\left[(M_{p}\otimes\mathbb{I})\rho_{\bm{w}}^{A_{1}\cdots
A_{k+1}}\right]=\mathrm{Tr}\left[M_{p}\rho_{\bm{w}}^{A_{1}\cdots
A_{k}}\right]\rho_{\bm{w},p}^{A_{N}}$ and the inequality
$\sum_{p}\|M_{p}X\|_{1}\leq\sum_{p}\mathrm{Tr}\left[M_{p}|X|\right]=\|X\|_{1}$
as $\sum_{p}M_{p}=\mathbb{I}$. Therefore, by Markov’s inequality we deduce:

$\displaystyle\mathbb{P}_{l,\bm{v},\bm{w}}\left[\|\rho_{\bm{v,w}}^{A_{N}}-\rho^{A_{N}}_{\bm{w}}\|_{1}>\varepsilon^{\prime}\right]\leq\frac{\mathbb{E}_{l,\bm{v,w}}\left[\|\rho_{\bm{v,w}}^{A_{N}}-\rho^{A_{N}}_{\bm{w}}\|_{1}\right]}{\varepsilon^{\prime}}\leq
12\sqrt{\frac{2k^{3}d^{2}\log(d)}{N\varepsilon^{\prime 2}}}.$

∎

∎

## Acknowledgments

We acknowledge support from the European Research Council (ERC Grant AlgoQIP,
Agreement No. 851716), (ERC Grant Agreement No. 948139), from the European
Union’s Horizon 2020 research and innovation programme under Grant Agreement
No 101017733 within the QuantERA II Programme and from the PEPR integrated
project EPiQ ANR-22-PETQ-0007 part of Plan France 2030.
We would like to thank Mario Berta and Philippe Faist for helpful discussions.

## References

  * [1] Bruno De Finetti “Foresight: Its logical laws, its subjective sources” In _Breakthroughs in Statistics: Foundations and Basic Theory_ Springer, 1937, pp. 134–174
  * [2] Robin L Hudson and Graham R Moody “Locally normal symmetric states and an analogue of de Finetti’s theorem” In _Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete_ 33.4 Springer, 1976, pp. 343–351
  * [3] Persi Diaconis and David Freedman “Finite exchangeable sequences” In _The Annals of Probability_ JSTOR, 1980, pp. 745–764
  * [4] Persi Diaconis and David Freedman “A dozen de Finetti-style results in search of a theory” In _Annales de l’IHP Probabilités et statistiques_ 23.S2, 1987, pp. 397–423
  * [5] Daniel Gottesman “Theory of fault-tolerant quantum computation” In _Physical Review A_ 57.1 APS, 1998, pp. 127
  * [6] Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith and Alain Tapp “Authentication of quantum messages” In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ , 2002, pp. 449–458 IEEE
  * [7] Carlton M Caves, Christopher A Fuchs and Rüdiger Schack “Unknown quantum states: the quantum de Finetti representation” In _Journal of Mathematical Physics_ 43.9 American Institute of Physics, 2002, pp. 4537–4559
  * [8] Robert König and Renato Renner “A de Finetti representation for finite symmetric quantum states” In _Journal of Mathematical physics_ 46.12 AIP Publishing, 2005
  * [9] Gilles Brassard, Anne Broadbent, Joseph Fitzsimons, Sébastien Gambs and Alain Tapp “Anonymous quantum communication” In _Advances in Cryptology–ASIACRYPT 2007: 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007. Proceedings 13_ , 2007, pp. 460–473 Springer
  * [10] Matthias Christandl, Robert König, Graeme Mitchison and Renato Renner “One-and-a-half quantum de Finetti theorems” In _Communications in mathematical physics_ 273.2 Springer, 2007, pp. 473–498
  * [11] Maris Ozols “Clifford group” In _Essays at University of Waterloo, Spring_ , 2008
  * [12] Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin and Yi-Kai Liu “Efficient quantum state tomography” In _Nature communications_ 1.1 Nature Publishing Group UK London, 2010, pp. 149
  * [13] Fernando GSL Brandao, Matthias Christandl and Jon Yard “Faithful squashed entanglement” In _Communications in Mathematical Physics_ 306 Springer, 2011, pp. 805–830