# Non-destructive Local Discrimination of Entangled Quantum States

Youngrong Lim  School of Computational Sciences, Korea Institute for Advanced
Study, Seoul 02455, Korea  Minki Hhan  Quantum Universe Center, Korea
Institute for Advanced Study, Seoul 02455, Korea  Hyukjoon Kwon
<EMAIL_ADDRESS>School of Computational Sciences, Korea Institute for
Advanced Study, Seoul 02455, Korea

###### Abstract

We demonstrate a substantial gap between local and nonlocal strategies in a
quantum state discrimination task under a non-destructiveness condition. The
condition imposes additional constraints to conventional state discrimination
that the initial state should be returned without disturbance. For a set of
maximally entangled states, the success probability of the proposed task using
local operations and classical communications is completely suppressed; it
cannot beat random guessing. We also show that a local strategy that
efficiently exploits pre-shared entanglement for this task can be essentially
different from the conventional approaches. We construct a non-destructive and
adaptive strategy to achieve perfect discrimination of maximally entangled
states which has a strictly lower entanglement cost than the best-known method
based on teleportation. Our approach can be generalized to multipartite
scenarios, offering an application in entanglement certification of a quantum
network.

Quantum state discrimination has served as a basic toolkit to explore the
foundation of quantum theory [1, 2, 3, 4, 5]. While the no-cloning theorem [6]
prohibits the perfect discrimination of non-orthogonal states, even orthogonal
states cannot be definitively distinguished when only local operations and
classical communications (LOCC) are allowed. The limitation of LOCC in a
discrimination task highlights the role of entanglement in quantum information
processing, as LOCC aided by sufficient pre-shared entanglement can perfectly
discriminate any set of mutually orthogonal states [7, 8, 9].

Nevertheless, establishing the exact boundary between local and nonlocal
operations in quantum state discrimination remains a non-trivial problem. One
might expect that the limitation of LOCC originates directly from the
entanglement of states to be distinguished, but this is not the case. Even
without entanglement, there exists a set of product states that cannot be
perfectly distinguished by LOCC [10]. More surprisingly, any two maximally
entangled states (MESs) are perfectly distinguishable by LOCC, whenever they
are orthogonal to each other [11]. Despite these counterintuitive examples,
extensive investigations have consistently demonstrated a prevailing trend
that the ability of LOCC is highly restricted when discriminating entangled
quantum states [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. Notably, a
general success probability bound of LOCC for discriminating MESs [16] shows
that perfect local discrimination is impossible when the number of states is
larger than the local dimension. However, the bound in Ref. [16] does not
always saturate [24, 22], and the highest success probability of LOCC heavily
relies on the choice of MESs [18, 25, 26, 27]. Hence, a complete understanding
of the limitation of LOCC in quantum state discrimination and its relationship
with entanglement remains open.

Once the achievable bound of LOCC in quantum state discrimination is
established, determining the minimum pre-shared entanglement to promote LOCC
to achieve perfect discrimination and constructing the corresponding optimal
strategy become central questions [28, 29, 30, 31]. An intuitive approach is
adopting quantum teleportation to send one party’s quantum state to the other
by consuming the pre-shared entanglement between the two parties. The quantum
state is then localized to a single party so that it can be perfectly
discriminated by local measurements. Notably, this simple strategy has been
proven to be optimal in discriminating several families of entangled quantum
states [29, 32]. While some strategies outperforming teleportation were
studied for discriminating product states [33, 34], it is so far unknown
whether there exists a strategy for discriminating entangled states with a
lower pre-shared entanglement cost than the teleportation strategy.

In this Letter, we propose a non-destructive quantum state discrimination
(NDSD) task to exhibit a significant gap between local and nonlocal
strategies. To this end, we add a condition that the state after the
discrimination should not be disturbed. Such a modification results in a
decrease in the success probability of a local strategy as the degree of
entanglement of the states to be discriminated increases. Remarkably, for a
set of MESs, the success probability using any separable operations cannot
surpass that of random guessing, implying that the ability of LOCC is
completely suppressed. We emphasize that our bound holds for any set of MESs,
which provides a stronger restriction on LOCC beyond conventional state
discrimination [16].

Furthermore, we investigate the entanglement cost of NDSD for MESs. The non-
destructiveness condition demands additional entanglement cost, as
entanglement in the initial state can be destroyed during measurements. A
naïve approach to detour this problem is first to apply possibly destructive
strategies used in conventional discrimination tasks and then reprepare the
initial entangled state. The total entanglement cost of such a discrimination-
and-repreparation approach is then given by the sum of the costs for each
step. We demonstrate that there exists a more efficient strategy than the
naïve one, achievable through a fully non-destructive scheme. The strategy is
based on adaptive syndrome measurements that read the parity information of
stabilizer generators without disturbing the state. Remarkably, this yields a
strictly lower entanglement cost to perform the perfect NDSD than the
discrimination-and-repreparation method [29]. Our result also provides new
insight into conventional quantum state discrimination. We find an intriguing
example in which entanglement is gained after discrimination via a non-
destructive strategy, while any teleportation-based strategy cannot achieve
positive entanglement gain [18].

Our approach can be practically exploited as a certification of entanglement
by witnessing the success probability of NDSD exceeding that of random
guessing. This can be readily extended to test multipartite entanglement in a
quantum network.

Non-destructive state discrimination.—

Figure 1: Schematic of conventional state discrimination task (red dashed box)
and NDSD task (red dashed + blue dashed boxes). Black (green) arrows represent
quantum (classical) transmissions. (a) Charlie chooses a state from the
ensemble $\\{p_{z},\left|\Psi_{z}\right>\\}$ and sends it to Alice and Bob.
(b) Alice and Bob perform LOCC. (c) A classical answer $z^{\prime}=f(\lambda)$
is determined from the measurement outcome $\lambda$. If $z^{\prime}=z$, the
task succeeds. (d) For NDSD, Alice and Bob also return the quantum state
$\rho_{z}^{\lambda}$ after performing the measurement. The NDSD succeeds when
both $z^{\prime}=z$ and
$\langle\Psi_{z}|\rho_{z}^{\lambda}\left|\Psi_{z}\right>=1$ are satisfied.

In conventional state discrimination performed by two local parties Alice and
Bob [4, 5], the referee Charlie chooses a quantum state $\rho_{z}$ from a set
of $k$ different quantum states $\\{\rho_{z}\\}_{z=1}^{k}$ with probability
$p_{z}$ and sends it to Alice and Bob (see Fig. 1). Alice and Bob then guess
the state by performing a positive operator-valued measurement (POVM)
$\Pi^{\lambda}$, satisfying $\Pi^{\lambda}\geq 0$ and
$\sum_{\lambda=1}^{N}\Pi^{\lambda}=1$. Since the probability to get outcome
$\lambda$ for a given state $\rho_{z}$ is
$p(\lambda|z)=\mbox{Tr}\left[\Pi^{\lambda}\rho_{z}\right]$, the success
probability to correctly guess Charlie’s initial choice $z$ becomes
$p_{\text{succ}}=\sum_{z}p_{z}\sum_{\lambda}p(\lambda|z)\delta_{f(\lambda),z}$,
where $f(\lambda)\in\\{1,2,\cdots,k\\}$ is a function to guess $z$ from the
measurement outcome $\lambda$.

We extend the scenario by requiring Alice and Bob to return not only their
answer to guess $z$ but also the quantum state after the measurement. The
state after the measurement with outcome $\lambda$ can be written as
$\rho_{z}^{\lambda}=\frac{K^{\lambda}\rho_{z}K^{\lambda\dagger}}{p(\lambda|z)}$,
where $K^{\lambda}$ are Kraus operators composing the POVMs,
$\Pi^{\lambda}=K^{\lambda\dagger}K^{\lambda}$. In the non-destructive
scenario, Charlie additionally checks whether the returned state
$\rho_{z}^{\lambda}$ remains the same as the initially chosen state
$\rho_{z}$. While this can be a non-trivial task in general, for a set of
mutually orthogonal pure states
$\\{\rho_{z}\\}_{z=1}^{k}=\\{\left|\Psi_{z}\right>\langle\Psi_{z}|\\}_{z=1}^{k}$
such that
$\langle{\Psi_{z}}|{\Psi_{z^{\prime}}}\rangle=\delta_{z,z^{\prime}}$, it can
be done by performing a projection onto the initial state as
$\left|\Psi_{z}\right>\langle\Psi_{z}|$. From now on we will focus on such a
case throughout this Letter. The success probability of NDSD can then be
defined as

$p^{\text{ND}}_{\text{succ}}=\sum_{z}p_{z}\sum_{\lambda}p(\lambda|z)\delta_{f(\lambda),z}\langle\Psi_{z}|\rho_{z}^{\lambda}\left|\Psi_{z}\right>.$
(1)

In other words, the NDSD succeeds when both the classical and quantum answers
are correct, i.e., $f(\lambda)=z$ and
$\rho_{z}^{\lambda}=\left|\Psi_{z}\right>\langle\Psi_{z}|$. From the
expression of $\rho_{z}^{\lambda}$ after the measurement, Eq. (1) can be
simplified to

$\displaystyle
p^{\text{ND}}_{\text{succ}}=\sum_{z}p_{z}\sum_{\lambda_{z}}\left|\langle\Psi_{z}|K^{\lambda_{z}}\left|\Psi_{z}\right>\right|^{2},$
(2)

where we denote $\sum_{\lambda_{z}}$ as the summation over $\lambda_{z}$ such
that $f(\lambda_{z})=z$.

We demonstrate a limitation in only using local operations for NDSD, by
establishing an upper bound on the success probability.

######  Theorem 1.

Suppose that $k$ different bipartite orthogonal states
$\\{\left|\Psi_{z}\right>_{AB}\\}_{z=1}^{k}$ with local dimensions $d_{A}$ and
$d_{B}$ for $A$ and $B$ are distributed with probabilities $p_{z}$. Then, the
success probability of NDSD for any separable measurements, whose Kraus
operators are in the form of $K^{\lambda}=K_{A}^{\lambda}\otimes
K_{B}^{\lambda}$, is upper bounded by

$p^{{\rm ND}}_{{\rm succ}}\leq d_{A}d_{B}\max_{z}\\{p_{z}\xi_{z}^{4}\\},$ (3)

where $\xi_{z}$ is the maximum Schmidt coefficient of
$\left|\Psi_{z}\right>_{AB}$.

The proof of Theorem 1 can be found in Supplemental Material (SM) [35]. Note
that this result holds for separable measurements, which strictly include
measurements throughout LOCC. Theorem 1 directly leads to the following result
for NDSD of a set of equally distributed MESs having uniform Schmidt
coefficients $1/\sqrt{d}$ when the local dimensions are the same.

######  Corollary 1.1.

For equally distributed $k$ different bipartite orthogonal MESs with the same
local dimension $d=d_{A}=d_{B}$, any strategy with separable operations has no
advantage over random guessing in the success probability of NDSD, i.e.,

$p^{{\rm ND}}_{{\rm succ}}\leq\frac{1}{k}.$ (4)

We highlight that the bound on the success probability does not depend on the
local dimension $d$. In comparison, for a conventional (destructive) state
discrimination, the upper bound can reach $d/k$, which scales by the local
dimension $d$ [16]. In particular, even though LOCC can perfectly discriminate
two MESs ($k=2$) [11], the non-destructiveness condition strongly restricts
the success probability no larger than $1/2$. Our upper bound holds for any
strategy based on separable operations, fully generalizing the previous
studies on quantum delocalized interaction [36, 37],

Entanglement cost of non-destructive state discrimination.— We have shown that
the non-destructiveness condition imposes a substantial restriction on the
local discrimination of entangled quantum states. Note that this restriction
can be relaxed by utilizing additional pre-shared entanglement between local
parties. We provide an upper bound on the success probability of such a case,
which presents a limitation of entanglement usage.

######  Theorem 2.

Suppose we have $k$ different MESs with $p_{z}=1/k$. If local parties have
$c$-ebits of pre-shared entanglement, an upper bound on the success
probability of NDSD is given by

$p^{{\rm ND}}_{{\rm succ}}\leq\frac{2^{c}}{k}.$ (5)

The proof of Theorem 2 is given in SM [35].

As an illustrative example, we consider the NDSD of Bell states,
$\left|\Phi^{j}\right>_{AB}$ with $j=0,1,2,3$ in the standard Bell basis,
especially focusing on the case of achieving the unit success probability. We
first show that the bound in Theorem 2 can be saturated for $k=2$, by using a
discrimination-and-repreparation scheme. This can be done by noting that any
two Bell states are locally distinguishable [11]. For example,
$\left|\Phi^{0}\right>_{AB}=(1/\sqrt{2})(\left|00\right>_{AB}+\left|11\right>_{AB})$
and
$\left|\Phi^{2}\right>_{AB}=(1/\sqrt{2})(\left|01\right>_{AB}+\left|10\right>_{AB})$
can be perfectly distinguished by local measurements on
$\\{\left|0\right>,\left|1\right>\\}$ basis for both $A$ and $B$ and checking
whether their outcomes coincide or not. However, as entanglement is totally
destroyed after performing the local measurement to guess the correct state,
an additional entanglement is required to reprepare the initial Bell state.
This $1$ ebit of entanglement cost saturates the bound in Theorem 2. For $k=3$
and $4$, however, local discrimination of the Bell states is no more possible,
and at least one additional ebit is required to achieve the perfect
discrimination [29]. By using teleportation, the total cost for the perfect
NDSD becomes 2 ebits for both cases; 1 ebit for the teleportation and 1 ebit
for the state repreparation. For $k=4$, this also saturates the bound in
Theorem 2.

Since teleportation leads to the same pre-shared entanglement cost for $k=3$
and $4$ to achieve the perfect NDSD, one may wonder if there exists a more
efficient strategy to reduce the cost for $k=3$. We show that there exists an
adaptive and non-destructive strategy that has the average entanglement cost
of $5/3$ ebits, strictly less than 2 ebits. This can be done by adopting the
stabilizer formalism [38], based on which, the Bell states are stabilized by
generators in a set $\\{\pm Z_{A}Z_{B},\pm X_{A}X_{B}\\}$. Here, we denote
$X_{A(B)}$ and $Z_{A(B)}$ as the Pauli $X$ and $Z$ operators acting on the
subsystem $A(B)$. The Bell states $\left|\Phi^{j}\right>_{AB}$ are then
uniquely characterized by the signs of generators $Z_{A}Z_{B}$ and
$X_{A}X_{B}$. We also note that these signs can be determined in a non-
destructive manner by using a parity measurement. For example, the sign of
$Z_{A}Z_{B}$ can be determined by the measurement operator
$\left\\{\frac{\mathbb{1}\pm Z_{A}Z_{B}}{2}\right\\}$. While being a nonlocal
operator, such a parity measurement can be realized via local operations
between the state with a pre-shared Bell state
$\left|\Phi^{0}\right>_{A^{\prime}B^{\prime}}$. More precisely, one can apply
a controlled unitary operator $U_{P}=\mathbb{1}\otimes\left|0\right>\langle
0|+P\otimes\left|1\right>\langle 1|$ for Pauli operators $P=X$ or $P=Z$ on
both $AA^{\prime}$ and $BB^{\prime}$ followed by the measurements on the
ancillary systems $A^{\prime}$ and $B^{\prime}$ in $\\{\left|\pm\right>\\}$
basis. If both measurement outcomes are the same, the quantum state is
projected onto $\frac{\mathbb{1}+P_{A}P_{B}}{2}$, while for the other case,
the state is projected onto $\frac{\mathbb{1}-P_{A}P_{B}}{2}$ (see Fig. 2).
Therefore, $1$ ebit is consumed to determine each sign of generators, and the
state after the measurement remains unchanged.

Figure 2: Circuit diagram for non-destructive determination of the sign of the
stabilizer $P_{A}P_{B}$. The upper (lower) half in blue (yellow) color
represents the local party Alice (Bob). Using a pre-shared Bell state
$\left|\Phi^{0}\right>_{A^{\prime}B^{\prime}}$ (red lines), controlled-Pauli
operations are performed in both local parties. If the outcomes of the local
measurements in the basis $\left|\pm\right>$ coincide, the measurement effect
is $\frac{\mathbb{1}+P_{A}P_{B}}{2}$. For the opposite outcomes, the
measurement effect becomes $\frac{\mathbb{1}-P_{A}P_{B}}{2}$.

Let us apply this scheme to the NDSD of three Bell states. Without loss of
generality, we consider a set of Bell states
$\\{\left|\Phi^{0}\right>,\left|\Phi^{1}\right>,\left|\Phi^{2}\right>\\}$. The
signs of generators to determine those Bell states are summarized in the
following table:

| $Z_{A}Z_{B}$ | $X_{A}X_{B}$
---|---|---
$\left|\Phi^{0}\right>$ | $+$ | $+$
$\left|\Phi^{1}\right>$ | $+$ | $-$
$\left|\Phi^{2}\right>$ | $-$ | $+$

If we measure the sign of the first generator, $Z_{A}Z_{B}$, the ‘$-$’ sign
comes out with probability $1/3$ and ‘$+$’ with $2/3$. For the former case,
the state is determined as $\left|\Phi^{2}\right>$, and the protocol ends with
consuming $1$ ebit. For the latter case, the sign of the second generator,
$X_{A}X_{B}$, distinguishes between $\left|\Phi^{0}\right>$ and
$\left|\Phi^{1}\right>$ by using additional $1$ ebit cost. Thus, the average
entanglement cost of the overall process becomes $\frac{1}{3}\times
1+\frac{2}{3}\times 2=\frac{5}{3}$ (ebits), which has a strict advantage over
the discrimination-and-repreparation scheme having $2$ ebits of entanglement
cost. Such a gap arises as the stabilizer method can utilize the sign
information more compactly by reading each column in the sign table
adaptively, while the teleportation-based method can only access the signs of
two columns at once. For $k=2$ or 4, our method has the same cost as the
teleportation-based method [35].

We illustrate an interesting implication of our scheme in conventional state
discrimination by considering an NDSD of 6 MESs,

$\left\\{\left|\Phi^{012}\right>,\left|\Phi^{021}\right>,\left|\Phi^{102}\right>,\left|\Phi^{120}\right>,\left|\Phi^{201}\right>,\left|\Phi^{210}\right>\right\\},$
(6)

where $\left|\Phi^{j_{1}\cdots
j_{n}}\right>_{AB}=\left|\Phi^{j_{1}}\right>_{A_{1}B_{1}}\otimes\cdots\otimes\left|\Phi^{j_{n}}\right>_{A_{n}B_{n}}$
is a tensor product of the Bell states. Let us first compare the average
entanglement cost for the perfect NDSD between the stabilizer method and the
teleportation-based method. In SM [35], we show that the minimum average
entanglement cost using the stabilizer method is $8/3$ ebits. In contrast, any
qubit teleportation combined with local operations cannot determine two states
among the states in Eq. (6) with a cost less than $3$ ebits, when including
the cost for state repreparation (see SM [35] for the detailed derivation of
the costs). Hence, the entanglement cost gap between the two protocols becomes
$1/3$ ebits.

Next, we apply these strategies to conventional state discrimination, where
Alice and Bob do not need to return to the initial quantum state after
discrimination. By noting that the initially distributed $3$-Bell pair states
contain larger entanglement (3 ebits) than the entanglement cost ($8/3$ ebits)
based on the stabilizer method for non-destructive discrimination, Alice and
Bob gain $1/3$ ebits per each round of discrimination by keeping their final
state. This can be interpreted as entanglement earning from discrimination,
further extending the notion of entanglement discrimination catalysis [18]. We
highlight that the newly proposed non-destructive strategy makes this
possible, while a teleportation-based strategy cannot yield positive net
entanglement after discrimination.

We also show that the entanglement cost gap is extendable by considering a set
of $n$-Bell pairs with only three indices $\left\\{\left|\Phi^{j_{1}\cdots
j_{n}}\right>_{AB}\right\\}_{j_{1},\cdots,j_{n}\in\\{0,1,2\\}}$, which
contains $k=3^{n}$ different MESs with local dimension $d=2^{n}$. In this
case, the entanglement cost of the stabilizer method is $5n/3$ ebits, while a
method using teleportation of each Bell-pair requires $2n$ ebits for the
perfect NDSD [35]; hence the gap $n/3$ grows linearly by increasing the number
of Bell pairs $n$.

Application to entanglement certification and multipartite generalization.— As
a practical application, we discuss how NDSD can be utilized in entanglement
certification. Let us start with the bipartite case. In order to confirm the
existence of entanglement between Alice and Bob, the referee Charlie
distributes $k$ MESs to them and estimates the success probability of NDSD. If
the success probability is higher than $1/k$, entanglement is certified by the
result from Corollary 1.1. This only requires surpassing trivial random
guessing, thus providing a simpler scheme for entanglement certification.

We extend this approach to multipartite scenarios. To certify entanglement
between three nodes in a quantum network, the referee tests NDSD for $k$
different GHZ states
$(1/\sqrt{2})(\left|x_{1}x_{2}x_{3}\right>\pm\left|\bar{x}_{1}\bar{x}_{2}\bar{x}_{3}\right>)$,
where $x_{i}\in\\{0,1\\}$ and $\bar{x}=x+1~{}({\rm mod}~{}2)$. By noting that
any multipartite LOCC is a subset of LOCC between the bipartition of the total
system and any bipartition of GHZ states is maximally entangled with uniform
Schmidt coefficients $1/\sqrt{2}$, the success probability using LOCC is
bounded above by $p^{\rm ND}_{\rm succ}\leq 2/k$ by Theorem 1. Hence, choosing
any three GHZ states is sufficient to certify entanglement by witnessing the
success probability of NDSD higher than $2/3$. In contrast, without the non-
destructiveness condition, some sets of up to four GHZ states can be perfectly
discriminated by using LOCC [15]. We also highlight the bound $2/k$ is valid
even allowing an unlimited amount of pre-shared entanglement between only two
parties. In this manner, the proposed protocol effectively tests whether
entanglements are well distributed throughout the network.

For a general $N$-node quantum network, we can adopt the absolutely maximally
entangled (AME) states [39, 40, 41], any bipartition of which leads to an MES.
In particular, when $N$ is even, the highest LOCC success probability of NDSD
for $k$ different AME states becomes $1/k$, which is a multiparty extension of
Corollary 1.1. This is because any multipartite local strategy for NDSD of AME
states is a subset of a bipartite local strategy used for NDSD of MESs with
the same local dimension by taking the $N/2$ node bipartition. We note that
AME states exist for any number of parties with sufficiently high local
dimension [40] (see also, Refs. [42, 43] for limitations in low dimensions)
and can be constructed from various systematic methods, such as using quantum
error correction codes [40, 44, 45] and graph states [46]. Alternatively, we
can utilize randomly generated states, which approximately satisfy the AME
property with high probability [47, 48] so that the LOCC bound of NDSD
deviates slightly from that of random guessing.

We also show that the advantage of non-destructive strategies is also valid in
multipartite scenarios. We illustrate this by investigating the pre-shared
entanglement costs for NDSD of GHZ states, determined by the signs of
stabilizers $Z_{1}Z_{2}$, $Z_{2}Z_{3}$, and $X_{1}X_{2}X_{3}$. Similarly to
the bipartite case, we consider NDSD of three GHZ states with the same sign of
$X_{1}X_{2}X_{3}$. In fact, those states can be perfectly distinguished by
using LOCC [15]. Therefore, in the discrimination-and-repreparation strategy,
the entanglement cost is 1 GHZ state for the repreparation, which is
equivalent to 2 ebits. If one adopts teleportation, the entanglement cost is
always higher than or equal to $2$ ebits as at least an additional $1$ ebit is
required for the repreparation. In contrast, the average entanglement cost for
discriminating the three GHZ states using the nonlocal syndrome measurement is
$5/3$ ebits, following the same arguments of the bipartite case to determine
the signs of $Z_{1}Z_{2}$ and $Z_{2}Z_{3}$. Hence, a strict gap exists between
the two strategies, even in a multipartite scenario. While this observation
can be further generalized for any stabilizer states, characterizing the
advantage of the non-destructive strategy becomes more complicated when
determining the signs of stabilizer generators with more than two nonlocal
terms, for example, $X_{1}X_{2}X_{3}$.

Remarks.— We have established a strong limitation of LOCC by imposing an
additional non-destructiveness condition to conventional quantum state
discrimination. In particular, we have shown that the success probability of
the non-destructive discrimination of MESs using LOCC cannot exceed that of
random guessing. By investigating the pre-shared entanglement cost to achieve
the unit success probability of the proposed task, we have discovered a non-
destructive method that outperforms the previously best-known teleportation-
based method. Therefore, our results not only provide a sharp boundary between
local and nonlocal operations in quantum state discrimination but also pave
the way for efficient usage of entanglement for local discrimination. By
generalizing our approach to the multipartite case, we have also discussed a
feasible application of the proposed task to entanglement certification in a
quantum network.

From a thermodynamic perspective, the advantage of the proposed non-
destructive strategy lies in overcoming the inherent irreversibility between
measurement and repreparation of quantum states. In this direction,
constructing a general formalism that precisely describes the difference
between destructive and non-destructive strategies in terms of irreversibility
will be an interesting future work. A possible approach is to analyze
additional entanglement cost for the initial state repreparation, based on the
irreversibility of entanglement concentration [49].

###### Acknowledgements.

This work was supported by Institute of Information & Communications
Technology Planning & Evaluation (IITP) grant funded by the Korea government
(MSIT) (No. 2022-0-00463). M.H. and H.K. are supported by the KIAS Individual
Grant Nos. QP089801 (M.H.) and CG085301 (H.K) at Korea Institute for Advanced
Study.

## References

  * Helstrom [1969] C. W. Helstrom, Quantum detection and estimation theory, Journal of Statistical Physics 1, 231 (1969).
  * Holevo [1974] A. S. Holevo, Remarks on optimal quantum measurements, Problemy Peredachi Informatsii 10, 51 (1974).
  * Gisin  _et al._ [2002] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, Quantum cryptography, Reviews of Modern Physics 74, 145 (2002).
  * Barnett and Croke [2009] S. M. Barnett and S. Croke, Quantum state discrimination, Advances in Optics and Photonics 1, 238 (2009).
  * Bae and Kwek [2015] J. Bae and L.-C. Kwek, Quantum state discrimination and its applications, Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
  * Wootters and Zurek [1982] W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299, 802 (1982).
  * Cirac  _et al._ [2001] J. I. Cirac, W. Dür, B. Kraus, and M. Lewenstein, Entangling operations and their implementation using a small amount of entanglement, Physical Review Letters 86, 544 (2001).
  * Bandyopadhyay  _et al._ [2009] S. Bandyopadhyay, G. Brassard, S. Kimmel, and W. K. Wootters, Entanglement cost of nonlocal measurements, Physical Review A 80, 012313 (2009).
  * Bandyopadhyay  _et al._ [2016] S. Bandyopadhyay, S. Halder, and M. Nathanson, Entanglement as a resource for local state discrimination in multipartite systems, Physical Review A 94, 022311 (2016).
  * Bennett  _et al._ [1999] C. H. Bennett, D. P. DiVincenzo, C. A. Fuchs, T. Mor, E. Rains, P. W. Shor, J. A. Smolin, and W. K. Wootters, Quantum nonlocality without entanglement, Physical Review A 59, 1070 (1999).
  * Walgate  _et al._ [2000] J. Walgate, A. J. Short, L. Hardy, and V. Vedral, Local distinguishability of multipartite orthogonal quantum states, Physical Review Letters 85, 4972 (2000).
  * Terhal  _et al._ [2001] B. M. Terhal, D. P. DiVincenzo, and D. W. Leung, Hiding bits in bell states, Physical Review Letters 86, 5807 (2001).
  * Horodecki  _et al._ [2003] M. Horodecki, A. Sen, U. Sen, K. Horodecki, _et al._ , Local indistinguishability: More nonlocality with less entanglement, Physical Review Letters 90, 047902 (2003).
  * Fan [2004] H. Fan, Distinguishability and indistinguishability by local operations and classical communication, Physical Review Letters 92, 177905 (2004).
  * Hayashi  _et al._ [2006] M. Hayashi, D. Markham, M. Murao, M. Owari, and S. Virmani, Bounds on multipartite entangled orthogonal state discrimination using local operations and classical communication, Physical Review Letters 96, 040501 (2006).
  * Nathanson [2005] M. Nathanson, Distinguishing bipartitite orthogonal states using locc: Best and worst cases, Journal of Mathematical Physics 46, 062103 (2005).
  * Calsamiglia  _et al._ [2010] J. Calsamiglia, J. De Vicente, R. Muñoz-Tapia, and E. Bagan, Local discrimination of mixed states, Physical Review Letters 105, 080504 (2010).
  * Yu  _et al._ [2012] N. Yu, R. Duan, and M. Ying, Four locally indistinguishable ququad-ququad orthogonal maximally entangled states, Physical Review Letters 109, 020506 (2012).
  * Nathanson [2013] M. Nathanson, Three maximally entangled states can require two-way local operations and classical communication for local discrimination, Physical Review A 88, 062316 (2013).
  * Lugli  _et al._ [2020] M. Lugli, P. Perinotti, and A. Tosini, Fermionic state discrimination by local operations and classical communication, Physical Review Letters 125, 110403 (2020).
  * Ha and Kim [2022] D. Ha and J. S. Kim, Bound on optimal local discrimination of multipartite quantum states, Scientific Reports 12, 14130 (2022).
  * Yuan  _et al._ [2022] J.-T. Yuan, Y.-H. Yang, and C.-H. Wang, Finding out all locally indistinguishable sets of generalized bell states, Quantum 6, 763 (2022).
  * Ha and San Kim [2023] D. Ha and J. San Kim, Entanglement witness and multipartite quantum state discrimination, Journal of Physics A: Mathematical and Theoretical 56, 205303 (2023).
  * Wang  _et al._ [2017] Y.-L. Wang, M.-S. Li, S.-M. Fei, and Z.-J. Zheng, The local distinguishability of any three generalized bell states, Quantum Information Processing 16, 1 (2017).
  * Cosentino and Russo [2014] A. Cosentino and V. Russo, Small sets of locally indistinguishable orthogonal maximally entangled states, Quantum Infomation and Computation 14, 1098–1106 (2014).
  * Li  _et al._ [2015] M.-S. Li, Y.-L. Wang, S.-M. Fei, and Z.-J. Zheng, d locally indistinguishable maximally entangled states in $\mathbb{c}^{d}\otimes\mathbb{c}^{d}$, Physical Review A 91, 042318 (2015).
  * Tian  _et al._ [2016] G. Tian, S. Yu, F. Gao, and Q. Wen, Classification of locally distinguishable and indistinguishable sets of maximally entangled states, Physical Review A 94, 052315 (2016).
  * Yu  _et al._ [2014] N. Yu, R. Duan, and M. Ying, Distinguishability of quantum states by positive operator-valued measures with positive partial transpose, IEEE Transactions on Information Theory 60, 2069 (2014).
  * Bandyopadhyay  _et al._ [2015] S. Bandyopadhyay, A. Cosentino, N. Johnston, V. Russo, J. Watrous, and N. Yu, Limitations on separable measurements by convex optimization, IEEE Transactions on Information Theory 61, 3593 (2015).
  * Bandyopadhyay  _et al._ [2018] S. Bandyopadhyay, S. Halder, and M. Nathanson, Optimal resource states for local state discrimination, Physical Review A 97, 022314 (2018).
  * Lovitz and Johnston [2022] B. Lovitz and N. Johnston, Entangled subspaces and generic local state discrimination with pre-shared entanglement, Quantum 6, 760 (2022).
  * Bandyopadhyay and Russo [2021] S. Bandyopadhyay and V. Russo, Entanglement cost of discriminating noisy bell states by local operations and classical communication, Physical Review A 104, 032429 (2021).
  * Cohen [2008] S. M. Cohen, Understanding entanglement as resource: Locally distinguishing unextendible product bases, Physical Review A 77, 012304 (2008).
  * Rout  _et al._ [2019] S. Rout, A. G. Maity, A. Mukherjee, S. Halder, and M. Banik, Genuinely nonlocal product bases: Classification and entanglement-assisted discrimination, Physical Review A 100, 032321 (2019).
  * [35] See Supplemental Material for the proofs and detailed analysis, which includes Refs. [50-53].
  * Paige  _et al._ [2020] A. Paige, H. Kwon, S. Simsek, C. N. Self, J. Gray, and M. Kim, Quantum delocalized interactions, Physical Review Letters 125, 240406 (2020).
  * [37] B. Bilash, Y. Lim, H. Kwon, Y. Kim, H.-T. Lim, W. Song, and Y.-S. Kim, Nondestructive discrimination of bell states via quantum delocalized interaction, in preparation .
  * Gottesman [1997] D. Gottesman,  _Stabilizer codes and quantum error correction_ (California Institute of Technology, 1997).
  * Helwig  _et al._ [2012] W. Helwig, W. Cui, J. I. Latorre, A. Riera, and H.-K. Lo, Absolute maximal entanglement and quantum secret sharing, Physical Review A 86, 052335 (2012).
  * Helwig and Cui [2013] W. Helwig and W. Cui, Absolutely maximally entangled states: existence and applications, arXiv preprint arXiv:1306.2536 (2013).
  * Goyeneche  _et al._ [2015] D. Goyeneche, D. Alsina, J. I. Latorre, A. Riera, and K. Życzkowski, Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices, Physical Review A 92, 032316 (2015).
  * Scott [2004] A. J. Scott, Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions, Physical Review A 69, 052330 (2004).
  * Huber  _et al._ [2018] F. Huber, C. Eltschka, J. Siewert, and O. Gühne, Bounds on absolutely maximally entangled states from shadow inequalities, and the quantum macwilliams identity, Journal of Physics A: Mathematical and Theoretical 51, 175301 (2018).
  * Raissi  _et al._ [2018] Z. Raissi, C. Gogolin, A. Riera, and A. Acín, Optimal quantum error correcting codes from absolutely maximally entangled states, Journal of Physics A: Mathematical and Theoretical 51, 075301 (2018).
  * Raissi  _et al._ [2020] Z. Raissi, A. Teixidó, C. Gogolin, and A. Acín, Constructions of k-uniform and absolutely maximally entangled states beyond maximum distance codes, Physical Review Research 2, 033411 (2020).
  * Raissi  _et al._ [2022] Z. Raissi, A. Burchardt, and E. Barnes, General stabilizer approach for constructing highly entangled graph states, Physical Review A 106, 062424 (2022).
  * Page [1993] D. N. Page, Average entropy of a subsystem, Physical Review Letters 71, 1291 (1993).
  * Zyczkowski and Sommers [2001] K. Zyczkowski and H.-J. Sommers, Induced measures in the space of mixed quantum states, Journal of Physics A: Mathematical and General 34, 7111 (2001).
  * Kumagai and Hayashi [2013] W. Kumagai and M. Hayashi, Entanglement concentration is irreversible, Physical Review Letters 111, 130407 (2013).
  * Kraft [1949] L. G. Kraft,  _A device for quantizing, grouping, and coding amplitude-modulated pulses_ , Ph.D. thesis, Massachusetts Institute of Technology (1949).
  * McMillan [1956] B. McMillan, Two inequalities implied by unique decipherability, IRE Transactions on Information Theory 2, 115 (1956).
  * Bennett  _et al._ [2000] C. H. Bennett, S. Popescu, D. Rohrlich, J. A. Smolin, and A. V. Thapliyal, Exact and asymptotic measures of multipartite pure-state entanglement, Physical Review A 63, 012307 (2000).
  * Jing [2015] N. Jing, Unitary and orthogonal equivalence of sets of matrices, Linear Algebra and its Applications 481, 235 (2015).

##  Appendix A Supplemental Material

##  Appendix B Proof of Theorem 1

###### Proof.

Let us consider non-destructive discrimination of a set of $k$ different
bipartite pure states $\\{\left|\Psi_{z}\right>_{AB}\\}_{z=1}^{k}$ with
associated probability $p_{z}$. If Alice and Bob can only perform a separable
measurement, described by Kraus operators
$K^{\lambda}_{AB}=K^{\lambda}_{A}\otimes K^{\lambda}_{B}$, an upper bound on
the success probability can be found as

$\displaystyle p^{\text{ND}}_{\text{succ}}$
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\left|\langle\Psi_{z}|K^{\lambda_{z}}_{A}\otimes
K^{\lambda_{z}}_{B}\left|\Psi_{z}\right>\right|^{2}$ (7)
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}\left[\left|\Psi_{z}\right>\langle\Psi_{z}|K^{\lambda_{z}\dagger}_{A}\otimes
K^{\lambda_{z}\dagger}_{B}\left|\Psi_{z}\right>\langle\Psi_{z}|K^{\lambda_{z}}_{A}\otimes
K^{\lambda_{z}}_{B}\right]$ (8)
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}\left[\left|\Psi_{z}\right>\langle\Psi_{z}|(K^{\lambda_{z}\dagger}_{A}\otimes\mathbb{1}_{B})(\mathbb{1}_{A}\otimes
K^{\lambda_{z}\dagger}_{B})\left|\Psi_{z}\right>\langle\Psi_{z}|(K^{\lambda_{z}}_{A}\otimes\mathbb{1}_{B})(\mathbb{1}_{A}\otimes
K^{\lambda_{z}}_{B})\right]$ (9)
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}\left[\left|\Psi_{z}\right>\langle\Psi_{z}|(\mathbb{1}_{A}\otimes
K^{\lambda_{z}\dagger}_{B})(K^{\lambda_{z}\dagger}_{A}\otimes\mathbb{1}_{B})\left|\Psi_{z}\right>\langle\Psi_{z}|(K^{\lambda_{z}}_{A}\otimes\mathbb{1}_{B})(\mathbb{1}_{A}\otimes
K^{\lambda_{z}}_{B})\right]$ (10)
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}\left[(K^{\lambda_{z}\dagger}_{A}\otimes\mathbb{1}_{B})\left|\Psi_{z}\right>\langle\Psi_{z}|(K^{\lambda_{z}}_{A}\otimes\mathbb{1}_{B})(\mathbb{1}_{A}\otimes
K^{\lambda_{z}}_{B})\left|\Psi_{z}\right>\langle\Psi_{z}|(\mathbb{1}_{A}\otimes
K^{\lambda_{z}\dagger}_{B})\right]$ (11)
$\displaystyle\leq\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}_{A}\left[K^{\lambda_{z}}_{A}K^{\lambda_{z}\dagger}_{A}\mbox{Tr}_{B}(\left|\Psi_{z}\right>\langle\Psi_{z}|)\right]\mbox{Tr}_{B}\left[K^{\lambda_{z}\dagger}_{B}K^{\lambda_{z}}_{B}\mbox{Tr}_{A}(\left|\Psi_{z}\right>\langle\Psi_{z}|)\right]$
(12)
$\displaystyle=\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}_{A}\left[K^{\lambda_{z}}_{A}K^{\lambda_{z}\dagger}_{A}\rho_{A,z}\right]\mbox{Tr}_{B}\left[K^{\lambda_{z}\dagger}_{B}K^{\lambda_{z}}_{B}\rho_{B,z}\right],$
(13)

where $\rho_{A,z}$ and $\rho_{B,z}$ are reduced density matrices of
$\left|\Psi_{z}\right>_{AB}\langle\Psi_{z}|$. From the Schmidt decomposition
$\left|\Psi_{z}\right>_{AB}=\sum_{i=1}^{d}r_{i}^{z}\left|\psi_{i}^{z}\right>_{A}\otimes\left|\psi_{i}^{z}\right>_{B}$,
where $d={\min(d_{A},d_{B})}$ and $d_{A}$ and $d_{B}$ are the dimensions of
the local systems $A$ and $B$, one can obtain the eigendecomposition of the
local states
$\rho_{A,z}=\sum_{i=1}^{d}(r_{i}^{z})^{2}\left|\psi_{i}^{z}\right>_{B}\langle\psi_{i}^{z}|$
and
$\rho_{B,z}=\sum_{i=1}^{d}(r_{i}^{z})^{2}\left|\psi_{i}^{z}\right>_{A}\langle\psi_{i}^{z}|$.
By noting that $\rho_{A,z}\leq\xi_{z}^{2}\mathbb{1}_{A}$ and
$\rho_{B,z}\leq\xi_{z}^{2}\mathbb{1}_{B}$ with $\xi_{z}=\max\\{r_{i}^{z}\\}$ ,
we have a bound on the success probability,

$\displaystyle p^{\text{ND}}_{\text{succ}}$
$\displaystyle\leq\sum_{z=1}^{k}p_{z}\sum_{\lambda_{z}}\mbox{Tr}_{A}\left[K^{\lambda_{z}}_{A}K^{\lambda_{z}\dagger}_{A}\rho_{A,z}\right]\mbox{Tr}_{B}\left[K^{\lambda_{z}\dagger}_{B}K^{\lambda_{z}}_{B}\rho_{B,z}\right]$
(14)
$\displaystyle\leq\sum_{z=1}^{k}p_{z}\xi_{z}^{4}\sum_{\lambda_{z}}\mbox{Tr}_{A}\left[K^{\lambda_{z}}_{A}K^{\lambda_{z}\dagger}_{A}\right]\mbox{Tr}_{B}\left[K^{\lambda_{z}\dagger}_{B}K^{\lambda_{z}}_{B}\right]$
(15)
$\displaystyle\leq\left(\max_{z}\\{p_{z}\xi_{z}^{4}\\}\right)\sum_{z=1}^{k}\sum_{\lambda_{z}}\mbox{Tr}_{A}\left[K^{\lambda_{z}}_{A}K^{\lambda_{z}\dagger}_{A}\right]\mbox{Tr}_{B}\left[K^{\lambda_{z}\dagger}_{B}K^{\lambda_{z}}_{B}\right]$
(16)
$\displaystyle=\left(\max_{z}\\{p_{z}\xi_{z}^{4}\\}\right)\sum_{\lambda_{z}}\mbox{Tr}\left[\left(K^{\lambda_{z}\dagger}_{A}\otimes
K^{\lambda_{z}\dagger}_{B}\right)\left(K^{\lambda}_{A}\otimes
K^{\lambda_{z}}_{B}\right)\right]$ (17)
$\displaystyle=\left(\max_{z}\\{p_{z}\xi_{z}^{4}\\}\right)\mbox{Tr}\left[\mathbb{1}_{A}\otimes\mathbb{1}_{B}\right]$
(18) $\displaystyle=d_{A}d_{B}\max_{z}\\{p_{z}\xi_{z}^{4}\\}.$ (19)

When $k$ quantum states $\\{\left|\Psi_{z}\right>\\}_{z=1}^{k}$ are equally
distributed ($p_{z}=1/k$), the bound becomes
$p^{\text{ND}}_{\text{succ}}\leq\frac{d_{A}d_{B}}{k}\max_{z}\xi_{z}^{4}$.
Furthermore, for NDSD of $k$ different MESs for local dimensions
$d_{A}=d_{B}=d$ and $\xi_{z}=1/\sqrt{d}$, the bound becomes

$p^{\text{ND}}_{\text{succ}}\leq\frac{1}{k},$

which is the same as the random guessing and independent of the local
dimension $d$. ∎

##  Appendix C Proof of theorem 2

###### Proof.

Suppose that Alice and Bob have a pre-shared MES
$\left|\alpha\right>=1/\sqrt{f}\sum_{\ell=1}^{f}\left|\ell\right>_{A^{\prime}}\otimes\left|\ell\right>_{B^{\prime}}$.
We write the given maximally entangled state $\left|\Psi_{z}\right>$ by
$1/\sqrt{d}\sum_{i=1}^{d}\left|ii\right>_{AB}$ for each $z$ by appropriately
choosing the basis of Alice and Bob. (Here, the choice of basis depends on
$z$, but it turns out that it is not important.) Since the initial state is
changed to $\left|\Psi_{z}\right>\otimes\left|\alpha\right>$, the success
probability of NDSD is given by

$\displaystyle p^{\text{ND}}_{\text{succ}}$
$\displaystyle=\frac{1}{k}\sum_{z}\sum_{\lambda_{z}}\left\|\langle\Psi_{z}|_{AB}K^{\lambda_{z}}_{AA^{\prime}}\otimes
K^{\lambda_{z}}_{BB^{\prime}}\left|\Psi_{z}\right>_{AB}\left|\alpha\right>_{A^{\prime}B^{\prime}}\right\|^{2}$
(20)
$\displaystyle=\frac{1}{k}\sum_{z}\sum_{\lambda_{z}}\sum_{m,n}\left|\langle\Psi_{z}|_{AB}\langle
mn|_{A^{\prime}B^{\prime}}K^{\lambda_{z}}_{AA^{\prime}}\otimes
K^{\lambda_{z}}_{BB^{\prime}}\left|\Psi_{z}\right>_{AB}\left|\alpha\right>_{A^{\prime}B^{\prime}}\right|^{2}$
(21)
$\displaystyle=\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\sum_{mn}\left|\sum_{i,j,\ell}\langle
ii|_{AB}\langle mn|_{A^{\prime}B^{\prime}}K^{\lambda_{z}}_{AA^{\prime}}\otimes
K^{\lambda_{z}}_{BB^{\prime}}\left|jj\right>_{AB}\left|\ell\ell\right>_{A^{\prime}B^{\prime}}\right|^{2}$
(22)
$\displaystyle=\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\sum_{m,n}\left|\sum_{i,j,\ell}\langle
im|_{AA^{\prime}}K^{\lambda_{z}}_{AA^{\prime}}\left|j\ell\right>_{AA^{\prime}}\cdot\langle
in|_{BB^{\prime}}K^{\lambda_{z}}_{BB^{\prime}}\left|j\ell\right>_{BB^{\prime}}\right|^{2}$
(23)
$\displaystyle\leq\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\sum_{m,n}\left(\sum_{i,j,\ell}\left|\langle
im|_{AA^{\prime}}K^{\lambda_{z}}_{AA^{\prime}}\left|j\ell\right>_{AA^{\prime}}\right|^{2}\right)\cdot\left(\sum_{i,j,\ell}\left|\langle
in|_{BB^{\prime}}K^{\lambda_{z}}_{BB^{\prime}}\left|j\ell\right>_{BB^{\prime}}\right|^{2}\right)$
(24)
$\displaystyle=\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\sum_{m,n}\mbox{Tr}_{A}\left[\langle
m|_{A^{\prime}}K^{\lambda_{z}}_{AA^{\prime}}K^{\lambda_{z}\dagger}_{AA^{\prime}}\left|m\right>_{A^{\prime}}\right]\cdot\mbox{Tr}_{B}\left[\langle
n|_{B^{\prime}}K^{\lambda_{z}}_{BB^{\prime}}K^{\lambda_{z}\dagger}_{BB^{\prime}}\left|n\right>_{B^{\prime}}\right]$
(25)
$\displaystyle=\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\mbox{Tr}_{AA^{\prime}}\left[K^{\lambda_{z}}_{AA^{\prime}}K^{\lambda_{z}\dagger}_{AA^{\prime}}\right]\cdot\mbox{Tr}_{BB^{\prime}}\left[K^{\lambda_{z}}_{BB^{\prime}}K^{\lambda_{z}\dagger}_{BB^{\prime}}\right]$
(26)
$\displaystyle=\frac{1}{d^{2}fk}\sum_{z}\sum_{\lambda_{z}}\mbox{Tr}\left[(K^{\lambda_{z}\dagger}_{AA^{\prime}}\otimes
K^{\lambda_{z}\dagger}_{BB^{\prime}})(K^{\lambda_{z}}_{AA^{\prime}}\otimes
K^{\lambda_{z}}_{BB^{\prime}})\right]$ (27)
$\displaystyle=\frac{1}{d^{2}fk}\mbox{Tr}\left[\mathbb{1}_{AA^{\prime}}\otimes\mathbb{1}_{BB^{\prime}}\right]=\frac{(df)^{2}}{d^{2}fk}=\frac{f}{k}.$
(28)

Since we assume that Alice and Bob pre-shared $c$-ebit, $f=2^{c}$ holds and we
have the desired result. ∎

##  Appendix D Average entanglement cost of two strategies

In the stabilizer method, we have a sign table for generators of stabilizers.
To compute the cost for certainly distinguishing the states by reading the
sign information, we can adopt uniquely decodable code or prefix code by
matching bit strings to quantum states. For instance, in NDSD of three Bell
states
$\\{\left|\Phi^{0}\right>,\left|\Phi^{1}\right>,\left|\Phi^{2}\right>\\}$, we
can assign $0$ to $\left|\Phi^{2}\right>$, $10$ to $\left|\Phi^{0}\right>$,
and $11$ to $\left|\Phi^{1}\right>$. Since $1$ ebit is needed for deciding
each sign (bit) of a generator, the average cost is $1/3\times 1+2/3\times
2=5/3$ (ebits). We represent such cost as $\\{1,2,2\\}$. The optimality of
this cost under the stabilizer method is ensured by the Kraft-McMillan
inequality from the coding theory [50, 51]. First, we show that the optimal
cost for a given number of states is provided by the following lemma:

######  Lemma 1.

Suppose we have $2^{n}+k$ uniformly distributed words consists of binary
alphabets with $n\in\\{2,3,\dots\\}$ and $k\in\\{1,2,\dots,2^{n}-1\\}$. Then
the optimal codeword length for the prefix code is
$\\{n,\dots,n,n+1,\dots,n+1\\}$ with the number of $n$’s is $2^{n}-k$, and
$(n+1)$’s is $2k$.

###### Proof.

It is easy to figure out that the optimal codeword length of $2^{n}$ words is
$\\{n,\dots,n\\}$ because it can reach the Shannon entropy as
$-\sum\frac{1}{2^{n}}\log_{2}\frac{1}{2^{n}}=n$. Then let us consider adding
one more word to them, i.e., $k=1$. Since $n$ bits are fully occupied to
represent $2^{n}$ words, a simple method uses two $n+1$ bits to represent the
last two words. This costs $\\{n,\dots,n,n+1,n+1\\}$ with $2^{n}-1$ of $n$’s,
which saturates Kraft-McMillan inequality. To check its optimality, suppose we
use a $n-1$ bit for a codeword. This reduces cost by 1 but causes the
collapsing of two codewords, so one needs additional two codewords, which
finally yields the codeword length $\\{n,\dots,n,n-1,n+1,n+1,n+1,n+1\\}$ with
$2^{n}-4$ of $n$’s. One can check this codeword length is also saturating the
Kraft-McMillan inequality, but there is one-bit gap compared with the former
method. Therefore, we cannot use a $n-1$ bit codeword for an additional word,
and a similar procedure renders the result for additional $k$ words. ∎

For NDSD of Bell states, the optimal average cost is $\\{1,1\\}=2$ ebits when
$k=2$, and $\\{2,2,2,2\\}=4$ ebits when $k=4$, the same cost of the
discrimination-and-repreparation method. The stabilizer method also can
achieve these costs by reading the sign of one (two) generator for $k=2(k=4)$.

For $n$-Bell pairs with only three indices, the cost of teleportation of each
Bell pair is obviously 2$n$ ebits. On the other hand, we can have a sign table
for the stabilizer method, which is essentially $n$-copy of the sign table of
the three Bell state case. Thus the average cost that we can achieve is $5n/3$
ebits.

Now, we consider the example of 6 MESs. First, we compute the average
entanglement cost of the stabilizer scheme. Let us represent the given set of
states
$\left\\{\left|\Phi^{012}\right>,\left|\Phi^{021}\right>,\left|\Phi^{102}\right>,\left|\Phi^{120}\right>,\left|\Phi^{201}\right>,\left|\Phi^{210}\right>\right\\}$
as a sign table whose elements indicate the signs of $Z_{A_{i}}Z_{B_{i}}$ and
$X_{A_{i}}X_{B_{i}}$ where $i=\\{1,2,3\\}$, which can be written as

| $Z_{A_{1}}Z_{B_{1}}$ | $X_{A_{1}}X_{B_{1}}$ | $Z_{A_{2}}Z_{B_{2}}$ | $X_{A_{2}}X_{B_{2}}$ | $Z_{A_{3}}Z_{B_{3}}$ | $X_{A_{3}}X_{B_{3}}$
---|---|---|---|---|---|---
$\left|\Psi^{012}\right>$ | $+$ | $+$ | $+$ | $-$ | $-$ | $+$
$\left|\Psi^{021}\right>$ | $+$ | $+$ | $-$ | $+$ | $+$ | $-$
$\left|\Psi^{102}\right>$ | $+$ | $-$ | $+$ | $+$ | $-$ | $+$
$\left|\Psi^{120}\right>$ | $+$ | $-$ | $-$ | $+$ | $+$ | $+$
$\left|\Psi^{201}\right>$ | $-$ | $+$ | $+$ | $+$ | $+$ | $-$
$\left|\Psi^{210}\right>$ | $-$ | $+$ | $+$ | $-$ | $+$ | $+$

We measure the sign of the first column. When the outcome is $-$, check the
fourth column to distinguish two states of them, which costs 2 ebits. If the
outcome of the first column is $+$, we can check the second and third columns
to distinguish the remaining states, which costs 3 ebits. Therefore, the total
cost is $\\{2,2,3,3,3,3\\}$, i.e., 16/6 ebits, which is the optimal by Lemma
1.

Second, let us consider the entanglement cost of the qubit teleportation
scheme. A naive strategy needs 3 ebits because one can distinguish the first
Bell state among three states $\Phi^{0},\Phi^{1},\Phi^{2}$ by teleportation
using 2 ebits including the repreparation, and another ebit is used for local
discrimination and repreparation for the second Bell state according to the
result on the first one. However, we need to consider LOCC convertibility of
our set of states. Specifically, two classes of sets achieve the optimal cost
using the qubit teleportation scheme. The first case is that four Bell states
can appear in the first qubit. Then by local teleportation and local
discrimination, one can easily check that the entanglement cost of this case
is the optimal one, i.e., $\\{2,2,3,3,3,3\\}$. To confirm that our set of
states cannot be LOCC equivalent to this set, we use the condition of the
unitary equivalent of sets of matrices. Especially, a set of tensor products
of multiple-Bell pairs can be represented by a set of unitary matrices $U_{i}$
such that $U_{i}\otimes\mathbb{1}\left|\psi\right>$ for a reference state
$\left|\psi\right>$. Since LOCC is equivalent to local unitary (LU) for pure
state [52], LOCC equivalence of the set of tensor products of multiple-Bell
pairs is converted to the unitary equivalence of sets of unitary matrices. An
equivalent condition of unitary equivalence between sets of matrices
$\\{U_{i}\\}$ and $\\{V_{i}\\}$ is satisfying
$\mbox{Tr}[w\\{U_{i}U^{\dagger}_{j}\\}]=\mbox{Tr}[w\\{V_{i}V^{\dagger}_{j}\\}]$
for all words $w\\{\\}$ [53]. In our case, the set of matrices are 3-qubit
Pauli matrices, so we need to check which words make the identity. Because the
corresponding Pauli operators are $\\{IZX,IXZ,ZIX,ZXI,XIZ,XZI\\}$, the
constructed words from the set are as
$\\{IYY,ZZI,ZYX,XZY,XIX,ZXY,ZIZ,XXI,XYZ,IXX,YIY,YZX,YXZ,YYI,IZZ\\}$. Let us
consider a word of all products of elements in the set. From the symmetry of
our set, this yields $III$. However, the set having four Bell states,
$\\{I,Z,X,Y,I,Z\\}$ in the first qubit, always makes the word including Pauli
operator instead of the identity, so thus leading to zero trace. This fact
shows our set is not LOCC equivalent to the set including four Bell states.

In the second case, the first qubit can be only two of four Bell states so
that local discrimination is possible. Since a set $\\{I,I,I,Z,Z,Z\\}$ in the
first qubit makes Pauli operator for the all-product word, consider
$\\{I,I,Z,Z,Z,Z\\}$. To achieve the optimal cost, the second qubit should have
an unbalanced set of Pauli operators, for instance, $\\{X,Z,I,I,Z,Z\\}$. Then
this yields a Pauli operator in the second qubit for the all-product word,
which shows the LOCC inequivalence with our set.