# Sample-efficient device-independent quantum state verification and
certification

Aleksandra Gočanin  Faculty of Physics, University of Belgrade, Studentski Trg
12-16, 11000 Belgrade, Serbia  Ivan Šupić  CNRS, LIP6, Sorbonne Université, 4
place Jussieu, 75005 Paris, France  Département de Physique Appliquée,
Université de Genève, 1211 Genève, Switzerland  Borivoje Dakić  University of
Vienna, Faculty of Physics, Vienna Center for Quantum Science and Technology,
Boltzmanngasse 5, 1090 Vienna, Austria  Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3,
1090 Vienna, Austria

(August 27, 2024)

###### Abstract

Authentication of quantum sources is a crucial task in building reliable and
efficient protocols for quantum-information processing. Steady progress vis-à-
vis verification of quantum devices in the scenario with fully characterized
measurement devices has been observed in recent years. When it comes to the
scenario with uncharacterized measurements, the so-called black-box scenario,
practical verification methods are still rather scarce. Development of self-
testing methods is an important step forward, but these results so far have
been used for reliable verification only by considering the asymptotic
behavior of large, identically and independently distributed (IID) samples of
a quantum resource. Such strong assumptions deprive the verification procedure
of its truly device-independent character. In this paper, we develop a
systematic approach to device-independent verification of quantum states free
of IID assumptions in the finite copy regime. Remarkably, we show that device-
independent verification can be performed with optimal sample efficiency.
Finally, for the case of independent copies, we develop a device-independent
protocol for quantum state certification: a protocol in which a fragment of
the resource copies is measured to warrant the rest of the copies to be close
to some target state.

##  I Introduction

Entangled states have been identified as a key resource in applications of
quantum technologies, such as quantum communication repeaters , computation
ruv , cryptography Gisin_2002 , and sensing Giovannetti_2011 . Harvesting a
complete quantum advantage demands an increased precision in manufacturing the
relevant components and devices. However, realistic quantum devices are rarely
perfect: they suffer from unavoidable errors, noise or decoherence and in some
cases, they are not trusted. Therefore, characterization and validation play a
central role in real applications of quantum technologies. Verification
techniques have a multifaceted complexity. Complexity is measured in terms of
a minimal number of queries or instances of resource used (sample complexity),
a different number of local measurement settings needed for the procedure
(measurement complexity), quantum computational power needed to prepare
verification circuit (quantum computational complexity), or classical
resources needed to postprocess the verification results (postprocessing
complexity). A compact comparison of different techniques in terms of
complexity can be found in Ref. Eisert_2020 .

Complexity directly depends on required confidence and informativeness
Eisert_2020 ; PRXQuantum.2.010201 : how much of the information we would like
to learn about the underlying system and how certain we want to be about the
result. The required informativeness depends on the application, and usually,
there is a trade-off between informativeness and complexity. Take, for
instance, sampling complexity. A less informative technique is, for example, a
simple entanglement verification guhne2009entanglement ; friis2019entanglement
in which (sample) complexity can be reduced to several copies only Saggio_2019
or even to a logical minimum of a single-copy verification Dimic1 . On the
other hand, fully informative techniques, such as quantum state tomography
Fano ; Leonhardt ; Hradil_1997 ; James_2001 ; Bisio_2009  exhibit exponential
sample complexity. Trading informativeness for complexity results in a
reduction of resources. Somewhere in between low complexity (e.g.,
entanglement verification) and exponential complexity (full tomography), one
finds resource-efficient tasks such as direct fidelity estimation Flammia_2011
and shadow tomography tasks huang2020predicting ; morris2019selective ;
aaronson2019shadow . Another important example is quantum state verification,
which can be achieved with remarkably low sampling complexity PallisterML_2018
; Zhu3 ; Zhu4 . A specific feature of quantum state verification is that all
measurements are local and postprocessing complexity is much lower compared to
that of the tomographic methods. The technique received a lot of attention and
has been applied to construct verification protocols for various classes of
states Dimic1 ; Morimae ; Takeuchi ; Zhu1 ; Zhu2 ; Yu_2019 ; Zhu3 ; Zhu4 ; Liu
. It has also been successfully experimentally implemented in Refs.
zhang2019experimental ; jiang2020towards . This task is the central focus of
our work.

One drawback of the techniques mentioned so far is that they all assume
perfect characterization of all the measurements implemented during the
process. This is inconsistent with a device-independent (DI) scenario in which
all devices, including the measurement ones, are treated as black boxes
colbeck ; pironio2010random ; diqkd ; scarani . Such a paradigm is very useful
in the context of protocols involving any potential adversarial activity. A
prominent candidate for device-independent state verification is the self-
testing method STreview ; MY . However, self-testing conclusions are drawn
from the knowledge of the asymptotic behavior of an experiment, which in
practice invokes the identically and independently distributed (IID)
assumption: IID experimental runs. For this reason, self-testing is more of a
theoretical prerequisite for practical DI quantum state verification. The
literature concerning self-testing usually does not discuss the sample
complexity of the procedure. The finite statistics effects in self-testing in
the non-IID setting are rigorously treated in Ref. JD  on the example of self-
testing the maximally entangled pair of qubits. This is closely related to
conditional estimators of the Bell inequality violation used in the hypothesis
test of local realism without the IID assumption barrett2002quantum ;
gill2001accardi ; zhang2011asymptotically ; bierhorst2015robust ;
elkouss2016nearly . Other examples for taking into account non-IID effects can
be mostly found in the works incorporating self-testing results into protocols
for delegated quantum computing such as Refs. reichardt2013classical ;
gheorghiu2017rigidity ; coladangelo2019verifier .

Another downside of verification, in general, is that the measurement process
destroys the quantum resource and the conclusion is made about the resource,
which is fully consumed. This hinders the possibility to use the resource for
other protocols, without invoking further assumptions. A certification
protocol, as we define it, represents a way out: a fragment of copies is
measured and a conclusion is drawn about the remaining copies. Protocols of
this kind have been used for entanglement certification Arnon_Friedman_2019 ,
quantum state verification wu2020efficient , authentication of teleportation
anu , quantum contract signing Yadav_2019 , and single-copy fidelity
certification Zhu3 ; Zhu4 .

In this paper, we develop a systematic way to build practical DI quantum state
verification protocols starting from self-testing results. Our verification
protocol achieves optimal sample efficiency by taking into account the finite
statistics effect and is free of the IID assumption. With our methods, self-
testing tools find direct application even in cryptographic protocols, where
earlier they were deemed inappropriate because of the IID assumption they
invoke. Based on these results we design a DI certification protocol in which
a certificate about the unmeasured copies can be guaranteed based on the DI
verification procedure performed on the measured copies. This is done by
joining together insights from quantum state verification methods with those
native to self-testing, and building a general protocol for sample-efficient
DI quantum state verification and certification.

Figure 1: Comparison of quantum state verification and quantum state
certification. The crucial difference is that the former provides a conclusion
only after completely consuming the resource, while the latter provides a
certificate about the unmeasured resource. For untrusted measurements and the
black box scenario we speak of DI quantum state verification and
certification.
(a) Protocol for quantum state verification. In quantum state verification all
available copies are measured and the sample is verified to be (or not) close
to the target state. (b) Protocol for quantum state certification. In quantum
state certification a part of the sample is measured, and if verified, the
rest of the sample is certified to be (or not) close to the target state.

##  II Preliminaries

In this section, we clarify the terminology and notation and define rigorously
the verification and certification tasks, which will be explained in the next
sections. Furthermore, we introduce appropriate figures of merit.

###  II.1 Verification VS certification

Typically, the terms verification and certification are used interchangeably
in the literature Eisert_2020 . Here, we distinguish these two terms and
associate them to two different tasks. Both tasks refer to the situation in
which specification of certain quantum property is confirmed or refuted.

Quantum verification refers to the task in which a certain property of a
quantum system is checked, i.e., verified. For example, a source emits $N$
copies, and the aim is to confirm or refute that the states of the copies are
to some degree close to the referent state, by performing appropriate
measurements on all of them (Fig. 1(a)). Importantly, all the copies produced
by the source are consumed during the verification process.

Quantum certification refers to the scenario in which a subset of the emitted
copies is measured, but a certificate of some property of the rest, e.g.,
proximity to the target state, can still be invoked. If the certification is
successful, there is a certificate referring to the state of the unmeasured
copies (Fig. 1(b)).

###  II.2 Figures of merit

Verification. In order to quantify the quality of the verification and
certification procedure, one needs to choose an appropriate figure of merit.
The scenario we consider is the following: a source is producing $N$
independent copies of the quantum system
$S=\\{\sigma_{1},\cdots,\sigma_{N}\\}$, where $\sigma_{i}$ is the state of the
$i$th copy. For now, we abandon the assumption that the copies are identical
but still assume that they are independently distributed. The generalizations
to the full non-IID case will follow by the end of the next section. In
general, our goal is to verify and certify whether the source produces the
copies close to some target state ${\lvert\psi\rangle}$. Formally, the aim is
to infer, with some confidence level $1-\delta$, that the average state
fidelity of the states from $S$ with ${\lvert\psi\rangle}$

$F_{\mathrm{av}}(S,\psi)=\frac{1}{N}\sum_{j=1}^{N}{\langle\psi\rvert}\sigma_{j}{\lvert\psi\rangle}$
(1)

is larger than some value $1-\eta$, with $\eta\in(0,1)$.

The closeness of the average state fidelity ensures that any (local)
measurement on the emitted copies will give statistics close to the target
state statistics. To see this, let $\Pi$ be an arbitrary measurement operator,
$\psi={\lvert\psi\rangle\\!\langle\psi\rvert}$ and $||\cdot,\cdot||_{1}$ the
trace distance. The following chain of inequalities holds:

$\displaystyle\frac{1}{N}\sum_{j=1}^{N}\textrm{Tr}\left[\Pi(\sigma_{j}-\psi)\right]$
$\displaystyle\leq\frac{1}{N}\sum_{j=1}^{N}||\psi,\sigma_{j}||_{1}$
$\displaystyle\leq\frac{1}{N}\sum_{j=1}^{N}\sqrt{1-F(\psi,\sigma_{j})}$
$\displaystyle\leq\sqrt{1-F_{\mathrm{av}}(S,\psi)}.$

The first inequality is the property of the trace distance, while the second
follows from the relation between trace distance and fidelity bible . The last
line is obtained by using Jensen’s inequality. From these bounds, we see that
the average mean is close to the target mean value for arbitrary measurement.
Consequently, we know from the Chernoff bound for independent variables that
sample mean concentrates around the average mean chernoff1952measure ;
hoeffding1994probability , which in turn implies that local measurement on the
sample will give approximately the same statistics as the target state.

However, in a device-independent scenario, one cannot hope to verify fidelity
with some particular state. This is due to the fact that the device-
independent scenario cannot detect potential local isometries, so a pair of
states related by one local isometry can perform equally well in all device-
independent tasks. More details about this are given in the next section. The
figure of merit has to be fidelity optimized over all local isometries applied
to one of the states. In the device-independent literature, this quantity is
called _extractability_ bardyn ; Jed . Formally, it is defined as follows. Let
$\mathscr{H}_{j}$ be a Hilbert space native to the $j$-th emitted state and
let $\mathscr{D}(\mathscr{H}_{j})$ be the set of all density operators on it.
We also define the ancillary Hilbert space $\mathscr{H}_{a}$, which is the
same as the Hilbert space native to the target state, and the set of density
operators on it $\mathscr{D}(\mathscr{H}_{a})$. Consider a state the source
emits in $j$-th round $\sigma_{j}\in\mathscr{D}(\mathscr{H}_{j})$, an
arbitrary local isometriy
$\Phi:\mathscr{D}(\mathscr{H}_{j})\longrightarrow\mathscr{D}(\mathscr{H}_{j}\otimes\mathscr{H}_{a})$
and a target state $\psi\in\mathscr{D}(\mathscr{H}_{a})$. Then the
extractability of $\psi$ from $\sigma_{j}$ 111The standard terminology is
‘extractability of the target state from the physical state’. When it is clear
from the context what is the target state we will use simply ‘extractability’.
is given by

$\Xi(\sigma_{j},\psi)=\max_{\Phi}F\left(\textrm{Tr}_{j}\left[\Phi(\sigma_{j})\right],\psi\right).$
(2)

For a sequence of states $S=\\{\sigma_{1},\cdots,\sigma_{N}\\}$ we define the
average extractability of $\psi$ from $S$ as

$\bar{\Xi}(S,\psi){\stackrel{{\scriptstyle\textrm{def}}}{{=}}}\frac{1}{N}\sum_{j=1}^{N}\Xi(\sigma_{j},\psi).$
(3)

For all practical purposes, the extractability is DI equivalent of fidelity,
as in a device-dependent scenario, it simply reduces to fidelity. As we
commented above, if some state has high fidelity with a given pure target
state it means that performing an arbitrary measurement on these two states
results in approximately the same statistics. High extractability of the
target state from the physical state means that there is an isometry bringing
the physical state close to the target state. This isometry has to be taken
into account when comparing the measurement statistics, i.e., the statistics
obtained by applying an arbitrary measurement to the target state will be
approximately the same as the statistics obtained when the image under the
inverse isometry of that same measurement is applied to the physical state
222Note that we can talk about inverse isometry only if the isometry is
bijection, hence the statement made here is valid only for bijective
isometries. In practice, local isometries used in self-testing are bijections,
more precisely they can be seen as local unitaries mapping the physical state
in tensor product with a set of ancillas to the target state in a tensor
product with some junk state..

Certification. In the certification process, the source produces the set of
independent states $S=\\{\sigma_{1},\cdots,\sigma_{N}\\}$. A fraction
$N_{1}\approx\mu N$, is randomly chosen to be measured, where $\mu$ is the
probability for one copy to be measured. Let us denote the set of labels of
measured copies with $I$ and the corresponding set of states with
$S_{v}=\\{\sigma_{i}|i\in I\\}$. The remaining $N_{2}=N-N_{1}$ copies, we
label with $J$, and they are preserved as certificate
$S_{c}=\\{\sigma_{j}|j\in J\\}$. We perform the verification task on $S_{v}$
and if the test passes we certify (with certain confidence) that $S_{c}$ has
the average fidelity with the target state

$\bar{F}_{\mathrm{cer}}(S_{c},\psi)=\frac{1}{N_{2}}\sum_{j\in
J}{\langle\psi\rvert}\sigma_{j}{\lvert\psi\rangle},$ (4)

higher than some value $1-\eta$. To adapt this figure of merit to the device-
independent scenario we optimize it over all local isometries and obtain the
average extractability of the target state from the remaining copies:

$\bar{\Xi}_{\mathrm{cer}}(S_{c},\psi)=\frac{1}{N_{2}}\sum_{j\in
J}\Xi(\sigma_{j},\psi).$ (5)

So, device-independent certification aims to show that if a test we make
passes, the average extractability of the target state from the unmeasured
copies must be higher than some value with a given confidence level.

Non-IID case. Up to now, we assumed that the copies produced by the source are
mutually independent, i.e., there are no correlations among them. To indicate
how correlations can hinder the verification process, let us consider the
source that over $N$ rounds produces the full state
$0.5{\lvert\psi\rangle\\!\langle\psi\rvert}^{\otimes N}+0.5\chi^{\otimes N}$,
where ${\lvert\psi\rangle}$ is the target state and $\chi$ is some separable
state with very low fidelity with $\psi$. Such a source is not reliable as it
has a $50\%$ chance to produce a "bad" state in all rounds. In an actual
experiment the source would emit either the sequence
$\\{{\lvert\psi\rangle},\cdots,{\lvert\psi\rangle}\\}$ or the sequence
$\\{\chi,\cdots,\chi\\}$. The first one would pass all verification tests, and
based on such a test one might wrongly conclude that the source is good. To
circumvent this behavior of non-IID sources, one way out is to verify not the
correct functionality of the source, but the sequence generated in the
specific experiment. To formalize the former, one introduces conditional
states that actually correctly capture the above example. Of course, one may
potentially formalize non-IIDness in a different way, unfortunately there is
not much literature on this topic and this is left for future considerations.

In this work, we adhere to the idea of conditional fidelity, introduced in
Ref. JD . With the aid of the techniques introduced there we can consider the
verification process also in the case when the full state produced by the
source $\sigma^{N}$ is correlated, or even entangled. In that case, in every
round we consider the conditional state

${\tilde{\sigma}_{j}=\frac{1}{p_{1,\cdots,j-1}}\textrm{Tr}_{1,\cdots,j-1,j+1,\cdots,N}[(\otimes_{k=1}^{j-1}M_{\mathbf{o}_{k}|\mathbf{i}_{k}})\sigma^{N}],}$
(6)

where $M_{o_{k}|i_{k}}$ is the measurement performed on the $k$-th copy, while
$p_{1,\cdots,j-1}=\textrm{Tr}[(\otimes_{k=1}^{j-1}M_{\mathbf{o}_{k}|\mathbf{i}_{k}})\sigma^{N}]$.
Thus, the sequence of states
$\tilde{S}=\\{\tilde{\sigma}_{1},\cdots,\tilde{\sigma}_{N}\\}$ consists of
mutually independent copies, and it represents the sequence of states actually
measured in this particular experiment of $N$ runs. The conditional states
trivially encompass the IID and independent case scenario (per definition).
Clearly, they also correctly capture the example provided above, i.e. the test
fails if the “bad” state $\chi^{\otimes N}$ is produced, while the test passes
if the sequence of target states is generated. The figure of merit in this
case is the average conditional fidelity

$\tilde{F}_{\mathrm{cond}}(S,\psi)=\frac{1}{N}\sum_{j=1}^{N}{\langle\psi\rvert}\tilde{\sigma}_{j}{\lvert\psi\rangle}$
(7)

and its device-independent counterpart, the average conditional extractability

$\bar{\Xi}_{\mathrm{cond}}(S,\psi)=\frac{1}{N}\sum_{j=1}^{N}\Xi(\tilde{\sigma}_{j},\psi).$
(8)

Hence, the non-IID verification process at the end returns the average
extractability of the target state ${\lvert\psi\rangle}$ from the sequence of
the conditional states $\tilde{S}$.

In the following sections we design the first general protocol for DI quantum
state verification, both in the scenario where different experimental rounds
are independent but not identical, and in the full non-IID scenario. As far as
we know the only rigorous treatment of non-IID and DI quantum state
verification was presented in Ref. JD  for the particular case of maximally
entangled pair of qubits. Our method is general, and can be used to verify any
quantum state that can be self-tested. Concerning the DI quantum state
certification we propose the first protocol in the scenario with independent
experimental rounds, and comment on the conceptual difficulties when it comes
to designing the full non-IID protocol.

##  III A framework for device-independent quantum state verification

In this section, we build the protocol for non-IID quantum state verification.
We start by discussing two main ingredients for the protocol, which are
quantum state verification, Sec. III.1, and self-testing Sec. III.2. Then we
show how they can be used to construct a DI protocol for quantum state
verification and present a few case studies.

###  III.1 Quantum state verification

_Independent copies._ In this section, we recall the framework for quantum
state verification pallister_2018 ; PallisterML_2018 ; Zhu3 ; Zhu4 . The aim
is to verify that an uncharacterized source is producing the target state
$\sigma={\lvert\psi\rangle\\!\langle\psi\rvert}$ by using only local
measurements. Here, the source is assumed to produce a sequence of mutually
independent copies $S=\\{\sigma_{1},\cdots,\sigma_{N}\\}$.

The verification procedure consists of performing fully characterized
measurements on the copies produced by the source. The measurement strategy
$\Omega$, thus consists of $l$ different binary local measurements
$\\{M_{o|i}\\}$, where measurement settings are labeled with
$i\in\\{1,\cdots,l\\}$ and outputs with $o\in\\{0,1\\}$. In the $j$th round, a
label $i$ is randomly sampled and the corresponding measurement is applied to
the state $\sigma_{j}$. We say that the state $\sigma_{j}$ has passed the
round if it returned the output $o=1$. Otherwise, we say it failed. The first
time a round fails, the process is aborted. The measurements are chosen to be
such that ${\lvert\psi\rangle\\!\langle\psi\rvert}$ is the only state with
${\langle\psi\rvert}M_{1|i}{\lvert\psi\rangle}=1$ for all $i=1,\cdots,l$. In
other words, only the target state has $100\%$ chance to successfully pass all
the rounds. If all $N$ rounds are passed we verify with certain confidence
level $1-\delta$ that the average fidelity $F_{\mathrm{av}}(S,\psi)$, defined
in Eq. (1), must be higher than some value $1-\eta$:

$F_{\mathrm{av}}(S,\psi)>1-\eta.$ (9)

The analysis is based on finding the second-largest eigenvalue of the strategy
operator $\hat{\Omega}=\sum_{i}p_{i}M_{1|i}$, where $p$ usually corresponds to
a uniform distribution. The largest eigenvalue of $\hat{\Omega}$ is $1$ and
the corresponding eigenvector is ${\lvert\psi\rangle\\!\langle\psi\rvert}$. Of
all states $\rho$ with ${\langle\psi\rvert}\rho{\lvert\psi\rangle}=1-\eta$,
the highest average probability to pass a randomly chosen round has the state
$(1-\eta){\lvert\psi\rangle\\!\langle\psi\rvert}+\eta{\lvert\psi^{\prime}\rangle\\!\langle\psi^{\prime}\rvert}$,
where ${\lvert\psi^{\prime}\rangle}$ is the eigenvector of $\hat{\Omega}$
associated to the second-largest eigenvalue $1-\nu(\Omega)$ [here
$\nu(\Omega)$ is defined as the gap between the largest and the second largest
eigenvalue of $\hat{\Omega}$] , resulting in the probability of
$1-\eta\nu(\Omega)$ to pass the round in the best case. Thus, for $N$ rounds,
the best strategy is achieved when all states have exactly the same fidelity
with ${\lvert\psi\rangle}$ Zhu3  resulting in overall success probability
$[1-\eta\nu(\Omega)]^{N}$. Our aim is to confirm that the average fidelity of
the states from $S$ with ${\lvert\psi\rangle}$ is larger than $1-\eta$. Hence,
to verify the target state with the confidence level $1-\delta$,

$N\geq{\frac{\ln{\delta}}{\ln[1-\eta\nu(\Omega)]}}\approx\frac{1}{\eta\nu(\Omega)}\ln\delta^{-1},$
(10)

which scales as $N=O[1/\nu(\Omega)\eta]$.

Note that the efficiency of the procedure depends on the spectral gap of the
strategy operator $\hat{\Omega}$. In theory, the largest gap is equal to $1$,
in which case the strategy consists of a single measurement
${{\lvert\psi\rangle\\!\langle\psi\rvert},1-{\lvert\psi\rangle\\!\langle\psi\rvert}}$,
and for which one gets optimal scaling of $N=O(1/\eta)$. However, such a
measurement is entangled whenever ${\lvert\psi\rangle}$ is, and for the sake
of experimental simplicity, one of the requirements of the protocol is that
the strategy involves only local measurements. Surprisingly, Eq. (10) shows
that in certain cases we can achieve the same optimal scaling for local
strategies (up to a constant factor). One can generalize the procedure to
nonperfect strategies characterized by the strategy operator $\hat{\Omega}$,
such that $\textrm{Tr}[\hat{\Omega}\psi]<1$ and obtain quadratically worse
scaling pallister_2018 . In that case, the procedure does not halt the first
time a round is failed. After $N$ rounds the lower bound of the average
fidelity is estimated based on the frequency of the successful rounds. This is
particularly important for creating DI verification protocols, as for some
states there are no self-tests that can be phrased as tasks passed by the
target state with maximum probability. In this case, we get quadratically
worst scaling of the number of copies ${O}(1/\eta^{2})$, which we call
suboptimal scaling, but still efficient in terms of resources.

_Non-IID case._ Until now, adapting the quantum verification procedure to a
non-IID scenario has not received a lot of attention. So far, recent work Zhu3
presented the method for building verification protocols adapted to such a
scenario, starting from an already existing one for the independent copies
Zhu4 . In their work, authors construct a non-IID protocol in which measuring
$N-1$ copies allows the fidelity certificate for the remaining unmeasured one
to be proved. This procedure is discussed in more details in Sec. IV. In our
work, we implement a DI scenario and go beyond one-copy certification with the
goal to certify an asymptotically large number of copies $O(N)$.

###  III.2 Self-testing

Self-testing is the only known device-independent verification procedure MY ;
STreview . It aims to verify that a source is producing a certain target state
${{\lvert\psi\rangle}}$. The state actually produced by the source is called
the physical state and the applied measurements are termed physical
measurements. The key aspect of self-testing is device-independence: local
measurements are not characterized, nor trusted. All devices are treated as
black boxes. Different parties, sharing a multipartite state ${\sigma}$ are
spatially separated and noncommunicating. Each party queries their box with
classical input $i$, denoting the measurement choice, and the boxes return
classical output $o$. Usually, the sources are assumed to be IID. Therefore,
by repeating the measurement process for many rounds the parties can estimate
the probabilities of obtaining the set of outputs $o_{1},o_{2},\cdots,o_{n}$
when the set of inputs is $i_{1},i_{2},\cdots,i_{n}$:

$\\{p(o_{1},o_{2},\cdots,o_{n}|i_{1},i_{2},\cdots,i_{n})\\}$

The set of probabilities is usually termed, simply, correlations. Assuming the
correctness of quantum mechanics, the correlations are related to the physical
state and measurements through the Born rule:

$p(o_{1},o_{2},\cdots,o_{n}|i_{1},i_{2},\cdots,i_{n})=\textrm{Tr}\left[\bigotimes_{j=1}^{n}M_{o_{j}|i_{j}}\sigma\right].$
(11)

As all information is drawn only from the correlation probabilities it is
impossible to verify the exact form of the physical state. Indeed, certain
transformations such as simultaneous local rotations of the state and
measurements, or embedding in Hilbert spaces of larger dimension, leave the
observed probabilities unchanged. These transformations are captured by the
notion of local isometries, and the best one can hope for is to verify that a
local isometry maps the physical state to the target one. If such local
isometry exists one says that the physical and the target state are
equivalent. Rigorously written, the states
$\sigma\in\mathscr{D}(\mathscr{H}^{\prime})$ and
${\psi}\in\mathscr{D}(\mathscr{H})$ are equivalent if there exists a local
isometry
$\Phi:\mathscr{D}(\mathscr{H}^{\prime})\longrightarrow\mathscr{D}(\mathscr{H}^{\prime}\otimes\mathscr{H})$
such that

$\Phi(\sigma)=\xi\otimes{\psi}.$ (12)

In some cases, if the observed correlations are the same as the correlations
obtained from the target state, one can infer the equivalence between the
physical and the target state. In general, the self-testing statement does not
need to specify the form of the isometry, but in most cases, the proof is
based on the specific isometry.

One of the bigger challenges on the way towards constructing a self-testing
protocol is to find candidate correlations. Natural candidates are the
correlations reaching the quantum bound of some of Bell’s inequalities:

$b=\sum_{\begin{subarray}{c}o_{1},o_{2}\cdots o_{n}\\\ i_{1},i_{2},\cdots
i_{n}\end{subarray}}\beta_{o_{1},o_{1},\cdots,o_{n}}^{i_{1},i_{2},\cdots,i_{n}}p(o_{1},o_{2},\cdots,o_{n}|i_{1},i_{2},\cdots,i_{n}).$
(13)

The local bound $b_{L}$ is the limit achievable by the correlations compatible
with local hidden variable models. The quantum bound $b_{Q}$ is the maximal
violation achievable by the correlations compatible with quantum theory, i.e.,
those for which there exist measurement operators
$\\{M_{o_{j}|i_{j}}\\}_{j=1}^{n}$ and density matrix $\sigma$, satisfying Eq.
(11). In many cases, the quantum bound can be achieved only by using a
specific state named the target state (up to local isometries), which is the
basis of self-testing.

The simplest and probably the most widely used in self-testing are the
correlations that maximally violate the Clauser-Horn-Shimony-Holt (CHSH)
inequality chsh . It has been proven that two parties can maximally violate
the CHSH inequality only if they apply anticommuting measurements on a
maximally entangled state of two qubits. Thus, the CHSH inequality can be used
to self-test the maximally entangled pair of qubits.

Let us now concentrate on quantum bounds that are also algebraic bounds, i.e.
bounds constrained only by the positivity of observed probabilities. Notably,
for a fixed set of inputs $\mathbf{i}=(i_{1},i_{2},\cdots,i_{n})$, we define
$\beta^{\mathbf{i}}=\max_{o_{1},o_{2},\cdots,o_{n}}\\{\beta_{o_{1},o_{2},\cdots,o_{n}}^{i_{1},i_{2},\cdots,i_{n}}\\}$.
If the quantum bound of the inequality is equal to the algebraic bound, the
probabilities $p(o_{1},o_{2},\cdots,o_{n}|i_{1},i_{2},\cdots,i_{n})$,
associated with coefficients
$\beta_{o_{1},o_{2},\cdots,o_{n}}^{i_{1},i_{2},\cdots,i_{n}}=\beta^{\mathbf{i}}$
have to sum to $1$. Probabilities associated to the coefficients
$\beta_{o_{1},o_{2},\cdots,o_{n}}^{i_{1},i_{2},\cdots,i_{n}}<\beta^{\mathbf{i}}$
are equal to $0$. This holds for all sets of inputs. An example of a Bell
inequality whose quantum bound is equal to the algebraic one and self-tests
the underlying state is the Mermin inequality Mermin . All states maximally
violating it have to be equivalent up to local isometries to the Greenberger-
Horn-Zeilinger (GHZ) state ${\lvert\psi_{GHZ}\rangle}=({\lvert
000\rangle}+{\lvert 111\rangle})/\sqrt{2}$.

A very important aspect of a self-testing procedure is its robustness. Let us
consider a self-test based on the maximal violation of a certain Bell
inequality. The maximal violation is very difficult to reach due to the
unavoidable presence of noise and imperfections. It is desirable that one can
establish a lower bound on the extractability of the target state from the
physical state in the case when maximal violation is not exactly reached.

A self-test is robust if observing violation $b<b_{Q}$ allows putting a lower
bound on the extractability of the target state from the physical one. The
extractability $\Xi(\sigma,{\lvert\psi\rangle})$ of the target state $\psi$
from any state $\sigma$ achieving the Bell violation
$b_{Q}-\tilde{\varepsilon}$ is at least $1-f(\tilde{\varepsilon})$, where $f$
is a function, which depends on the characteristics of the given self-test. As
shown in Ref. Jed , a lower bound to the extractability can always be
represented as a linear function of the Bell violation, i.e., without loss of
generality we take $f(\tilde{\varepsilon})=\tilde{c}\tilde{\varepsilon}$ that
$\tilde{c}$ is a constant. Furthermore, if the isometry $\Phi$ used in the
self-test is optimal, we say that the self-test is _tight_ in terms of
robustness. Such is the self-test of the GHZ state based on the violation of
the Mermin inequality Jed .

###  III.3 Device-independent quantum state verification

The previous two sections gave us all the ingredients for constructing a
protocol for DI quantum state verification. For clarity, we start with the
case where the target state for the self-test achieves the algebraic bound of
the corresponding Bell inequality, and we discuss the general case afterwards.
The verification can be performed in two different setups, i.e., in the case
of independently distributed copies and the case of non-IID source. Both
scenarios aim to construct a DI verification procedure characterized by the
optimal sample efficiency.

Independently distributed copies. As the procedure is DI the aim is to verify
whether the average extractability $\bar{\Xi}(S,\psi)$ of the target state
${\lvert\psi\rangle}$ from the set of states
$S=\\{\sigma_{1},\sigma_{2},...,\sigma_{N}\\}$

$\bar{\Xi}(S,\psi)=\frac{1}{N}\sum_{j=1}^{N}\Xi(\sigma_{j},{\lvert\psi\rangle})$
(14)

is above some value or not. In the language of hypothesis testing, our
hypothesis is the following: the average extractability $\bar{\Xi}(S,\psi)$ of
the target state from $S$ is higher than a given value, and we aim to test it.

The first step is to view the Bell inequality as a procedure in which only the
states equivalent to the target state can pass all rounds, i.e., as a nonlocal
game. For the criteria and procedure to convert a Bell inequality into the
nonlocal game see Ref. Silman . For the set of inputs
$\mathbf{i}=(i_{1},i_{2},\cdots,i_{n})$ let us denote the outputs
corresponding to
$\beta^{\mathbf{i}}=\max_{o_{1},o_{2},\cdots,o_{n}}\\{\beta_{o_{1},o_{2},\cdots,o_{n}}^{i_{1},i_{2},\cdots,i_{n}}\\}$
as the correct outputs, while all the others are denoted as wrong outputs. As
only a state equivalent to the target state is able to maximally violate the
Bell inequality, such a state alone can return the correct outputs for every
set of inputs. This already provides us with contours for a DI verification
procedure. The first time the boxes return a set of wrong outputs the
procedure can be halted, since either the underlying state is not equivalent
to the target state or the measurements performed are not those allowing
construction of a successful verification procedure.

For the second step, we need to estimate the number of copies necessary to
exceed a certain bound on the average extractability. For that purpose let us
look into the robustness bounds. Conversely, the robustness statement (see the
previous section) says that the state $\sigma$ for which there exists isometry
$\Phi$, such that $F[\Phi(\sigma),{\lvert\psi\rangle}]=1-\eta$, and thus
$\Xi(\sigma,\psi)\leq 1-\eta$, at best can achieve the Bell violation
$b_{Q}-\eta/\tilde{c}$, where $\tilde{c}$ is a constant characterizing linear
dependence between extractability and the Bell violation. Furthermore, we
translate the self-test procedure into a binary task, the so-called nonlocal
game, in which local input settings correspond to binary questions queried at
random. The performance is characterized by the percentage of the correct
answers, i.e., the winning probability. Thus, a Bell violation
$b_{Q}-\eta/\tilde{c}$ directly translates to probability of success
$1-\eta/b_{Q}\tilde{c}=1-\eta c$, where we set $c=1/b_{Q}\tilde{c}$ that we
use frequently throughout the text.

Note that, in the case of a nonalgebraic bound, i.e., a Bell inequality with a
gap between quantum and algebraic bound, the maximal probability of success is
$p_{\mathrm{QM}}<1$ ($p_{\mathrm{QM}}$ denotes quantum bound), but relation
remains linear. This establishes a direct relation between extractability and
probability of success in a self-test. Once this is known it is easy to
estimate the number of copies necessary to pass the verification test.

After a more general description, it is instructive to look at a specific
case. The simplest example is the tripartite qubit GHZ state and self-testing
based on Mermin’s inequality Mermin

$\displaystyle\sum$
${}_{o_{1},o_{2},o_{3}}(-1)^{o_{1}+o_{2}+o_{3}}\big{[}p(o_{1},o_{2},o_{3}|0,0,1)+p(o_{1},o_{2},o_{3}|0,1,0)+$
(15) $\displaystyle+$ $\displaystyle
p(o_{1},o_{2},o_{3}|1,0,0)-p(o_{1},o_{2},o_{3}|1,1,1)\big{]}\leq 2.$

Any violation of the Mermin inequality allows a nontrivial conclusion to be
made about the extractability of the GHZ state from the underlying state. In
particular, a state $\sigma_{j}$ achieving violation
$4-\tilde{\varepsilon}_{j}$ has extractability with GHZ higher than
$1-\tilde{\varepsilon}_{j}/c$, where $c=2-\sqrt{2}$. This bound is proven to
be tight Jed . Therefore, we translate the self-test procedure into the
nonlocal game and characterize it using probability of success. For example,
if in a round we ask one of the global questions [set of inputs $(0,0,1)$,
$(0,1,0)$, $(1,0,0)$, or $(1,1,1)$] and get the correct outputs, the achieved
score in the round is $p_{j}=1$, otherwise $p_{j}=0$. The final score is
$P=\sum_{j=1}^{N}p_{j}/N$. Since the self-test is tight we can conclude that
if extractability of the GHZ state from the state $\sigma_{j}$ is not greater
than $1-\eta_{j}$, the highest violation of the Mermin inequality the state
$\sigma_{j}$ can achieve is $4-\eta_{j}/\tilde{c}$. It further means that the
state has probability of success
$p_{\eta_{j}}=1-\eta_{j}/4\tilde{c}=1-c\eta_{j}$.

The probability that the sequence of states $S$ passes all rounds
$\Pi_{j=1}^{N}p_{\eta_{j}}=\Pi_{j=1}^{N}(1-c\eta_{j})$ is bounded

$\Pi_{j=1}^{N}(1-c\eta_{j})\leq\Pi_{j=1}^{N}(1-c\eta)=(1-c\eta)^{N},$ (16)

where $1-\eta=1-\sum_{j=1}^{N}\eta_{j}/N$ is the average extractability
$\bar{\Xi}(S,\sigma)$. Relation (16) is a consequence between the inequality
of arithmetic and geometric means:

$\displaystyle\frac{1}{N}\sum_{j=1}^{N}(1-c\eta_{j})$ $\displaystyle=1-c\eta$
$\displaystyle=\sqrt[N]{(1-c\eta)\times\cdots\times(1-c\eta)}$
$\displaystyle\geq\sqrt[N]{(1-c\eta_{1})\times\cdots\times(1-c\eta_{N})}.$

The bound is saturated when $\eta_{j}=\eta$ for all $j=1,\cdots,N$. For the
fixed average extractability $1-\eta$, the optimal performance is achieved
when the GHZ state has the same extractability $1-\eta$ from all the states
belonging to the sequence $S$. In this case, a probability that a sequence of
states, characterized by the average extractability of the target state lower
than $1-\eta$, gives a correct answer in all $N$ rounds is

$\displaystyle p\left[o_{1}=...=o_{N}=1|\bar{\Xi}(S,\psi)\leq
1-\eta\right]\leq(1-c\eta)^{N}$ (17)

In other words, the confidence level $1-\delta$ that the average
extractability $\bar{\Xi}(S,\psi)$ is larger than $1-\eta$ has a lower bound
$1-(1-c\eta)^{N}$. From here we can estimate the number of copies:

$N\geq{\frac{\ln\delta}{\ln(1-c\eta)}}\approx\frac{1}{c\eta}\ln\delta^{-1}.$
(18)

Importantly, this is asymptotically the best sample efficiency one can achieve
(up to a constant factor).

Here we discuss the case where all the copies passed the test successfully,
which is impossible in real experiments. For that reason, we now adapt the
procedure to a more realistic scenario in which some number of failed rounds
is allowed before halting the protocol. Furthermore, in what follows we do not
impose that the target state has to be self-testable through a Bell inequality
whose quantum bound is equal to the algebraic one. The general protocol for DI
quantum state verification can be summarized as follows. Protocol 1: Device-
independent quantum state verification.

$\mathbf{1)}$ Fix the lower bound on average extractability that we want to
certify $1-\eta$. This implies the lower bound on the average success
probability of the whole sample $p_{\mathrm{QM}}-\varepsilon_{2}$, i.e.,
$p_{\mathrm{QM}}-c\eta$.

$\mathbf{2)}$ Fix the allowed tolerance from the optimal success rate
$\varepsilon_{1}<\varepsilon_{2}$, i.e., $P\geq
p_{1}=p_{\mathrm{QM}}-\varepsilon_{1}$ and the corresponding verification
confidence $1-\delta$.

$\mathbf{3)}$ Fix the number of samples $N$ according to the lower bound given
in Eq. (23).

$\mathbf{4)}$ Run the protocol: measure all the available copies according to
a procedure corresponding to a self-test for the corresponding target state.

$\mathbf{5)}$ If the success rate $P\geq p_{1}$, the protocol is successful
and average extractability of the measured sequence of states is
$\bar{\Xi}\geq 1-\eta$ with confidence level $1-\delta$. Otherwise, the
protocol is inconclusive.

We start the explanation of the protocol with the observation that a self-
testing robustness bound provides the relation between the success probability
and extractability. A state $\sigma_{j}$ providing extractability $1-\eta_{j}$
to the target state has maximal achievable success probability
$p_{\eta_{j}}=p_{\mathrm{QM}}-c\eta_{j}$, where $p_{\mathrm{QM}}$ is the
success probability of the target state. A given sequence of independent
copies $S=\\{\sigma_{1},...,\sigma_{N}\\}$ can be characterized with the
average extractability $\bar{\Xi}(S,\psi)$, which corresponds to the upper
bound on average success probability
$\bar{p}{\stackrel{{\scriptstyle\textrm{def}}}{{=}}}\frac{1}{N}\sum_{j=1}^{N}p_{\eta_{j}}$.
We say that the verification test is successful if the success rate
$P=\frac{1}{N}\sum_{j=1}^{N}o_{j}$ passes certain fixed threshold
$p_{1}=p_{\mathrm{QM}}-\varepsilon_{1}$. The aim is to show that the
probability for a sequence of states characterized with average extractability
$\bar{\Xi}\leq 1-\eta$ to pass the test decreases exponentially with the
number of copies. In order to do so, we prove that this holds under stronger
assumption, i.e., if success probability $\bar{p}\leq
p_{\mathrm{QM}}-\varepsilon_{2}$ ($\varepsilon_{2}=c\eta$). The relation
between two is as follows. If we denote the set of states satisfying
$\bar{\Xi}(S,\psi)\leq 1-\eta$ with $\Sigma_{\eta}$, and the set of states
satisfying $\bar{p}\leq p_{\mathrm{QM}}-c\eta$ with $\Pi_{\eta}$, then on the
level of sets we have $\Sigma_{\eta}\subseteq\Pi_{\eta}$. Our target quantity
is the probability

$p\left[P\geq p_{\mathrm{QM}}-\varepsilon_{1}|\bar{\Xi}\leq
1-\eta\right]\stackrel{{\scriptstyle\textrm{def}}}{{=}}p\left[P\geq
p_{1}|S\in\Sigma_{\eta}\right].$ (19)

Similarly, we define

$p\left[P\geq p_{1}|\bar{p}\leq
p_{\mathrm{QM}}-\varepsilon_{2}\right]\stackrel{{\scriptstyle\textrm{def}}}{{=}}p\left[P\geq
p_{1}|S\in\Pi_{\eta}\right].$ (20)

Following the set relations one directly reads

$\displaystyle\max_{S\in\Sigma_{\eta}}\;$ $\displaystyle p$
$\displaystyle\left[P\geq p_{1}|S\in\Sigma_{\eta}\right]\leq$ (21)
$\displaystyle\leq\max_{S\in\Pi_{\eta}}\;$ $\displaystyle p$
$\displaystyle\left[P\geq
p_{1}|S\in\Pi_{\eta}\right]{\stackrel{{\scriptstyle\textrm{def}}}{{=}}}p_{\textrm{max}}\left[P\geq
p_{1}|\bar{p}\leq p_{\mathrm{QM}}-\varepsilon_{2}\right]$

Further on, we derive the upper bound on $p_{\textrm{max}}$ related to the
probability of success, which will then automatically imply, by Eq. (21), the
desired bound on extractability. This probability can be expressed with the
help of the Chernoff-like bound (for details, see Appendix A):

$p_{\textrm{max}}\left[P\geq p_{\mathrm{QM}}-\varepsilon_{1}|\bar{p}\leq
p_{\mathrm{QM}}-\varepsilon_{2}\right]\leq\mathrm{e}^{-D(p_{1}||p_{2})N},$
(22)

where $p_{2}=p_{\mathrm{QM}}-\varepsilon_{2}$ and
$D(a||b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$ is the Kullback-Leibler (KL)
divergence. From here we can estimate the number of copies needed to verify
the lower bound of the extractability

$N\geq\frac{\ln{\delta^{-1}}}{D(p_{\mathrm{QM}}-\varepsilon_{1}||p_{\mathrm{QM}}-\varepsilon_{2})}$
(23)

where $1-\delta$ is the required confidence level. Note that, if the test is
passed, the condition $\bar{p}>p_{\mathrm{QM}}-\varepsilon_{2}$ directly
translates to the extractability bound, i.e., extractability must be greater
than $1-\epsilon_{2}/c$.

Now, we see how KL divergence gives two completely different scalings in two
regimes. Let us consider the case when the quantum bound is equal to the
algebraic bound $p_{\mathrm{QM}}=1$ and make a Taylor expansion of Eq. (23).
In this case, we obtain that the number of copies $N$ scales like
$O(\ln{\delta^{-1}}/c\eta)$, which is the optimal scaling. On the other hand,
if we work with nonalgebraic bound $p_{\mathrm{QM}}<1$, Taylor expansion of
Eq. (23) gives $N=O(\ln{\delta^{-1}}/c^{2}\eta^{2})$. All details of the
expansions can be found in Appendix A.

Finally, with this we can formulate our first result. Result 1: DI quantum
state verification. _The entangled state $\psi$ can be device-independently
verified if there exists a robust self-test for it, based on the set of
correlations, which can be phrased as a nonlocal game. The verification test
achieves optimal sample efficiency of $O(\ln{\delta^{-1}}/c\eta)$ if the state
saturates the algebraic bound of a corresponding Bell inequality. For
nonalgebraic bound self-tests, the state is verified with suboptimal sample
efficiency of $O(\ln{\delta^{-1}}/c^{2}\eta^{2})$._

In comparison with the device-dependent case, see Eq. (10) and comments below,
obtained results for the device-independent case differ only by a constant
factor, both for optimal and suboptimal scaling.

Figure 2: Examples of DI quantum state verification. (a) The verification of
the tripartite GHZ state. We compare the number of state copies $N$ needed for
quantum state verification in the device-independent, Eq. (18), versus device-
dependent scenario for a fixed confidence level li2020optimal . The scaling of
the device-dependent version of verification is better only by a constant
factor, which in the particular example has the value $2(2+\sqrt{2})/3$. This
is the type of test where we assume that all rounds are successfully passed
(i.e., $p_{1}=1$ in our protocol 1).
(b) Verification of tripartite GHZ state in a realistic scenario. For
different values of $\eta$, where $1-\eta$ is the average extractability, we
compare the growth of the confidence level as a function of the number of
copies $N$ of the prepared quantum state under the assumption that on average
$95\%$ of experimental runs are successful (i.e., overall success rate $P$ is
greater than $p_{1}=0.95$).

In Fig. 2(a) we compare the sample efficiency of device-dependent and device-
independent quantum state verification of the tripartite GHZ state. The DI
protocol is based on the performance in Mermin’s GHZ game. As a device-
dependent verification protocol we use the optimal protocol, proposed in Ref.
li2020optimal . The scaling of the device-dependent version of quantum state
verification is better only by a constant factor. This scaling is obtained for
the protocol not tolerating any failed rounds, as in the standard quantum
state verification. The theoretical plot for stabilization of the confidence
level for different average fidelities $1-\eta$ in a more realistic scenario
is given in Fig. 2(b). In particular, we take that $0.95$ of copies
successfully passed experimental runs, therefore the maximal estimated value
for extractability is approximately $0.90$ (obtained using linear dependence
between fidelity and the average probability of success).

Non-IID source. The previous section accounts for independent copies the
source produces. Here we adopt the strategy used in the context of
experimental self-testing protocol JD  to adapt our verification protocol to
the non-IID case. As indicated in Sec. II the idea is to verify, not the
correct functioning of the source, but the average extractability of the
target state from the states produced by the source in a given sequence. Let
us return to the example from Sec. II: a source "flips a coin" and depending
on the outcome decides whether to send a sequence of target states
${\lvert\psi\rangle}$, or a sequence of useless separable states $\chi$, such
that $F(\chi,\psi)=0.5$. The full state the source produces is
$\rho=({\lvert\psi\rangle\\!\langle\psi\rvert}^{\otimes n}+\chi^{\otimes
n})/2$. Obviously, the source is not good, as the extractability cannot pass
$0.75$. However, with probability $50\%$ the source sends the sequence of
target states, which can pass the test in all rounds. If this happens, we can
indeed verify that the actual produced sequence is good. And, for practical
purposes, it is a perfectly plausible task: verification of the sequence of
the states one had access to, rather than the verification of the source
itself.

To formalize this let us introduce the conditioning. Conditional
extractability of the target state from the state available in round $j$ is
defined in the following way:

$\Xi_{j|\mathrm{past}}(\tilde{\sigma}_{j},{\lvert\psi\rangle}){\stackrel{{\scriptstyle\textrm{def}}}{{=}}}\\\
\frac{1}{p_{1,\cdots,j-1}}\left\\{\Xi\left[\textrm{Tr}_{1,\cdots,j-1}\left((\otimes_{k=1}^{j-1}M_{\mathbf{o}_{k}|\mathbf{i}_{k}})\sigma^{[j]}\large\right),{\lvert\psi\rangle}\right]\right\\}$
(24)

where $\sigma^{[j]}$ is the full state over $j$ rounds,
$M_{\mathbf{o}_{k}|\mathbf{i}_{k}}$ is the measurement operator used in the
$k$-th round,
$p_{1,\cdots,j-1}=\textrm{Tr}[(\otimes_{k=1}^{j-1}M_{\mathbf{o}_{k}|\mathbf{i}_{k}})\rho]$.
Average conditional extractability for the sequence of states $S$ is defined
as

$\bar{\Xi}_{\mathrm{cond}}(S,\psi){\stackrel{{\scriptstyle\textrm{def}}}{{=}}}\frac{1}{N}\sum_{j=1}^{N}\Xi_{j|{\mathrm{past}}}({\tilde{\sigma}_{j}},{\lvert\psi\rangle}).$
(25)

If the states used in different rounds are correlated, as in the example given
above, the score in round $i$ can be viewed as conditional, as it might depend
on all the previous scores. Of course, the rounds are performed sequentially
in order to get adequate conditional probabilities. Such a conditional score
in the round $j$ is denoted with $p_{j|\mathrm{past}}$, and importantly all
conditional scores are mutually independent by construction:
$p_{j+1,j|\mathrm{past}}=p_{j+1|\mathrm{past}}p_{j|\mathrm{past}}$. The final
score is average of all the conditional scores
$\bar{p}=\frac{1}{N}\sum_{j=1}^{N}p_{j|\mathrm{past}}$. This score can be used
to estimate the number of rounds needed to state with a certain confidence
level that the average conditional extractability of the target state from all
states is above some limit. With the introduced figures of merit, everything
we said in the previous section can be translated to the scenario with a non-
IID source, if the probability to pass a random round $p_{j}$ is exchanged
with the conditional probability $p_{j|\mathrm{past}}$ and the average
extractability is exchanged with average conditional extractability. As all
conditional probabilities are independent, in the derivation of the final
result given by Eq. (23), in Eq. (19) we use $\bar{\Xi}_{\mathrm{cond}}$
instead of $\bar{\Xi}$, and in Eq. (20) we use a modified definition of
$\bar{p}$.

##  IV A framework for device-independent quantum state certification

In practice, there is a strong interest to verify the functionality of an
uncharacterized source before using it in some information-processing
protocol. The DI quantum state verification protocol we introduced above is
not applicable in such a scenario for two reasons. Firstly, as we explained,
it is not the functionality of the source that is verified, but the average
extractability of the target state from the produced copies. Secondly, all the
copies are consumed in the process of verification, and they cannot be reused.

In this section, we address this issue and construct a protocol for DI
certification: from the copies emitted by the source, some fraction is
randomly chosen to be measured, the same way they would be measured in the DI
quantum state verification, while all the remaining copies are preserved to be
used in some other protocol of interest. Importantly, we show that the
performance of the measured copies in the quantum state verification test
allows us to say something about the average extractability of the target
state from the remaining copies. The task of certifying one copy based on the
previous $N$ measurements has been discussed in the fully non-IID scenario in
Refs. Zhu3 ; Zhu4 . While the protocol works in a full adversarial scenario,
it can be used to certify just a single (out of $N$) copy. In this work, we
rather consider the problem of certifying a large number of copies in a DI
manner. We develop an efficient scheme for the case of independent copies,
while the full non-IID solutions still remain for future investigations. As in
the scenario for the DI quantum state verification, the underlying self-
testing procedure can be seen as a nonlocal game, in which for every set of
inputs, the collective set of outputs is either correct or wrong. Hence, every
measurement round is either passed, if the set of outputs is correct, and
otherwise it is failed.

_Independent copies._ As a starting point for this section, let us state the
protocol for device-independent quantum state certification, free of IID
assumption.

Protocol 2: Device-independent quantum state certification.

$\mathbf{1)}$ Fix the lower bound $1-\eta_{c}$ on the certificate average
extractability we want to certify. This implies the lower bound $1-\eta$ on
the average extractability of the whole sample, and consequently to the
average success probability of the whole sample
$p_{\mathrm{QM}}-\varepsilon_{2}$.

$\mathbf{2)}$ Fix the allowed departure from the optimal success rate
$\varepsilon_{1}<\varepsilon_{2}$, i.e., $P\geq
p_{1}=p_{\mathrm{QM}}-\varepsilon_{1}$ and the corresponding verification
confidence $1-\delta$.

$\mathbf{3)}$ Fix the number of samples $N$ according to the lower bound given
in Eq. (27).

$\mathbf{4)}$ Run the protocol: randomly choose $N_{1}\approx\mu N$ instances
of the given quantum system, measure them as in DI quantum state verification
protocol.

$\mathbf{5)}$ The number of successful rounds is $q_{1}$. If $q_{1}/N_{1}\geq
p_{1}$, the protocol is successful and the average extractability of the
certificate can be found with confidence level $1-\delta$. Otherwise, the
protocol is inconclusive.

Assume that the source has produced $N$ independent copies
$S=\\{\sigma_{1},\cdots,\sigma_{N}\\}$. For each copy we randomly choose
whether it will be measured or not, for example by flipping a $\mu$-biased
coin. In the end, a fraction $N_{1}\approx\mu N$ of them is chosen for the
verification process, and we denote this set with $I$. The set of indices
labeling the remaining $N_{2}=N-N_{1}$ copies is denoted with $J$. The $N_{1}$
chosen copies undergo the same procedure we describe in the DI quantum state
verification. In each round, the boxes provide a correct $(p_{j}=1)$ or wrong
$(p_{j}=0)$ answer, hence one can regard the measurement process as revealing
the output of a dichotomic random variable. The measurement phase is
characterized by the number of times the boxes provided a correct answer,
which we denote with $q_{1}$. Thus the overall verification success is
$P=\sum_{j\in I}p_{j}/N_{1}=q_{1}/N_{1}$. The certification is said to be
successful if $P\geq p_{\mathrm{QM}}-\varepsilon_{1}\equiv p_{1}$. Here
$p_{\mathrm{QM}}$ denotes the quantum bound achieved for the target state. The
aim is to show that if the average extractability $\bar{\Xi}$ is upper bounded
by $1-\eta$, i.e., the success probability is upper bounded by
$p_{\mathrm{QM}}-\varepsilon_{2}\equiv p_{2}$, the verification task can be
passed with exponentially small probability. Note that, in order to derive
exponential tail bounds on the certification probability, we assume
$\varepsilon_{2}>\varepsilon_{1}$. Namely, having $N$ copies at our disposal,
the probability to achieve success, i.e., to have $P\geq p_{1}$, given average
extractability $\bar{\Xi}\leq 1-\eta$, i.e., $\bar{p}\leq p_{2}$
[argumentation on the level of sets is the same as in quantum state
verification section, see discussion around Eq. (21)], is given with the
following Chernoff-like bound (for the proof, see Appendix A):

$\displaystyle p$ $\displaystyle\left[P\geq p_{1}|\bar{\Xi}\leq
1-\eta\right]\leq$ (26) $\displaystyle\leq$ $\displaystyle p$
$\displaystyle\left[P\geq p_{1}|\bar{p}\leq
p_{2}\right]\leq\left[1-\mu+\mu\mathrm{e}^{-D(p_{1}||p_{2})}\right]^{N}.$

From here, we can estimate the number of copies

${N\geq\frac{\ln{\delta}}{\ln{(1-\mu+\mu\mathrm{e}^{-D(p_{1}||p_{2})})}},}$
(27)

where $1-\delta$ is the confidence level. Now we derive lower bounds on the
success probability of the remaining copies with the confidence level
$1-\delta$. The success probability of the whole sample is

$\bar{p}=\frac{p_{v}N_{1}+p_{c}(N-N_{1})}{N},$ (28)

where $p_{v}=\sum_{j\in I}p_{\eta_{j}}/N_{1}$ is the success probability of
measured states and $p_{c}=\sum_{j\in J}p_{\eta_{j}}/(N-N_{1})$ the success
probability of the remaining ones. Given that trivially $p_{v}\leq
p_{\mathrm{QM}}$, the expression $\bar{p}\geq p_{2}$ implies

$p_{c}\geq{\frac{Np_{2}-N_{1}p_{\mathrm{QM}}}{N-N_{1}}=p_{\mathrm{QM}}-\frac{\epsilon_{2}N}{N-N_{1}}\approx
p_{\mathrm{QM}}-\frac{\epsilon_{2}}{1-\mu}}.$ (29)

Due to the existence of the self-testing robust bounds (e.g.
$p_{\eta_{c}}=p_{\mathrm{QM}}-c\eta_{c}$), we can conclude that the remaining,
unmeasured copies have the average extractability $\bar{\Xi}_{c}$ higher than
$1-{\eta}_{c}$, with confidence level $1-\delta$, under the certification
condition demanding that a randomly chosen sequence of measured quantum
systems passed successfully $q_{1}$ rounds in the verification part.

Again, we discuss the case of the algebraic and nonalgebraic bound separately.
In the case of $p_{\mathrm{QM}}=1$, Taylor expansion of eq. (27) gives the
optimal sample efficiency $N=O(\ln{\delta^{-1}}/\mu(1-\mu)c\eta_{c})$. On the
other hand, for a nonalgebraic bound, i.e., $p_{\mathrm{QM}}<1$, one obtains
sample efficiency of
$N=O[\ln{\delta^{-1}}/\mu(1-\mu)^{2}c^{2}{\eta}_{c}^{2}]$. Details of the
expansions are presented in Appendix A.

Result 2: DI quantum state certification. _The entangled state
${\lvert\psi\rangle}$ can be device-independently certified if there exists a
robust self-test for it, based on the Bell inequality, which can be phrased as
a nonlocal game. The sample efficiency is $N=O(\ln{\delta^{-1}}/c{\eta}_{c})$
in the case of a Bell inequality whose quantum bound is also the algebraic
bound and $N=O(\ln{\delta^{-1}}/c^{2}{\eta}_{c}^{2})$ in the case of a
nonequivalence between the quantum and the algebraic bound._

We give a concrete example of certification of a tripartite GHZ state through
a Mermin test. In our numerical simulations, we take $\mu=1/2$ and
$N_{1}\approx N/2$ and we set the overall verification success to $0.98$. We
provide an estimation of the average extractability $1-{\eta}_{c}$ of the GHZ
state from the remaining copies $S_{c}$. Figure 3 illustrates how confidence
level grows with a total size of the sample (number of copies) if we want to
certify that average extractability of the remaining copies is greater than
some value. By making this number lower, i.e., having a smaller success rate
in the verification phase, the size of the sample for the reliable
certification grows and the bound on the average extractability of the GHZ
state from the certificate decreases for the same confidence level.

Figure 3: The average extractability of the GHZ state from the certificate in
the case of a tripartite GHZ state. The verification phase is done using a
Mermin test. Confidence
level for certifying average extractability of the GHZ state from the
remaining copies $S_{c}$ is greater than $\;\;\;\;\;\;1-\eta_{c}$ depending on
the total number of copies $N$. Here $\mu=\frac{1}{2}$ and the success rate in
the verification phase is set to $0.98$.

##  V Discussion

In this paper, we developed a protocol for sample-efficient device-independent
quantum state verification and certification. The procedures merge well-
explored protocols for quantum state verification and self-testing. The
biggest room for improvement is the verification procedure in fully non-IID
certification scenario. In the verification scenario we tackled the problem by
introducing the conditional fidelities, but it remains an open question
whether some nontrivial statements can be made about the full state produced
by the source. We managed to adapt the procedure to the certification scenario
where not all copies are consumed through verification in cases where
different copies are not identical, but are independent from each other. While
trying to build a fully non-IID DI certification protocol we encountered
technical difficulties whenever we aimed to certify the average extractability
for more than one remaining copy. In the situation where all copies but one
are measured fully non-IID DI protocol could be constructed by using the
approach of conditional extractability. The aim is to build such a protocol in
the near future. For future research, we are left to explore the possibility
of building a certification protocol in a strictly sequential scenario, where
resorting to permutational invariance is not allowed. We hope that this might
be possible with the help of entropy accumulation theorems dupuis2016entropy ;
Arnon_Friedman_2019 . Let us also note that our methods could be used for DI
verification of resources different than states, for example, quantum gates,
by merging quantum verification Zhu_2020  and self-testing methods
Sekatski_2018 . Finally, a trivial consequence of our work is sample-efficient
nonlocality detection. While our work focused on the certification of quantum
states, if one aims to simply detect nonlocality, it is possible to do it with
a very few copies of the state, as it was similarly done for entanglement in
Refs. Dimic1 ; Saggio_2019 . Similar work has been done in Ref.
zhang2011asymptotically , where optimal sample efficiency was achieved for
detecting nonlocality. The same method was adapted for entanglement detection
zhang2013efficient  and confidence-interval construction wills2017performance
. The method presented in Ref. zhang2011asymptotically  works with early
stopping rules, such that the number of samples to be used needs not to be
fixed in advance.

##  VI Acknowledgements

We acknowledge fruitful discussions with Dragoljub Gočanin and Jean-Daniel
Bancal. We thank Boris Bourdoncle and Flavio Baccari for their valuable
comments about the paper. We especially thank Yunguang Han for pointing out
the mistake in Fig. 2(a) in the first version of our work. A.G. acknowledges
the funding provided by the Faculty of Physics, University of Belgrade,
through the grant by the Ministry of Education, Science, and Technological
Development of the Republic of Serbia. A.G. acknowledges Grant No. FQXi-
MGA-1806 that supported her stay in Vienna. A.G. would also like to thank the
University of Vienna and the University of Geneva for hospitality during her
stay. I.Š. acknowledges support from SNSF (Starting Grant DIAQ) and funding
from Starting ERC Grant QUSCO. B.D. acknowledges support from the Austrian
Science Fund (FWF) through BeyondC-F7112.

##  Appendix A Proof of Chernoff bounds for device independent quantum state
verification and certification

Let us take $N$ copies of the quantum system produced by an untrusted source.
In our protocol we assume that copies are independent
$\sigma_{1},\;\sigma_{2},...,\;\sigma_{N}$, but not necessarily identically
distributed. We denote with $p_{\eta_{j}}=q-c\eta_{j}$ maximal probability for
the $j$th copy to pass the round, where $1-\eta_{j}$ is extractability of the
given copy and $c$ the constant that depends on the self-test. The average
probability of success is given by
$\bar{p}=\frac{1}{N}\sum_{j=1}^{N}p_{\eta_{j}}$. In order to obtain a
certificate, we measure part of the sample and compare the result with the
quantum bound $p_{\mathrm{QM}}$. Quantum bound $p_{\mathrm{QM}}$ represents
the probability of success of the target quantum state $|\psi\rangle$. We set
$\mu$ to be the probability for a copy to be measured. On average, the
experiment consumes $N_{1}\approx\mu N$ copies for verification. The remaining
$N_{2}=N-N_{1}$ copies are left as a certificate. The protocol can be
summarized in the following steps:

  * •

In each run we toss a $\mu$-biased coin and we get a sequence of bits
$\\{m_{1},m_{2},...,m_{N}\\}$. If $m_{j}=1$ we measure the $j$th copy and
obtain result $o_{j}$; otherwise we leave it as a (potential) certificate. The
total number of measured copies is $N_{1}=\sum_{j=1}^{N}m_{j}$.

  * •

In order to extend our analysis to all copies, we artificially define a
measurement result for both measured and unmeasured copies by
$\tilde{o}_{j}=m_{j}o_{j}$, $j=1,2,...,N$.

  * •

The success rate in the verification phase can be written as
$P=\frac{1}{N_{1}}\sum_{j=1}^{N}\tilde{o}_{j}$.

  * •

The test is successful if $P>p_{\mathrm{QM}}-\varepsilon_{1}$.

Suppose that our sample has the average extractability $\bar{\Xi}$, which is
upper bounded by $1-\eta$, consequently the average success probability of the
whole sample $\bar{p}$ is smaller than
$p_{\mathrm{QM}}-c\eta=p_{\mathrm{QM}}-\varepsilon_{2}$. Our target quantity
is the upper bound on probability to obtain success rate of the measured part
greater than $p_{\mathrm{QM}}-\varepsilon_{1}$, under assumption $\Xi\leq
1-\eta$, i.e., $\bar{p}\leq p_{\mathrm{QM}}-\epsilon_{2}$. Here
$\varepsilon_{1}$ and $\varepsilon_{2}$ are free parameters lying in the
interval $(0,1)$. In what follows, we see that a valid expression can only be
derived for $\varepsilon_{2}>\varepsilon_{1}$.

For the sake of compactness, we set $p_{1}=p_{\mathrm{QM}}-\varepsilon_{1}$
and $p_{2}=p_{\mathrm{QM}}-\varepsilon_{2}$ and write certification condition
as $p\left[P\geq p_{1}|\bar{p}\leq p_{2}\right]$. Probability to pass the test
given average success probability $\bar{p}\leq p_{2}$ is given by

$\displaystyle p\left[P\geq p_{1}|\bar{p}\leq p_{2}\right]=$
$\displaystyle=p\left[\tilde{o}_{1}+...+\tilde{o}_{N}\geq(m_{1}+...+m_{N})p_{1}|\bar{p}\leq
p_{2}\right]$
$\displaystyle=p\left[(m_{1}o_{1}-m_{1}p_{1})+...+(m_{N}o_{N}-m_{N}p_{1})\geq
0|\bar{p}\leq p_{2}\right]$ $\displaystyle=p\left[s_{1}+...+s_{N}\geq
0|\bar{p}\leq p_{2}\right]$
$\displaystyle=p\left[\mathrm{e}^{(s_{1}+...+s_{N})t}\geq 1|\bar{p}\leq
p_{2}\right],$

for $t>0$. We introduce random variables $s_{k}=m_{k}o_{k}-m_{k}p_{1}$ with
possible values $\\{0,-p_{1},1-p_{1}\\}$ and respective probabilities
$\\{1-\mu,\mu(1-p_{k}),\mu p_{k}\\}$. For the purpose of an example, we have
$m_{k}=1$ with probability $\mu$, while $o_{k}=1$ with probability $p_{k}$,
thus outcome $s_{k}=1-p_{1}$ appears with probability $\mu p_{k}$. Then, we
apply Markov’s inequality and given that $s_{k}$s are independent random
variables (fourth line below):

$\displaystyle p\left[\mathrm{e}^{(s_{1}+...+s_{N})t}\geq 1|\bar{p}\leq
p_{2}\right]\leq$
$\displaystyle\leq\mathbb{E}\left[\mathrm{e}^{t(s_{1}+...+s_{N})}\right]$
$\displaystyle=\Pi_{k=1}^{N}\mathbb{E}\left[\mathrm{e}^{t(m_{k}o_{k}-m_{k}p_{1})}\right]$
$\displaystyle=\Pi_{k=1}^{N}[1-\mu+\mu(1-p_{k})\mathrm{e}^{-p_{1}t}+\mu
p_{k}\mathrm{e}^{(1-p_{1})t}]$
$\displaystyle\leq\left\\{\frac{1}{N}\sum_{k=1}^{N}[1-\mu+\mu(1-p_{k})\mathrm{e}^{-p_{1}t}+\mu
p_{k}\mathrm{e}^{(1-p_{1})t}]\right\\}^{N}$
$\displaystyle=\left\\{[1-\mu+\mu(1-\bar{p})\mathrm{e}^{-p_{1}t}+\mu\bar{p}\mathrm{e}^{(1-p_{1})t}]\right\\}^{N}$
$\displaystyle\leq\left\\{1-\mu+\mu\mathrm{e}^{-p_{1}t}+\mu
p_{2}[\mathrm{e}^{(1-p_{1})t}-\mathrm{e}^{-p_{1}t}]\right\\}^{N}.$

The fifth line is the consequence of the relation between the arithmetic and
the geometric means. The sixth line follows from $\sum_{k}p_{k}=N\bar{p}$,
while the seventh line is a consequence of the condition $\bar{p}\leq p_{2}$.

The function $f(t)=1-\mu+\mu\mathrm{e}^{-p_{1}t}+\mu
p_{2}(\mathrm{e}^{(1-p_{1})t}-\mathrm{e}^{-p_{1}t})$ attains the minimal value
for $t=\log\frac{p_{1}(1-p_{2})}{(1-p_{1})p_{2}}$ or equivalently
$\mathrm{e}^{t}=\frac{p_{1}(1-p_{2})}{(1-p_{1})p_{2}}$, which after
substitution gives

$\displaystyle p_{\mathrm{max}}\left[P\geq
p_{\mathrm{QM}}-\varepsilon_{1}|\bar{p}\leq
p_{\mathrm{QM}}-\varepsilon_{2}\right]\leq$ (30)
$\displaystyle\left[1-\mu+\mu\mathrm{e}^{-D(p_{\mathrm{QM}}-\varepsilon_{1}||p_{\mathrm{QM}}-\varepsilon_{2})}\right]^{N}.$

Here $D(a||b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$ is the Kullback-Leibler
divergence. It is worth mentioning that the derivation of equation (30)
follows the idea of deriving Hoeffding’s inequality hoeffding1994probability .
Finally, let us discuss the obtained result in different situations.

Verification. If we take $\mu=1$, which means that all copies are measured, we
obtain

$p_{\textrm{max}}\left[P\geq p_{1}|\bar{p}\leq
p_{2}\right]\leq\mathrm{e}^{-D(p_{1}||p_{2})N},$ (31)

which gives bound (22) from the main text. Having fixed confidence level
$1-\delta$, we easily estimate the average number of copies given by (23). In
order to recover scaling, we find the Taylor expansion of Eq. (23) in the
limit of small $\varepsilon_{1}$ and $\varepsilon_{2}$. We obtain two
different behaviors for algebraic ($p_{\mathrm{QM}}=1$) and nonalgebraic bound
($p_{\mathrm{QM}}<1$). For $p_{\mathrm{QM}}=1$, we have

$N\approx\frac{\ln{\delta^{-1}}}{\varepsilon_{2}}\left(1+\frac{\varepsilon_{1}}{\varepsilon_{2}}\right)+o(1),$
(32)

where $\varepsilon_{1}<\varepsilon_{2}$. Usually, $\varepsilon_{1}$ and
$\varepsilon_{2}$ are of the same order of magnitude, e.g. we can set
$\varepsilon_{1}=\varepsilon_{2}/2$, giving
$N=O(\ln{\delta^{-1}}/\varepsilon_{2})=O(\ln{\delta^{-1}}/c\eta)$. Here we
employ the relation $\varepsilon_{2}=c\eta$. In the case of
$p_{\mathrm{QM}}<1$, we obtain

$N\approx\frac{2(1-p_{\mathrm{QM}})p_{\mathrm{QM}}\ln{\delta^{-1}}}{\varepsilon_{2}^{2}}\left(1+\frac{2\varepsilon_{1}}{\varepsilon_{2}}\right)+o\left(\frac{1}{\varepsilon_{2}}\right),$
(33)

which recovers
$N=O(\ln{\delta^{-1}}/\varepsilon_{2}^{2})=O(\ln{\delta^{-1}}/c^{2}\eta^{2})$.
Certification. In any other case $\mu<1$. Again, by fixing
$\varepsilon_{1}<\varepsilon_{2}$ and taking confidence level $1-\delta$, we
can estimate the number of copies, Eq. (27), necessary for certification
protocol. If the protocol is successful, we have a lower bound on the average
success probability $\bar{p}$ and an estimate for the lower bound on the
success probability of the remaining copies $p_{c}$, with confidence level
$1-\delta$. We have

$\bar{p}=\frac{N_{1}p_{v}+(N-N_{1})p_{c}}{N},$ (34)

where $p_{v}$ is the average success probability of the measured copies. If
$\bar{p}\geq p_{2}$, directly from Eq. (34) and from the logical bound
$p_{v}\leq p_{\mathrm{QM}}$ we obtain

$p_{c}\geq{\frac{Np_{2}-N_{1}p_{\mathrm{QM}}}{N-N_{1}}=p_{\mathrm{QM}}-\frac{\epsilon_{2}N}{N-N_{1}}},$
(35)

which directly translates to average certificate extractability

$1-\eta_{c}\geq{1-\frac{N\varepsilon_{2}}{c(N-N_{1})}}\approx
1-\frac{\varepsilon_{2}}{c(1-\mu)}$ (36)

with confidence level greater than

$1-\delta=1-\left[1-\mu+\mu\mathrm{e}^{-D(p_{\mathrm{QM}}-\varepsilon_{1}||p_{\mathrm{QM}}-\varepsilon_{2})}\right]^{N}.$
(37)

For completeness, we make Taylor expansion of Eq. (27) and comment on the
scaling. In the case of $p_{\mathrm{QM}}=1$, Taylor expansion gives

$N\approx\frac{\ln{\delta^{-1}}}{\mu\varepsilon_{2}}\left(1+\frac{\varepsilon_{1}}{\varepsilon_{2}}\right)+o(1),$
(38)

which after introducing $\varepsilon_{2}\geq c\eta_{c}(1-\mu)$ and
$\varepsilon_{1}<\varepsilon_{2}$ recreates optimal scaling
$N=O[\ln{\delta^{-1}}/\mu(1-\mu)c\eta_{c}]$. Similarly, for
$p_{\mathrm{QM}}<1$, after expansion we obtain

$N\approx\frac{2(1-p_{\mathrm{QM}})p_{\mathrm{QM}}\ln{\delta^{-1}}}{\mu\varepsilon_{2}^{2}}\left(1+\frac{2\varepsilon_{1}}{\varepsilon_{2}}\right)+o\left(\frac{1}{\varepsilon_{2}}\right),$
(39)

which gives quadratically worse scaling
$N=O[\ln{\delta^{-1}}/\mu(1-\mu)^{2}c^{2}{\eta}_{c}^{2}]$.

## References

  * (1) H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller.  Quantum repeaters: The role of imperfect local operations in quantum communication.  Phys. Rev. Lett., 81:5932–5935, 1998.  doi:10.1103/PhysRevLett.81.5932.
  * (2) Ben W. Reichardt, Falk Unger, and Umesh Vazirani.  Classical command of quantum systems.  Nature, 496:456, 2013.  doi:10.1038/nature12035.
  * (3) Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, and Hugo Zbinden.  Quantum cryptography.  Reviews of Modern Physics, 74(1):145–195, 2002.  doi:10.1103/revmodphys.74.145.
  * (4) Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Advances in quantum metrology.  Nature Photonics, 5(4):222–229, 2011.  doi:10.1038/nphoton.2011.35.
  * (5) Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi.  Quantum certification and benchmarking.  Nature Reviews Physics, 2(7):382–390, 2020.  doi:10.1038/s42254-020-0186-4.
  * (6) Martin Kliesch and Ingo Roth.  Theory of quantum system certification.  PRX Quantum, 2:010201, 2021.  doi:10.1103/PRXQuantum.2.010201.
  * (7) Otfried Gühne and Géza Tóth.  Entanglement detection.  Physics Reports, 474(1-6):1–75, 2009.  doi:10.1016/j.physrep.2009.02.004.
  * (8) Nicolai Friis, Giuseppe Vitagliano, Mehul Malik, and Marcus Huber.  Entanglement certification from theory to experiment.  Nature Reviews Physics, 1(1):72–87, 2018.  doi:10.1038/s42254-018-0003-5.
  * (9) Valeria Saggio, Aleksandra Dimić, Chiara Greganti, Lee A. Rozema, Philip Walther, and Borivoje Dakić.  Experimental few-copy multipartite entanglement detection.  Nature Physics, 15(9):935–940, 2019.  doi:10.1038/s41567-019-0550-4.
  * (10) Aleksandra Dimić and Borivoje Dakić.  Single-copy entanglement detection.  npj Quantum Information, 4(1):1–8, 2018.
  * (11) U. Fano.  Description of states in quantum mechanics by density matrix and operator techniques.  Rev. Mod. Phys., 29:74–93, 1957.  doi:10.1103/RevModPhys.29.74.
  * (12) Ulf Leonhardt.  Quantum-state tomography and discrete Wigner function.  Phys. Rev. Lett., 74:4101–4105, 1995.  doi:10.1103/PhysRevLett.74.4101.
  * (13) Z. Hradil.  Quantum-state estimation.  Physical Review A, 55(3):R1561–R1564, 1997.  doi:10.1103/physreva.55.r1561.
  * (14) Daniel F. V. James, Paul G. Kwiat, William J. Munro, and Andrew G. White.  Measurement of qubits.  Physical Review A, 64(5), 2001.  doi:10.1103/physreva.64.052312.
  * (15) A. Bisio, G. Chiribella, G.M. D’Ariano, S. Facchini, and P. Perinotti.  Optimal quantum tomography.  IEEE Journal of Selected Topics in Quantum Electronics, 15(6):1646–1660, 2009.  doi:10.1109/jstqe.2009.2029243.
  * (16) Steven T. Flammia and Yi-Kai Liu.  Direct fidelity estimation from few Pauli measurements.  Physical Review Letters, 106(23), 2011.  doi:10.1103/physrevlett.106.230501.
  * (17) Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 2020.  doi:10.1038/s41567-020-0932-7.
  * (18) Joshua Morris and Borivoje Dakić.  Selective quantum state tomography, 2020.  arXiv:1909.05880.
  * (19) Scott Aaronson.  Shadow tomography of quantum states.  SIAM Journal on Computing, 49(5):STOC18–368, 2019.  doi:10.1137/18M120275X.
  * (20) Sam Pallister, Noah Linden, and Ashley Montanaro.  Optimal verification of entangled states with local measurements.  Physical Review Letters, 120(17):170502, 2018.  doi:10.1103/physrevlett.120.170502.
  * (21) Huangjun Zhu and Masahito Hayashi.  General framework for verifying pure quantum states in the adversarial scenario.  Physical Review A, 100(6):062335, 2019.  doi:10.1103/physreva.100.062335.
  * (22) Huangjun Zhu and Masahito Hayashi.  Efficient verification of pure quantum states in the adversarial scenario.  Phys. Rev. Lett., 123:260504, 2019.  doi:10.1103/PhysRevLett.123.260504.
  * (23) Tomoyuki Morimae, Yuki Takeuchi, and Masahito Hayashi.  Verification of hypergraph states.  Phys. Rev. A, 96:062321, 2017.  doi:10.1103/PhysRevA.96.062321.
  * (24) Yuki Takeuchi and Tomoyuki Morimae.  Verification of many-qubit states.  Phys. Rev. X, 8:021060, 2018.  doi:10.1103/PhysRevX.8.021060.
  * (25) Huangjun Zhu and Masahito Hayashi.  Efficient verification of hypergraph states.  Phys. Rev. Applied, 12:054047, 2019.  doi:10.1103/PhysRevApplied.12.054047.
  * (26) Huangjun Zhu and Masahito Hayashi.  Optimal verification and fidelity estimation of maximally entangled states.  Physical Review A, 99(5):052346, 2019.  doi:10.1103/physreva.99.052346.
  * (27) Xiao-Dong Yu, Jiangwei Shang, and Otfried Gühne.  Optimal verification of general bipartite pure states.  npj Quantum Information, 5(1):1–5, 2019.  doi:10.1038/s41534-019-0226-z.
  * (28) Ye-Chao Liu, Xiao-Dong Yu, Jiangwei Shang, Huangjun Zhu, and Xiangdong Zhang.  Efficient verification of Dicke states.  Phys. Rev. Applied, 12:044020, 2019.  doi:10.1103/PhysRevApplied.12.044020.
  * (29) Wen-Hao Zhang, Chao Zhang, Zhe Chen, Xing-Xiang Peng, Xiao-Ye Xu, Peng Yin, Shang Yu, Xiang-Jun Ye, Yong-Jian Han, Jin-Shi Xu, Geng Chen, Chuan-Feng Li, and Guang-Can Guo.  Experimental optimal verification of entangled states using local measurements.  Phys. Rev. Lett., 125:030506, 2020.  doi:10.1103/PhysRevLett.125.030506.
  * (30) Xinhe Jiang, Kun Wang, Kaiyi Qian, Zhaozhong Chen, Zhiyu Chen, Liangliang Lu, Lijun Xia, Fangmin Song, Shining Zhu, and Xiaosong Ma.  Towards the standardization of quantum state verification using optimal strategies.  npj Quantum Information, 6(1):1–8, 2020.  doi:10.1038/s41534-020-00317-7.
  * (31) Roger Colbeck.  Quantum And Relativistic Protocols For Secure Multi-Party Computation.  PhD thesis, University of Cambridge, 2006.  URL: https://arxiv.org/abs/0911.3814.
  * (32) Stefano Pironio, Antonio Acín, Serge Massar, A Boyer de La Giroday, Dzimitry N Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T Andrew Manning, et al.  Random numbers certified by Bell’s theorem.  Nature, 464(7291):1021–1024, 2010.  doi:10.1038/nature09008.
  * (33) Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani.  Device-independent security of quantum cryptography against collective attacks.  Physical Review Letters, 98(23):230501, 2007.  doi:10.1103/PhysRevLett.98.230501.
  * (34) Valerio Scarani.  The device-independent outlook on quantum physics (Lecture notes on the power of Bell’s theorem).  Acta Physica Slovaca, 62:347–409, 2012.  doi:10.2478/v10155-012-0003-4.
  * (35) Ivan Šupić and Joseph Bowles.  Self-testing of quantum systems: a review.  Quantum, 4:337, 2020.  doi:10.22331/q-2020-09-30-337.
  * (36) D. Mayers and A. Yao.  Self testing quantum apparatus.  Quantum Info. Comput., 4:273, 2004.
  * (37) Jean-Daniel Bancal, Kai Redeker, Pavel Sekatski, Wenjamin Rosenfeld, and Nicolas Sangouard.  Self-testing with finite statistics enabling the certification of a quantum network link.  Quantum, 5:401, 2021.  doi:10.22331/q-2021-03-02-401.
  * (38) Jonathan Barrett, Daniel Collins, Lucien Hardy, Adrian Kent, and Sandu Popescu.  Quantum nonlocality, bell inequalities, and the memory loophole.  Physical Review A, 66(4):042111, 2002.
  * (39) Richard D Gill.  Accardi contra bell (cum mundi): the impossible coupling.  arXiv preprint quant-ph/0110137, 2001.
  * (40) Yanbao Zhang, Scott Glancy, and Emanuel Knill.  Asymptotically optimal data analysis for rejecting local realism.  Physical Review A, 84(6):062118, 2011.
  * (41) Peter Bierhorst.  A robust mathematical model for a loophole-free clauser–horne experiment.  Journal of Physics A: Mathematical and Theoretical, 48(19):195302, 2015.
  * (42) David Elkouss and Stephanie Wehner.  (nearly) optimal p values for all bell inequalities.  Npj Quantum Information, 2(1):1–8, 2016.
  * (43) Ben W Reichardt, Falk Unger, and Umesh Vazirani.  Classical command of quantum systems.  Nature, 496(7446):456–460, 2013.  doi:10.1038/nature12035.
  * (44) Alexandru Gheorghiu, Petros Wallden, and Elham Kashefi.  Rigidity of quantum steering and one-sided device-independent verifiable quantum computation.  New Journal of Physics, 19(2):023043, 2017.  doi:10.1088/1367-2630/aa5cff.
  * (45) Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick.  Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 247–277. Springer, 2019.  doi:10.1007/978-3-030-17659-4_9.
  * (46) Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick.  Simple and tight device-independent security proofs.  SIAM Journal on Computing, 48(1):181–225, 2019.  doi:10.1137/18m1174726.
  * (47) Ya-Dong Wu, Ge Bai, Giulio Chiribella, and Nana Liu.  Efficient verification of continuous-variable quantum states and devices without assuming identical and independent preparation, 2020.  arXiv:2012.03784.
  * (48) Anupama Unnikrishnan and Damian Markham.  Authenticated teleportation and verification in a noisy network.  Phys. Rev. A, 102:042401, 2020.  doi:10.1103/PhysRevA.102.042401.
  * (49) Preeti Yadav, Paulo Mateus, Nikola Paunković, and André Souto.  Quantum contract signing with entangled pairs.  Entropy, 21(9):821, 2019.  doi:10.3390/e21090821.
  * (50) Michael A. Nielsen and Isaac L. Chuang.  Quantum computation and quantum information.  Cambridge University Press, 2018.  doi:10.1017/CBO9780511976667.
  * (51) Herman Chernoff et al.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, 23(4):493–507, 1952.  doi:10.1214/aoms/1177729330.
  * (52) Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In The Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994.  doi:10.2307/2282952.
  * (53) C.-E. Bardyn, T. C. H. Liew, S. Massar, M. McKague, and V. Scarani.  Device-independent state estimation based on Bell’s inequalities.  Phys. Rev. A, 80:062327, 2009.  doi:10.1103/PhysRevA.80.062327.
  * (54) Jędrzej Kaniewski.  Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities.  Phys. Rev. Lett., 117:070402, 2016.  doi:10.1103/PhysRevLett.117.070402.
  * (55) The standard terminology is ‘extractability of the target state from the physical state’. When it is clear from the context what is the target state we will use simply ‘extractability’.
  * (56) Note that we can talk about inverse isometry only if the isometry is bijection, hence the statement made here is valid only for bijective isometries. In practice, local isometries used in self-testing are bijections, more precisely they can be seen as local unitaries mapping the physical state in tensor product with a set of ancillas to the target state in a tensor product with some junk state.
  * (57) Sam Pallister.  Verification and validation of quantum systems.  PhD thesis, University of Bristol, 2018.  URL: https://research-information.bris.ac.uk/files/175860643/SamPallister_HardboundThesis_uwlavf.pdf.
  * (58) John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  Proposed experiment to test local hidden-variable theories.  Phys. Rev. Lett., 23:880–884, 1969.  doi:10.1103/PhysRevLett.23.880.
  * (59) N. David Mermin.  Extreme quantum entanglement in a superposition of macroscopically distinct states.  Phys. Rev. Lett., 65:1838–1840, 1990.  doi:10.1103/PhysRevLett.65.1838.
  * (60) J. Silman, S. Machnes, and N. Aharon.  On the relation between bell’s inequalities and nonlocal games.  Physics Letters A, 372(21):3796–3800, 2008.  doi:10.1016/j.physleta.2008.03.001.
  * (61) Zihao Li, Yun-Guang Han, and Huangjun Zhu.  Optimal verification of Greenberger-Horne-Zeilinger states.  Physical Review Applied, 13(5):054002, 2020.  doi:10.1103/PhysRevApplied.13.054002.
  * (62) Frederic Dupuis, Omar Fawzi, and Renato Renner.  Entropy accumulation.  Commun. Math. Phys., 379:867–913, 2020.  doi:10.1007/s00220-020-03839-5.
  * (63) Huangjun Zhu and Haoyu Zhang.  Efficient verification of quantum gates with local operations.  Physical Review A, 101(4), 2020.  doi:10.1103/physreva.101.042316.
  * (64) Pavel Sekatski, Jean-Daniel Bancal, Sebastian Wagner, and Nicolas Sangouard.  Certifying the building blocks of quantum computers from Bell’s theorem.  Phys. Rev. Lett., 121:180505, 2018.  doi:10.1103/PhysRevLett.121.180505.
  * (65) Yanbao Zhang, Scott Glancy, and Emanuel Knill.  Efficient quantification of experimental evidence against local realism.  Physical Review A, 88(5):052119, 2013.
  * (66) Peter Wills, Emanuel Knill, Kevin Coakley, and Yanbao Zhang.  Performance of test supermartingale confidence intervals for the success probability of bernoulli trials.  arXiv preprint arXiv:1709.04078, 2017.