# Quantum verification with few copies

Joshua Morris  University of Vienna, Faculty of Physics, Vienna Center for
Quantum Science and Technology (VCQ), 1090 Vienna, Austria  Valeria Saggio
University of Vienna, Faculty of Physics, Vienna Center for Quantum Science
and Technology (VCQ), 1090 Vienna, Austria  Aleksandra Gočanin  Faculty of
Physics, University of Belgrade, Studentski Trg 12-16, 11000 Belgrade, Serbia
Borivoje Dakić  University of Vienna, Faculty of Physics, Vienna Center for
Quantum Science and Technology (VCQ), 1090 Vienna, Austria  Institute for
Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences,
Boltzmanngasse 3, 1090 Vienna, Austria

###### Abstract

As quantum technologies advance, the ability to generate increasingly large
quantum states has experienced rapid development. In this context, the
verification of large entangled systems represents one of the main challenges
in the employment of such systems for reliable quantum information processing.
Though the most complete technique is undoubtedly full tomography, the
inherent exponential increase of experimental and post-processing resources
with system size makes this approach unfeasible even at moderate scales. For
this reason, there is currently an urgent need to develop novel methods that
surpass these limitations. This review article presents novel techniques
focusing on a fixed number of resources (sampling complexity), and thus prove
suitable for systems of arbitrary dimension. Specifically, a probabilistic
framework requiring at best only a single copy for entanglement detection is
reviewed, together with the concept of shadow and selective quantum state
tomography, which enables the estimation of arbitrary elements of an unknown
state with a number of copies that is independent of the system’s size. These
hyper-efficient techniques define a dimensional demarcation for partial
tomography and open a path for novel applications.

##  1 Introduction

In the coming decades, thanks to rapid technological advances, the probability
of a new information revolution appears quite high. Quantum systems involving
photons, atoms, spins, molecules, solid-state and optomechanical devices, even
with the absence of perfect control and manipulation, are already promising
candidates for building new applications aside from universal quantum
computing. As difficult as it is to predict how emerging technologies will be
most effectively applied, one can expect to see quantum technologies with a
high degree of variability in architecture and capacity (as when classical
computers emerged in the 1950s), the so-called noisy, intermediate-scale
quantum (NISQ) preskill2018quantum . Here intermediate-scale refers to the
size of the quantum processors, in the regime of tens of qubits up to a few
hundred in the next decade or so. Remarkable achievements in creating larger
quantum states have already been reported kelly2019operating ;
friis2018observation ; zhong2020quantum ; wang2019boson ; gong2021quantum ;
ebadi2021quantum ; mooney2021wholedevice  using different quantum platforms,
from superconducting architectures to trapped ion systems and photonic setups.
Moreover, impressive demonstrations (such as those of a computational quantum
advantage) have recently been reported by several groups that used 53
arute2019quantum  and 56 wu2021strong  superconducting qubits and up to 113
photons zhong2020quantum ; zhong2021phase .

Such rapid development and demonstration of a quantum supremacy indicate that
quantum information processing is sufficiently mature that another problem,
quite aside from noisy quantum systems, has begun to make its presence known
with increasing frequency. While it is all very well to coherently process
quantum states that reside in an exponentially large space, it means little if
one cannot retrieve and validate the results of such manipulations. So begins
consideration for the metrology of quantum systems. The gold standard of
quantum measurement is full state tomography james2005measurement , wherein
complete knowledge about the state is gained via measurement. Though certainly
sufficient, the complexity in both measurements and computational processing
power grows exponentially fast with the dimension of the quantum system.

Given that our interest in quantum information processing is this rapid
growth, inserting a step that requires exponential resources seems rather
counterproductive. Until very recently, however, this exponential cost was
largely irrelevant as our ability to rapidly measure or classically compute
vastly outstripped our ability to perform meaningful operations with more than
a few qubits. Thus, simply performing full state tomography and retrieving a
complete quantum state was a viable strategy. This approach was only ever
practical at the very small scale of NISQ and pre-NISQ however. In the long
term, fault-tolerant and noise-resistant quantum computers ought to make a
complete validation of the system less important but we are far away from such
feats of quantum engineering, while still being capable of constructing large
quantum systems. Thus a gap has appeared - systems are too large for anything
nearing complete tomography but not advanced enough to assume low errors.

The advantages of a complete tomography are obvious. One need make no
assumptions on any properties of the target system except that it can be
repeatedly produced (reinitialised) and measured. The price of such ignorance
is an exponential cost in measuring, reconstructing and storing the state of
the target and is naturally unsustainable as we move into the intermediate
regime. But such a problem has hardly taken the quantum estimation community
by surprise and many strategies exist to mitigate such a heinous complexity
cost. Often, complete information is not required in many cases and when
married with random sampling techniques can result in powerful verification
methods knill2008randomized ; gross2010quantum ; pappa2012multipartite ;
tran2015quantum ; montanaro2017learning ; pallister2018optimal ;
torlai2018neural ; zhu2019efficient ; kueng2018 ; kueng2019 ; dimic2018single
; saggio2019experimental ; huang2020predicting ; zhu2019optimal ;
dimicsupicdakic ; aaronson2017 ; morris2019selective  (see also Eisert2020
for general review on the topic) that probe only some specific quantities one
might wish to know about a given state. To name but a few, one might wish to
investigate only the presence of entanglement in a certain quantum state
dimic2018single ; saggio2019experimental  or directly estimate the state
fidelity flammia2011direct  i.e. the quantification of the overlap between
prepared and ideal states. It follows naturally that reducing the amount of
obtainable information comes with a lower demand in terms of experimental
resources, thus making these methods more viable alternatives when the full
density matrix is not needed. For clarity, we will explicitly define here that
any interrogation of a quantum system which reveals information about that
system is termed a partial tomography.

It appears then that a trade-off of some kind must occur. Complexity costs can
be reduced in one regard but increased in another Eisert2020 , essentially
shifting the difficulty to another stage of an experiment, or we can reduce
the information extracted. Ultimately, an explicit dimension dependence
remains in most tasks and this serves as a problematic complication for large-
scale systems. With this in mind, we concern ourselves with strategies that
appear to saturate some notion of maximal information extraction, paired with
a resource cost (at every stage of the protocol) that has moderate growth in
the dimension. This suggests a different mode of thinking may be in order.
Rather than asking how large a quantum system we can effectively probe with a
given strategy, consider instead the central question of this review:

> Given a limited number of interactions with a large system, how much
> classical information can we learn with a high degree of certainty?

This extracted classical information can take many forms and one must be
careful of the kinds of questions one asks. Consider the task of entanglement
detection, which may be performed indirectly by estimating the mean value
$\expectationvalue{W}$ of an appropriate witness $W$ and comparing it to some
threshold value $W_{c}$, which requires repeated measurements on large
ensembles of identically prepared quantum states. An alternative to this is a
direct approach by an oracular question “Is $\expectationvalue{W}<W_{c}$?”,
which potentially can be queried with a single copy. For detecting
entanglement they of course produce the same answer, but estimating the
expectation value is far more resource-intensive than bounding it from above
in the first place. The benefit of doing so is clear, however, the question
then is how to operationally reformulate the former into the latter. This
process of reformulation is one of the central topics that shall form this
review.

Such thinking engenders a curious divergence from the norm of quantum
metrology wherein both the dimension of a system and the number of copies are
seen as a given and large. On the other hand, this decision-theory centric
approach, that has estimation as comparable to traversing a finite tree of
outcomes to arrive at a final conclusion has been shown kueng2019 ;
dimic2018single ; saggio2019experimental ; huang2020predicting ;
zhu2019optimal ; dimicsupicdakic ; aaronson2017 ; morris2019selective  to
yield vastly improved complexity bounds for previously challenging measurement
tasks. By rephrasing the problem of verification in this decision-theoretic
way we define our starting condition as the resources of an efficient
strategy, such as a limited number of state copies, and then list measurement
protocols that operate within these constraints. As an illustration of the
method, consider testing some property with $N$ copies available, where $N$ is
potentially low (e.g. few copies). Each copy may then be considered as a
precious resource for measurements we are permitted to ask a quantum system in
order to ascertain its properties. For example, we wish to test if the state
$\rho\in A$ or $\rho\in\bar{A}$ (with $A\cup\bar{A}$ being the complete set of
states) where $A$ denotes the property being tested (as in Figure 1). An
efficient strategy is one where the queried system is overwhelmingly unlikely
to pass a test condition if it does not contain the queried property $A$.

The strategy is as follows. A set of carefully designed and easy-to-perform
measurements $\mathbf{Q}=\\{Q_{1},Q_{2},Q_{3}\dots Q_{L}\\}$ that serve as
queries to the system are constructed. For the $k$th instance of the $N$
copies of a state, a query $q_{k}\in\mathbf{Q}$ is randomly chosen and applied
to that instance, producing a sequence of query outcomes
$\mathbf{i}=(i_{1},...,i_{N})$ for $i_{k}\in\\{0,1\\}$. This sequence together
with the sequence of chosen queries $\mathbf{q}=(q_{1},...,q_{N})$ is then
passed to a decision (cost) function $S(\mathbf{q},\mathbf{i})$ which produces
a pass/fail result. A strategy is bestowed the title of “efficient” if the
following probabilistic statement

$\Pr\left[S(\mathbf{q},\mathbf{i})=\mathrm{"pass"}|\rho\in\bar{A}\right]\leq\exp[-\alpha(d,N)],\;\;\alpha(d,N)\geq
0,$ (1)

holds for a dimension $d$ state $\rho$ with $N$ repetitions (queries). This
deceptively simple equation is at the heart of every strategy considered in
this review. Conceptually it states that any estimator is only as good as its
worst-case performance which is dictated by its probability of failure,
defined as a system passing a test protocol that it should fail. If this false
positive probability has a functional dependence $\alpha(d,N)$ that grows in
$N$ and does not vanish asymptotically in $d$, for example typically
$\alpha(N,d)=O(1)N$ is dimension free, then failure is exponentially unlikely
for all targets of the protocol and it is deemed efficient. This concept is
schematically depicted in Figure 1, where the probability that the target
state $\rho$ contains the property $A$ scales exponentially with the number of
questions $Q_{k}$ that are asked to repeated copies of $\rho$.

Figure 1: Schematic of the probabilistic procedure. The probability Pr that
the quantum system contains the property $A$ is found by asking relevant
questions $Q_{k}$ to the system. A probability close to $1$ is indicated by a
dark region, in contrast to a probability close to $0$, associated to a
lighter colour. Asking more and more questions builds up the probability that
the system contains $A$.

In principle, every partial tomography task (on finite-dimensional systems)
may be posed in this decision theory point of view. In a similar spirit, we
require this demarcation not just in time but space as well, insisting on
simple-to-implement queries on each quantum state. This will almost always
mean local queries on the target system alone, rather than for example global
(entangled) measurements on multiple instances. Finally, the computation of
the decision function $S(\mathbf{q},\mathbf{i})$ itself must also be
efficient, in that it cannot have a computational complexity that depends on
the system dimension in any significant way. To summarise our requirements:

  1. 1.

Dimension demarcation: $\alpha(d,N)$ is not asymptotically small for large
$d$, for example $\alpha(d,N)=O(1)N$.

  2. 2.

Fast convergence in the number of queries: $\alpha(d,N)$ grows with $N$ for
example, typically linearly.

  3. 3.

Low computational complexity where the measurement queries $Q_{k}$ are
implemented by local measurement or low-depth quantum circuits.

  4. 4.

Simple post-processing, e.g. simple evaluation of the decision function
$S(\mathbf{q},\mathbf{i})$.

This review will progress through query/answer strategies that satisfy these
demanding properties when a single copy is available for analysis up to a few
thousand of an arbitrarily sized quantum state. Beginning with single copy
entanglement detection/verification and progressing to estimation of a general
class of bounded observables using a few thousand samples, we will investigate
what commonality exists between such strategies, discussing both their
implementation and the steps that constitute them.

##  2 Entanglement verification

In searching for worthwhile tasks, it is not a contentious statement that
entanglement represents a crucial resource in many quantum-information
protocols horodecki2009quantum . For this reason, the task of entanglement
verification has by necessity spurred the development of a variety of
different approaches over the past years friis2019entanglement .
Traditionally, the methods of detection (see friis2019entanglement ;
guhne2009entanglement  for a focused review) rely on the estimation of
expectation values of observables linked to certain fundamental inequalities,
such as is the case of entanglement witnesses guhne2009entanglement ;
terhal2000bell ; bruss2002reflections , Bell inequalities baccari2017efficient
; rabelo2011device ; werner2001bell  or the use of quantum Fisher information
akbari2019entanglement ; hyllus2012fisher ; li2013entanglement , local
uncertainty relations zhao2019entanglement  and nonlinear witnesses
guhne2006nonlinear . Typically, strategies will involve testing if (some
function of) the expectation value(s) of some observable(s) exceeds a certain
threshold, such as testing if $\expectationvalue{W}<W_{c}$ and demanding, in
practice, repeated measurements on large ensembles of identically prepared
copies. This can be costly in terms of experimental requirements, scaling to
impossibility with just a few steps as in photonic systems where coincidence
rates fall exponentially fast in the system size adcock2018hard . An
impressive yet example of this may be found in a recent 12-photon entanglement
witness experiment zhong201812 , where the detection rate was approximately
one copy per hour. The extraction of a mean value of a single local
observable, which typically requires one hundred to one thousand copies of a
given quantum state, in this case, translated to an experiment duration
measured in weeks. Such non-viability is a consequence of the indirect
approach for testing entanglement. If instead we employ the direct method in
which we pose the detection question differently, i.e. to ask: "What is the
chance for the system to achieve a value $\langle{W}\rangle<W_{c}$ in a
single-shot experiment?”, we can gain a vast reduction in the detection
complexity. In this respect, we will review several highly efficient methods
dimic2018single ; saggio2019experimental ; zhu2019optimal  based on the
information-theoretic framework introduced in the previous section.

###  2.1 Probabilistic detection scheme

Consider a quantum system consisting of $n$ subsystems, each residing in a
finite-dimensional Hilbert space of dimension $d$. The first step in any
partial tomography is to define the relevant set of queries $Q_{m}$ that will
be used to interrogate the system – as no information may be gleaned without
them. Commonly these correspond to certain binary local measurements
associated to yes/no questions. For the sake of generality, we include here
the quantum measurements that go beyond binary logic, that is, the positive-
operator valued measures (POVMs) $E^{(k)}_{i|m}$, where
$\sum_{i}E^{(k)}_{i|m}=\mathds{1}^{(k)}$. Here $k$ labels the subsystem,
$m\in\\{1,...,L\\}$ the local measurement setting, and $i$ is the measurement
outcome. For every subsystem, we can generate one random query associated to
the setting $m_{k}$ which when applied to the $k$th party results in some
outcome $i_{k}$.

Figure 2: Probabilistic entanglement detection. A single copy of an
$n$-partite quantum system $\rho$ is repeatedly interrogated via random
(local) measurements $m_{1}$,$m_{2}$,…,$m_{n}$. The performance of the system
is measured via the evaluation of a cost function $S_{[n]}$. Repeating this
procedure $N$ times, the probability of detecting entanglement goes to unity
exponentially fast in $N$ for target state preparations, i.e. the (lower bound
on) detection confidence grows as $C_{\min}=1-\exp[-\alpha(n)N]$.

The probabilistic entanglement detection procedure, schematically shown in
Figure 2, goes as follows:

  1. 1.

A sequence of random local measurements $(m_{1},...,m_{n})$ drawn from a prior
distribution $\Pi(m_{1},...,m_{n})$ is applied to a copy of quantum state
$\rho$ to generate the sequence of outcomes $(i_{1},...,i_{n})$.

  2. 2.

A certain binary cost function of settings and outcomes
$S_{[n]}=S_{m_{1}...m_{n}}^{i_{1}...i_{n}}\in\\{0,1\\}$ is calculated.

  3. 3.

If $S_{[n]}=0/1$ we associate “success/failure” to the experimental run.

  4. 4.

Repeat $N$ times steps $1-3$.

The figure of merit for entanglement detection is the probability of success
$P[S_{[n]}=1]$. In essence, the cost functions are created such that this
probability vanishes exponentially fast in the size of the system $n$ and/or
in the number of repetitions $N$ for all separable states $\rho_{sep}$:

$P_{\rho_{sep}}[S_{[n]}=1]\leq\exp[-\alpha(n)N],$ (2)

where $\alpha(n)$ is a function depending on the particular strategy and
system’s size. On the other hand, the procedure is tailored to detect
entanglement in the vicinity of some target state $\rho_{T}$, i.e.
$P_{\rho_{T}}[S_{[n]}=1]\approx 1$, thus, given the target-state preparations
and desired detection confidence $1-\delta$, we can estimate the average
number of copies required to verify entanglement:

$N=\frac{\log\delta^{-1}}{\alpha(n)}.$ (3)

It is abundantly clear that as long as $\alpha(n)$ is not vanishingly small
with the size $n$, for example $\alpha(n)=O(1)$, we will have a logarithmic
growth of the number of copies in $\delta$. Considering it in the opposite
direction: the confidence for entanglement detection grows exponentially fast
in the number of repetitions $N$ which constitutes what we dub the few-copy
detection regime saggio2019experimental  where we achieve the high confidence
detection by measuring only (thus the name) a few copies of the system (see
Section 2.3). The reduction of resources can be further traced down in the
case where $\alpha(n)$ grows in $n$. In this case, for a sufficiently large
system (large $n$) this number is reduced to the logical minimum leading to
the single-copy detection dimic2018single ; dimic2018central . This
possibility is presented in detail in the next section.

An important aspect of these methods is that they bypass the so-called i.i.d.
(independent and identically distributed) assumption taken for granted in
standard approaches. This assumption means that a source produces identical
copies of a quantum state in every experimental run. This is very questionable
from a practical point of view, especially given the lack of perfect control
and manipulation as is the case for NISQ systems. In contrast, the shown
methods surpass i.i.d. through use of random sampling a set of measurement
queries. In this case, the entanglement is seen as the ability of a system to
compute a certain cost function (as quantified by the probability of success)
in a single-shot experiment. In such a construction of the problem, the i.i.d.
requirement may be relaxed without compromising the protocol.

###  2.2 Single-copy scenario

We review the construction of the single-copy detection procedure for
$k$-producible states guhne2005multipartite  which naturally extends to
cluster states briegel2001persistent . Further examples include ground states
for local Hamiltonians with the entanglement gap dowling2004energy , among
which we find many important classes of quantum states, such as the matrix
product states perez2006matrix  and projected-entangled pair states
verstraete2008matrix . In all examples provided we explicitly constrain to a
single experimental repetition ($N=1$) and attempt to optimise the chance of
entanglement detection. We put the main emphasis on the construction of
protocol, i.e. appropriate choice of the settings and cost function.

####  2.2.1 Example of k-producible quantum state

We start with the example of the $k$-producible entangled state
guhne2005multipartite , i.e.
$\ket{\phi_{1}}\ket{\phi_{2}}\dots\ket{\phi_{m}}$, where the products
$\ket{\phi_{s}}$ involve at most $k$ parties.111This example is rather
explanatory and used to demonstrate the method. A “real” example of cluster
states will naturally follow in the next section. Our aim is to show that
entanglement can be detected with one copy of an $n$-folded state as long as
$n$ is large. To clarify the probabilistic procedure even better, we take the
target state to be the product of quantum singlets
$\ket{\psi_{0}}=\ket{\psi^{-}}^{\otimes n}$, where
$\ket{\psi^{-}}=\frac{1}{\sqrt{2}}(\ket{01}-\ket{10})$. The quantum singlet
has the property of being the only state that returns perfect anti-
correlations (the outcome $-1$) when measured with one of the operators
$X\otimes X$, $Y\otimes Y$, or $Z\otimes Z$. Therefore, the suitable
measurements to identify singlet uniquely are the following projectors

$Q_{X}=\frac{\mathds{1}-X\otimes X}{2},\;\;Q_{Y}=\frac{\mathds{1}-Y\otimes
Y}{2},\;\;Q_{Z}=\frac{\mathds{1}-Z\otimes Z}{2}.$ (4)

The pertinent fact is that no separable state may reveal $Q_{X}=Q_{Y}=Q_{Z}=1$
simultaneously; as already emphasised, this is the unique property of the
target singlet state. Thus, the maximum probability to obtain the outcome $1$
for all separable inputs if measurement settings are uniformly sampled from
the set $\\{XX,YY,ZZ\\}$ is $2/3$:

${P}_{\rho_{sep}}=\langle{\frac{1}{3}(Q_{X}+Q_{Y}+Q_{Z})}\rangle\leq\frac{2}{3},$
(5)

for all separable two-qubit states $\rho_{sep}$. With this we can construct
detection procedure for $n$ pairs as follows: the set of $2n$ qubits is
divided into consecutive pairs and for each pair, a random measurement from
the set $\\{XX,YY,ZZ\\}$ is applied to get a sequence of results
$...,(i_{k},j_{k}),...$. From these measurement outcomes we construct the
following local cost function for every pair
$S_{k}=\frac{1}{2}\left(1-(-1)^{i_{k}+j_{k}}\right)$, where $k=1...n$ labels
the qubit pair. Now, given bound (5), the relative frequency of the outcome
$1$ shall not exceed $2/3$ significantly for all separable states. Therefore,
we define the overall test to be

$S_{[n]}=\left\\{\begin{array}[]{ll}1,&\hbox{$\sum_{k=1}^{n}S_{k}\geq(\frac{2}{3}+\epsilon)n$;}\\\
0,&\hbox{$\sum_{k=1}^{n}S_{k}<(\frac{2}{3}+\epsilon)n$,}\end{array}\right.$
(6)

where $\epsilon>0$ is a free parameter. The overall probability of success
reads

$P[S_{[n]}=1]=P\left[S_{1}+\dots+S_{n}\geq\left(\frac{2}{3}+\epsilon\right)n\right].$
(7)

Using the standard Chernoff bound chernoff1952measure  we obtain:

$P_{\rho_{prod}}[S_{[n]}=1]\leq e^{-D(\frac{2}{3}+\epsilon||\frac{2}{3})n},$
(8)

where $D(x||y)=x\log{\frac{x}{y}}+(1-x)\log{\frac{1-x}{1-y}}\geq 0$ is the
Kullback–Leibler divergence. The probability of success vanishes exponentially
fast in $n$ for all $\epsilon>0$. The procedure is convenient as we do not
have to set $\epsilon$ in advance, i.e. we calculate $\epsilon$ as the
experimental deviation of the measured sum $\frac{1}{n}\sum_{k=1}^{n}S_{k}$
from the separable bound $2/3$. In the perfect case of $n$ singlets
$\ket{\psi_{0}}=\ket{\psi^{-}}^{\otimes n}$, we shall measure $S_{k}=1$
deterministically, thus we find that $\epsilon=1/3$. The bound (8) becomes

$P_{\rho_{sep}}[S_{[n]}=1]\leq\left(\frac{2}{3}\right)^{n}.$ (9)

Therefore, if $n$ is large enough, a single copy of $\ket{\psi_{0}}$ is
sufficient to certify entanglement with high probability. For example, already
for $n=8$, the confidence level for entanglement detection is at least $96\%$.

Before we proceed further, let us illustrate the i.i.d. issue in the following
situation. Suppose that we have only $n=8$ qubit pairs at our disposal and we
want to inspect the presence of entanglement. Given the prescription above, we
may try to measure the witness operator $W=\frac{1}{3}(Q_{X}+Q_{Y}+Q_{Z})$.
However, it is not clear how to divide 8 pairs into three groups to measure
three local observables $Q_{X}$, $Q_{Y}$ and $Q_{Z}$. Also, there is no
guarantee for these pairs to be in an i.i.d. state $\rho_{12}^{\otimes 8}$
which seems to be needed for separate estimation of $\langle{Q_{X}}\rangle$,
$\langle{Q_{Y}}\rangle$ and $\langle{Q_{Z}}\rangle$. In this case, it is not
clear how to proceed. For example, we may use the first three copies to
measure $Q_{X}$, the second three to measure $Q_{Y}$, and the last two for the
measurement of $Q_{Z}$. However, if the order of measurements is known in
advance we may arrive at false entanglement verification: the following
product state $\ket{\phi_{p}}=(\ket{x+}\ket{x-})^{\otimes
3}(\ket{y+}\ket{y-})^{\otimes 3}(\ket{z+}\ket{z-})^{\otimes 2}$ gives exactly
the same result as the i.i.d. singlet state $\ket{\psi^{-}}^{\otimes 8}$ for
these fixed measurements. The key procedure to surpass i.i.d. assumption is
random sampling and the probabilistic detection described above. It provides a
clear separation between the state $\ket{\psi^{-}}^{\otimes 8}$ and the
product state $\ket{\phi_{p}}$, as the later has only the chance of
$(2/3)^{8}\approx 0.039$ in the best case to reveal the result
$S_{1}+\dots+S_{8}=8$. In contrast, the experiment with the single-state
preparation $\ket{\psi_{0}}$ reveals “success” always, thus we verify
entanglement with at least $C_{\min}=1-0.039\approx 0.96$ confidence.

####  2.2.2 Single-copy detection of cluster states

Another example we present here is that of cluster states
briegel2001persistent  as a natural generalisation of the previous example of
$k$-producible state. In contrast however, cluster states contain genuine
multiparty entanglement hein2004multiparty  and represent a universal resource
for measurement-based quantum computation raussendorf2001one . For simplicity,
we work out in detail an example of a linear cluster state (LCS);
generalisations of the scheme to higher dimensions are straightforward and
briefly discussed at the end of the section.

The $n$-qubit LCS is uniquely defined by the set of $2^{n}$ stabilizers

$G_{q_{1}\dots q_{n}}\ket{LCS}=G_{1}^{q_{1}}\dots
G_{n}^{q_{n}}\ket{LCS}=+1\ket{LCS},$ (10)

where $G_{k}=Z_{k-1}X_{k}Z_{k+1}$ and $q_{k}=0,1$. Here
$\\{X_{k},Y_{k},Z_{k}\\}$ is the set of standard Pauli matrices acting on
$k^{\text{th}}$ qubit and without loss of generality we have chosen the
cluster state with periodic boundaries, i.e.
$Z_{n+1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}Z_{1}$ and
$X_{n+1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}X_{1}$.

Let us analyse a small sub-cluster of four qubits (e.g. qubits
$\\{1,2,3,4\\}$) with the corresponding stabilizers

$G_{2}=Z_{1}X_{2}Z_{3},\;\;G_{3}=Z_{2}X_{3}Z_{4}\;\;\text{and}\;\;G_{2}G_{3}=Z_{1}Y_{2}Y_{3}Z_{4}$
(11)

acting exclusively on it. Even though these three stabilizers are commutative,
they are not locally compatible, which means one can not measure all three
simultaneously with local measurements. Therefore, there is no separable state
for which $G_{2}=G_{3}=G_{2}G_{3}=+1$ simultaneously. Consequently, if we
randomly chose to measure one of the stabilizers (with probability $1/3$),
there is only a chance of $2/3$ to get the result $+1$, for all separable
inputs. This observation empowers our detection method to work. The strategy
is to pick a random partition of the set of $n$ qubits into $4$-qubit clusters
and then measure one of the corresponding stabilizers randomly on each of
them. Given our previous analysis, the relative frequency of the outcome $+1$
can not substantially surpass the value of $2/3$. It is convenient to
introduce regular partitions (i.e. neighbouring clusters overlap on at most
one qubit) of $n$-qubit cluster state into $L$-partition of 4-qubit clusters
$\\{c_{t_{1}},c_{t_{2}},\dots c_{t_{L}}\\}$, where $c_{t_{k}}$ is the cluster
consisting of the sequence of four neighbouring qubits:

$c_{t_{k}}=\\{t_{k},t_{k}+1,t_{k}+2,t_{k}+3\\}.$ (12)

The set of all regular partitions of size $L$ is denoted by $\mathscr{C}_{L}$.
For every cluster $c_{t_{k}}$ in the partition we associate three stabilizers:

$\begin{split}&G_{t_{k}+1}=Z_{t_{k}}X_{t_{k}+1}Z_{t_{k}+2},\;\\\
&G_{t_{k}+2}=Z_{t_{k}+1}X_{t_{k}+2}Z_{t_{k}+3}\;\text{, and}\\\
\;&G_{t_{k}+1,t_{k}+2}=G_{t_{k}+1}G_{t_{k}+2}=Z_{t_{k}}Y_{t_{k}+1}Y_{t_{k}+2}Z_{t_{k}+3}.\end{split}$
(13)

To each of them we associate three projectors

$Q_{t_{k}}=\frac{\mathds{1}+G_{t_{k}+1}}{2},\leavevmode\nobreak\
W_{t_{k}}=\frac{\mathds{1}+G_{t_{k}+2}}{2},\leavevmode\nobreak\
R_{t_{k}}=\frac{\mathds{1}+G_{t_{k}+1}G_{t_{k}+2}}{2},$ (14)

projecting on the $+1$ outcome. To these we associate the following
measurement settings $\\{ZXZZ,ZZXZ,ZYYZ\\}$, and we assign “success” to the
cluster measurement only if the outcome $+1$ (for the value of measured
stabilizer) occurs. Formally speaking, for every cluster we define the
following local cost function

$S_{k}=S_{m}^{i_{1}i_{2}i_{3}i_{4}}=\frac{1}{2}+\frac{1}{2}\left\\{\begin{array}[]{ll}(-1)^{i_{1}+i_{2}+i_{3}},&\hbox{$m=ZXZZ$;}\\\
(-1)^{i_{2}+i_{3}+i_{4}},&\hbox{$m=ZZXZ$;}\\\
(-1)^{i_{1}+i_{2}+i_{3}+i_{4}},&\hbox{$m=ZYYZ$,}\end{array}\right.$ (15)

where $k=1\dots L$. Finally, for a given partition
$\\{c_{t_{1}},c_{t_{2}},\dots,c_{t_{L}}\\}$ the overall cost function is
represented in the following way

$S_{[n]}=\left\\{\begin{array}[]{ll}1,&\hbox{$S_{1}+\dots+S_{L}\geq(\frac{2}{3}+\epsilon)L$;}\\\
0,&\hbox{$S_{1}+\dots+S_{L}<(\frac{2}{3}+\epsilon)L$,}\end{array}\right.$ (16)

where $\epsilon>0$ is a free parameter. We associate “success” to the
experimental run if the number of local successes exceeds a certain threshold
of $(\frac{2}{3}+\epsilon)L$. The detection procedure goes as follows:

  * 1.

Randomly generate a partition of $n$-qubit cluster state
$\\{c_{t_{1}},c_{t_{2}},\dots,c_{t_{L}}\\}$ from the set $\mathscr{C}_{L}$
with probability $1/|\mathscr{C}_{L}|$.

  * 2.

Draw one measurement setting for each cluster in the partition with
probability $1/3$.

  * 3.

Perform local measurements and collect the sequence of results
$S_{1},S_{2},\dots,S_{L}$.

  * 4.

Calculate the cost function $S_{[n]}$ by using (16).

We shall analyse the probability to pass the test for separable states. First,
for all product states the local cost functions $S_{k}$ are independent binary
random variables with $\langle{S_{k}}\rangle\leq 2/3$ for all $k=1\dots L$.
The overall probability of success reads

${P}_{\rho_{prod}}[S_{[n]}=1]=P_{\rho_{prod}}\left[S_{1}+\dots+S_{L}\geq\left(\frac{2}{3}+\epsilon\right)L\right],$
(17)

which is the probability that the sum of independent random variables
$S_{1}+\dots+S_{L}$ exceeds the value of $(\frac{2}{3}+\epsilon)L$. As
$\langle{S_{k}}\rangle\leq 2/3$, the sum $S_{1}+\dots+S_{L}$ cannot exceed
$2L/3$ significantly. Indeed, as before, the Chernoff bound holds (for
detailed proof see Supplementary Information of dimic2018single ), i.e.

${P}_{\rho_{prod}}[S_{[n]}=1]\leq e^{-D(\frac{2}{3}+\epsilon||\frac{2}{3})L},$
(18)

where $D(x||y)$ is the Kullback-Leibler divergence. As the bound holds for all
product states, it also holds for their mixtures, i.e. for all separable
states.

On the other hand, for the case of cluster state preparation $\ket{LCS}$, each
local cost function takes the value $S_{k}=1$, thus we have $\epsilon=1/3$.
The bound (18) reduces to

$P_{\rho_{sep}}[S_{[n]}=1]\leq\left(\frac{2}{3}\right)^{L}.$ (19)

For the sufficiently large number of qubits even a single-copy of the LCS
suffices to certify the presence of entanglement with high probability. For
example, already for $n=24$, we have $L=8$ which gives a confidence level
greater than $95\%$.

Finally, let us comment briefly on the generalization to the higher
dimensional case. In the case of a 2D cluster state, one can introduce
partitions into $4\times 4$ qubit clusters with the corresponding stabilizer
projectors (using complete analogy to $Q_{t_{k}}$, $W_{t_{k}}$ and $R_{t_{k}}$
for LCS) and define the local cost functions. The 2D detection scheme also
consists of drawing a random partition followed by a random measurement of
local projectors on individual clusters. The separable bound similar to (18)
can be derived. On the other hand, if the 2D cluster state is the input state,
the probability of success is $1$.

####  2.2.3 Single-copy detection of ground-states of local Hamiltonians

One of the strong reasons why the single-copy entanglement scheme works for
the cluster states is the robustness of entanglement to local perturbations,
meaning that local measurements on qubits do not destroy the entanglement
between the remaining qubits completely. Thus one can expect other classes of
states sharing this property to admit single-copy entanglement detection. The
ground states of local Hamiltonians share this property eldar2017local ;
therefore they are good candidates. Let us consider an $L$-local Hamiltonian
on some graph of $n$ particles $H=\sum_{k=1}^{n}H^{(k)}$, where $H^{(k)}$ acts
on at most $L$ subsystems ($L$ is fixed and independent of $n$). Now, let
$\ket{\psi_{0}}$ be the ground state of the Hamiltonian
$H\ket{\psi_{0}}=n\epsilon_{0}\ket{\psi_{0}}$, where $E_{0}=n\epsilon_{0}$ is
the ground-state energy. We are working with Hamiltonians that exhibit the so-
called entanglement gap $g_{E}=\epsilon_{\text{sep}}-\epsilon_{0}>0$, where
$\epsilon_{sep}=\frac{1}{n}\min_{\rho_{sep}}\mathrm{Tr}H\rho_{sep}$ is the
minimal obtainable energy per particle by a separable state dowling2004energy
. The main idea of the procedure is to use mean energy $\langle{H}\rangle$ as
an entanglement witness: $\langle{H}\rangle\geq n\epsilon_{sep}$ holds for all
separable states, while at least the ground state violates this bound. This
fact can be exploited to develop an efficient probabilistic procedure by
employing a tomographically complete set of measurements. In this case, the
operator $H$ translates into a classical random variable $H_{[n]}$ which
serves to witness entanglement in practice (the general procedure is explained
in detail in the next Section 2.3). The central object for our detection
protocol is then the following overall cost function:

$S_{[n]}=\left\\{\begin{array}[]{ll}1,&\hbox{$H_{[n]}\leq
n(\epsilon_{sep}-\delta)$;}\\\
0,&\hbox{$H_{[n]}>n(\epsilon_{s}-\delta)$,}\end{array}\right.$ (20)

where $0<\delta<\epsilon_{sep}-\epsilon_{0}=g_{E}$ is a free parameter. Since
$\langle{H}\rangle\geq n\epsilon_{sep}$ holds for all separable states, for
the case of $n$ being large, $H_{[n]}$ is unlikely to precede the separable
bound $n\epsilon_{sep}$ in a single-shot experiment. Indeed, analogously to
the previous two examples, one can derive the Chernoff bound for all separable
states:

$\displaystyle{P}_{\rho_{sep}}[S_{[n]}=1]$ $\displaystyle\leq$
$\displaystyle\exp\left[-n\kappa^{2}\delta^{2}\right],$ (21)

where $\kappa>0$ is constant. Thus, for all separable inputs, the probability
of success vanishes exponentially fast with $n$. In contrast, for the ground-
state preparation $\ket{\psi_{0}}$, the probability of success reaches $1$ in
the thermodynamic limit, as it follows from the following bound:

${P}_{\psi_{0}}[S_{[n]}=1]\geq 1-\frac{\beta^{2}}{n(g_{E}-\delta)^{2}},$ (22)

where $\beta>0$ is constant. The first inequality (21) is the consequence of
the McDiarmid’s inequality, while the second (22) is derived by using the
Chebyshev’s inequality. Both bounds are rigorously derived in the
Supplementary Information of dimic2018single .

####  2.2.4 Tolerance to noise

In the end, we briefly comment on the effects of noise on single-copy
entanglement detection. Consider a $n$-partite target state $\rho_{0}$ which
passes the single-copy test with probability $p_{0}$. In practice, one needs
on average $1/p_{0}$ copies of $\rho_{0}$ to detect entanglement. On the other
hand, let the separable bound hold, meaning that the probability of success
for all separable inputs is exponentially small in $n$. We consider a mixture
$\rho=\lambda\rho_{sep}+(1-\lambda)\rho_{0}$, where $\rho_{sep}$ is an
arbitrary separable state and parameter $0<\lambda<1$ quantifies the amount of
noise. The overall probability of success is a mixture of probabilities
$P_{\rho}=\lambda
P_{\rho_{sep}}+(1-\lambda)P_{\rho_{0}}\approx(1-\lambda)p_{0}$, as long as
$(1-\lambda)p_{0}$ is significantly larger than $P_{\rho_{sep}}=O(\exp[-nc])$.
This implies that noise impacts detection by suppressing the probability of
success by a factor $1-\lambda$, for any kind of noise representable by a
separable state. Therefore, one requires on average
$\frac{1}{(1-\lambda)p_{0}}$ experimental runs to confirm the presence of
entanglement. This represents a strong resistance to noise as long as
$(1-\lambda)p_{0}$ is not exponentially small in $n$. For example, if we
consider $(1-\lambda)p_{0}>0$ constant and independent of $n$, then we verify
entanglement with a fixed cost in terms of the number of samples. This
described scenario is very different in comparison with conventional detection
techniques. Generally, a witnessing method tolerates noise below a certain
critical point, i.e. $\lambda<\lambda_{c}$, meaning that if noise passes the
threshold, the scheme fails to detect entanglement.

###  2.3 Entanglement detection with a few copies

In this section we review an entanglement detection method where the required
number of copies grows logarithmically slow with the confidence as shown in
equation (3). The main goal of this section is to translate one of the most
common methods for entanglement detection, that is, the one based on
entanglement witnesses terhal2000bell ; bruss2002reflections  (see
guhne2009entanglement  for concise review), into an efficient framework that
requires only a few experimental repetitions. What makes the witness-based
technique practical is the simplicity of its detection criterion, based on a
simple mean value estimation of a single (witness) observable. Specifically,
an observable $W$ is designated a witness if
$\langle{W}\rangle=\mathrm{Tr}(W\rho_{s})\geq 0$ for all separable states
$\rho_{s}$, while $\langle{W}\rangle<0$ holds for at least one entangled
state. In principle, we can construct an entanglement witness for every
entangled state $\rho$ (theorem of completeness of witnesses
horodecki2001separability ), which is then used to detect entanglement in a
target state. While straightforward, a drawback of the method is that the
witness $W$ cannot be accessed locally, instead it must be decomposed into a
sum of local observables $W=\sum_{i=1}^{L}W_{i}$ that must be individually
estimated. This means that the mean value $\langle{W}\rangle$ is obtained from
the $\langle{W_{i}}\rangle$’s, each of which is measured in an independent
experiment. The sampling complexity of the procedure is therefore dependent on
the number of local terms $L$, which become a significant factor for generic
witnesses on a large system. To overcome this problem, remarkable effort has
been put into constructing entanglement witnesses whose measurement requires a
smaller number of measurement settings, thus reducing the experimental
requirements laskowski2013optimized ; knips2016multipartite ;
chen2020verification ; bavaresco2018measurements  (for more references, see
recent review friis2019entanglement ). For example, refs. guhne2002detection ;
lu2007experimental  find optimal decompositions of entanglement witnesses into
a few local operators, even reducing in some cases the witness decomposition
to only two local operators toth2005detecting . However, even with a minimal
number of measurement settings, this method may become inconvenient or even
unfeasible simply due to the lack of sufficient number of copies of the
resource state needed to extract the witness expectation value. In such cases,
alternative methods going beyond mean-value extraction are required. We review
here the general method developed in Ref. saggio2019experimental  that
translates the witness method into a resource-efficient probabilistic
framework described in Section 2. In this scenario, the typical procedure
achieves very high confidence in entanglement detection with just few
experimental repetitions (copies of target state). As we shall see, the number
of measurement settings involved into the local decomposition is not the
crucial parameter determining the sampling complexity, in contrast to the
standard belief toth2005detecting . We also review an experiment performed
with a photonic system to test the practicality of the method.

####  2.3.1 Embedding entanglement witnesses in a probabilistic detection
framework

The aim of this section is to review the translation of any entanglement
witness into the probabilistic framework. As previously discussed, an
entanglement witness $W$ is normalised such that

$\displaystyle\ \ \langle{W}\rangle_{s}=\mathrm{Tr}(W\rho_{s})\geq 0$ (23)

for all separable states $\rho_{s}$. On the other hand there exist at least
one entangled state $\rho$ for which $\langle{W}\rangle=\mathrm{Tr}(W\rho)<0$.
The witness operator is normally tailored to detect entanglement in the
vicinity of some target state for which $\langle{W}\rangle$ reaches the lowest
possible value. We shall slightly change the general form of $W$ and introduce
the witness operator $O$ in the following way:

$W=\gamma_{s}\mathds{1}-O,$ (24)

thus equation (23) translates to

$\langle{O}\rangle_{s}=\mathrm{Tr}(O\rho_{s})\leq\gamma_{s}$ (25)

for all separable states $\rho_{s}$. Now $O$ can be decomposed in terms of $L$
local observables $O_{i}$ as $O=\sum_{i=1}^{L}O_{i}$, where each $O_{i}$ can
be turned into a non-negative observable by adding a constant term, i.e.
$O_{i}^{{}^{\prime}}=O_{i}+\alpha_{i}\mathds{1}\geq 0$ with $\alpha_{i}\geq
0$. Thus we get a new witness operator
$O^{{}^{\prime}}=\sum_{i=1}^{L}O_{i}^{{}^{\prime}}=\sum_{i=1}^{L}(O_{i}+\alpha_{i}\mathds{1})=O+\alpha\mathds{1}$,
with $\alpha=\sum_{i}\alpha_{i}$, which is positive semi-definite operator.
Inequality (25) translates to the new condition:

$\langle{O^{{}^{\prime}}}\rangle_{s}=\langle{O}\rangle_{s}+\alpha
L\leq\gamma_{s}+\alpha L$ (26)

for all separable states $\rho_{s}$. We now write the spectral decomposition
of $O_{i}^{{}^{\prime}}$ in terms of eigenprojectors (i.e. binary observables)
$M_{ik}$ as $O_{i}^{{}^{\prime}}=\sum_{k=1}^{J_{i}}\lambda_{ik}M_{ik}$, where
$\lambda_{ik}\geq 0$ because $O_{i}$’s are non-negative. Here $J_{i}$ counts
the non-zero eigenvalues of $O_{i}$. Since $O_{i}^{{}^{\prime}}$ are local,
$M_{ik}$ can be as well chosen to be local operators. To simplify the
notation, we define the constant
$\tau=\sum_{i=1}^{L}\sum_{k=1}^{J_{i}}\lambda_{ik}$ and we set
$\mu_{ik}=\lambda_{ik}/\tau\geq 0$. Finally, the witness condition (26) reads

$\sum\limits_{i=1}^{L}\sum\limits_{k=1}^{J_{i}}\mu_{ik}\mathrm{Tr}(M_{ik}\rho_{s})\leq\frac{\gamma_{s}+\alpha
L}{\tau}=p_{s},$ (27)

for all separable states $\rho_{s}$. The last formula completely determines a
probabilistic procedure for detection. Namely, since $\sum_{ik}\mu_{ik}=1$ and
$\mu_{ik}\geq 0$, these numbers are sampling probabilities for local binary
observables $M_{ik}$. The LHS of the equation is just the probability of
success to get $M_{ik}=1$, while the RHS is the corresponding separable bound
$p_{s}$. On the other hand, for target state preparations we have violation of
separable bound (26) which directly translates to a different probability of
success (the entanglement value) $p_{e}=(\gamma_{e}+\alpha L)\tau$, with
$\gamma_{e}>\gamma_{s}$ or equivalently the deviation $p_{e}-p_{s}>0$.

To summarise, the procedure consists of the following steps:

  * 1.

Randomly measure observables $M_{ik}$ (with probability $\mu_{ik}$) $N$ times
to get the sequence of results $m_{1},...,m_{N}$;

  * 2.

Calculate the observed success rate $S_{[N]}=\frac{1}{N}(m_{1}+...+m_{N})$.

As before, we do not expect $S_{[N]}$ to significantly exceed the separable
bound $p_{s}$ for all separable states, which is encapsulated into the
following Chernoff bound

${P_{\rho}}_{s}[S_{[n]}\geq p_{s}+\epsilon]\leq
e^{-D(p_{s}+\epsilon||p_{s})N}.$ (28)

On the other hand, for target state preparation we expect $S_{[N]}\approx
p_{e}$ and thus the average number of target-state copies needed to achieve
some fixed confidence $C=1-\delta$ is estimated as

$N\approx\frac{\log\delta^{-1}}{D(p_{e}||p_{s})}.$ (29)

This number grows in a logarithmic fashion with the required confidence and as
we shall see from examples below, only a few copies are needed to detect
entanglement with a very high confidence.

####  2.3.2 Example I: Projective witness for graph states

Consider the standard projective witness for a graph state $\ket{G}$
guhne2009entanglement :

$W_{1}=\frac{1}{2}\mathds{1}-\outerproduct{G}{G},$ (30)

tailored for detection of genuine multipartite entanglement. This witness
comes already in the form of (24), and it is therefore straightforward to
identify the parameter $\gamma_{s}=1/2$ and the observable
$O=\outerproduct{G}{G}$. We also have the local decomposition
$O=\sum_{i=1}^{2^{n}}S_{i}/2^{n}$, where $S_{i}$ are stabilizers of state
$\ket{G}$ and are in general tensor products of the Pauli operators
browne2016one . One can therefore easily identify $L=2^{n}$ and
$O_{i}=S_{i}/2^{n}$. The operators $O_{i}$ have to be shifted for
$\alpha_{i}=1/2^{n}$ to get non-negative observables
$O^{{}^{\prime}}=\sum_{i=1}^{2^{n}}(S_{i}/2^{n}+\mathds{1}/2^{n})$. These are
already in eigenform, thus we have $J_{i}=1$, $\tau=2$, $\lambda_{i}=2/2^{n}$
and $M_{i}=(S_{i}+\mathds{1})/2$. The sampling probabilities are $1/2^{n}$ and
the separable bound is calculated from

$\sum_{i=1}^{2^{n}}\frac{1}{2^{n}}\mathrm{Tr}(M_{i}\rho_{s})\leq\frac{3}{4}=p_{s}.$
(31)

On the other hand, for the target state preparation
$\rho_{T}=\outerproduct{G}{G}$ we have

$\sum_{i=1}^{2^{n}}\frac{1}{2^{n}}\mathrm{Tr}(M_{i}\rho_{T})=1,$ (32)

thus the entanglement value reads $p_{e}=1$. To estimate the number of copies,
we can choose, for example, a confidence of $1-\delta=0.99$. Equation (29)
gives us $N\approx\mathrm{log}(1-0.99)^{-1}/D(1||3/4)\approx 16$, which is a
notably small number. A naive approach of measuring all $2^{n}$ observables
$M_{i}$ independently will quickly become unfeasible, while with the
probabilistic detection we achieve the same confidence with a constant number
of copies, regardless of the system size.

####  2.3.3 Example II: witness requiring two local measurements

The second example we consider is the witness tailored to detect entanglement
in $n$-qubit cluster state $\ket{C}$ presented in Ref. toth2005detecting  (an
equivalent example is also presented for the GHZ state which in full analogy
can be adapted here). An optimal witness decomposition for detecting genuine
multipartite entanglement requiring only two measurement settings is found:

$W_{2}=3\mathds{1}-2\Big{(}\prod\limits_{\mathrm{even\
}i}\frac{\mathds{1}+G_{i}}{2}+\prod\limits_{\mathrm{odd\
}i}\frac{\mathds{1}+G_{i}}{2}\Big{)},$ (33)

with $i=1,...,n$. The observables $G_{i}$ are called generators of the state
(in this case the cluster state $\ket{C}$), and constitute a subset of the
stabilizing operators $S_{i}$. To translate this witness, we can apply the
procedure described in Section 2.3.1. Firstly, we easily identify
$\gamma_{s}=3$ and $O=2\Big{(}\prod_{\mathrm{even\
}i}\frac{\mathds{1}+G_{i}}{2}+\prod_{\mathrm{odd\
}i}\frac{\mathds{1}+G_{i}}{2}\Big{)}$. We notice that $O$ is already
decomposed into two non-negative binary observables
$M_{1}=\prod_{\mathrm{even\ }i}\frac{\mathds{1}+G_{i}}{2}$ and
$M_{2}=\prod_{\mathrm{odd\ }i}\frac{\mathds{1}+G_{i}}{2}$ and the sampling
probabilities are $1/2$. The separable bound is given by

$\sum_{i=1}^{2}\frac{1}{2}\mathrm{Tr}(M_{i}\rho_{\mathrm{sep}})\leq\frac{3}{4}=p_{s}.$
(34)

On the other hand, the target state preparation returns $p_{e}=1$ and the
estimated number of copies entirely matches the analysis provided in the
previous example. From here we see that although the projective witness (30)
involves exponential terms in the local decomposition, it performs equally
well as the witness with two settings only.

####  2.3.4 Generic witness

In the last two examples the sampling complexity was completely independent of
the system size: the average number of required copies solely depends on the
required confidence for entanglement detection. However, we cannot expect such
size-free behaviour in the general case. The key parameter dictating the
scaling behaviour is the deviation between entanglement value and separable
bound $p_{e}-p_{s}$, which can become asymptotically small with the size of
the system. To illustrate this, we consider the example of the following
witness

$W=(N-1)\mathds{1}-\sum_{i=1}^{n}S_{i},$ (35)

constructed to detect entanglement in the vicinity of the state stabilized by
the set $S_{1},...,S_{n}$ toth2005entanglement . The translation procedure is
very straightforward in this case resulting in the following separable bound

$\sum_{i=1}^{n}\frac{1}{n}\mathrm{Tr}(M_{i}\rho_{\mathrm{sep}})\leq
1-\frac{1}{n}=p_{s},$ (36)

where $M_{i}=(\mathds{1}+S_{i})/2$, while for the target state preparation we
have $p_{e}=1$. In this case, the estimated number of copies is
$N\approx\frac{\log\delta^{-1}}{D(1||1-\frac{1}{n})}$. For large $n$ this can
be approximated with $N\approx n\log\delta^{-1}$, which defines a linear
growth in the system size. In the general case, supposing that
$\epsilon_{0}=p_{e}-p_{s}$ is asymptotically small in $n$, then we have two
regimes: if $p_{e}=1$ formula (29) gives
$N\approx\frac{\log\delta^{-1}}{\epsilon_{0}}$, while for $p_{e}<1$ this
scaling becomes qudratically worse
$N\approx\frac{2p_{e}(1-p_{e})\log\delta^{-1}}{\epsilon_{0}^{2}}$. For a
generic witness, as long as $\epsilon_{0}^{-1}=\mathrm{poly}[n]$, the
procedure remains efficient.

####  2.3.5 Experimental scenario

The theoretical framework presented above was tested in the experiment
presented in Ref. saggio2019experimental . The setup was designed to produce
the following six-photon cluster state

$\displaystyle\ket{Cl_{6}}=$
$\displaystyle\frac{1}{2}(\ket{000000}+\ket{000111}+\ket{111000}-\ket{111111}),$
(37)

which is an equivalent version (up to local unitary transformations) of the
six-qubit H-shaped cluster state depicted in Figure 3a. The state is produced
with a photonic setup where logical qubits are encoded in the photons’
polarization. The entanglement verification test was performed both for
witnesses $W_{1}$ and $W_{2}$ introduced in equations (30) and (33). The
binary observables $M_{i}$ defining the witness $W_{1}$ were sampled $N=160$
times, while the $M_{i}$ constituting $W_{2}$ were drawn $N=150$ times. The
observed deviation $\epsilon=S_{[6]}-3/4$ from the separable bound was plugged
into equation (28) to put the lower bound on the confidence for entanglement
detection. Figures 3b, c provide the experimental plots for the two witnesses.
In the case of witness $W_{1}$, the plot in Figure 3b shows that only 50
copies of the experimental state are needed to verify genuine multipartite
entanglement with at least 0.97 confidence, and that 112 suffice to reach at
least 0.99. In the same way, using the witness $W_{2}$, it is visible from
Figure 3c that 126 copies are enough to reach a confidence of at least 0.97.
The deviation from the expected theoretical values are due to experimental
imperfections that lead to a limited fidelity of $F\approx 0.75$.

Figure 3: Experimental scenario. (a) H-shaped six-qubit cluster state. Each
disk represents a qubit prepared in the superposition state
$\ket{+}=(\ket{0}+\ket{1})\sqrt{2}$, and the solid lines indicate entanglement
between them. (b), (c) Growth of the minimum confidence with the number of
copies. The blue dots represent $C_{\mathrm{min}}$ calculated from equation
(29) for $W_{1}$ (b) and $W_{2}$ (c). The insets show the region where the
confidence stabilizes. The images are adapted from Ref. saggio2019experimental
.

###  2.4 Related work

Probabilistic detection techniques similar to those presented here can be
found in several other works. In the context of Bell’s inequalities, similar
kinds of probabilistic protocols are constructed for the single-shot non-
locality detection araujo2020bell  and entanglement detection via preparation
games weilenmann2020quantum . In the context of quantum state verification
pallister2018optimal ; zhang2019experimental ; zhang2020experimental ;
liu2021universally , a single-shot entanglement verification naturally arises
in bipartite states as long as the dimension of marginal systems becomes
sufficiently large zhu2019general ; zhu2019efficientadversarial . The
generalisation to the GHZ states can be found in li2020optimal . These results
show a more intimate relation between our probabilistic detection and quantum
state verification protocols. This is supported by the fact that our
probability of success (to calculate the cost function) is usually maximised
to 1 for the target state, thus the correct set of outputs does not witness
only the presence of entanglement, it also indicates that the preparation
state is close to the target state. Therefore, it seems that our protocols
naturally extend from entanglement detection to more informative quantum state
verification without significantly increasing the cost in terms of resources.
Given this relation, we will review in what follows the basics of quantum
state verification and its recent extension to the device-independent scenario
and quantum state certification dimicsupicdakic .

####  2.4.1 Quantum state verification and certification

The quantum state verification (QSV) is a protocol that verifies if an unknown
input state is close (in fidelity) to some target state. Due to its simplicity
and low complexity, it has recently attracted a lot of attention in the
community, and several verification protocols have been constructed for
various classes of states zhu2019efficient ; zhu2019optimal ;
liu2021universally ; yu2019optimal ; liu2019efficient ;
takeuchi2018verification  together with experimental demonstrations
zhang2019experimental ; jiang2020towards ; zhang2020classical . From the
theoretical point of view, QSV plays an important role in protocols such as
blind quantum computation and quantum networks hayashi2015verifiable ;
fujii2017verifiable ; hayashi2018self ; markham2020simple ; morimae2013blind ;
takeuchi2019quantum ; perseguers2013distribution ; mccutcheon2016experimental
. In this section, we recall the framework for QSV as defined by
pallister2018optimal . The main goal is to verify if a sequence of states
$S_{N}=\\{\sigma_{1},\cdots,\sigma_{N}\\}$ is close to the target state
$\sigma=\outerproduct{\psi}{\psi}$ by using only local measurements. The
measurement strategy labelled by $\Omega$ thus consists of $L$ different local
measurements $\\{M_{i|m}\\}$, where $m\in\\{1,\cdots,L\\}$ labels the setting
and $i\in\\{0,1\\}$ the binary outcome. In the $k$-th round a measurement from
$\Omega$ is randomly sampled (with probability $p_{k}$) and applied to the
state $\sigma_{k}$. We say that the state $\sigma_{k}$ passed the round if it
returned the output $i=1$. Otherwise, we say it failed. The first time a round
is failed the process is aborted. The measurements are chosen such that the
strategy operator $\hat{\Omega}=\sum_{m}p_{m}M_{1|m}$ is uniquely optimised
for the target state: $\hat{\Omega}\ket{\psi}=+1\ket{\psi}$, meaning that only
target state passes all verification rounds with probability 1. Under the
premise that all emitted states are either $\bra{\psi}\sigma_{k}\ket{\psi}\leq
1-\epsilon$ away from target state or all of them are actually target states
$\sigma_{k}=\outerproduct{\psi}{\psi}$, one can derive the average number of
tests $N=\frac{\log{\delta^{-1}}}{\nu(\Omega)\epsilon}$ needed to achieve the
confidence of $1-\delta$. The value $\nu(\Omega)$ is the so-called spectral
gap which is the second largest eigenvalue of $\hat{\Omega}$.

The sampling complexity of the QSV is only up to a constant factor optimal in
error $\epsilon$, as the best strategy is achieved for the projection on
target state measurement
$\\{\outerproduct{\psi}{\psi},1-\outerproduct{\psi}{\psi}\\}$ resulting in
$\sim\frac{\log{\delta^{-1}}}{\epsilon}$ scaling. While this is a remarkable
result, the downside of the QSV scheme as proposed by pallister2018optimal  is
its impracticality, i.e. the verification condition of all states either being
$1-\epsilon$ away from the target or all being target states. Such assumption
is very hard to justify operationally and extremely hard to achieve in
laboratory jiang2020towards . In our recent work, we relax this assumption and
we fully adapt the protocol to device-independent (DI) quantum state
verification dimicsupicdakic . In this case, all devices are not characterised
nor trusted and all operations are treated as black-boxes colbeck ;
pironio2010random ; diqkd ; scarani . Remarkably, we have shown that the
optimal scaling of $N=O(\frac{\log{\delta^{-1}}}{\epsilon})$ translates to the
DI scenario. The scheme is more practical as it tolerates $O(\epsilon)$
failure events during the verification process without losing the optimal
scaling.

A general drawback of QSV is that the verification process destroys the
quantum resource and the conclusion is made about the resource which is fully
consumed. This prevents the possibility of using it for other protocols and
further processing. The solution to this problem is found in quantum state
certification: a protocol in which a fragment of the resource copies is
measured to authorise the rest of the copies. The pioneering quantum state
certification protocols are developed in zhu2019general ;
zhu2019efficientadversarial . In these works, one explores permutation
symmetry and measures all but one copy, which then serves as a certificate.
The protocol is very powerful as it applies to a generic adversarial scenario,
but it unfortunately consumes $O(N)$ resources to certify a single copy only.
Our new approach on DI QSV developed in dimicsupicdakic  fully extends to
quantum state certification. There a reliable certification scheme is provided
for the case of independent copies to large certificates, e.g. consisting of
$O(N)$ copies. Unfortunately, the full adversarial scenario is still
unresolved and remains for future investigations.

##  3 Universal data records and partial tomography

We have seen that in the limit of tens of copies, one can still construct
powerful techniques that extract surprisingly sophisticated conclusions on
unknown quantum data. We end this review by considering the limits of such
extraction, that is, what is the limit of information one can know about an
arbitrarily sized state given a constant number of copies of that state? Many
things we might wish to know may be formulated as some kind of partial
tomographic task, for example “Is the state entangled?” or “Is the state
$\epsilon$-close to some target quantum state?”. With so many possible
questions for the same target, we might ask ourselves how many of them can be
determined in parallel? Can it be done efficiently or rather, can we
accurately extract multiple classical features from a moderate number of data
samples?

Suppose now we introduce another “resource” to manage in our pursuit of
efficient query protocols; our own indecision. If we do not _a priori_ know
what classical information we wish to extract from our target quantum system,
what choice of measurements maximises our knowledge at a later point? Since
our choice is made _a posteriori_ , then all possible questions we could ask a
state are equally possible and so we must take some kind of _universal data
samples_ that best approximates the space of all possible future queries. This
is certainly achievable via full state tomography. Tomography schemes abound
that aim to attack the difficulty of this task through this tactic, however a
seemingly unavoidable fact of estimating properties of an arbitrary density
operator is the required polynomial number of measurements in the dimension
$d$. More precisely, achieving an absolute error $\epsilon$ in the estimation
of an unknown density matrix requires at least ${O}(d^{2}\epsilon^{-2})$
aaronson2017  copies of a quantum state. This has to be combined with post-
processing which requires storing and manipulation of exponentially large
matrices. Such tasks is certainly beyond the scope for large quantum systems.

On the other hand full state tomography may provide more information than
actually needed. Our task may not require the computation of any feature of a
quantum state but some more restricted class. Clearly there is a resource-gain
trade-off relation as further knowledge requires further resources, but one
can get surprisingly far extracting interesting properties of the system while
needing very little resources. The most significant development towards
addressing this problem in recent times is due to Aaraonsons aaronson2017
breakthrough. Within it he describes a protocol dubbed ’shadow tomography’,
wherein an exponentially sized list (of mean values) of binary observables on
a quantum state of dimension $d$ (mixed or otherwise) may be estimated to high
precision using a measurement sample of $O(\log d)$ size.

The name is derived from the idea that one is not especially interested in the
entire quantum state but rather its projections onto a fixed set of
observables- the lower dimensional ‘shadows’ of a quantum state. With this in
mind, suppose we wish to estimate a set of $M$ linear features
$\\{\mathrm{Tr}[\rho E_{1}],..,\mathrm{Tr}[\rho E_{M}]\\}$ with as few copies
of $\rho$ as possible. Rather surprisingly, shadow tomography shows that $M$
can be exponentially large with only a polynomial resource overhead. This
statement is certainly worthy of consideration given our original problem. The
main result of Aaransons paper is the following theorem:

######  Theorem 1.

(Aarronson aaronson2017 ) Shadow tomography is solvable using only

$N=\tilde{O}\left(\frac{\log{1/\delta}}{\epsilon^{4}}\cdot\log{M}^{4}\cdot\log{d}\right)$
(38)

copies of the target state $\rho$ where the $\tilde{O}$ hides a polylog
factor. The procedure is fully explicit.

The consequences of this should be readily apparent given the preceding
review. A set of binary observables $\\{E_{1},...,E_{M}\\}$ on an arbitrary
quantum state can be estimated to within an $\epsilon$ absolute error with
probability $1-\delta$ using a number of samples that grows logarithmically
with the dimension and size of the estimated set. We direct interested readers
to the original paper for proof of the above theorem and content ourselves
here with answering why this does not immediately solve the problem of partial
tomography. Though shadow tomography is theoretically efficient in most of the
required categories, namely in terms of sample number, computational
complexity and memory complexity, it unfortunately fails when considering the
sophistication of the required measurements. The protocol requests joint
measurements to be made on tensor products of the target state of a size
$\epsilon^{-2}\log{d}$, which are repeatedly measured using carefully
performed non-demolition measurements braginsky1980 , themselves a difficult
procedure to perform in experiments. It is worth noting that it is not shown
that these resource demands are strictly required for the protocol and indeed
this was not a stated goal of the work.

We review here two protocols that go beyond these limitations: _selective
quantum state tomography_ morris2019selective  and _classical shadows_
kueng2019 ; huang2020predicting . The main emphasis here is on low-cost
implementation and a universality property: we ask for the possibility of
extracting _on demand_ (a posteriori) arbitrary features (from a given class)
of a quantum state from some kind of _universal data record_ of moderate size.
To illustrate this, suppose we wish for a protocol that allows for efficient
estimation of a (finite) selection of observables from a continuous class -
after our experiment is complete. On the surface this seems a monstrous
request to make and one that can only begun to be fulfilled by a full state
tomography. Ultimately, we shall see how this is done (for a class of bounded
observables) with a cost that is completely dimension independent and requires
a resource complexity that is $\log M$ for $M$ different features (a linear
cost in exponentially many). The general protocol is illustrated in Figure 4
and it reassembles the one defined in the introductory section with the
difference being the possibility of re-using the same data (a universal
record) to estimate on demand (a posteriori) a feature from some predefined
(continuous) class of features. The protocol is described concretely in
subsequent sections.

Figure 4: Protocol for estimation on demand. The central idea is based around
a two stage procedure: data acquisition and post-processing. In the first
phase the universal data record of size $N$ is collected via some kind of
universal POVM (e.g. information complete measurement). In the second phase,
an user chooses on demand certain feature to extract (e.g. from a continuous
class). A simple post-processing (low memory and computation) of the collected
data furnishes the task, resulting in estimation confined to an absolute error
of $O(\frac{1}{\sqrt{N}})$. Every new estimation (from the same data) comes at
the logarithmic cost thus enabling extraction of $M$ features with the $\log
M$ overhead.

###  3.1 Selective quantum state tomography (SQST)

Our task now is to weaken the stringent requirements on the measurements
required for shadow tomography while still being able to estimate many
operators simultaneously. To begin, let us settle for simultaneous estimation
of the unit operators $A_{ij}=\outerproduct{j}{i}$, where $i=1\dots d$ and $d$
is arbitrarily large. The expectation values of these operators corresponds to
the density operator element $\rho_{ij}$. A naive one-by-one measurement
strategy is obviously inefficient here, as estimation of another unit operator
may then require an entirely new set of measurements resulting in the general
cost growing with the dimension of the system $d$. On the other hand, if one
estimates various functions from the same data sample, wherein each individual
estimation is efficient in the sense of a Chernoff-like bound (1), then we can
ensure the accuracy of multiple estimations within the fixed overall error
only at the logarithmic cost $\log M$ for $M$ parallel estimations (this
follows from a simple union bound boole1847  for multiple random variables).
This point is the crux of the protocol - once a sufficient set of measurements
have been generated for a universal data record (see Figure 4), any density
matrix element $\rho_{ij}$ can be estimated on demand at guaranteed precision
from identical data. To do this without the complexity of measurements
demanded by shadow tomography requires the introduction of a special POVM
based on mutually unbiased bases durt2010 .

To construct the protocol, we shall first pick an adequate set of
measurements. The set of all matrix units $A_{ij}$ forms a basis in the
operator (Hilbert-Schmidt) space, thus the universal data record has to be
constructed from an informationally complete POVM. The simplest and most
practical choice is local measurements which are sufficient for information
completeness in general but they are of limited applicability in the context
of partial tomography kueng2019 . Thus one needs entangled measurements in
general, keeping in mind that these shall be of a low computation complexity
(i.e. implementable via low-depth quantum circuits).

The first such basis that springs to mind is one built from mutually unbiased
bases (MUB)s. MUB sets are groups of orthogonal bases defined on a finite
dimensional (of dimension $d$) Hilbert space. They hold the special property
whereby any two basis elements $\ket{i,m}$ and $\ket{j,n}$ drawn from
different bases – indexed as $m$ and $n$ – have a constant inner product
$|\innerproduct{i,m}{j,n}|^{2}=1/d,\;\forall m\neq n$. Here $i,j=1\dots d$
index the basis elements, while $n,m=1\dots d+1$ label the basis. While there
are infinitely many complete MUBs for a given dimension, we are always free to
apply a global unitary to each element of the set, transforming them into
another while maintaining the inner product between elements. Due to this, we
will always choose the $m=1$ basis to be the computational basis and define
the remaining bases in terms of this set

$\ket{k,m}=\frac{1}{\sqrt{d}}\sum_{l=1}^{d-1}\alpha_{l}^{km}\ket{l,1};\quad
m\neq 1,$ (39)

with $|\alpha_{l}^{km}|=1$. The specific form of $\alpha_{l}^{km}$ is
dependent on the dimension of the underlying Hilbert space, with different
expressions for prime ivonovic1981  and prime power Paterek_opdef  dimensions.
To proceed we use a useful fact Paterek_opdef  about arbitrary operators $A$
acting on the same space our MUB is defined upon, namely that

$A=-\mathrm{Tr}(A)\mathds{1}+\sum_{m=1}^{d+1}\sum_{k=1}^{d}O_{k}^{(m)}\Pi_{k}^{(m)},$
(40)

with $O_{k}^{(m)}=\mathrm{Tr}[A\cdot\Pi_{k}^{(m)}]$. The $\Pi_{k}^{(m)}$ are
constructed from the basis elements of the MUB such that
$\Pi_{k}^{(m)}=\outerproduct{k,m}{k,m}$. The presented decomposition proves
information completeness of MUBs and we can define the corresponding POVM
as$\\{R_{k}^{(m}=\Pi_{k}^{(m)}/d\\}$ with $k,m$ indexed as before.

A particularly critical example may be found in the matrix unit operators. Let
$A_{ij}=\outerproduct{j}{i}$ with $\ket{i}$ defined in the computational basis
and $i\neq j$. Their decomposition (40) adapted to the POVM elements reads

$A_{ij}=\sum_{k=1}^{d}\sum_{m=2}^{d+1}\eta_{ij}^{km}R_{km}.$ (41)

Here $\eta_{ij}^{km}=\alpha_{i}^{km*}\alpha_{j}^{km}$, thus
$|\eta_{ij}^{km}|=1$ which is the crucial property. Since
$\expectationvalue{A_{ij}}=\Tr[\rho A_{ij}]=\rho_{ij}$, measuring a particular
operator element $\rho_{ij}$ amounts to estimating the expectation value of
$A_{ij}$. Given the decomposition above, the mean values
$\expectationvalue{A_{ij}}$ are equivalent to the expectation value of the
random variable $\eta_{ij}^{(s)}\in\\{\eta_{ij}^{km}\,|\,m=2\dots
d+1,k=\\!1\dots d\\}$, associated with outcomes of the POVM
$\\{R_{k}^{(m)}\\}$. Practical implementation of this POVM amounts to randomly
choosing one of $d$ orthonormal basis sets (not including $m=1$) to measure a
copy of $\rho$ in, each with probability $1/d$ of being selected. A tomography
to estimate $\rho_{ij}$ would then proceed by the generation of $N$ copies of
$\rho$, each measured using this POVM. For each measurement outcome, indexed
by $s$, we update an approximation to the above sum as the following estimator

$\rho_{ij}^{\prime}=\frac{1}{N}\sum_{s=1}^{N}\eta_{ij}^{(s)}.$ (42)

To be completely explicit, a selective quantum state tomography would proceed
in experiment as follows:

  1. 1.

Measure a copy of the quantum state $\rho$ using the POVM defined by
$\\{R_{k}^{(m)}\\}$, to get the measurement result $(k,m)$.

  2. 2.

Repeat the procedure $N$ times to get the (universal) measurement record of
outcomes $\\{(k_{1},m_{1}),\dots(k_{N},m_{N})\\}$. This concludes the
experimental phase of the SQST.

  3. 3.

In post processing, chose a particular element $\rho_{ij}$ to compute
$\eta_{ij}^{(s)}$ and the sum in Eq. (42).

  4. 4.

To estimate a different element $\rho_{st}$, simply update the values of $i,j$
to $s,t$ and recompute the estimator, without further measurements.

For statements on performance, we calculate the number of state copies $N$ of
$\rho$ required for the estimator $\rho_{ij}^{\prime}$ to converge to
$\rho_{ij}$ within some error $\epsilon$ and failure probability $\delta$.
Though $\eta_{ij}^{(s)}$ is complex, we may still apply the usual
concentration inequalities by considering $\eta_{ij}^{(s)}$ as two bounded
random variables such that
$|\real[\eta_{ij}^{(s)}]+i\imaginary[\eta_{ij}^{(s)}]|=1$ . Recall that
$\rho_{ij}^{\prime}=N^{-1}\sum_{s=1}^{N}\eta_{ij}^{(s)}$ and note that
$\mathbb{E}[\rho_{ij}^{\prime}]=\rho_{ij}$. So we wish to compute the bound
$\Pr(\left|\rho_{ij}^{\prime}-\mathbb{E}[\rho_{ij}^{\prime}]\right|\geq\epsilon)$.
First, we will isolate the real and complex components of the random variable
$\eta_{ij}^{(s)}$. By the triangle inequality we have that

$\Pr(\left|\rho_{ij}^{\prime}-\mathbb{E}[\rho_{ij}^{\prime}]\right|\geq\epsilon)\leq\Pr(|A|\geq\frac{\epsilon}{\sqrt{2}})+\Pr(|B|\geq\frac{\epsilon}{\sqrt{2}}),$
(43)

for $A=\real(\rho_{ij}^{\prime})-\mathbb{E}[\real(\rho_{ij}^{\prime})]$ and
$B=\imaginary(\rho_{ij}^{\prime})-\mathbb{E}[\imaginary(\rho_{ij}^{\prime})]$.
From here, we may apply Hoeffding’s inequality for bounded random variables to
each term individually to get

$\Pr(\left|\rho_{ij}^{\prime}-\mathbb{E}[\rho_{ij}^{\prime}]\right|\geq\epsilon)\leq
4e^{-\frac{N\epsilon^{2}}{2}}=\delta.$ (44)

We may then deduce the number of copies $N={O}(\epsilon^{-2}\log\delta^{-1})$
required to estimate $\rho_{ij}$ with an error bound
$|\rho_{ij}^{\prime}-\rho_{ij}|<\epsilon$ that occurs with probability greater
than $1-\delta$. This is in tandem with an ${O}(N)$ complexity overhead in
both the required memory and computation, given we need only to store the
outcomes of each measurement and the summation may be computed piece-wise. For
estimation of any $\rho_{ij}$, we need also to account for the diagonal case
$i=j$, something we neglect in the above formulation of SQST. Fortunately the
estimation of the diagonal elements of $\rho_{ii}$ is straightforward. This
stems from the fact that diagonal estimation of density operators is something
of a simple case, achievable with measurement in the computational basis. For
truly arbitrary estimation of the elements of a density operator we thus need
to maintain two measurement records; one for the diagonal elements which gives
the $\rho_{ii}$ directly, and another for the off diagonals $\rho_{ij}$, both
requiring $N={O}(\epsilon^{-2}\log\delta^{-1})$ copies of the state. Finally,
an additional factor must be included if multiple elements are $\rho_{ij}$ to
be estimated, corresponding to $M$ repetitions of step 4 in the experiment.
This amounts to $\log M$ overhead which comes from the union bound resulting
in $N={O}(\epsilon^{-2}\log\delta^{-1}\log M)$ repetition. Remarkably, this
scaling is free of the dimension $d$.

###  3.2 Relation to full tomography and arbitrary observables

It is tempting to conclude that if one can estimate all individual elements of
a density operator efficiently then one may estimate the density operator
itself efficiently. This is true but only in a technical sense - while SQST
will give a bounded error on individual elements with high probability, the
overall error of the estimated quantum state in the usual metrics - namely
trace distance - may be exponentially large. This comes from SQST estimation
error being equivalent to the max norm
$||E||_{\max}\coloneqq\max_{ij}|E_{ij}|\leq\epsilon$ which is related related
to the trace distance norm via

$\frac{1}{\sqrt{d^{3}}}||E||_{1}\leq||E||_{\max}\leq||E||_{1}.$ (45)

This is rather unsurprising as anything else would imply a protocol that
outperforms provably optimal full state tomography aaronson2017 . Of course,
it is still possible to perform state tomography in the supremum norm. In a
similar manner to maximum likelihood estimation, a semidefinite program

$\rho_{p}\coloneqq\operatornamewithlimits{argmin}_{\sigma\succeq
0}||\rho_{L}-\sigma||_{\max},$ (46)

may be constructed that yields positive semi definite solutions from the data
record generated by SQST morris2019selective . Though running such an
optimisation program would not be computationally efficient, the required
sample complexity for all $d^{2}$ elements remains efficient at $\log
d^{2}=2\log d$.

Another interesting point to investigate is the application of SQST to
estimate mean values of observables going beyond matrix units
$\outerproduct{j}{i}$. Consider a general decomposition given in Eq. (40) of
an operator $A$

$A=\sum_{k=1}^{d}a_{k1}\Pi_{k}^{(1)}+\sum_{m=2}^{d+1}\sum_{k=1}^{d}a_{km}\Pi_{k}^{(m)}=A_{0}+\tilde{A},$
(47)

where we intentionally separate decomposition into computational basis which
gives diagonal matrix $A_{0}$ and the rest $\tilde{A}$ matrix with all 0s on
the main diagonal. Furthermore, we restrict our attention to operators bounded
in entrywise 1-norm $||A||_{1}=\sum_{ij}|a_{ij}|$, where $a_{ij}$ are matrix
elements of $A$ in computational basis. Given $||A||_{1}$ bounded we have all
elements $|a_{ij}|\leq||A||_{1}$ also bounded. As before, the estimation is
broken into two stages: estimation of $A_{0}$ which is efficiently done in
computational basis (since $a_{ii}$ are bounded) and estimation of $\tilde{A}$
which is performed by random sampling of MUBs (see previous section). The
corresponding random variable $a_{km}$ is bounded, i.e.
$|a_{km}|=|d\Tr[A^{\prime}\Pi_{k}^{(m)}]|\leq
d\sum_{ij}|a_{ij}||\innerproduct{i,1}{k,m}\innerproduct{k,m}{j,1}|\leq||A||_{1}$,
thus the efficiency of the estimation follows from the Hoeffding bound of Eq.
(44) and we get $N={O}(\epsilon^{-2}\log\delta^{-1}||A||_{1}^{2})$.

The previous analysis shows that operators bounded in entry-wise $l_{1}$-norm
can be efficiently estimated by the SQST procedure. However, these bounds are
not optimal. To see this, suppose we simultaneously estimate the mean values
of $4^{n}-1$ Pauli operators (excluding identity)
$A=\sigma_{1}\otimes...\otimes\sigma_{n}$, where $\sigma_{k}$ is one of the
standard Pauli matrices. We have $||A||_{1}=d=2^{n}$, thus our previous
analysis predicts a sample cost of $N={O}(4^{n}n)$, where the factor
$n\sim\log 4^{n}$ comes from the union bound. However, it is well known
anton2002  that the set of $4^{n}-1$ Pauli operators can be factored into
$2^{n}+1$ groups each composed of $2^{n}-1$ commuting operators with their
common eigenbases being MUBs. This means that a single MUB measurement can
return all $2^{n}$ mean values (of commutative Paulis) at the cost of ${O}(n)$
thus the estimation of all $4^{n}$ requires ${O}(2^{n}n)$ copies (to measure
all in MUBs). This scaling is known to be optimal crawford2021 . Consequently,
this is quadratically better than the estimation given by the norm
$||\cdot||_{1}$ analysis meaning that the derived bounds can be further
improved. One way of doing this is to employ the Bernstein’s inequality
bernstein1946 ; zanten2001  which controls also the variance of the random
variable thus leading to potentially better bounds. Another possibility to
generically improve the scaling is to change the POVMs and type of estimator,
e.g. instead of a simple linear estimator, one may use the median of means
estimator lerasle2019 . This coincides with the next and final scheme in terms
of sample complexity and is superior in terms of measurement complexity and
efficiency for estimation of a general observable bounded in Frobenius norm.
Along with SQST the next scheme called classical shadows kueng2019 ;
huang2020predicting  is an entirely new regime of partial tomography not
previously possible.

###  3.3 Classical shadows

With shadow tomography suggesting the possibility of a sample-efficient
universal algorithm and SQST demonstrating that a degree of generality can
still be achieved with vastly simpler measurements, we close this review with
the current state of the art in efficient quantum tomography. Considering
again the protocol above, we defined an alternative scheme using a generalised
measurement basis - the mutually unbiased bases, producing a partial
tomography protocol that can construct many independent linear functions on a
target state while remaining resource-efficient.

One now wonders why this was the case - a choice of unbiased bases as a first
target for universal measurements is intuitive given that they form an
informationally complete POVM and their very nature of containing minimal
measurement bias, but they work unexpectedly well for an educated guess. A
possible reason for this lies in a so-far unmentioned MUB property, namely
that they form a $t$-design of degree two rotteler2005mubtdesign . While a
full description of $t$-designs is unnecessary here (see eisert2007tdesign
for a complete treatment in the context of quantum mechanics), it is
sufficient to understand that a quantum $t$-design is a probability
distribution that approximates polynomial functions of order $t$ over the
complete distribution for some set. A simple (classical) example are the
average of some polynomial function over the real sphere.

The relevance of this here is that such designs can be used to approximate the
probability distributions of a generalised measurement basis. Higher order
designs better reproduce the key properties of a distribution with a two
design correctly producing the same expectation value and a three design
correctly showing the same sample variance. The natural and immediate question
is what do higher order $t$-designs yield? We clearly see from the Bernstein
inequality that the variance of an observable plays a heavy role in terms of
the efficiency of an estimator, so one may presume that a $t$-design that
reproduces both the correct expectation value and variance of the approximated
distribution will have improved performance again.

Coupled with a statistical trick known as the median-of-means lerasle2019 ,
this is the strategy of Keung et al. kueng2019  who show that through
randomised Clifford measurements (a three-design) they are able to estimate
$M$ observables at a number of samples that grows as

$N=O\left(\frac{||A||_{max}^{2}\log M}{\epsilon^{2}}\log\delta^{-1}\right)$
(48)

with $||A||_{max}=\max(||A_{1}||_{2}\dots,||A_{L}||_{2})$ being the maximum
two-norm (Frobenius) of the $M$ observables to be estimated. Included within
this bound are entanglement witnesses and fidelity estimation, both of which
can be performed efficiently regardless of the system size. With regards to a
two design, a three design (when coupled with sufficient statistical methods)
is slightly more expensive in terms of gate complexity, requiring a cubic
number of Clifford gates to achieve sufficient randomness over the Haar
measure as compared to the linear cost of generating MUB measurements. Both
may be considered computationally efficient however and one gains a powerful
advantage when the use of a three-design Clifford measurement is allowed.

##  4 Concluding remarks

In this work, we have reviewed recent approaches to answering queries of
quantum states of increasing size, while avoiding an unacceptable overhead in
resources. By first considering efficient tomography to be a series of queries
that become exponentially unlikely to pass for all states excepting those that
answer positively, we showed how this leads to hyper-efficient protocols. We
demonstrated this through high-performance entanglement detection using a
single copy of a quantum state; a counter-intuitive result for an estimation
protocol. This was then extended by showing how the same protocol can be used
for cluster states, a specific class of quantum state and the ground states of
local Hamiltonian.

We proceeded to the case where a limited number of state copies is available,
one can work in the few-copy regime and observe the presence of entanglement
in the state with a protocol to translate any entanglement witness into a
probabilistic framework. We showed that this scenario is well-suited for
experimental implementations by reviewing an application to a photonic six-
qubit cluster state. By demonstrating that the method provides the ability to
detect quantum entanglement with very high confidence with only about hundreds
of state copies, the extremely low requirements in terms of time and
experimental resources were confirmed.

With experimental viability in mind, we gave a description of shadow
tomography which set the stage for Selective Quantum State Tomography, showing
how a special choice of POVM leads to the efficient estimation of a wide class
of linear quantum functionals. This in turn leads to the current state of the
art for partial tomography, a $t$-design based protocol using the classical
shadows of a quantum state which leads to efficient estimation of an
exceptionally large class of observables.

This high performance is most clearly seen in the context of possible partial
tomographies performed; namely fidelity estimation (where the observable is
another density operator), entanglement witnesses and entropies, correlation
functions up to order two and the energies of many-body local Hamiltonians.

Beyond the methods presented in this review, it is fair and also worth
mentioning novel techniques that instead employ machine learning to reduce the
verification requirements. In fact, the use of machine learning for quantum
applications is in general experiencing rapid progress and proving useful in
tasks like entanglement detection using neural networks roik2021accuracy ;
yosefpor2020finding  or unsupervised learning chen2021detecting , and quantum
state tomography using neural networks torlai2018neural . It is also pertinent
that a comparable method (to SQST) for estimating elements of a density matrix
exists in the continuous variable (CV) regime. Here, it is known that the
estimation error depends directly on the energies dariano1996 ; gheorg2018 ,
i.e. the estimation error for a matrix element $\rho_{nm}$ increases with $n$
and $m$ ($n,m$ index the energy eigenstates). Notably, the same behaviour is
not observed in SQST of discrete systems which forms a point of interest for
developing tomographic strategies targeting CV systems. With this in mind, it
appears that the time is nigh for an exciting new class of tomographic
protocols, ones without the apparent drawbacks that have plagued state
tomography since its inception allowing for direct probing of quantum systems
in the NISQ technology regime and beyond.

Acknowledgements

J.M. and B.D. acknowledge support from the Austrian Science Fund (FWF) through
BeyondC-F7112. V.S. acknowledges support from the FWF through BeyondC-F7113.
A.G. acknowledges 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.

Conflict of Interest

The authors declare they have no conflict of interest.

## References

  * (1) John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * (2) Julian Kelly, Zijun Chen, Ben Chiaro, Brooks Foxen, John Martinis, and Quantum Hardware Team Team.  Operating and characterizing of a 72 superconducting qubit processor“bristlecone”: Part 1.  APS, 2019:A42–002, 2019.
  * (3) Nicolai Friis, Oliver Marty, Christine Maier, Cornelius Hempel, Milan Holzäpfel, Petar Jurcevic, Martin B Plenio, Marcus Huber, Christian Roos, Rainer Blatt, et al.  Observation of entangled states of a fully controlled 20-qubit system.  Physical Review X, 8(2):021012, 2018.
  * (4) Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.
  * (5) Hui Wang, Jian Qin, Xing Ding, Ming-Cheng Chen, Si Chen, Xiang You, Yu-Ming He, Xiao Jiang, L You, Z Wang, et al.  Boson sampling with 20 input photons and a 60-mode interferometer in a 1 0 14-dimensional hilbert space.  Physical review letters, 123(25):250503, 2019.
  * (6) Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, et al.  Quantum walks on a programmable two-dimensional 62-qubit superconducting processor.  Science, 372(6545):948–952, 2021.
  * (7) Sepehr Ebadi, Tout T Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, et al.  Quantum phases of matter on a 256-atom programmable quantum simulator.  Nature, 595(7866):227–232, 2021.
  * (8) Gary J Mooney, Gregory AL White, Charles D Hill, and Lloyd CL Hollenberg.  Whole-device entanglement in a 65-qubit superconducting quantum computer.  arXiv preprint arXiv:2102.11521, 2021.
  * (9) Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * (10) Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.  Strong quantum computational advantage using a superconducting quantum processor.  arXiv preprint arXiv:2106.14734, 2021.
  * (11) Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al.  Phase-programmable gaussian boson sampling using stimulated squeezed light.  arXiv preprint arXiv:2106.15534, 2021.
  * (12) Daniel FV James, Paul G Kwiat, William J Munro, and Andrew G White.  On the measurement of qubits.  In Asymptotic Theory of Quantum Statistical Inference: Selected Papers, pages 509–538. World Scientific, 2005.
  * (13) Emanuel Knill, Dietrich Leibfried, Rolf Reichle, Joe Britton, R Brad Blakestad, John D Jost, Chris Langer, Roee Ozeri, Signe Seidelin, and David J Wineland.  Randomized benchmarking of quantum gates.  Physical Review A, 77(1):012307, 2008.
  * (14) David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert.  Quantum state tomography via compressed sensing.  Physical review letters, 105(15):150401, 2010.
  * (15) Anna Pappa, André Chailloux, Stephanie Wehner, Eleni Diamanti, and Iordanis Kerenidis.  Multipartite entanglement verification resistant against dishonest parties.  Physical review letters, 108(26):260502, 2012.
  * (16) Minh Cong Tran, Borivoje Dakić, François Arnault, Wiesław Laskowski, and Tomasz Paterek.  Quantum entanglement from random measurements.  Physical Review A, 92(5):050301, 2015.
  * (17) Ashley Montanaro.  Learning stabilizer states by bell sampling.  arXiv preprint arXiv:1707.04012, 2017.
  * (18) Sam Pallister, Noah Linden, and Ashley Montanaro.  Optimal verification of entangled states with local measurements.  Physical review letters, 120(17):170502, 2018.
  * (19) Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo.  Neural-network quantum state tomography.  Nature Physics, 14(5):447–450, 2018.
  * (20) Huangjun Zhu and Masahito Hayashi.  Efficient verification of hypergraph states.  Physical Review Applied, 12(5):054047, 2019.
  * (21) M Guţă, J Kahn, R Kueng, and J A Tropp.  Fast state tomography with optimal error bounds.  Journal of Physics A: Mathematical and Theoretical, 53(20):204001, apr 2020.  doi:10.1088/1751-8121/ab8111.
  * (22) Hsin-Yuan Huang and Richard Kueng.  Predicting features of quantum systems from very few measurements.  arXiv preprint arXiv:1908.08909, 2019.
  * (23) Aleksandra Dimić and Borivoje Dakić.  Single-copy entanglement detection.  npj Quantum Information, 4(1):1–8, 2018.
  * (24) 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.
  * (25) Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.
  * (26) Huangjun Zhu and Masahito Hayashi.  Optimal verification and fidelity estimation of maximally entangled states.  Physical Review A, 99(5):052346, 2019.
  * (27) Aleksandra Dimić, Ivan Šupić, and Borivoje Dakić.  Sample-efficient device-independent quantum state verification and certification.  arXiv preprint arXiv:2105.05832, 2021.
  * (28) Scott Aaronson.  Shadow tomography of quantum states.  SIAM Journal on Computing, 49(5):STOC18–368, 2019.
  * (29) Joshua Morris and Borivoje Dakić.  Selective quantum state tomography.  arXiv preprint arXiv:1909.05880, 2019.
  * (30) 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, Jun 2020.  URL: http://dx.doi.org/10.1038/s42254-020-0186-4, doi:10.1038/s42254-020-0186-4.
  * (31) Steven T Flammia and Yi-Kai Liu.  Direct fidelity estimation from few pauli measurements.  Physical review letters, 106(23):230501, 2011.
  * (32) Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki.  Quantum entanglement.  Reviews of modern physics, 81(2):865, 2009.
  * (33) Nicolai Friis, Giuseppe Vitagliano, Mehul Malik, and Marcus Huber.  Entanglement certification from theory to experiment.  Nature Reviews Physics, 1(1):72–87, 2019.
  * (34) Otfried Gühne and Géza Tóth.  Entanglement detection.  Physics Reports, 474(1-6):1–75, 2009.
  * (35) Barbara M Terhal.  Bell inequalities and the separability criterion.  Physics Letters A, 271(5-6):319–326, 2000.
  * (36) Dagmar Bruß, J Ignacio Cirac, Pawel Horodecki, Florian Hulpke, Barbara Kraus, Maciej Lewenstein, and Anna Sanpera.  Reflections upon separability and distillability.  Journal of Modern Optics, 49(8):1399–1418, 2002.
  * (37) Flavio Baccari, Daniel Cavalcanti, Peter Wittek, and Antonio Acín.  Efficient device-independent entanglement detection for multipartite systems.  Physical Review X, 7(2):021042, 2017.
  * (38) Rafael Rabelo, Melvyn Ho, Daniel Cavalcanti, Nicolas Brunner, and Valerio Scarani.  Device-independent certification of entangled measurements.  Physical Review Letters, 107(5):050502, 2011.
  * (39) Reinhard F Werner and Michael M Wolf.  Bell inequalities and entanglement.  arXiv preprint quant-ph/0107093, 2001.
  * (40) Y Akbari-Kourbolagh and M Azhdargalam.  Entanglement criterion for multipartite systems based on quantum fisher information.  Physical Review A, 99(1):012304, 2019.
  * (41) Philipp Hyllus, Wiesław Laskowski, Roland Krischek, Christian Schwemmer, Witlef Wieczorek, Harald Weinfurter, Luca Pezzé, and Augusto Smerzi.  Fisher information and multiparticle entanglement.  Physical Review A, 85(2):022321, 2012.
  * (42) Nan Li and Shunlong Luo.  Entanglement detection via quantum fisher information.  Physical Review A, 88(1):014301, 2013.
  * (43) Yuan-Yuan Zhao, Guo-Yong Xiang, Xiao-Min Hu, Bi-Heng Liu, Chuan-Feng Li, Guang-Can Guo, René Schwonnek, and Ramona Wolf.  Entanglement detection by violations of noisy uncertainty relations: A proof of principle.  Physical review letters, 122(22):220401, 2019.
  * (44) Otfried Gühne and Norbert Lütkenhaus.  Nonlinear entanglement witnesses.  Physical review letters, 96(17):170502, 2006.
  * (45) Jeremy C Adcock, Sam Morley-Short, Joshua W Silverstone, and Mark G Thompson.  Hard limits on the postselectability of optical graph states.  Quantum Science and Technology, 4(1):015010, 2018.
  * (46) Han-Sen Zhong, Yuan Li, Wei Li, Li-Chao Peng, Zu-En Su, Yi Hu, Yu-Ming He, Xing Ding, Weijun Zhang, Hao Li, et al.  12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion.  Physical review letters, 121(25):250505, 2018.
  * (47) Aleksandra Dimić and Borivoje Dakić.  On the central limit theorem for unsharp quantum random variables.  New Journal of Physics, 20(6):063051, 2018.
  * (48) Otfried Gühne, Géza Tóth, and Hans J Briegel.  Multipartite entanglement in spin chains.  New Journal of Physics, 7(1):229, 2005.
  * (49) Hans J Briegel and Robert Raussendorf.  Persistent entanglement in arrays of interacting particles.  Physical Review Letters, 86(5):910, 2001.
  * (50) Mark R Dowling, Andrew C Doherty, and Stephen D Bartlett.  Energy as an entanglement witness for quantum many-body systems.  Physical Review A, 70(6):062113, 2004.
  * (51) David Perez-Garcia, Frank Verstraete, Michael M Wolf, and J Ignacio Cirac.  Matrix product state representations.  arXiv preprint quant-ph/0608197, 2006.
  * (52) Frank Verstraete, Valentin Murg, and J Ignacio Cirac.  Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems.  Advances in Physics, 57(2):143–224, 2008.
  * (53) 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.
  * (54) Marc Hein, Jens Eisert, and Hans J Briegel.  Multiparty entanglement in graph states.  Physical Review A, 69(6):062311, 2004.
  * (55) Robert Raussendorf and Hans J Briegel.  A one-way quantum computer.  Physical Review Letters, 86(22):5188, 2001.
  * (56) Lior Eldar and Aram W Harrow.  Local hamiltonians whose ground states are hard to approximate.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 427–438. IEEE, 2017.
  * (57) Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki.  Separability of n-particle mixed states: necessary and sufficient conditions in terms of linear maps.  Physics Letters A, 283(1-2):1–7, 2001.
  * (58) Wiesław Laskowski, Christian Schwemmer, Daniel Richart, Lukas Knips, Tomasz Paterek, and Harald Weinfurter.  Optimized state-independent entanglement detection based on a geometrical threshold criterion.  Physical Review A, 88(2):022327, 2013.
  * (59) Lukas Knips, Christian Schwemmer, Nico Klein, Marcin Wieśniak, and Harald Weinfurter.  Multipartite entanglement detection with minimal effort.  Physical review letters, 117(21):210504, 2016.
  * (60) Yuanyuan Chen, Sebastian Ecker, Jessica Bavaresco, Thomas Scheidl, Lixiang Chen, Fabian Steinlechner, Marcus Huber, and Rupert Ursin.  Verification of high-dimensional entanglement generated in quantum interference.  Physical Review A, 101(3):032302, 2020.
  * (61) Jessica Bavaresco, Natalia Herrera Valencia, Claude Klöckl, Matej Pivoluska, Paul Erker, Nicolai Friis, Mehul Malik, and Marcus Huber.  Measurements in two bases are sufficient for certifying high-dimensional entanglement.  Nature Physics, 14(10):1032–1037, 2018.
  * (62) O Gühne, P Hyllus, D Bruß, A Ekert, M Lewenstein, C Macchiavello, and A Sanpera.  Detection of entanglement with few local measurements.  Physical Review A, 66(6):062305, 2002.
  * (63) Chao-Yang Lu, Xiao-Qi Zhou, Otfried Gühne, Wei-Bo Gao, Jin Zhang, Zhen-Sheng Yuan, Alexander Goebel, Tao Yang, and Jian-Wei Pan.  Experimental entanglement of six photons in graph states.  Nature physics, 3(2):91–95, 2007.
  * (64) Géza Tóth and Otfried Gühne.  Detecting genuine multipartite entanglement with two local measurements.  Physical review letters, 94(6):060501, 2005.
  * (65) Dan Browne and Hans Briegel.  One-way quantum computation.  Quantum Information: From Foundations to Quantum Technology Applications, pages 449–473, 2016.
  * (66) Géza Tóth and Otfried Gühne.  Entanglement detection in the stabilizer formalism.  Physical Review A, 72(2):022340, 2005.
  * (67) Mateus Araújo, Flavien Hirsch, and Marco Túlio Quintino.  Bell nonlocality with a single shot.  Quantum, 4:353, 2020.
  * (68) Mirjam Weilenmann, Edgar A Aguilar, and Miguel Navascues.  Quantum preparation games.  arXiv preprint arXiv:2011.02216, 2020.
  * (69) 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, Jul 2020.  doi:10.1103/PhysRevLett.125.030506.
  * (70) 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, et al.  Experimental optimal verification of entangled states using local measurements.  Physical Review Letters, 125(3):030506, 2020.
  * (71) Ye-Chao Liu, Jiangwei Shang, Rui Han, and Xiangdong Zhang.  Universally optimal verification of entangled states with nondemolition measurements.  Physical Review Letters, 126(9):090504, 2021.
  * (72) Huangjun Zhu and Masahito Hayashi.  General framework for verifying pure quantum states in the adversarial scenario.  Physical Review A, 100(6):062335, 2019.
  * (73) Huangjun Zhu and Masahito Hayashi.  Efficient verification of pure quantum states in the adversarial scenario.  Physical review letters, 123(26):260504, 2019.
  * (74) Zihao Li, Yun-Guang Han, and Huangjun Zhu.  Optimal verification of greenberger-horne-zeilinger states.  Physical Review Applied, 13(5):054002, 2020.
  * (75) Xiao-Dong Yu, Jiangwei Shang, and Otfried Gühne.  Optimal verification of general bipartite pure states.  npj Quantum Information, 5(1):1–5, 2019.
  * (76) Ye-Chao Liu, Xiao-Dong Yu, Jiangwei Shang, Huangjun Zhu, and Xiangdong Zhang.  Efficient verification of dicke states.  Physical Review Applied, 12(4):044020, 2019.
  * (77) Yuki Takeuchi and Tomoyuki Morimae.  Verification of many-qubit states.  Physical Review X, 8(2):021060, 2018.
  * (78) 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(90), Oct 2020.  doi:10.1038/s41534-020-00317-7.
  * (79) Wen-Hao Zhang, Xiao Liu, Peng Yin, Xing-Xiang Peng, Gong-Chu Li, Xiao-Ye Xu, Shang Yu, Zhi-Bo Hou, Yong-Jian Han, Jin-Shi Xu, et al.  Classical communication enhanced quantum state verification.  npj Quantum Information, 6(1):1–6, 2020.
  * (80) Masahito Hayashi and Tomoyuki Morimae.  Verifiable measurement-only blind quantum computing with stabilizer testing.  Physical review letters, 115(22):220502, 2015.
  * (81) Keisuke Fujii and Masahito Hayashi.  Verifiable fault tolerance in measurement-based quantum computation.  Physical Review A, 96(3):030301, 2017.
  * (82) Masahito Hayashi and Michal Hajdušek.  Self-guaranteed measurement-based quantum computation.  Physical Review A, 97(5):052308, 2018.
  * (83) Damian Markham and Alexandra Krause.  A simple protocol for certifying graph states and applications in quantum networks.  Cryptography, 4(1):3, 2020.
  * (84) Tomoyuki Morimae and Keisuke Fujii.  Blind quantum computation protocol in which alice only makes measurements.  Physical Review A, 87(5):050301, 2013.
  * (85) Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi.  Quantum computational universality of hypergraph states with pauli-x and z basis measurements.  Scientific reports, 9(1):1–14, 2019.
  * (86) Sébastien Perseguers, GJ Lapeyre Jr, D Cavalcanti, M Lewenstein, and A Acín.  Distribution of entanglement in large-scale quantum networks.  Reports on Progress in Physics, 76(9):096001, 2013.
  * (87) Will McCutcheon, Anna Pappa, BA Bell, Alex Mcmillan, André Chailloux, Tom Lawson, M Mafu, Damian Markham, Eleni Diamanti, Iordanis Kerenidis, et al.  Experimental verification of multipartite entanglement in quantum networks.  Nature communications, 7(1):1–8, 2016.
  * (88) Roger Colbeck.  Quantum and relativistic protocols for secure multi-party computation.  arXiv preprint arXiv:0911.3814, 2009.
  * (89) 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.
  * (90) 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.
  * (91) Valerio Scarani.  The device-independent outlook on quantum physics (Lecture notes on the power of Bell’s theorem).  Acta Physica Slovaca, 62, 2012.  doi:10.2478/v10155-012-0003-4.
  * (92) Vladimir B. Braginsky, Yuri I. Vorontsov, and Kip S. Thorne.  Quantum nondemolition measurements.  Science, 209(4456):547–557, 1980.  URL: https://science.sciencemag.org/content/209/4456/547, arXiv:https://science.sciencemag.org/content/209/4456/547.full.pdf, doi:10.1126/science.209.4456.547.
  * (93) George Boole.  The Mathematical Analysis of Logic: Being an Essay Towards a Calculus of Deductive Reasoning.  Cambridge University Press, 2009.  doi:10.1017/CBO9780511701337.
  * (94) Thomas Durt, Berthold-Georg Englert, Ingemar Bengtsson, and Karol Źyczkowski.  On mutually biased bases.  International Journal of Quantum Information, 08(04):535–640, 2010\.  arXiv:https://doi.org/10.1142/S0219749910006502, doi:10.1142/S0219749910006502.
  * (95) I D Ivonovic.  Geometrical description of quantal state determination.  Journal of Physics A: Mathematical and General, 14(12):3241–3245, dec 1981.  doi:10.1088/0305-4470/14/12/019.
  * (96) M. Wiesniak, T. Paterek, and A. Zeilinger.  Entanglement in mutually unbiased bases.  New J. Phys. 13, 053047 (2011), 2011.  URL: https://doi.org/10.1088%2F1367-2630%2F13%2F5%2F053047.
  * (97) Jay Lawrence, Časlav Brukner, and Anton Zeilinger.  Mutually unbiased binary observable sets on n qubits.  Phys. Rev. A, 65:032320, Feb 2002.  URL: https://link.aps.org/doi/10.1103/PhysRevA.65.032320, doi:10.1103/PhysRevA.65.032320.
  * (98) Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley.  Efficient quantum measurement of Pauli operators in the presence of finite sampling error.  Quantum, 5:385, January 2021.  doi:10.22331/q-2021-01-20-385.
  * (99) S.N. Bernstein.  The Theory of Probabilities.  Gastehizdat Publishing House, 1946.
  * (100) K. Dzhaparidze and J.H. van Zanten.  On bernstein-type inequalities for martingales.  Stochastic Processes and their Applications, 2001.  URL: https://www.sciencedirect.com/science/article/pii/S0304414900000867, doi:https://doi.org/10.1016/S0304-4149(00)00086-7.
  * (101) Matthieu Lerasle.  Lecture notes: Selected topics on robust statistical learning theory, 2019\.  arXiv:1908.10761.
  * (102) Andreas Klappenecker and Martin Rotteler.  Mutually unbiased bases are complex projective 2-designs.  Proceedings. International Symposium on Information Theory, 2005\. (ISIT 2005.), pages 1740–1744, 2005.  doi:10.1109/ISIT.2005.1523643.
  * (103) Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1), Jul 2009.  URL: http://dx.doi.org/10.1103/PhysRevA.80.012304, doi:10.1103/physreva.80.012304.
  * (104) Jan Roik, Karol Bartkiewicz, Antonín Černoch, and Karel Lemr.  Accuracy of entanglement detection via artificial neural networks and human-designed entanglement witnesses.  Physical Review Applied, 15(5):054006, 2021.
  * (105) Mohammad Yosefpor, Mohammad Reza Mostaan, and Sadegh Raeisi.  Finding semi-optimal measurements for entanglement detection using autoencoder neural networks.  Quantum Science and Technology, 5(4):045006, 2020.
  * (106) Yiwei Chen, Yu Pan, Guofeng Zhang, and Shuming Cheng.  Detecting quantum entanglement with unsupervised learning.  arXiv preprint arXiv:2103.04804, 2021.
  * (107) G M D'Ariano, S Mancini, V I Man'ko, and P Tombesi.  Reconstructing the density operator by using generalized field quadratures.  Quantum and Semiclassical Optics: Journal of the European Optical Society Part B, 8(5):1017–1027, oct 1996.  URL: https://doi.org/10.1088%2F1355-5111%2F8%2F5%2F007, doi:10.1088/1355-5111/8/5/007.
  * (108) Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi.  Verification of quantum computation: An overview of existing approaches.  Theory of Computing Systems, 63(4):715–808, 2018.  URL: https://link.springer.com/article/10.1007%2Fs00224-018-9872-3, doi:10.1007/s00224-018-9872-3.