# Fundamental Limitation on the Detectability of Entanglement

Pengyu Liu  Center for Quantum Information, Institute for Interdisciplinary
Information Sciences, Tsinghua University, Beijing 100084, China  Zhenhuan Liu
Center for Quantum Information, Institute for Interdisciplinary Information
Sciences, Tsinghua University, Beijing 100084, China  Shu Chen  Center for
Quantum Information, Institute for Interdisciplinary Information Sciences,
Tsinghua University, Beijing 100084, China  Xiongfeng Ma<EMAIL_ADDRESS>Center for Quantum Information, Institute for Interdisciplinary Information
Sciences, Tsinghua University, Beijing 100084, China

###### Abstract

Entanglement detection is essential in quantum information science and quantum
many-body physics. It has been proved that entanglement exists almost surely
for a random quantum state, while the realizations of effective entanglement
criteria usually consume exponential resources, and efficient criteria often
perform poorly without prior knowledge. This fact implies a fundamental
limitation might exist in the detectability of entanglement. In this work, we
formalize this limitation as a fundamental trade-off between the efficiency
and effectiveness of entanglement criteria via a systematic method to
theoretically evaluate the detection capability of entanglement criteria. For
a system coupled to an environment, we prove that any entanglement criterion
needs exponentially many observables to detect the entanglement effectively
when restricted to single-copy operations. Otherwise, the detection capability
of the criterion will decay double-exponentially. Furthermore, if multi-copy
joint measurements are allowed, the effectiveness of entanglement detection
can be exponentially improved, which implies a quantum advantage in
entanglement detection problems.

Quantum information technology promises advancement in various information
processing tasks. Currently, we are in a stage where noisy intermediate-scale
quantum devices Preskill (2018) with 50 to 200 qubits can be well manipulated
to demonstrate quantum advantages Arute  _et al._ (2019); Gong  _et al._
(2021); Zhong  _et al._ (2021); Madsen  _et al._ (2022). For these devices,
entanglement generation is regarded as an important benchmark, while the
verification on systems with only 18 qubits is already challenging Wang  _et
al._ (2018). This is rather counter-intuitive as entangled states have been
proved to constitute a large proportion of state-space Życzkowski  _et al._
(1998); Szarek (2005), even for highly mixed states Aubrun  _et al._ (2012).
Moreover, much evidence shows that the verification of entanglement often
consumes exponential resources in real-world experiments Brydges  _et al._
(2019); Elben  _et al._ (2020) or requires precise prior knowledge. Such
observations show that a fundamental limitation could exist in the
detectability of entanglement Lu  _et al._ (2016).

The simplest entanglement verification criteria make use of entanglement
witnesses (EWs) Gühne and Tóth (2009), which are special observables $W$
satisfying $\tr(W\rho)\geq 0,\forall\rho\in\mathrm{SEP}$ where $\mathrm{SEP}$
is the set of all separable states. EW criteria are the simplest and most
practical ones used widely in entanglement detection tasks Lu  _et al._
(2018); Wang  _et al._ (2018). However, the effectiveness of EW criteria
highly depends on the prior knowledge of quantum states. The unpredictable
noise of the prepared states will significantly reduce the success
probabilities of EW criteria.

Some other commonly-used criteria might utilize positive maps,
$\mathcal{N}:\mathcal{N}(M)>0$ if $M>0$. These criteria can detect those
states satisfying $\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\rho)\geq 0$, where
$A$ and $B$ are the two parties of $\rho$ and $\mathbb{I}$ is the identity
operation. The well-known positive partial transposition (PPT) criterion Peres
(1996) is one kind of positive map criteria. Compared with EW criteria, the
detection capability of a single positive map is much higher (in fact, a
positive map criterion is equivalent to a set of infinite EWs). However,
because positive map criteria depend on the positive test of a high-
dimensional matrix, the verification of positive map criteria usually consumes
exponential resources Zhou  _et al._ (2020); Elben  _et al._ (2020).

In addition to EW and positive map criteria, many case studies investigating
the detection capability of some specific entanglement criteria Collins and
Nechita (2016); Žnidarič  _et al._ (2007); Bhosale  _et al._ (2012);
Shapourian  _et al._ (2021); Jivulescu  _et al._ (2014, 2015); Aubrun and
Nechita (2012) also suggest that a trade-off may exist between the
effectiveness and the sample complexity of any entanglement detection
criterion. However, a general and quantitative study is still missing.

In this work, we develop a systematic method to upper bound the detection
capability of various entanglement criteria, including EW, positive map, and
faithful entanglement criteria. We further generalize it to any entanglement
criteria with single-copy implementations and theoretically formulate a
fundamental trade-off between efficiency and effectiveness, see Theorem 4.
Here we give an informal version.

######  Theorem 1 (Trade-off between Efficiency and Effectiveness, Informal).

To detect the entanglement of a random state coupled to a $k$-dimensional
environment, any entanglement criterion that can be verified experimentally
with $M$ observables is either

  1. 1.

Inefficient: The criterion requires $M=\Omega(k/\ln k)$ observables to verify,
or

  2. 2.

Ineffective: The criterion can detect the entanglement successfully with a
probability $P=e^{-\Omega(k)}$ even if the state is entangled.

Explicitly speaking, we investigate the entanglement within a bipartite system
$AB$, and system $R$ is their purification with dimension $k$. The composite
system $ABR$ as a whole is in a random pure state. System $R$ can be regarded
as the environment of $AB$, representing either the uncontrollable noise or
some system that is not of concern. Such a composite system $ABR$ often
appears in many-body physics as it can be generated by a generic Hamiltonian.
Note that $k$ usually scales exponentially with the environment size. So,
according to Theorem 1, the number of observables increases exponentially, and
the detection capability decreases double-exponentially with the environment
size.

To formalize our study quantitatively, here we give a formal definition of
density state distribution Collins and Nechita (2016); Nechita (2007).

######  Definition 1 ($k$-induced Distribution of Density Matrix).

$\pi_{d,k}$ is the distribution in $\mathcal{D}(\mathcal{H})$ induced by the
uniform distribution of pure states in $\mathcal{H}\otimes\mathcal{H}_{R}$,
where the dimensions of $\mathcal{H}$ and $\mathcal{H}_{R}$ are $d$ and $k$
respectively. A state $\rho$ following the distribution $\pi_{d,k}$ can be
generated by $\rho=\tr_{R}(\outerproduct{\phi}{\phi})$, where $\ket{\phi}$ is
a Haar-measured pure state in $\mathcal{H}\otimes\mathcal{H}_{R}$.

With this definition, we can define the detection capability of the EW
criterion with $W$ as

$\mathcal{C}_{k}(W)=\Pr_{\rho\sim\pi_{d,k}}\bqty{\tr(W\rho)<0},$ (1)

which represents the portion of states that can be detected by $W$. Without
loss of generality, hereafter, we assume the two subsystems $A$ and $B$ are
equal in dimension, $d_{A}=d_{B}=\sqrt{d}$. It has been proved that when
$k<cd^{\frac{3}{2}}$, where $c$ is some constant, a state following
$\pi_{d,k}$ distribution is entangled with probability $1$ asymptotically
Aubrun  _et al._ (2012). Throughout the letter, we will always assume
$k<cd^{\frac{3}{2}}$ so that the definition of $\mathcal{C}_{k}(W)$ can also
be viewed as the ratio of detected states to all entangled states.

Using Laurent-Massart’s lemma Laurent and Massart (2000), we can give an upper
bound of the detection capability of EW Criteria.

######  Theorem 2 (Detection Capability of EW Criteria).

The detection capability of an EW criterion with $W$ decays at least
exponentially with the dimension of the environment

$\mathcal{C}_{k}(W)<2\mathrm{e}^{-(\sqrt{1+\alpha}-1)^{2}k}\leq
2\mathrm{e}^{-(3-2\sqrt{2})k},$ (2)

where $\alpha=\frac{\tr(W)}{\sqrt{\tr(W^{2})}}\geq 1$ Johnston and Patterson
(2018) is a witness-dependent factor.

This theorem explains why the effectiveness of EW criteria highly depends on
the prior knowledge of the studied states, as the detection capability
decreases double-exponentially fast with the environment size. It is also
worth mentioning that this result holds for multipartite EWs and the leftmost
inequality holds for any observable $O$ with a positive trace.

To better understand this theorem, we use Fig. 1 to sketch the idea of this
theorem. Using this figure, we illustrate why $\alpha$ has a minimum value and
why the detection capability decrease as $k$ increase. Detailed proofs of this
theorem can be found in the Appendix A.

Figure 1: Graphical illustration of EW criteria. Here, we use Pauli-Liouville
representation to represent the density matrix and EWs as vectors in the
operator space. The normalized identity $\frac{\mathbb{I}}{\sqrt{d}}$ is the
$x$-axis, and the $y$-axis represents one of the other Pauli basis. The
expectation of an observable can be calculated by the inner product of the
state vector and the observable vector. Because of the trace condition
$\tr(\rho)=1$, the density matrix lies in a hyperplane that is orthogonal to
the $x$-axis. We use red and grey colors to represent the entangled and
separable states. An EW can detect those states colored in yellow with obtuse
angles with the EW. This observation and the fact that any state with a
distance to the maximally mixed state less than a certain threshold is
separable Gurvits and Barnum (2002) ensures that the angle between a valid EW
and $y$-axis is larger than some constant. Quantitatively speaking, this tells
us that $\alpha=\frac{\tr(W)}{\sqrt{\tr(W^{2})}}$ has a minimum value. Without
loss of generality, we assume all the EWs satisfy a normalization condition,
$\tr(W^{2})=\frac{1}{d}$. Thus all the EWs lie in a sphere centralized at the
original point, represented by the dashed circle. Due to the $\alpha\geq 1$
($\tr(W)\geq\frac{1}{\sqrt{d}}$) constraint, valid EWs are within the light
green area. Given an EW, the states that can be detected lie in a fixed area
in the space. When $k$ increases, the distribution of states, represented by
the darkness of the red color, will concentrate towards the maximally mixed
state, making the ratio of states covered by the yellow area decrease
accordingly.

We use two typical examples to illustrate the correctness of our results. The
first example is PPT-type EW, $W=\outerproduct{\phi}{\phi}^{\mathrm{T_{A}}}$,
where $\mathrm{T_{A}}$ is the partial transposition operator acting on
$\mathcal{H}_{A}$ and $\ket{\phi}$ is an arbitrary pure state. In the sense of
detection capability, they are optimal EWs as $\alpha$ achieves its minimum
value, $\alpha=\frac{\tr(W)}{\sqrt{\tr(W^{2})}}=1$, which is irrelevant with
the system dimension, $d$. Hence, we have

$\mathcal{C}_{k}(\outerproduct{\phi}{\phi}^{\mathrm{T_{A}}})=\mathrm{e}^{-\Omega(k)}.$
(3)

In fact, this inequality is rather tight as there exists an constant $c$ such
that
$\mathcal{C}_{k}(\outerproduct{\phi}{\phi}^{\mathrm{T_{A}}})\geq\mathrm{e}^{-ck}$
according to Ref. Žnidarič  _et al._ (2007).

The second example is the faithful EW, defined as
$W=\frac{\mathbb{I}}{\sqrt{d}}-\outerproduct{\Phi}{\Phi}$, where $\mathbb{I}$
is the identity operator and $\ket{\Phi}$ is a maximally entangled state in
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Such kinds of fidelity-based EWs are
commonly used in practical entanglement detection tasks Wang  _et al._ (2018)
as many efficient fidelity estimation protocols exist Huang  _et al._ (2020);
Flammia and Liu (2011). However, Theorem 2 tells us that such an entanglement
witness performs extremely weak in the sense that its detection capability
also decreases with system size since
$\alpha=\frac{\tr(W)}{\sqrt{\tr(W^{2})}}=\sqrt{\frac{d-\sqrt{d}}{2}}$. As a
result,

$\mathcal{C}_{k}\left(\frac{\mathbb{I}}{\sqrt{d}}-\outerproduct{\Phi}{\Phi}\right)=\mathrm{e}^{-\Omega(\sqrt{d}k)}.$
(4)

To make our results more convincing, we conduct several numerical experiments,
as shown in Fig. 2. We generate random states according to distribution
$\pi_{d,k}$ with different values of $d$ and $k$ and use the two kinds of EWs
discussed above to detect it. From Fig. 2a), one could find that the detection
capabilities of all types of EWs exponentially decay with $k$. Besides, the
slopes of the faithful EW with $d=4$ and two PPT EWs are almost the same,
which fulfills the prediction of Theorem 2 as $\alpha=1$ for these three EWs.
The slope of faithful EW with $d=9$ is smaller than the other three EWs,
reflecting that the value of $\alpha$ for faithful EWs increase with system
dimension. In Fig. 2b), we investigate the relation between detection
capability and system dimension. One could find that the detection
capabilities of PPT-type EWs have no apparent changes when increasing the
system dimension. In comparison, the detection capability of faithful EWs
shows exponential decaying behavior, and the slopes decrease as $k$ increases.
These phenomena all satisfy our predictions.

Figure 2: Scaling of Detection Capability of EW Criteria. To numerically
calculate the detection capability, we generate $10^{8}$ density matrices
following $\pi_{d,k}$ for each point and treat them as bipartite states
$\rho_{AB}$ with $d_{A}=d_{B}=\sqrt{d}$. For each randomly generated state, we
use two kinds of EWs to detect it: the PPT type EWs
$W=\outerproduct{\phi}{\phi}^{\mathrm{T_{A}}}$ and the faithful EWs
$W=\frac{\mathbb{I}}{\sqrt{d}}-\outerproduct{\psi}{\psi}$. Here $\ket{\phi}$
is a random state and $\ket{\psi}=U_{A}\otimes
U_{B}\sum_{i=1}^{\sqrt{d}}\ket{ii}$ is a random maximally entangled state,
where $U_{A}$ and $U_{B}$ follow Haar-measure distribution for each randomly
sampled state $\rho_{AB}$.

Since EW criteria highly depend on prior knowledge to succeed, a direct
improvement is to combine a large number of EWs. Naturally, we define an EW
set $\mathcal{W}=\Bqty{W_{i},i=1\cdots N}$ and the corresponding detection
capability as

$\mathcal{C}_{k}(\mathcal{W})=\Pr_{\rho\sim\pi_{d,k}}\bqty{\exists
W\in\mathcal{W}:\tr(W\rho)<0}.$ (5)

By union bound, this finite set of EWs does not change the exponential
decrease trend when $k$ is large:

$\mathcal{C}_{k}\pqty{\mathcal{W}}<2N\mathrm{e}^{-(\sqrt{1+\alpha_{\min}}-1)^{2}k}\leq
2\mathrm{e}^{\ln(N)-(3-2\sqrt{2})k}$ (6)

where
$\alpha_{\min}=\min_{W\in\mathcal{W}}\frac{\tr(W)}{\sqrt{\tr(W^{2})}}\geq 1$.
Therefore, to effectively detect entanglement, a total number of
$\mathrm{e}^{\Omega(k)}$ EWs is required, which is extremely impractical.

There are many other theoretically attractive entanglement criteria and
concepts based on EWs. Examples like the positive map criteria Gühne and Tóth
(2009) and faithful entanglement Weilenmann  _et al._ (2020); Gühne  _et al._
(2021); Riccardi  _et al._ (2021) are equivalent to infinitely many EWs. As a
result, Eq. (6) does not apply directly. To adapt the previous theorem to the
infinite case, here we define parameterized EW.

######  Definition 2 (Parameterized EW Criteria).

Parameterized EW is a set of an infinite number of EWs, which can be
represented by a map $\mathcal{M}$ from $M$ real parameters to EWs in
$\mathcal{D}(\mathcal{H})$, satisfying

$\forall{\bf\it\theta}\in\Theta\subset[-1,1]^{M},\forall\rho\in\mathrm{SEP}:\tr\left[\rho\mathcal{M}({\bf\it\theta})\right]\geq
0,$ (7)

where $\mathcal{M}({\bf\it\theta})$ is a normalized EW satisfying
$\norm{\mathcal{M}(\theta)}_{F}=1$ with
$\norm{A}_{F}=\sqrt{\sum_{i,j}|A_{i,j}|^{2}}$ being the Frobenius norm and
$\Theta$ is the feasible parameter space ensuring
$\mathcal{M}({\bf\it\theta})$ a valid EW. A state $\rho$ can be detected by
this criterion if and only if

$\exists{\bf\it\theta}\in\Theta:\tr\pqty{\rho\mathcal{M}({\bf\it\theta})}<0.$
(8)

Similarly, we can define the detection capability of a parameterized EW as

$\mathcal{C}^{p}_{k}(\mathcal{M})=\Pr_{\rho\sim\pi_{d,k}}\bqty{\exists{\bf\it\theta}\in\Theta:\tr(\rho\mathcal{M}({\bf\it\theta}))<0}.$
(9)

By using a coarse-graining method and adopting Theorem 2, we can derive an
upper bound for $\mathcal{C}^{p}_{k}(\mathcal{M})$.

######  Theorem 3 (Detection Capability of Parameterized EW Criteria).

For any parameterized EW represented by a normalized $l$-Lipschits map
$\mathcal{M}$ satisfying

$\forall{\bf\it\theta},{\bf\it\theta}^{\prime}\in\Theta:\norm{\mathcal{M}({\bf\it\theta})-\mathcal{M}({\bf\it\theta}^{\prime})}_{F}\leq
l\norm{{\bf\it\theta}-{\bf\it\theta}^{\prime}}_{2},$ (10)

the detection capability decays at least exponentially with $k$ after $k$
exceeds a certain threshold,

$\mathcal{C}^{p}_{k}(\mathcal{M})<2\mathrm{e}^{C_{1}-C_{2}k},$ (11)

where $C_{1}=M\ln 4\sqrt{M}ld$, $M$ is the number of real parameters in
$\mathcal{M}$, $C_{2}=(\sqrt{0.5+\alpha_{\min}}-1)^{2}$ where
$\alpha_{\min}=\min_{{\bf\it\theta}}\frac{\tr[\mathcal{M}({\bf\it\theta})]}{\sqrt{\tr[\mathcal{M}({\bf\it\theta})^{2}]}}=\min_{{\bf\it\theta}}\tr[\mathcal{M}({\bf\it\theta})]\geq
1$.

The definition of parameterized EW naturally covers positive map criteria. If
a state $\rho$ does not satisfy
$\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\rho)\geq 0$ for a positive map
$\mathcal{N}$, then
$\exists\ket{\phi}:\tr\left[\rho\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\outerproduct{\phi}{\phi})\right]<0$.
Regarding $\ket{\phi}$ as the parameters ${\bf\it\theta}$ in theorem 3, this
theorem can be applied directly. We leave the detailed discussion in Appendix
B.

Another example of parameterized EW is the faithful entanglement, proposed in
Weilenmann  _et al._ (2020), which refers to those entangled states detected
by faithful EWs as defined before. We define a parameterized EW that is
equivalent to all the faithful EWs as
$\mathcal{M}_{\mathrm{faithful}}({\bf\it\theta})=\pqty{\sqrt{2-\frac{2}{\sqrt{d}}}}^{-1}\pqty{\frac{\mathbb{I}}{\sqrt{d}}-\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}}$,
where $\ket{\phi({\bf\it\theta})}$ is a maximally entangled state Gühne  _et
al._ (2021). One could prove that
$\mathcal{M}_{\mathrm{faithful}}({\bf\it\theta})$ is at least
$\sqrt{2}$-Lipschitz and
$\alpha_{\mathrm{min}}=\sqrt{\frac{d-\sqrt{d}}{2}}\approx\sqrt{\frac{d}{2}}$
when $d$ is large. So that an upper bound for the ratio of faithful entangled
states can be summarized below using Theorem 3.

######  Corollary 1 (Ratio of Faithful Entanglement States).

The set of faithful entangled states has an exponential small ratio in the
state space:

$\Pr_{\rho\sim\pi_{d,k}}[\rho\in\mathrm{FE}]=\mathcal{C}^{p}_{k}\pqty{\mathcal{M}_{\mathrm{faithful}}}<2\mathrm{e}^{C_{1}-C_{2}k}$
(12)

where $\mathrm{FE}$ is the set of all faithful entangled states and
$C_{1}=3d\ln 4d$,
$C_{2}=\pqty{\sqrt{0.5+\sqrt{\frac{d-\sqrt{d}}{2}}}-1}^{2}\approx\sqrt{\frac{d}{2}}$.

This result shows when $k=\Omega(\sqrt{d}\ln d)$, the faithful EWs can hardly
detect entanglement, which is compatible with the numerical results shown in
Ref. Gühne  _et al._ (2021).

Besides positive map and faithful criteria, there are many other entanglement
criteria designed for different scenarios, like the one based on the state
moments Imai  _et al._ (2021); Elben  _et al._ (2020); Liu  _et al._ (2022),
uncertainty relations Duan  _et al._ (2000); Gühne (2004), and machine
learning Gray  _et al._ (2018); Yin  _et al._ (2022). They may use complex
mathematical relations and complicated post-processing to detect the
entanglement. While limited by the basic principles of quantum mechanics and
current technology, only values like $\tr(O\rho)$ can be measured directly.
Hence, we propose a general definition of entanglement criteria with single-
copy realizations.

######  Definition 3 (Single-Copy Criteria).

An entanglement criterion is said to have a single-copy realization if it can
be checked by the expectation of a set of observables
$\mathcal{O}=\Bqty{O_{i}|i=1,\cdots,M}$. After the measurement, one gets the
results, $r_{\rho,i}=\tr(O_{i}\rho),i=1,\cdots,M$, and can decide the feasible
region $F_{\mathcal{O}}(\rho)$ of the state

$F_{\mathcal{O}}(\rho)=\Bqty{\sigma\in\mathcal{D}(\mathcal{H}_{d})|\tr(O_{i}\sigma)=r_{\rho,i},i=1,\cdots,M}.$
(13)

If

$F_{\mathcal{O}}(\rho)\cap\mathrm{SEP}=\varnothing,$ (14)

then $\rho$ is entangled.

According to this definition, we can define the detection capability of the
single-copy criterion $\mathcal{O}$ as

$\mathcal{C}_{k}^{s}(\mathcal{O})=\Pr_{\rho\sim\pi_{d,k}}\bqty{F_{\mathcal{O}}(\rho)\cap\mathrm{SEP}=\varnothing}.$
(15)

Since the verification of Eq. (14) might require exponential classical
resources, many practical entanglement criteria are essentially designed by
finding supersets of $\mathrm{SEP}$ and $F_{\mathcal{O}}(\rho)$ and deciding
whether these two supersets are disjoint or not. Therefore, the previous
definition is the strongest criterion using the measurement results of
$\mathcal{O}$, and Eq. (15) gives an upper bound for all criteria using the
same data.

Without loss of generality, we could assume that all the observables are
mutually orthogonal and normalized, i.e., $\tr(O_{i}O_{j})=\delta_{i,j}$. In
Appendix C, we prove that if a state $\rho$ can be detected by a single-copy
criterion $\mathcal{O}$ which contains $M-1$ observables, then it can be
detected by a $1$-Lipschitz parameterized EW with $M$ parameters.

$\mathcal{M}(\theta_{0},\theta_{1},\cdots,\theta_{M-1})=\theta_{0}\mathbb{I}+\sum_{i=1}^{M-1}\theta_{i}O_{i}$
(16)

Hence, directly adopting Theorem 3, one can give an upper bound for
$\mathcal{C}_{k}^{s}(\mathcal{O})$.

######  Theorem 4 (Detection Capability of Single-Copy Criteria).

Any single-copy entanglement criterion $\mathcal{O}$ with $M-1$ observables
has detection capability:

$\mathcal{C}^{s}_{k}(\mathcal{O})<2\mathrm{e}^{C_{1}-C_{2}k}$ (17)

Where $C_{1}=M\ln 4\sqrt{M}d$, $C_{2}=(\sqrt{1.5}-1)^{2}\approx 0.05$.

Theorem 4 theoretically formulates the trade-off between the effectiveness and
sample complexities of entanglement criteria. According to this theorem, at
least $\Omega(\frac{k}{\ln k})$ observables are needed to effectively detect
the entanglement of a random state, even assuming the measurement results are
infinitely accurate. Besides, compared with Eq. (6), one could conclude that a
general single-copy detection can be exponentially better than simply using a
set of EWs.

Here, we numerically examine the detection capabilities of several nonlinear
criteria, like purity Gühne and Tóth (2009), fisher information Zhang and Fei
(2020), moments of partial transposed Yu  _et al._ (2021); Neven  _et al._
(2021) (labeled by $D_{3,\mathrm{opt}}$) and realigned density matrices Liu
_et al._ (2022) (labeled by $M_{4}$). We leave the description of these four
criteria in Appendix C.3. These criteria all have single-copy realizations
with resources independent of $k$. Therefore, from Fig. 3, one could find that
the detection capabilities of these four criteria decay exponentially with $k$
when $k$ is large, which is compatible with Theorem 4.

Figure 3: Detection Capability of Four Nonlinear Criteria. Here for each
point, we generate $10^{8}$ states
$\rho\in\mathcal{D}(\mathcal{H}_{4}\otimes\mathcal{H}_{4})$ with distribution
$\pi_{16,k}$ and calculate the detection capability of four different
nonlinear entanglement criteria.

Before the exponential decaying period, we also observe that the detection
capabilities hold constant. In Appendix C.4, we analyze these thresholds in
detail and numerically find that they all have polynomial relations with the
system dimension $d$. Like for the $D_{3,\mathrm{opt}}$ criterion, the
threshold is linearly depend on $d$. These observations together with Theorem
4 explain why the verification of these four criteria needs exponential
resource Brydges  _et al._ (2019); Rath  _et al._ (2021); Zhou  _et al._
(2020); Elben  _et al._ (2020); Liu  _et al._ (2022). From another point of
view, if not restricted to single-copy operations, some of these criteria only
need a few multi-copy observables to verify, implying a quantum advantage in
entanglement detection tasks by joint operations Huang  _et al._ (2022).

We can prove this advantage in some special cases. Let
$d_{A}=d_{B}=k=\sqrt{d}$, the distributions of $\tr(\rho_{A}^{2})$ and
$\tr(\rho_{AB}^{2})=\tr(\rho_{R}^{2})$ are completely same as systems $A$ and
$R$ are symmetric. Hence, using the purity criterion, i.e.
$\tr(\rho_{AB}^{2})\leq\tr(\rho_{A}^{2})\ \forall\rho\in\mathrm{SEP}$, the
detection capability is $0.5$ and the criterion can be verified using just one
two-copy observable,
$\tr(\rho_{AB}^{2})-\tr(\rho_{A}^{2})=\tr[(\mathbb{S}_{AB}-\mathbb{S}_{A})\rho_{AB}^{\otimes
2}]$, where $\mathbb{S}$ is the SWAP operator. So we can summarize the results
below.

######  Proposition 1 (Quantum Advantage in Entanglement Detection).

Consider a state following $\pi_{d,\sqrt{d}}$ distribution, and
$d_{A}=d_{B}=\sqrt{d}$. With only single-copy measurements,
$M=\Omega(\frac{\sqrt{d}}{\ln d})$ observables are required for any criterion
with detection capability greater than $0.5$. However, if multi-copy joint
measurements are allowed, one can detect with capability equaling $0.5$ with
only one two-copy observable.

Beyond Definition 3, adaptive methods could also be used to increase the
efficiency of entanglement detection. In Appendix C.2, we give similar results
as Theorem 4 and Proposition 1 for adaptive methods. It should be noticed that
the quantum advantage in Proposition 1 only holds in terms of the number of
observables. While considering real-world experiments where multi-copy
measurements may require much more resources than single-copy ones, will the
advantage still hold soundly? Besides, will Theorem 4 holds when a small
false-positive error rate is allowed? We will leave these questions to future
work.

###### Acknowledgements.

We thank Zhaohui Wei for valuable discussions. This work was supported by the
National Natural Science Foundation of China Grants No. 11875173 and No.
12174216 and the National Key Research and Development Program of China Grants
No. 2019QY0702 and No. 2017YFA0303903.

## References

  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * Arute  _et al._ (2019) F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Nature 574, 505 (2019).
  * Gong  _et al._ (2021) M. Gong, S. Wang, C. Zha, M.-C. Chen, H.-L. Huang, Y. Wu, Q. Zhu, Y. Zhao, S. Li, S. Guo, H. Qian, Y. Ye, F. Chen, C. Ying, J. Yu, D. Fan, D. Wu, H. Su, H. Deng, H. Rong, K. Zhang, S. Cao, J. Lin, Y. Xu, L. Sun, C. Guo, N. Li, F. Liang, V. M. Bastidas, K. Nemoto, W. J. Munro, Y.-H. Huo, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Science 372, 948 (2021).
  * Zhong  _et al._ (2021) H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, J. J. Renema, C.-Y. Lu, and J.-W. Pan, Phys. Rev. Lett. 127, 180502 (2021).
  * Madsen  _et al._ (2022) L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, _et al._ , Nature 606, 75 (2022).
  * Wang  _et al._ (2018) X.-L. Wang, Y.-H. Luo, H.-L. Huang, M.-C. Chen, Z.-E. Su, C. Liu, C. Chen, W. Li, Y.-Q. Fang, X. Jiang, J. Zhang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Phys. Rev. Lett. 120, 260502 (2018).
  * Życzkowski  _et al._ (1998) K. Życzkowski, P. Horodecki, A. Sanpera, and M. Lewenstein, Phys. Rev. A 58, 883 (1998).
  * Szarek (2005) S. J. Szarek, Phys. Rev. A 72, 032304 (2005).
  * Aubrun  _et al._ (2012) G. Aubrun, S. J. Szarek, and D. Ye, Phys. Rev. A 85, 030302 (2012).
  * Brydges  _et al._ (2019) T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Science 364, 260 (2019).
  * Elben  _et al._ (2020) A. Elben, R. Kueng, H.-Y. R. Huang, R. van Bijnen, C. Kokail, M. Dalmonte, P. Calabrese, B. Kraus, J. Preskill, P. Zoller, and B. Vermersch, Phys. Rev. Lett. 125, 200501 (2020).
  * Lu  _et al._ (2016) D. Lu, T. Xin, N. Yu, Z. Ji, J. Chen, G. Long, J. Baugh, X. Peng, B. Zeng, and R. Laflamme, Phys. Rev. Lett. 116, 230501 (2016).
  * Gühne and Tóth (2009) O. Gühne and G. Tóth, Physics Reports 474, 1 (2009).
  * Lu  _et al._ (2018) H. Lu, Q. Zhao, Z.-D. Li, X.-F. Yin, X. Yuan, J.-C. Hung, L.-K. Chen, L. Li, N.-L. Liu, C.-Z. Peng, Y.-C. Liang, X. Ma, Y.-A. Chen, and J.-W. Pan, Phys. Rev. X 8, 021072 (2018).
  * Peres (1996) A. Peres, Phys. Rev. Lett. 77, 1413 (1996).
  * Zhou  _et al._ (2020) Y. Zhou, P. Zeng, and Z. Liu, Phys. Rev. Lett. 125, 200502 (2020).
  * Collins and Nechita (2016) B. Collins and I. Nechita, Journal of Mathematical Physics 57, 015215 (2016).
  * Žnidarič  _et al._ (2007) M. Žnidarič, T. Prosen, G. Benenti, and G. Casati, Journal of Physics A: Mathematical and Theoretical 40, 13787 (2007).
  * Bhosale  _et al._ (2012) U. T. Bhosale, S. Tomsovic, and A. Lakshminarayan, Phys. Rev. A 85, 062331 (2012).
  * Shapourian  _et al._ (2021) H. Shapourian, S. Liu, J. Kudler-Flam, and A. Vishwanath, PRX Quantum 2, 030347 (2021).
  * Jivulescu  _et al._ (2014) M. A. Jivulescu, N. Lupa, and I. Nechita, Journal of Mathematical Physics 55, 112203 (2014).
  * Jivulescu  _et al._ (2015) M. A. Jivulescu, N. Lupa, and I. Nechita, arXiv preprint arXiv:1503.08008 (2015).
  * Aubrun and Nechita (2012) G. Aubrun and I. Nechita, Journal of mathematical physics 53, 102210 (2012).
  * Nechita (2007) I. Nechita, Annales Henri Poincaré 8, 1521 (2007).
  * Laurent and Massart (2000) B. Laurent and P. Massart, The Annals of Statistics 28, 1302 (2000).
  * Johnston and Patterson (2018) N. Johnston and E. Patterson, Linear Algebra and its Applications 550, 1 (2018).
  * Gurvits and Barnum (2002) L. Gurvits and H. Barnum, Phys. Rev. A 66, 062311 (2002).
  * Huang  _et al._ (2020) H.-Y. Huang, R. Kueng, and J. Preskill, Nature Physics 16, 1050 (2020).
  * Flammia and Liu (2011) S. T. Flammia and Y.-K. Liu, Phys. Rev. Lett. 106, 230501 (2011).
  * Weilenmann  _et al._ (2020) M. Weilenmann, B. Dive, D. Trillo, E. A. Aguilar, and M. Navascués, Phys. Rev. Lett. 125, 159903 (2020).
  * Gühne  _et al._ (2021) O. Gühne, Y. Mao, and X.-D. Yu, Phys. Rev. Lett. 126, 140503 (2021).
  * Riccardi  _et al._ (2021) G. Riccardi, D. E. Jones, X.-D. Yu, O. Gühne, and B. T. Kirby, Phys. Rev. A 103, 042417 (2021).
  * Imai  _et al._ (2021) S. Imai, N. Wyderka, A. Ketterer, and O. Gühne, Phys. Rev. Lett. 126, 150501 (2021).
  * Liu  _et al._ (2022) Z. Liu, Y. Tang, H. Dai, P. Liu, S. Chen, and X. Ma, arXiv preprint arXiv:2203.08391 (2022).
  * Duan  _et al._ (2000) L.-M. Duan, G. Giedke, J. I. Cirac, and P. Zoller, Phys. Rev. Lett. 84, 2722 (2000).
  * Gühne (2004) O. Gühne, Phys. Rev. Lett. 92, 117903 (2004).
  * Gray  _et al._ (2018) J. Gray, L. Banchi, A. Bayat, and S. Bose, Phys. Rev. Lett. 121, 150503 (2018).
  * Yin  _et al._ (2022) X.-F. Yin, Y. Du, Y.-Y. Fei, R. Zhang, L.-Z. Liu, Y. Mao, T. Liu, M.-H. Hsieh, L. Li, N.-L. Liu, D. Tao, Y.-A. Chen, and J.-W. Pan, Phys. Rev. Lett. 128, 110501 (2022).
  * Zhang and Fei (2020) Q.-H. Zhang and S.-M. Fei, Laser Physics Letters 17, 065202 (2020).
  * Yu  _et al._ (2021) X.-D. Yu, S. Imai, and O. Gühne, Phys. Rev. Lett. 127, 060504 (2021).
  * Neven  _et al._ (2021) A. Neven, J. Carrasco, V. Vitale, C. Kokail, A. Elben, M. Dalmonte, P. Calabrese, P. Zoller, B. Vermersch, R. Kueng, and B. Kraus, npj Quantum Information 7, 152 (2021).
  * Rath  _et al._ (2021) A. Rath, C. Branciard, A. Minguzzi, and B. Vermersch, Phys. Rev. Lett. 127, 260501 (2021).
  * Huang  _et al._ (2022) H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Science 376, 1182 (2022).

##  Appendix A Detection Capability Upper Bound of EW Criteria

###  A.1 Restriction of Valid EWs

######  Lemma 1 (Restriction of Valid EWs).

For any valid EW $W$ satisfying

$\forall\rho\in\mathrm{SEP}:\tr(W\rho)\geq 0,$ (18)

the following inequality always holds

$\alpha^{2}=\frac{\tr(W)^{2}}{\tr(W^{2})}\geq 1.$ (19)

###### Proof.

Given an EW $W$, without loss of generality, we assume $\tr(W)=1$. Write $W$
in the form

$W=\frac{\mathbb{I}}{d}+\frac{c\sigma}{d}$ (20)

Where $\sigma$ is a hermitian operator satisfying $\tr(\sigma^{2})=d$,
$\tr(\sigma)=0$ and $c$ is a constant. We have

$\tr(W^{2})=\tr(\frac{\mathbb{I}}{d^{2}})+\tr(\frac{c^{2}\sigma^{2}}{d^{2}})+2\tr(\frac{c\sigma}{d^{2}})=\frac{1+c^{2}}{d}.$
(21)

To show $\alpha^{2}=\frac{\tr(W)^{2}}{\tr(W^{2})}\geq 1$, we are going to
prove that $c^{2}\leq d-1$ by constructing a state:

$\rho_{0}=\frac{\mathbb{I}}{d}-\frac{\sigma}{\sqrt{d-1}d}.$ (22)

According to Gurvits and Barnum (2002), the set of separable states has a non-
zero inner radius

$\forall\rho\in\mathcal{D}(\mathcal{H}_{d}),\tr(\rho^{2})\leq\frac{1}{d-1}\to\rho\in\mathrm{SEP}.$
(23)

We can directly verify that

$\tr(\rho^{2}_{0})=\frac{1}{d}+\frac{1}{d(d-1)}=\frac{1}{d-1},$ (24)

which means $\rho_{0}$ is not only a valid state but also separable. Since $W$
is an EW, $\tr(W\rho_{0})\geq 0$.

$\begin{split}\tr(W\rho_{0})&\geq 0\\\ \frac{1}{d}-\frac{c}{d\sqrt{d-1}}&\geq
0\\\ c^{2}&\leq d-1\end{split}$ (25)

So we can conclude that for any valid entanglement witness $W$,

$\alpha^{2}=\frac{\tr(W)^{2}}{\tr(W^{2})}=\frac{d}{1+c^{2}}\geq 1.$ (26)

∎

###  A.2 Proof of Theorem 2

######  Theorem 2 (Detection Capability of EW Criteria).

The detection capability of an EW criterion with $W$ decays at least
exponentially with the dimension of the environment

$\mathcal{C}_{k}(W)<2\mathrm{e}^{-(\sqrt{1+\alpha}-1)^{2}k}\leq
2\mathrm{e}^{-(3-2\sqrt{2})k},$ (27)

where $\alpha=\frac{\tr(W)}{\sqrt{\tr(W^{2})}}\geq 1$ is a witness-dependent
factor.

###### Proof.

We first generalize the definition of detection capability for EW to any
observable $O$ with a positive trace and prove with this generalized
definition. Similarly, define

$\mathcal{C}_{k}(O)=\Pr_{\rho\sim\pi_{d,k}}\bqty{\tr(O\rho)<0}$ (28)

as the detection capability of an observable $O$.

Since $O$ can be decomposed as $O=U_{O}\Lambda_{O}U_{O}^{\dagger}$, where
$U_{O}$ is unitary, and $\Lambda_{O}$ is the eigenvalues of $O$, we can
equivalently rewrite

$\mathcal{C}_{k}(O)=\Pr_{\rho\sim\pi_{d,k}}\bqty{\tr(U_{O}\Lambda_{O}U_{O}^{\dagger}\rho)<0}=\Pr_{\rho\sim\pi_{d,k}}\bqty{\tr(\Lambda_{O}U_{O}^{\dagger}\rho
U_{O})<0}.$ (29)

According to the definition of Haar measure, if $\rho$ follows the
distribution of $\pi_{d,k}$, $U_{O}^{\dagger}\rho U_{O}$ also follows the
distribution of $\pi_{d,k}$ as $U_{O}$ is a fix unitary Nechita (2007).
Therefore,

$\mathcal{C}_{k}(O)=\mathcal{C}_{k}(\Lambda_{O})$ (30)

only depends on the eigenvalues of $O$.

To analyze $\mathcal{C}_{k}(O)$, we need to write down the distribution of
$\rho$ explicitly. According to the definition of $\pi_{d,k}$,
$\rho\in\mathcal{D}(\mathcal{H})$ can be written as the reduced density matrix
in a larger Hilbert space, $\rho=\tr_{R}(\outerproduct{\Psi}{\Psi})$, where
$\ket{\Psi}$ is a random state in $\mathcal{H}\otimes\mathcal{H}_{R}$. The
distribution of $\ket{\Psi}$ can be generated by random Gaussian variables:

$\ket{\Psi}=\sum_{i=1}^{d}\sum_{j=1}^{k}\frac{z_{i,j}}{\sqrt{\tr(ZZ^{\dagger})}}\ket{\phi_{i}}\ket{\psi_{j}},$
(31)

where $z_{i,j}$ is the element of the random complex Gaussian matrix, $Z$
Nechita (2007); $\\{\ket{\phi_{i}}\\}$ and $\\{\ket{\psi_{j}}\\}$ form
orthonormal bases for $\mathcal{H}$ and $\mathcal{H}_{R}$ respectively.
Precisely speaking,

$x_{i,j}=\real(z_{i,j})\sim N(0,1),y_{i,j}=\imaginary(z_{i,j})\sim N(0,1),$
(32)

are all standard Gaussian variables. Hence,

$\rho=\tr_{R}(\outerproduct{\Psi}{\Psi})=\sum_{i,j=1}^{d}\frac{\sum_{l=1}^{k}z_{i,l}z^{*}_{j,l}}{\tr(ZZ^{\dagger})}\ket{\phi_{i}}\bra{\phi_{j}}.$
(33)

Therefore, the detection capability can be written as

$\begin{split}\Pr_{\rho\sim\pi_{d,k}}\bqty{\tr(\Lambda_{O}\rho)<0}=&\Pr_{x_{i,j},y_{i,j}\sim
N(0,1)}\bqty{\pqty{\frac{1}{\tr(ZZ^{\dagger})}}\sum_{i=1}^{d}\sum_{j=1}^{k}\lambda_{i}z_{i,j}z_{i,j}^{*}<0}\\\
=&\Pr_{x_{i,j},y_{i,j}\sim
N(0,1)}\bqty{\sum_{i=1}^{d}\sum_{j=1}^{k}\lambda_{i}(x_{i,j}^{2}+y_{i,j}^{2})<0}.\end{split}$
(34)

We label the positive and negative eigenvalues of $O$ as $a_{1},\cdots,a_{p}$
and $-b_{1}\cdots-b_{q}$ with $a_{i},b_{j}>0$ and $p+q\leq d$. So we can
rewrite Eq. (34) as

$\Pr_{x_{i,j},y_{i,j}\sim
N(0,1)}\bqty{\sum_{i=1}^{d}\sum_{j=1}^{k}\lambda_{i}(x_{i,j}^{2}+y_{i,j}^{2})<0}=\Pr_{x_{i,j},y_{i,j}\sim
N(0,1)}\bqty{\sum_{j=1}^{2k}\pqty{\sum_{i=1}^{p}a_{i}x_{i,j}^{2}-\sum_{i=1}^{q}b_{i}y_{i,j}^{2}}<0},$
(35)

where the $x$ and $y$ in the left-hand and right-hand sides are not the same
variables. We relabel them to make the representation clearer while keeping
them independent variables.

For simplicity, we define ${\bf\it
u}=(a_{1},\dots,a_{p},\dots,a_{1},\dots,a_{p})$ and ${\bf\it
v}=(b_{1},\dots,b_{q},\dots,b_{1},\dots,b_{q})$ which are the $2k$ replica of
${\bf\it a}=(a_{1},\dots,a_{p})$ and ${\bf\it b}=(b_{1},\dots,b_{q})$
respectively. Accordingly,

$\Pr_{x_{i,j},y_{i,j}\sim
N(0,1)}\bqty{\sum_{j=1}^{2k}\pqty{\sum_{i=1}^{p}a_{i}x_{i,j}^{2}-\sum_{i=1}^{q}b_{i}y_{i,j}^{2}}<0}=\Pr_{x_{i},y_{i}\sim
N(0,1)}\left(\sum_{i=1}^{2kp}u_{i}x_{i}^{2}-\sum_{i=1}^{2kq}v_{i}y_{i}^{2}<0\right).$
(36)

Using union bound, we can prove that for any real number $c$

$\begin{split}\Pr_{x_{i},y_{i}\sim
N(0,1)}\left(\sum_{i=1}^{2kp}u_{i}x_{i}^{2}-\sum_{i=1}^{2kq}v_{i}y_{i}^{2}<0\right)&\leq\Pr_{x_{i},y_{i}\sim
N(0,1)}\left(\left(\sum_{i=1}^{2kp}u_{i}x_{i}^{2}\leq
c\right)\cup\left(\sum_{i=1}^{2kq}v_{i}y_{i}^{2}\geq c\right)\right)\\\
&\leq\Pr_{x_{i}\sim N(0,1)}\left(\sum_{i=1}^{2kp}u_{i}x_{i}^{2}\leq
c\right)+\Pr_{y_{i}\sim N(0,1)}\left(\sum_{i=1}^{2kq}v_{i}y_{i}^{2}\geq
c\right).\end{split}$ (37)

To bound this probability, we adopt the Laurent-Massart’s lemma Laurent and
Massart (2000), which states that for non-negative vectors ${\bf\it u}$ and
${\bf\it v}$ and i.i.d. variables $\\{x_{i}\sim N(0,1)\\}$, the following two
inequalities hold for all positive numbers $t_{1}$ and $t_{2}$:

$\begin{split}&\Pr_{x_{i}\sim
N(0,1)}\left(\sum_{i}u_{i}x_{i}^{2}\leq\norm{{\bf\it u}}_{1}-2\norm{{\bf\it
u}}_{2}\sqrt{t_{2}}\right)\leq\mathrm{e}^{-t_{2}}\\\ &\Pr_{y_{i}\sim
N(0,1)}\left(\sum_{i}v_{i}y_{i}^{2}\geq\norm{{\bf\it v}}_{1}+2\norm{{\bf\it
v}}_{2}\sqrt{t_{1}}+2\norm{{\bf\it
v}}_{\infty}t_{1}\right)\leq\mathrm{e}^{-t_{1}}\end{split}$ (38)

where $\norm{{\bf\it v}}_{1}=\sum_{i}\absolutevalue{v_{i}}$ ,$\norm{{\bf\it
v}}_{2}=\sqrt{\sum_{i}v_{i}^{2}}$ and $\norm{{\bf\it
v}}_{\infty}=\max_{i}\absolutevalue{v_{i}}$. Hence, if

$\begin{split}&\norm{{\bf\it u}}_{1}-2\norm{{\bf\it
u}}_{2}\sqrt{t_{2}}=2k\norm{{\bf\it a}}_{1}-2\sqrt{2k}\norm{{\bf\it
a}}_{2}\sqrt{t_{2}}=c\\\ &\norm{{\bf\it v}}_{1}+2\norm{{\bf\it
v}}_{2}\sqrt{t_{1}}+2\norm{{\bf\it v}}_{\infty}t_{1}=2k\norm{{\bf\it
b}}_{1}+2\sqrt{2k}\norm{{\bf\it b}}_{2}\sqrt{t_{1}}+2\norm{{\bf\it
b}}_{\infty}t_{1}=c\end{split}$ (39)

hold, then the probability can be upper bounded by

$\Pr_{x_{i},y_{i}\sim
N(0,1)}\left(\sum_{i=1}^{2kp}u_{i}x_{i}^{2}-\sum_{i=1}^{2kq}v_{i}y_{i}^{2}<0\right)\leq\mathrm{e}^{-t_{1}}+\mathrm{e}^{-t_{2}}.$
(40)

To find a $c$ that gives the tightest bound, one should notice that according
to Eq. (40), the upper bound is determined by the minimal one of $t_{1}$ and
$t_{2}$. Besides, Eq. (39) tells us that the values of $t_{1}$ and $t_{2}$ are
inversely related. Therefore, the tightest upper bound is reached when
$t_{1}=t_{2}=t$, which gives the exact value of $t$:

$\sqrt{\frac{t}{2k}}=\frac{-(\norm{{\bf\it a}}_{2}+\norm{{\bf\it
b}}_{2})+\sqrt{{(\norm{{\bf\it a}}_{2}+\norm{{\bf\it
b}}_{2})}^{2}+2\norm{{\bf\it b}}_{\infty}\tr(O)}}{2\norm{{\bf\it
b}}_{\infty}}.$ (41)

To further simplify this equation, let
$\alpha=\frac{\tr(O)}{\sqrt{\tr(O^{2})}}$, then we have

$\begin{split}\sqrt{\frac{t}{2k}}&=\frac{-(\norm{{\bf\it a}}_{2}+\norm{{\bf\it
b}}_{2})+\sqrt{{(\norm{{\bf\it a}}_{2}+\norm{{\bf\it
b}}_{2})}^{2}+2\norm{{\bf\it b}}_{\infty}\tr(O)}}{2\norm{{\bf\it
b}}_{\infty}}\\\
&\geq\frac{-\sqrt{2\tr(O^{2})}+\sqrt{2\tr(O^{2})+2\norm{{\bf\it
b}}_{\infty}\tr(O)}}{2\norm{{\bf\it b}}_{\infty}}\\\
&=\frac{-\alpha^{-1}\tr(O)+\sqrt{\alpha^{-2}{\tr(O)}^{2}+\norm{{\bf\it
b}}_{\infty}\tr(O)}}{\sqrt{2}\norm{{\bf\it b}}_{\infty}}.\end{split}$ (42)

The first inequality uses the fact that $f(x)=-x+\sqrt{1+x^{2}}$ is monotone
and $\tr(O^{2})=\norm{{\bf\it a}}_{2}^{2}+\norm{{\bf\it
b}}_{2}^{2}\geq\frac{{(\norm{{\bf\it a}}_{2}+\norm{{\bf\it b}}_{2})}^{2}}{2}$.
Define

$x=\frac{\alpha\norm{{\bf\it b}}_{\infty}}{\tr(O)}=\frac{\norm{{\bf\it
b}}_{\infty}}{\sqrt{\tr(O^{2})}}\geq 0.$ (43)

By definition, $\norm{{\bf\it b}}_{\infty}=\max_{i}|b_{i}|<\sqrt{\tr(O^{2})}$,
it is easy to prove that $0\leq x\leq\sqrt{1-\frac{1}{d}}<1$. Therefore,

$\sqrt{\frac{t}{k}}=\frac{-1+\sqrt{1+\alpha x}}{x}>\sqrt{1+\alpha}-1,$ (44)

where we use the fact that the function $\frac{-1+\sqrt{1+\alpha x}}{x}$ is
monotonically decreasing with $x$. Combined with Eq. (40), we have

$\mathcal{C}_{k}(O)<2\mathrm{e}^{-{(\sqrt{1+\alpha}-1)}^{2}k}.$ (45)

∎

##  Appendix B Detection Capability Upper Bound of Parameterized EW Criteria

###  B.1 Proof of Theorem 3

######  Theorem 3 (Detection Capability of Parameterized EW Criteria).

For any parameterized EW represented by a normalized $l$-Lipschits map
$\mathcal{M}$ satisfying

$\forall{\bf\it\theta},{\bf\it\theta}^{\prime}\in\Theta:\norm{\mathcal{M}({\bf\it\theta})-\mathcal{M}({\bf\it\theta}^{\prime})}_{F}\leq
l\norm{{\bf\it\theta}-{\bf\it\theta}^{\prime}}_{2},$ (46)

The detection capability decays at least exponentially with $k$ after $k$
exceeds a certain threshold

$\mathcal{C}^{p}_{k}(\mathcal{M})\leq 2\mathrm{e}^{C_{1}-C_{2}k},$ (47)

where $C_{1}=M\ln\frac{2\sqrt{M}ld}{\epsilon}$, $M$ is the number of real
parameters in $\mathcal{M}$, $C_{2}=(\sqrt{1+\alpha_{\min}-\epsilon}-1)^{2}$
where
$\alpha_{\min}=\min_{{\bf\it\theta}}\frac{\tr[\mathcal{M}({\bf\it\theta})]}{\sqrt{\tr[\mathcal{M}({\bf\it\theta})^{2}]}}=\min_{{\bf\it\theta}}\tr[\mathcal{M}({\bf\it\theta})]\geq
1$, and $0<\epsilon<1$ is an arbitrary number. By choosing $\epsilon=0.5$, we
have the original theorem in the main text.

We prove this theorem using a coarse-graining method. The proof sketch is
shown in Fig. 4.

Figure 4: Proof Sketch of Theorem 3. We prove that if $\mathcal{M}$ is
$l$-Lipschits, the set of detected states can be covered by a finite set of
different observables, like the colored area in this figure. Each observable
is close to but not necessarily an EW. Therefore, by bounding the total number
of observables and the difference between these observables and valid EWs, the
volume of the detected set can be upper bounded by Theorem 2.

###### Proof.

A parameterized EW $\mathcal{M}$ is a map that maps $M$ real parameters to a
continuous set of EWs:

$\forall{\bf\it\theta}\in\Theta\subset[-1,1]^{M},\rho\in\mathrm{SEP}:\tr(\rho\mathcal{M}({\bf\it\theta}))\geq
0.$ (48)

We are going to bound the detection capability of a parameterized EW

$\mathcal{C}^{p}_{k}(\mathcal{M})=\Pr_{\rho\sim\pi_{d,k}}\bqty{\exists{\bf\it\theta}\in\Theta:\tr(\rho\mathcal{M}({\bf\it\theta}))<0}$
(49)

by constructing a finite set of observables
$\mathcal{O}=\Bqty{O_{i}|i=1,\cdots,N}$ (not necessarily EWs), such that all
the entangled states $\rho$ that can be detected by $\mathcal{M}$ can also be
detected by $\mathcal{O}$,

$\forall\rho:\exists{\bf\it\theta}\in\Theta,\tr\left(\rho\mathcal{M}({\bf\it\theta})\right)<0\to\exists
O_{i}\in\mathcal{O},\tr\pqty{\rho O_{i}}<0.$ (50)

Once we find the observable set $\mathcal{O}$, the detection capability of
$\mathcal{M}$ is bounded by the detection capability of $\mathcal{O}$,

$\mathcal{C}^{p}_{k}(\mathcal{M})\leq\mathcal{C}_{k}(\mathcal{O})=\Pr_{\rho\sim\pi_{d,k}}\left[\exists
O\in\mathcal{O},\tr(O\rho)<0\right].$ (51)

Firstly, we coarse-grain the parameter space, define
$\Theta^{*}=\Bqty{{\bf\it\theta}_{i}\in\Theta,i=1,\cdots,N}$, such that

$\forall{\bf\it\theta}\in\Theta,\exists{\bf\it\theta}^{*}\in\Theta^{*}:\norm{{\bf\it\theta}-{\bf\it\theta}^{*}}_{2}\leq\delta.$
(52)

Since $\mathcal{M}$ is $l$-Lipschitz, we have

$\forall{\bf\it\theta}\in\Theta,\exists{\bf\it\theta}^{*}\in\Theta^{*}:\norm{\mathcal{M}({\bf\it\theta})-\mathcal{M}({\bf\it\theta}^{*})}_{F}\leq
l\delta,$ (53)

which means that

$\forall{\bf\it\theta}\in\Theta,\exists{\bf\it\theta}^{*}\in\Theta^{*}:\mathcal{M}({\bf\it\theta})-(\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I})\geq
0.$ (54)

Hence, for any state $\rho$ satisfying
$\tr\left(\rho\mathcal{M}({\bf\it\theta})\right)<0$, it also holds that

$\exists{\bf\it\theta}^{*}\in\Theta^{*}:\tr\left[\left(\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I}\right)\rho\right]<0.$
(55)

Therefore, we can choose $\mathcal{O}$ to be
$\mathcal{O}=\Bqty{\mathcal{M}({\bf\it\theta}_{i})-l\delta\mathbb{I},{\bf\it\theta}_{i}\in\Theta^{*}}$,
whose detection capability can also be bounded using Theorem 2.

To bound $\mathcal{C}_{k}(\mathcal{O})$, we need to figure out two problems:
what is the detection capability of a single $O_{i}$ in $\mathcal{O}$ and what
is the number of elements in $\mathcal{O}$. According to Theorem 2, the key
quantity to bound
$\mathcal{C}_{k}\left(\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I}\right)$
is

$\begin{split}\alpha^{2}=\frac{\tr(\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I})^{2}}{\tr((\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I})^{2})}=\frac{(\alpha^{*}-l\delta
d)^{2}}{1-2l\delta\alpha^{*}+(l\delta)^{2}d},\end{split}$ (56)

where
$\alpha^{*}=\frac{\tr(\mathcal{M}({\bf\it\theta}^{*}))}{\sqrt{\tr(\mathcal{M}({\bf\it\theta}^{*})^{2})}}=\tr(\mathcal{M}({\bf\it\theta}^{*}))\geq
1$. It can also be directly verified by norm inequality,
$\alpha^{*}\leq\sqrt{d}$. Define $0<l\delta d=\epsilon<1$, we have

$1-2l\delta\alpha^{*}+(l\delta)^{2}d=1-2\frac{\epsilon\alpha^{*}}{d}+\frac{\epsilon^{2}}{d}>0$
(57)

and

$1-2\frac{\epsilon\alpha^{*}}{d}+\frac{\epsilon^{2}}{d}\leq 1$ (58)

Combine these inequalities with Eq. (56), and we get
$\alpha\geq\alpha^{*}-\epsilon$. Thus the detection capability of a single
observable in $\mathcal{O}$ can be bounded by

$\mathcal{C}_{k}\left(\mathcal{M}({\bf\it\theta}^{*})-l\delta\mathbb{I}\right)<2\mathrm{e}^{-(\sqrt{1+\alpha_{\mathrm{min}}-\epsilon}-1)^{2}k},$
(59)

where
$\alpha_{\min}=\min_{{\bf\it\theta}\in\Theta}\frac{\tr(\mathcal{M}({\bf\it\theta}))}{\sqrt{\tr(\mathcal{M}({\bf\it\theta})^{2})}}\geq
1$.

To find the number of elements in $\mathcal{O}$, we can divide the parameter
space into small cubes with side length $\frac{\delta}{\sqrt{M}}$. In each
cube, there exists a ${\bf\it\theta}_{i}$, such that for all the
${\bf\it\theta}$ contained in this cube,
$\norm{{\bf\it\theta}-{\bf\it\theta}_{i}}_{2}\leq\sqrt{M\left(\frac{\delta}{\sqrt{M}}\right)^{2}}=\delta$,
which fulfills the condition of Eq. (52). As the volume of parameter space is
upper bounded by $2^{M}$, the number of cubes, which is also the upper bound
of the number of elements in $\mathcal{O}$, is

$\absolutevalue{\mathcal{O}}=\left(\frac{2\sqrt{M}}{\delta}\right)^{M}=\left(\frac{2\sqrt{M}ld}{\epsilon}\right)^{M}.$
(60)

Combining Eq. (59) and Eq. (60), we can finish the proof by

$\mathcal{C}^{p}_{k}(\mathcal{M})\leq\mathcal{C}_{k}(\mathcal{O})<2\mathrm{e}^{M\ln\frac{2\sqrt{M}ld}{\epsilon}-(\sqrt{1+\alpha_{min}-\epsilon}-1)^{2}k}.$
(61)

∎

###  B.2 Examples: Positive Map and Faithful Entanglement Criteria

A bipartite state $\rho\in\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
can be detected by a positive map $\mathcal{N}$ if and only if there exists a
parameterized EW
$\mathcal{M}_{\mathcal{N}}\pqty{{\bf\it\theta}}=\frac{\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})})}{\norm{\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})})}_{F}}$
to detect it. This is equivalent to

$\exists{\bf\it\theta}\in
S^{2d-1}:\tr\bqty{\mathcal{N}_{A}\otimes\mathbb{I}_{B}\left(\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}\right)\rho}<0,$
(62)

where $S^{2d-1}$ is the unit sphere in the $2d$-dimensional parameter space,
and $\bra{j}\ket{\phi({\bf\it\theta})}=\theta_{2j}+i\theta_{2j+1}$. Hence,
substituting $M$ with $2d$, we have:

######  Corollary 2 (Detection Capability of Positive Maps).

A normalized $l$-Lipschitz positive map $\mathcal{N}$ has detection
capability:

$\mathcal{C}^{p}_{k}(\mathcal{M}_{\mathcal{N}})<2\mathrm{e}^{C_{1}-C_{2}k}$
(63)

where $C_{1}=2d\ln\bqty{2^{2.5}d^{1.5}l}$,
$C_{2}=(\sqrt{0.5+\alpha_{\min}}-1)^{2}$,
$\alpha_{\mathrm{min}}=\min_{{\bf\it\theta}}\frac{\tr[\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})})]}{\sqrt{\tr[\mathcal{N}_{A}\otimes\mathbb{I}_{B}(\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})})^{2}]}}$.

###### Proof.

It follows directly from Theorem 3 by choosing $\epsilon=0.5$ and $M=2d$. ∎

Also take the PPT criterion as an example, where
$\mathcal{M}_{\mathrm{PPT}}({\bf\it\theta})=\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}^{\mathrm{T_{A}}}$.
It can be easily proved that the partial transposition map is
$\sqrt{2}$-Lipschits and $\alpha_{\mathrm{min}}=1$. First, we give the
relationship between the $F$-norm of the density matrix representation and the
$2$-norm of the real-valued vector representation.

$\begin{split}\norm{{{\bf\it\theta}}-{{\bf\it\theta}^{\prime}}}_{2}^{2}&=\norm{\ket{\phi({\bf\it\theta})}-\ket{\phi({\bf\it\theta}^{\prime})}}_{2}^{2}\\\
&=2-2\real(\innerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta}^{\prime})})\\\
&\geq
2-2\absolutevalue{\bra{\phi({\bf\it\theta})}\ket{\phi({\bf\it\theta}^{\prime})}},\end{split}$
(64)
$\begin{split}\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}-\outerproduct{\phi({\bf\it\theta}^{\prime})}{\phi({\bf\it\theta}^{\prime})}}_{F}^{2}&=2-2\absolutevalue{\bra{\phi({\bf\it\theta})}\ket{\phi({\bf\it\theta}^{\prime})}}^{2}\\\
&=(2-2\absolutevalue{\bra{\phi({\bf\it\theta})}\ket{\phi({\bf\it\theta}^{\prime})}})(1+\absolutevalue{\bra{\phi({\bf\it\theta})}\ket{\phi({\bf\it\theta}^{\prime})}})\\\
&\leq 2\norm{{{\bf\it\theta}}-{{\bf\it\theta}^{\prime}}}_{2}^{2}\end{split}$
(65)

So the map
$\mathcal{M}({\bf\it\theta})=\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}$
is $\sqrt{2}$-Lipschitz.

For partial transposition map,
$\mathcal{M}({\bf\it\theta})=\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}^{\mathrm{T_{B}}}$,
it is normalized by itself,

$\norm{\mathcal{M}({\bf\it\theta})}=\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}^{\mathrm{T_{B}}}}_{F}=\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}}_{F}=1$
(66)

and

$\begin{split}\norm{\mathcal{M}({\bf\it\theta})-\mathcal{M}({\bf\it\theta}^{\prime})}&=\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}^{T_{B}}-\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}^{T_{B}}}_{F}\\\
&=\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}-\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}}_{F}\\\
&\leq\sqrt{2}\norm{{\bf\it\theta}-{\bf\it\theta}^{\prime}}_{2}.\end{split}$
(67)

Therefore partial transposition map is $\sqrt{2}$-Lipschitz. Corollary 2 shows
that for $k=\Omega(d\ln d)$, the PPT criterion can hardly detect any
entanglement, which meets the former results Žnidarič  _et al._ (2007);
Bhosale  _et al._ (2012); Shapourian  _et al._ (2021).

For faithful EW, the parameterized EW can be defined as

$\mathcal{M}({\bf\it\theta})=\pqty{\sqrt{2-\frac{2}{\sqrt{d}}}}^{-1}\pqty{\frac{\mathbb{I}}{\sqrt{d}}-\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}}$
(68)

where $\pqty{\sqrt{2-\frac{2}{\sqrt{d}}}}^{-1}\leq 1$ is a factor to ensure
$\mathcal{M}({\bf\it\theta})$ is normalized, then

$\begin{split}\norm{\mathcal{M}({\bf\it\theta})-\mathcal{M}({\bf\it\theta}^{\prime})}_{F}&=\pqty{\sqrt{2-\frac{2}{\sqrt{d}}}}^{-1}\norm{\outerproduct{\phi({\bf\it\theta})}{\phi({\bf\it\theta})}-\outerproduct{\phi({\bf\it\theta}^{\prime})}{\phi({\bf\it\theta}^{\prime})}}_{F}\\\
&\leq\sqrt{2}\norm{{\bf\it\theta}-{\bf\it\theta}^{\prime}}_{2}.\end{split}$
(69)

So faithful map is also $\sqrt{2}$-Lipschitz with $2d$ real parameters.
Combined with the fact that $\alpha_{\min}=\sqrt{\frac{d-\sqrt{d}}{2}}$, we
have

######  Corollary 3 (Ratio of Faithful Entanglement States).

The set of faithful entangled states has an exponential small ratio in the
state space:

$\Pr_{\rho\sim\pi_{d,k}}[\rho\in\mathrm{FE}]=\mathcal{C}^{p}_{k}\pqty{\mathcal{M}_{\mathrm{faithful}}}<2\mathrm{e}^{C_{1}-C_{2}k}$
(70)

where $\mathrm{FE}$ is the set of all faithful entangled states and
$C_{1}=3d\ln 4d$,
$C_{2}=\pqty{\sqrt{0.5+\sqrt{\frac{d-\sqrt{d}}{2}}}-1}^{2}\approx\sqrt{\frac{d}{2}}$.

##  Appendix C Detection Capability Upper Bound of Single-copy Criteria

###  C.1 Proof of Theorem 4

######  Theorem 4 (Detection Capability of Single-Copy Criteria).

Any single-copy entanglement criterion $\mathcal{O}$ with $M-1$ observables
has detection capability:

$\mathcal{C}^{s}_{k}(\mathcal{O})\leq 2\mathrm{e}^{C_{1}-C_{2}k}$ (71)

Where $C_{1}=M\ln\frac{2\sqrt{M}d}{\epsilon}$,
$C_{2}=(\sqrt{2-\epsilon}-1)^{2}$. $0<\epsilon<1$ is an arbitrary number. By
choosing $\epsilon=0.5$, we have the original theorem in the main text.

###### Proof.

Without loss of generality, we add $O_{M}=\frac{\mathbb{I}}{\sqrt{d}}$ to the
set, so $\mathcal{O}$ has $M$ observables now. We further assume $\mathcal{O}$
is mutually orthonormal in the operator space $\tr(O_{i}O_{j})=\delta_{ij}$.
If this condition is not satisfied, we can normalize and orthogonalize the
operator set without changing the feasible region. Given the observable set
$\mathcal{O}$ with $M$ observables and the measurement result

$r_{\rho,i}=\tr(O_{i}\rho),i=1\cdots M,$ (72)

the quantum state is restricted in the feasible region defined as

$F_{\mathcal{O}}(\rho)=\Bqty{\sigma\in\mathcal{D}(\mathcal{H}_{d})|\tr(O_{i}\sigma)=r_{\rho,i},i=1\cdots
M}.$ (73)

If the feasible region is disjoint with SEP, then the entanglement is
successfully detected by $\mathcal{O}$. Therefore, the detection capability of
$\mathcal{O}$ is defined as

$\mathcal{C}^{s}_{k}(\mathcal{O})=\Pr_{\rho\sim\pi_{d,k}}\bqty{F_{\mathcal{O}}(\rho)\cap\mathrm{SEP}=\varnothing}.$
(74)

To benefit our proof, we extend the definition of $F_{\mathcal{O}}(\rho)$ from
density states to Hermitian matrices, define

$F_{\mathcal{O}}^{\prime}(\rho)=\Bqty{\sigma|\tr(O_{i}\sigma)=r_{\rho,i},\sigma^{\dagger}=\sigma}.$
(75)

It is easy to prove that $F_{\mathcal{O}}(\rho)\cap\mathrm{SEP}=\varnothing$
if and only if $F_{\mathcal{O}}^{\prime}(\rho)\cap\mathrm{SEP}=\varnothing$ as
SEP is only in the density matrices set. By definition, SEP and
$F_{\mathcal{O}}(\rho)$ are all convex sets. Hence, from the hyperplane
separation theorem, we can find Hermitian operators $W$ that separate SEP and
$F_{\mathcal{O}}^{\prime}$

$\exists W:\tr(W\sigma)<0,\forall\sigma\in
F_{\mathcal{O}}^{\prime}(\rho)\text{ and }\tr(W\sigma^{\prime})\geq
0,\forall\sigma^{\prime}\in\mathrm{SEP},$ (76)

which is also an EW separate SEP and $F_{\mathcal{O}}(\rho)$. It can be proved
that $W$ must have the form

$W=\sum_{i=1}^{M}\theta_{i}O_{i}.$ (77)

If not, suppose $W=\sum_{i}\theta_{i}O_{i}+\tilde{O}$, where $\tilde{O}\neq 0$
is orthogonal to each $O_{i}\in\mathcal{O}$, Then for any $\sigma\in
F_{\mathcal{O}}^{\prime}(\rho)$, $\sigma+C\tilde{O}\in
F_{\mathcal{O}}^{\prime}(\rho)$ where $C$ is an arbitrary real number. In this
scenario, $\tr\left((\sigma+C\tilde{O})W\right)=C\tr(\tilde{O}^{2})$ can be
arbitrary large, which contradicts the requirement (76).

Accordingly, the entangled states that can be detected by $\mathcal{O}$ can
also be detected by the following parameterized EW

$\mathcal{M}({\bf\it\theta})=\sum_{i=1}^{M}\theta_{i}O_{i}$ (78)

where ${\bf\it\theta}\in\Theta$ and $\Theta$ is constituted by all
${\bf\it\theta}$ such that $\sum_{i}\theta_{i}^{2}=1$ and makes
$\mathcal{M}({\bf\it\theta})$ a valid EW. Therefore, the detection capability
of the single-copy criteria $\mathcal{O}$ is bounded by the detection
capability of the parameterized EW $\mathcal{M}$

$\mathcal{C}^{s}_{k}(\mathcal{O})\leq\mathcal{C}^{p}_{k}(\mathcal{M}).$ (79)

Such parameterized EW with $M$ parameters is normalized, and $1$-Lipschitz

$\norm{W({\bf\it\theta})-W({\bf\it\theta})^{\prime}}^{2}_{F}=\sum_{i}(\theta_{i}-\theta_{i}^{\prime})^{2}\tr(O_{i}^{2})=\norm{{\bf\it\theta}-{\bf\it\theta}^{\prime}}^{2}_{2}.$
(80)

By directly applying Theorem 3, we have

$\mathcal{C}^{s}_{k}(\mathcal{O})<2\mathrm{e}^{M\ln\frac{2\sqrt{M}d}{\epsilon}-(\sqrt{2-\epsilon}-1)^{2}}$
(81)

Where $0<\epsilon<1$ is an arbitrary number. ∎

###  C.2 Adaptive Single-Copy Measurement

The most general method to detect entanglement may take advantage of adaptive
measurements. After the previous $j-1$ measurement, One can determine $O_{j}$
as a function of previous measurement results. Here we consider a case where
each measurement or query gives $1$ bit of information.

######  Definition 4 (Measurement with $1$ Bit Information).

The measurement can be viewed as a quantum oracle, given an observable $O$,
the oracle will output $\mathrm{sign}(\tr(O\rho))$, more specifically, $+1$ if
$\tr(O\rho)\geq 0$ and $-1$ if $\tr(O\rho)<0$.

To determine whether $\tr(O\rho)\geq c$, one may simply replace $O$ by
$O-c\mathbb{I}$. To determine any observable up to $\epsilon$ precision, one
may use a binary search method with $O(\ln\frac{1}{\epsilon})$ queries. Next,
we define the most general adaptive single-copy measurement where observables
may depend on previous results. Formally, we define:

######  Definition 5 (Adaptive Single-Copy Protocols).

An adaptive single-copy entanglement detection protocol with finite precision
contains a program $\mathcal{P}$ that can generate an observable based on the
previous results. More specifically, after the previous $j-1$ measurement, one
get the measurement results $(k_{1}...k_{j-1})\in\\{-1,+1\\}^{j-1}$. Based on
these result, the program can generate $O_{j}=f_{j}(k_{i}...k_{j-1})$. After
$M$ iterations, one gets the following equations:

$\mathrm{sign}(\tr(O_{i}\rho))=k_{i}\in\\{-1,+1\\},\forall i=1,\cdots,M$ (82)

We can still define the feasible set

$F_{\mathcal{P}}(\rho)=F_{\mathcal{K}}(k_{1},\cdots,k_{M})=\Bqty{\sigma\in\mathcal{D}(\mathcal{H}_{d})|\mathrm{sign}(\tr(O_{i}\sigma))=k_{i},i=1,\cdots,M}$
(83)

And the detection capability is similarly defined as

$\mathcal{C}_{k}^{s}(\mathcal{P})=\Pr_{\rho\sim\pi_{d,k}}\bqty{F_{\mathcal{P}}(\rho)\cap\mathrm{SEP}=\varnothing}$
(84)

Use the measurement outcome ${\bf\it k}=(k_{1},\cdots,k_{M})\in\\{-1,1\\}^{M}$
to rewrite the previous definition:

$F_{\mathcal{P}}(\rho)\cap\mathrm{SEP}=\varnothing\Longleftrightarrow\exists{\bf\it
k}:\rho\in F_{\mathcal{K}}({\bf\it k})\text{ and }F_{\mathcal{K}}({\bf\it
k})\cap\mathrm{SEP}=\varnothing$ (85)

So that

$\begin{split}\mathcal{C}_{k}^{s}(\mathcal{P})&=\Pr_{\rho\sim\pi_{d,k}}\bqty{\exists{\bf\it
k}:\rho\in F_{\mathcal{K}}({\bf\it k})\text{ and }F_{\mathcal{K}}({\bf\it
k})\cap\mathrm{SEP}=\varnothing}\\\ &=\sum_{{\bf\it
k}}\Pr_{\rho\sim\pi_{d,k}}\bqty{\rho\in F_{\mathcal{K}}({\bf\it k})\text{ and
}F_{\mathcal{K}}({\bf\it k})\cap\mathrm{SEP}=\varnothing}\end{split}$ (86)

Notice that for any ${\bf\it k}$, $F_{\mathcal{K}}({\bf\it k})$ is a convex
set. So if $F_{\mathcal{K}}({\bf\it k})\cap\mathrm{SEP}=\varnothing$, then by
the hyperplane separation theorem, there exists an EW $W$ s.t.

$\tr(W\sigma)<0,\forall\sigma\in F_{\mathcal{K}}({\bf\it k})\text{ and
}\tr(W\sigma^{\prime})\geq 0,\forall\sigma^{\prime}\in\mathrm{SEP}$ (87)

According to Theorem 2, each term in the summation is bounded by
$2e^{-(3-2\sqrt{2})k}$. And there are a total of $2^{M}$ different terms in
the summation,

$\mathcal{C}_{k}^{s}(\mathcal{P})\leq 2^{M+1}e^{-(3-2\sqrt{2})k}=2e^{M\ln
2-(3-2\sqrt{2})k}.$ (88)

So the detection capability of any adaptive single-copy method also suffers
from exponential decay.

###  C.3 Details of Figure 3

In Fig. 3 of the main text, we use four entanglement criteria to demonstrate
our conclusion of the single-copy criteria. We explicitly list them here.
Suppose the state $\rho_{AB}$ we consider is bipartite with subsystems $A$ and
$B$.

  1. 1.

Purity Gühne and Tóth (2009):

$\forall\rho_{AB}\in\mathrm{SEP}:\tr(\rho_{AB}^{2})\leq\tr(\rho_{A}^{2}).$
(89)

  2. 2.

Fisher Information Zhang and Fei (2020):

$\forall\rho_{AB}\in\mathrm{SEP}:F(\rho,A\otimes I+I\otimes
B)\leq\Delta(A\otimes I-I\otimes B)_{\rho}^{2},$ (90)

where

$F(\rho,A)=\sum_{k,l}\frac{(\lambda_{k}-\lambda_{l})^{2}}{2\left(\lambda_{k}+\lambda_{l}\right)}\absolutevalue{\matrixelement{k}{A}{l}}^{2},$
(91)

$\rho=\sum_{k}\lambda_{k}\outerproduct{k}{k},$ (92)

and

$\Delta(A)_{\rho}^{2}=\expectationvalue{A^{2}}_{\rho}-\expectationvalue{A}^{2}_{\rho}.$
(93)

Since this criterion holds for any observable $A$ and $B$, we randomly choose
$10$ different $A$s and $B$s to build a series of criteria. If any of them is
violated, the state is classified as entangled.

  3. 3.

$M_{4}$ Liu  _et al._ (2022):

$\forall\rho_{AB}\in\mathrm{SEP}:E_{4}(\rho_{AB}-\rho_{A}\otimes\rho_{B})\leq\sqrt{(1-\tr(\rho_{A}^{2}))(1-\tr(\rho_{B}^{2}))}.$
(94)

where $E_{4}(\rho)=\sqrt{\frac{q(qM_{2}+U)}{q+1}}+\sqrt{\frac{M_{2}-U}{q+1}}$,
$q=\lfloor\frac{M_{2}^{2}}{M_{4}}\rfloor$, $U=\sqrt{q(q+1)M_{4}-qM_{2}^{2}}$,
$M_{2}=\tr(\rho_{AB}^{2})$,
$M_{4}=\tr[(\mathbb{S}_{A}^{(1,2)}\otimes\mathbb{S}_{A}^{(3,4)}\otimes\mathbb{S}_{B}^{(2,3)}\otimes\mathbb{S}_{B}^{(4,1)})\rho_{AB}^{\otimes
4}]$, and $\mathbb{S}_{A}^{(i,j)}$ is the SWAP operator acting on the $i$-th
and $j$-th copies of subsystem $A$.

  4. 4.

$D_{3,\mathrm{opt}}$ Yu  _et al._ (2021); Neven  _et al._ (2021):

$\forall\rho_{AB}\in\mathrm{SEP}:\beta x^{3}+(1-\beta
x)^{3}\leq\tr\left((\rho_{AB}^{T_{B}})^{3}\right),$ (95)

where $\beta=\lfloor\frac{1}{\tr(\rho_{AB}^{2})}\rfloor$ and
$x=\frac{\beta+\sqrt{\beta\left((\beta+1)\tr(\rho_{AB}^{2})-1\right)}}{\beta(\beta+1)}$.

###  C.4 More Numerical Experiments

We also conduct numerical experiments regarding the relationship between the
threshold $k_{th}$ and $d$ for different criteria. We found that numerically,
for purity, $k_{th}\approx\sqrt{d}$, and for $M_{4}$ $k_{th}\approx 0.6d$ and
for $D_{3,\mathrm{opt}}$, $k_{th}\approx d$. These polynomial relations show
that an exponential number of observables are needed to verify these criteria
with only single-copy observables.

Figure 5: The three figures represents the detection capability of purity,
$M_{4}$ and $D_{3,\mathrm{opt}}$ respectively. The $y$ axes are the detection
capability, and $x$ axes are $k$ divided by factors depending on $d$. The
factors are chosen so that the relation between $k_{th}$ and $d$ can be easily
observed. Each point is generated through $10^{8}$ independent experiments.