QED

    quantum entanglement distillation
w.r.t.

    with respect to
i.i.d.

    independent and identically distributed
pmf

    probability mass function
pdf

    probability density function
cdf

    cumulative distribution function
iff

    if and only if
POVM

    positive operator-valued measure
QBER

    quantum bit error rate

# Minimization of the estimation error for entanglement distribution networks
with arbitrary noise

Liangzhong Ruan  School of Cyber Science and Engineering, Xi’an Jiaotong
University, China
Qutech, Delft University of Technology, The Netherlands

###### Abstract

Fidelity estimation is essential for the quality control of entanglement
distribution networks. Because measurements collapse quantum states, we
consider a setup in which nodes randomly sample a subset of the entangled
qubit pairs to measure and then estimate the average fidelity of the unsampled
pairs conditioned on the measurement outcome. The proposed estimation protocol
achieves the lowest mean squared estimation error in a difficult scenario with
arbitrary noise and no prior information. Moreover, this protocol is
implementation friendly because it only performs local Pauli operators
according to a predefined sequence. Numerical studies show that compared to
existing fidelity estimation protocols, the proposed protocol reduces the
estimation error in both scenarios with i.i.d. noise and correlated noise.

##  I Introduction

Entanglement distribution networks [1] are an important developmental stage on
the way to a full-blown quantum Internet [2, 3, 4]. Such networks enable
device-independent protocols [5, 6, 7, 8, 9], thereby achieving the highest
level of quantum security [10]. Entanglement distribution networks do not
require nodes to have local quantum memory. Since efficient communication-
compatible quantum memories are still under development [11], entanglement
distribution networks serve as a cornerstone for realizing trustworthy quantum
applications with state-of-the-art quantum technology [12, 13, 14, 15].

Entanglement quality assessment is a key building block for entanglement
distribution networks. To this end, fidelity estimation for entangled states
is a promising candidate. Fidelity is a metric that indicates the quality of
quantum states [16, 17, 18, 19] and can be estimated with separable quantum
measurements and classical post-processing. Several fidelity estimation
protocols have been proposed [20, 21, 22, 23], and fidelity estimation
protocols of entangled states have been implemented in several recent
experiments [24, 12, 13, 14]. However, there are still two challenges that
need to be addressed.

  * •

Excessive estimation error due to arbitrary noise: Quantum networks often face
heterogeneous and correlated noise. When distributing quantum keys and
estimating channel capacities, this noise leads to excessive estimation errors
[25, 26]. Therefore, designing low-error fidelity estimation protocols in the
presence of arbitrary noise is an interesting area of research.

  * •

Efficiency loss due to separable operations: In the absence of quantum memory,
nodes in entanglement distribution networks perform operations that are
separable between all qubits. Such operations result in significantly lower
estimation efficiency [27] compared to joint operations. Minimizing the loss
of efficiency due to separable operations is a major challenge for fidelity
estimation.

This work focuses on fidelity estimation for entanglement distribution
networks. Since measurements collapse quantum states, we consider a network in
which nodes randomly sample a subset of qubit pairs to measure and estimate
the average fidelity of unsampled pairs conditioned on the measurement
outcome.

We prove that the protocol proposed in this paper achieves the lowest
estimation error in the difficult scenario with arbitrary noise and no prior
information, thereby overcoming the challenges listed above. Moreover, the
proposed protocol is implementation friendly. This protocol uses only local
Pauli measurements, standard operations that can be implemented on a variety
of quantum platforms, [28, 12, 24, 29], and determines the basis of each Pauli
measurement according to a predefined sequence, so that no adaptive operation
is required.

The remainder of the paper is organized as follows. Section II formulates the
problem of minimizing the estimation error of fidelity in a scenario with
arbitrary noise and no prior information. Section III and IV solve the
formulated problem and present a protocol that minimizes the estimation error
of fidelity. Section V evaluates the proposed protocol by comparing it with
exsiting ones. Finally, Section VI presents the conclusion.

##  II System Setup and Problem Formulation

Consider a scenario in which two nodes share $N$ noisy qubit pairs and have no
prior information of the noise. The nodes want to estimate the fidelity of the
qubit pairs with respect to (w.r.t.) the target maximally entangled state.
Since maximally entangled states are mutually convertible via local
operations, we set the target state to $|\Psi^{-}\rangle$ without loss of
generality, where
$|\Psi^{\pm}\rangle=\frac{|01\rangle\pm|10\rangle}{\sqrt{2}}$,
$|\Phi^{\pm}\rangle=\frac{|00\rangle\pm|11\rangle}{\sqrt{2}}$ are the four
Bell states. Denote the set of all qubit pairs by ${\cal{N}}$. The nodes
randomly sample $M(<N)$ number of qubit pairs to measure. The set of sampled
pairs, ${\cal{M}}$, is drawn from all $M$-subsets of ${\cal{N}}$ with equal
probability.

Entanglement distribution networks do not require nodes to have local quantum
memory [1]. Consequently, the nodes execute operators that are separable
between all qubits. Denote the separable operators by

$\displaystyle\bm{M}_{r}=\sum_{k}\otimes^{n\in{\cal{M}}}(\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}),$
(1)

where the node index $\mathrm{X}\in\\{\mathrm{A},\mathrm{B}\\}$, the qubit
pair index $n\in{\cal{M}}$, and the operator index $r\in{\cal{R}}$, with
${\cal{R}}$ denoting the set of all possible measurement outcomes. As positive
operator-valued measure (POVM) operators,

$\displaystyle\bm{M}^{\mathrm{(X)}}_{r,n,k}\succcurlyeq\bm{0},\;\sum_{r}\bm{M}_{r}=\mathbb{I}_{4^{M}},$
(2)

where $\succcurlyeq$ denotes the matrix inequality. The measurement operation
performed on all qubit pairs can be defined as

$\displaystyle{\cal{O}}=\\{\bm{M}_{r},\;r\in{\cal{R}}\\},$ (3)

Denote $\bm{\rho}_{\mathrm{all}}$ as the joint state of all qubit pairs before
the measurements, and denote the $\bm{\rho}_{\mathrm{all}}^{(r)}$ as the joint
state of the qubit pairs conditioned on the measurement outcome $r$. In this
case, the state of the $n$-th pair is

$\displaystyle\bm{\rho}^{(r)}_{n}=\mathrm{Tr}_{i\in{{\cal{N}}}\backslash\\{n\\}}\bm{\rho}_{\mathrm{all}}^{(r)}.$
(4)

Because measurements collapse quantum states, the nodes estimate the average
fidelity of unsampled pairs conditioned on the measurement outcome $r$, i.e.,

$\displaystyle\bar{f}=\frac{1}{N-M}\sum_{n\in{\cal{N}}\backslash{\cal{M}}}\langle\Psi^{-}|\bm{\rho}^{(r)}_{n}|\Psi^{-}\rangle.$
(5)

The imperfection of the measurements is considered as part of the noise. Based
on the measurement outcome, the estimator ${\cal{D}}$ is used to estimate the
average fidelity of the unsampled qubit pairs $\bar{f}$, i.e.,

$\displaystyle\check{f}={{\cal{D}}}(r).$ (6)

The nodes target at minimizing the mean squared error of the estimated
fidelity. Because the set of sampled qubit pairs ${\cal{M}}$ is drawn from all
$M$-subsets of ${\cal{N}}$ with equal probability, each $M$-subset is selected
with probability ${N\choose M}^{-1}$. Therefore, the mean squared estimation
error is given by

$\displaystyle{N\choose
M}^{-1}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{]}.$
(7)

Since the factor ${N\choose M}^{-1}$ does not affect the optimization of the
measurement protocol $\\{{\cal{O}},{\cal{D}}\\}$, it is omitted in the
following problem formulation for clarity.

To ensure the robustness of the fidelity estimation protocol, we consider the
scenario with arbitrary noise and no prior information. Since there is
arbitrary noise, the state of all qubit pairs
$\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{arb}}$, where
${{\cal{S}}}_{\mathrm{arb}}$ is the set of all $N$ qubit-pair states. Since
there is no prior information, the state $\bm{\rho}_{\mathrm{all}}$ that leads
to the largest error must be considered. This optimization problem is
formulated as follows.

######  $\mathscr{P}$\- 1:

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{arb}}}{N\choose
M}^{\\!-1\\!}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{]}$
(8a) subject to
$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{F}\big{]}=0,\;\;\forall\bm{\rho}_{\mathrm{all}}\in{{{\cal{S}}}_{\mathrm{arb}}}$
(8b)

where $\check{F}$, $\bar{F}$, and $R$ are the random variable form of the
estimated fidelity $\check{f}$, the average fidelity $\bar{f}$, and the
measurement outcome $r$, respectively, (8b) is the unbiased constraint of the
estimate.

The following two sections elaborates the key procedures and ideas for solving
$\mathscr{P}$-1, which involves two main steps, namely problem transformation
and operation construction. Readers may refer to Appendices A and B for the
formal propositions and detailed derivations of these two steps.

##  III Problem Transformation

This step shows that $\mathscr{P}$-1 can be transformed into an equivalent
problem with independent noise. It consists of three substeps.

  * •

A1. This substep simplifies $\mathscr{P}$-1 to an equivalent one with
classical correlated noise, that is,

######  $\mathscr{P}$\- 2:

Special case of $\mathscr{P}$-1, with ${{\cal{S}}}_{\mathrm{arb}}$ replaced by
${{\cal{S}}}_{\mathrm{sp}}$, i.e., the set of $\bm{\rho}_{\mathrm{all}}$ that
are separable among all qubit pairs.

The key concept is to construct an operation ${\cal{T}}$ that removes the
entanglement among different qubit pairs without changing the fidelity. This
operation transforms the states in ${{\cal{S}}}_{\mathrm{arb}}$ to those in
${{\cal{S}}}_{\mathrm{sp}}$. Then, the transformed state can be estimated by
the optimal solution of $\mathscr{P}$-2, ensuring that the minimum estimation
error for states in ${{\cal{S}}}_{\mathrm{arb}}$ is no higher than for states
in ${{\cal{S}}}_{\mathrm{sp}}$.

Specifically, the probabilistic rotation ${\cal{T}}$ acts independently on
each qubit pair. This operation rotates both qubits first along the $x$-axis
by $180^{\circ}$ with probability 0.5 and then along the $y$-axis by
$180^{\circ}$ with probability 0.5. For Bell states
$|\phi\rangle,|\psi\rangle\in\\{|\Phi^{\pm}\rangle$, $|\Psi^{\pm}\rangle\\}$,

$\displaystyle|\phi\rangle\langle\psi|$ $\displaystyle\mbox{if
}|\phi\rangle=|\psi\rangle$ (9a) $\displaystyle\bm{0}$ $\displaystyle\mbox{if
}|\phi\rangle\neq|\psi\rangle$ (9b)

(9a) ensures that ${\cal{T}}$ does not change the fidelity of the qubit pairs.
(9b) shows that ${\cal{T}}$ removes the off-diagonal terms of a density matrix
expressed in Bell basis. Such a diagonal density matrix corresponds to states
separable among all qubit pairs.

  * •

A2. This substep shows that to solve $\mathscr{P}$-2, it is sufficient to
consider the special case with independent noise, i.e.,

######  $\mathscr{P}$\- 3:

Special case of $\mathscr{P}$-2, with ${{\cal{S}}}_{\mathrm{sp}}$ replaced by
${{\cal{S}}}_{\mathrm{id}}$, i.e., the set of $\bm{\rho}_{\mathrm{all}}$ that
are product states.

Denote $\check{f}(r)$ as the estimated fidelity given the measurement outcome
$r$, and denote $\bar{f}(\bm{\rho}_{\mathrm{all}},{\cal{M}},r)$ as the average
fidelity given the state $\bm{\rho}_{\mathrm{all}}$, the sample set
${\cal{M}}$ and the measurement outcome $r$. Separable states
$\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{sp}}$ are ensembles of
product states, i.e.,
$\bm{\rho}_{\mathrm{all}}=\sum_{k}p_{k}\bm{\rho}^{(k)}_{\mathrm{all}}$, where
$\bm{\rho}^{(k)}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}$, and ensemble
probabilities $p_{k}$ satisfy $p_{k}\geqslant 0$, $\sum_{k}p_{k}=1$.
Consequently, for each set ${\cal{M}}$, the estimation error with a separable
state $\bm{\rho}_{\mathrm{all}}$ and that with product states
$\\{\bm{\rho}^{(k)}_{\mathrm{all}}\\}$ are related by the following
inequality.

$\displaystyle\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{|}\bm{\rho}_{\mathrm{all}}\big{]}$
$\displaystyle=\sum_{r}\mathrm{Pr}(r|{\cal{M}})\big{(}\check{f}(r)-\bar{f}(\bm{\rho}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(10a)
$\displaystyle=\sum_{r}\mathrm{Pr}(r|{\cal{M}})\big{(}\check{f}(r)-\sum_{k}\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(10b)
$\displaystyle\leqslant\sum_{r,k}\mathrm{Pr}(r|{\cal{M}})\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)\big{(}\check{f}(r)-\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(10c)
$\displaystyle=\sum_{k}p_{k}\\!\sum_{r}\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}})\big{(}\check{f}(r)-\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(10d)
$\displaystyle=\sum_{k}p_{k}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f})^{2}\big{|}\bm{\rho}^{(k)}_{\mathrm{all}}\big{]}.$
(10e)

where $\mathrm{Pr}(\cdot)$ denotes the probability, (10c) is true because
$(\sum_{k}w_{k}x_{k})^{2}\leqslant\sum_{k}w_{k}x^{2}_{k}$,
$\forall\,x_{k}\in\mathbb{R},w_{k}\geqslant 0,\sum_{k}w_{k}=1$, and (10d)
holds because according to Bayes’ theorem

$\displaystyle\mathrm{Pr}(r|{\cal{M}})\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)$
$\displaystyle=\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}})\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}})$
$\displaystyle=\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}})\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}})$
$\displaystyle=p_{k}\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}}),$
(11)

where the second equation holds becase that the sampling set ${\cal{M}}$ and
the state $\bm{\rho}^{(k)}_{\mathrm{all}}$ are independent. Because
$\bm{\rho}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{sp}}$ and
$\bm{\rho}^{(k)}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{id}}$, $\forall k$, (10)
shows that the minimum estimation error of $\mathscr{P}$-2 is upper bounded by
that of $\mathscr{P}$-3.

######  Remark 1 (Limit the effect of correlation):

The result of step A2 is unexpected because correlated noise usually leads to
a higher estimation error compared to independent noise. To understand this
result, recall that the estimation target, i.e., the average fidelity of the
unsampled qubit pairs, is evaluated conditioned on the measurement outcome.
Consequently, the conditional distribution
$\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)$ appears in the
expression of the estimation error, i.e., (10b). This conditional probability
allows the application of Bayes’ theorem in (11), which bounds the estimation
error of the states in ${\cal{S}}_{\mathrm{sp}}$ by that of the states in
${\cal{S}}_{\mathrm{id}}$. ∎

  * •

A3. This substep shows that to solve $\mathscr{P}$-3, it is sufficient to
minimize the estimation error of the sampled pairs, i.e.,

######  $\mathscr{P}$\- 4:

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\scriptstyle\bm{\rho}_{\mathrm{all}}\in\atop\scriptstyle{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})}{N\choose
M}^{\\!-1\\!}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}$
subject to
$\displaystyle\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{]}=0,\,\forall\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),{\cal{M}}\subset{\cal{N}}$

where
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})=\\{\otimes^{n\in{\cal{N}}}\bm{\rho}_{n}\\}$
is the set of product states with fidelity composition
$\bm{f}_{\mathrm{all}}=\\{f_{n},n\in{\cal{N}}\\}$, in which $f_{n}$ is the
fidelity of $\bm{\rho}_{n}$, and $\bar{f}_{{\cal{M}}}$ is the average fidelity
of the sampled qubit pairs.

In the case of independent noise, the measurement does not affect the fidelity
of the unsampled qubit pairs. Consequently, the estimation error of
$\mathscr{P}$-3 can be decomposed into two parts, namely the estimation error
of the sampled qubit pairs,

$\displaystyle{N\choose
M}^{\\!-1\\!}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]},$
(12)

and the sampling error, i.e., the deviation between the average fidelity of
the sampled and the unsampled qubit pairs,

$\displaystyle{N\choose
M}^{\\!-1\\!}\sum_{{\cal{M}}}(\bar{f}_{{\cal{M}}}-\bar{f})^{2}.\,$ (13)

The sampling error (13) is not affected by the estimation protocol. Therefore,
$\mathscr{P}$-3 can be simplified to $\mathscr{P}$-4, which minimizes (12).

##  IV Operation Construction

The next step is to construct the optimal solution of $\mathscr{P}$-1, which
involves the following two substeps.

  * •

B1. This substep characterizes the minimum estimation error of
$\mathscr{P}$-4.

The characterization of the minimal estimation error has been a subject of
intense research. For $\mathscr{P}$-4, the Cramér-Rao bound [30, 31]
characterizes the lower bound of the estimation error for a given measurement
operation ${\cal{O}}$, and the quantum Fisher information [32, 33] identifies
this lower bound under the condition that all measurement operations are
available.

However, $\mathscr{P}$-4 aims to minimize the estimation error when all
separable measurement operations are available. Therefore, the Cramér-Rao
bound alone does not provide the lowest bound, while the quantum Fisher
information provides a lower bound that is infeasible. We will close this gap
by first further simplifying $\mathscr{P}$-4, and then characterizing the
limit of separable operators.

The derivation of a Cramér-Rao bound [30, 31] requires knowledge of the
distribution of a measurement outcome. In $\mathscr{P}$-4, this distribution
is determined by the state of the qubit pairs $\bm{\rho}_{\mathrm{all}}$ and
the measurement operation ${\cal{O}}$. However, even with independent noise,
the state of each qubit pair $\bm{\rho}_{n}\in{\cal{H}}^{4\times 4}$ has
several parameters other than the fidelity. This fact complicates the
expression of the measurement outcome and makes the analysis of the Cramér-Rao
bound not feasible. To overcome this challenge, we show that the minimum
estimation error of general independent states is bounded below by that of
independent Werner states, i.e.,

######  $\mathscr{P}$\- 5:

Special case of $\mathscr{P}$-4, with
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})$ replaced by
${{\cal{S}}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}})=\\{\otimes^{n\in{\cal{N}}}\bm{\sigma}_{n}\\}$,
where

$\displaystyle\bm{\sigma}_{n}=f_{n}|\Psi^{-}\rangle\langle\Psi^{-}|+\frac{1-f_{n}}{3}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|).$
(14)

Specifically, recall the bilateral rotation operation ${\cal{B}}$ in [34],
which transforms generic states of a qubit pair into the Werner state with the
same fidelity. Using logic similar to that in step A1, one can see that
because the states in ${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})$ can
be transformed into those in ${{\cal{S}}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}})$
via the separable operation ${\cal{B}}$, the minimum estimation error of
$\mathscr{P}$-4 is no higher than that of $\mathscr{P}$-5. The states in
${{\cal{S}}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}})$ are fully parameterized by
the fidelity composition $\bm{f}_{\mathrm{all}}$, which allows the Cramér-Rao
bound analysis of $\mathscr{P}$-5.

The other factor affecting the distribution of measurement outcome is the
separable measurement operation ${\cal{O}}$. Since the fidelity of each
separable state w.r.t. a maximally entangled state lies in the interval
$[0,\frac{1}{2}]$ [35], we have that for any separable operator $\bm{M}$,

$\displaystyle
0\leqslant\frac{\mathrm{Tr}(|\Psi^{-}\rangle\langle\Psi^{-}|\bm{M})}{\mathrm{Tr}(\bm{M})}\leqslant\frac{1}{2}.$
(15)

For all separable operators, (15) limits the sensitivity of the measurement
outcome to the changes in fidelity. Plugging this result into the Cramér-Rao
bound, we lower bound the estimation error of $\mathscr{P}$-5 by

$\displaystyle\sum_{n\in{\cal{N}}}\frac{(2f_{n}+1)(1-f_{n})}{2MN}.$ (16)

  * •

B2. The second substep constructs an estimation protocol that is the optimal
solution of $\mathscr{P}$-1.

Protocol 1 Fidelity estimation

1:Preprocessing. The nodes select the sample set ${\cal{M}}$ completely at
random, i.e, select ${\cal{M}}$ from all $M$-subsets of ${\cal{N}}$ with equal
probability, and generate $M$ number of independent and identically
distributed (i.i.d.) random variables $A_{n}\in\\{x,y,z\\}$, $n\in{\cal{M}}$,
with distribution $\Pr[A_{n}=u]=\frac{1}{3},\quad u\in\\{x,y,z\\}.$

2:Perform measurements. For the qubit pair $n\in{\cal{M}}$, both nodes measure
the qubit in the $A_{n}$-basis. If the measurement results of the two nodes
match, record measurement outcome $r_{n}=1$, otherwise record $r_{n}=0$.

3:Estimate fidelity. The number of errors and the quantum bit error rate
(QBER) are expressed as $e_{{\cal{M}}}=\sum_{n\in{\cal{M}}}r_{n}$, and
$\varepsilon_{{\cal{M}}}=\dfrac{e_{{\cal{M}}}}{M}$, respectively. The
estimated fidelity is
$\displaystyle\check{f}=1-\frac{3}{2}\varepsilon_{{\cal{M}}}.$ (17)

The analysis in step B1 shows that to achieve the Cramér-Rao bound, each
measurement operator must balance either of the two inequalities in (15) (For
details, see the proof of thm:min, the derivation from (98) to (104)).
According to this principle, the measurement operation ${\cal{O}}^{*}$ of
Protocol 1 is constructed. For example, when nodes measure in the $z$-basis,
the operators corresponding to $r=0$ and $r=1$ are respectively

$\displaystyle\begin{split}&\bm{M}_{z,0}=\left|01\right>\\!\left<01\right|+\left|10\right>\\!\left<10\right|=|\Psi^{-}\rangle\langle\Psi^{-}|+|\Psi^{+}\rangle\langle\Psi^{+}|,\\\
&\bm{M}_{z,1}=\left|00\right>\\!\left<00\right|+\left|11\right>\\!\left<11\right|=|\Phi^{-}\rangle\langle\Phi^{-}|+|\Phi^{+}\rangle\langle\Phi^{+}|.\end{split}$
(18)

According to (18), $\bm{M}_{z,0}$ and $\bm{M}_{z,1}$ balance the second and
first inequalities of (15), respectively. Moreover, according to the
preprocessing step, the basis of measurement on each qubit pair are chosen in
an i.i.d. manner. With these properties, we show that in scenarios with
independent noise, the measurement outcome $R_{n}\in{\cal{M}}$ are independent
random variables with variance

$\displaystyle\frac{2(2f_{n}+1)(1-f_{n})}{9}.$ (19)

Further noticing that the sample set ${\cal{M}}$ is selected from all
$M$-subsets of ${\cal{N}}$ with equal probability, we substitute (19) into
(17) and obtain that the operation ${\cal{O}}^{*}$ achieves the minimum
estimation error given by (16) for states in ${\cal{S}}_{\mathrm{id}}$.
Therefore, ${\cal{O}}^{*}$ is optimal for $\mathscr{P}$-4. In this case,
according to the problem transformation step, the composite operation
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}$ is optimal for
$\mathscr{P}$-1.

To further simplify the measurement operation, we note that according to (9),
the operation ${\cal{T}}$ on each qubit pair can be expressed by the following
four Kraus operators

$\displaystyle\bm{T}_{\phi}$
$\displaystyle=|\phi\rangle\langle\phi|,\quad\mbox{where}\quad\phi\in\\{\Phi^{\pm},\Psi^{\pm}\\}.$
(20)

Substituting (20) into (18) shows that the operation ${\cal{T}}$ does not
change the operators of ${\cal{O}}^{*}$, e.g.,

$\displaystyle\bm{M}_{z,r}$
$\displaystyle=\sum_{\phi\in\\{\Phi^{\pm},\Psi^{\pm}\\}}\bm{T}^{\dagger}_{\phi}\bm{M}_{z,r}\bm{T}_{\phi},\;\;r\in\\{0,1\\},$
(21)

(21) shows that
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}={\cal{O}}^{*}$, i.e.,
$\hat{{\cal{O}}}^{*}$ and ${\cal{O}}^{*}$ are equivalent. Therefore,
${\cal{O}}^{*}$ is optimal for $\mathscr{P}$-1.

######  Remark 2 (The advantage of Protocol 1):

It may seem that using bilateral Pauli measurements as in Protocol 1 is a
quite natural choice for estimating the fidelity of entangled qubit pairs. In
fact, using these standard measurements to obtain optimal performance in
scenarios with arbitrary noise is a key advantage of Protocol 1.

To ensure implementability of Protocol 1, simpler operations are chosen with
priority. In fact, by using more complicated operations, one can obtain
optimal solutions of $\mathscr{P}$-1 other than Protocol 1. For example,
consider a protocol in which the nodes perform the operation ${\cal{T}}$
defined in (9) before making the Pauli measurements in Protocol 1. Then
according to the paragraph after (18), this protocol is also optimal for
$\mathscr{P}$-1. We have made additional efforts to simplify the measurement
operators while preserving the optimality of the protocol.

To achieve optimal performance in scenarios with arbitrary noise, the
preprocessing step, i.e., step 1, is developed. The complete randomness of the
sampling set ${\cal{M}}$, and the i.i.d. distribution of the bases of the
measurements are necessary for handling arbitrary noise. For example, when the
measurements in the $x$-, $y$-, or $z$-basis are made in a clustered manner,
the estimated fidelity is biased or has a higher estimation error for some
non-i.i.d. noises. The preprocessing in step 1 neutralizes the effect of the
arbitrary nose without compromising the implementability of Protocol 1. ∎

##  V Protocol Evaluation

In this section, we evaluate the proposed protocol for fidelity estimation by
comparing it to existing fidelity estimation protocols.

Noise model: The noise is modeled as correlated and heterogeneous depolarizing
channels. Specifically, the corresponding density matrix of all qubit pairs is

$\displaystyle\bm{\rho}_{\mathrm{all}}=\frac{1}{2}\Big{(}$
$\displaystyle\big{(}\otimes^{\frac{N}{4}}\bm{\rho}^{(g)}\big{)}\otimes\big{(}\otimes^{\frac{3N}{4}}\bm{\rho}^{(b)}\big{)}+$
$\displaystyle\big{(}\otimes^{\frac{3N}{4}}\bm{\rho}^{(g)}\big{)}\otimes\big{(}\otimes^{\frac{N}{4}}\bm{\rho}^{(b)}\big{)}\Big{)},$
(22)

where the state of each qubit pair

$\displaystyle\bm{\rho}^{(s)}=p^{(s)}\frac{\mathbb{I}_{4}}{4}+(1-p^{(s)})|\Psi^{-}\rangle\langle\Psi^{-}|,\quad
s\in\\{g,b\\}$ (23)

in which the error probabilities $p^{(s)}$, $s\in\\{g,b\\}$ of good and bad
channels satisfy $0\leqslant p^{(g)}\leqslant p^{(b)}\leqslant 1$, and $N$ is
a multiple of $4$.

The mean of the error probabilities of the bad and good channels, i.e.,

$\displaystyle p=\frac{p^{(b)}+p^{(g)}}{2}\in[0,1],$ (24)

represents the noisy intensity, and the difference between the two
probabilities, i.e.,

$\displaystyle d=p^{(b)}-p^{(g)}\in[0,1],$ (25)

represents the degree of correlation and heterogeneity of the noise. In
particular, the noise is i.i.d. when $d=0$. $\square$

Figure 1: The variance of the estimated fidelity given by different protocols
as a function of the noisy intensity $p$ and the degree of correlation and
heterogeneity $d$. In this figure, $N=1000$, $M=500$. In subfigure A, $d=0$,
i.e., the noise is i.i.d.. In subfigure B, $p=0.5$.

Fig. 1 shows the mean squared estimation error, i.e.,
$\mathrm{Var}(\check{F})$, as a function of the noisy intensity $p$ and the
degree of correlation and heterogeneity $d$. The proposed protocol is compared
with those proposed in [22] and [21]. This figure shows that the estimation
error is an increasing function of both $p$ and $d$. In all cases, the
proposed protocol has the lowest estimation error. This result is consistent
with thm:opt, which states that Protocol 1 is an optimal solution of
$\mathscr{P}$-1.

##  VI Conclusion

In this paper, we propose a protocol to estimate the fidelity of entangled
qubit pairs shared by remote nodes. The proposed protocol uses only Pauli
measurements, and achieves the minimum mean squared error in a challenging
scenario with arbitrary noise and no prior information. The numerical tests
confirm the efficiency and reliability of the proposed protocol.

##  VII Acknowledgement

The author would like to thank Stephanie Wehner and Bas Dirkse at TUDelft, The
Netherlands, for refining the structure of the paper and stimulating
discussions on the treatment of non-i.i.d. noise. The author is also indebted
to Wenhan Dai at UMass, USA, who distilled the logic of the derivation and
proofread the manuscript.

The author thanks the EU Flagship on Quantum Technologies and the Quantum
Internet Alliance (funded by the EU Horizon 2020 Research and Innovation
Programme, Grant No. 820445).

## Notations

In this document, random variables and their realizations are represented in
upper and lower case letters, respectively, e.g. $F$ and $f$. Vectors and
matrices are denoted by bold letters, e.g., $\bm{\rho}$. $\mathbb{E}[\cdot]$,
and $\mathbb{V}[\cdot]$ denote the expectation and variance of a random
variable, respectively. $\mathbb{I}_{n}$ denotes an $n\times n$ identity
matrix. $\mathrm{Pr}(\cdot)$ denotes the probability of an event,
$\mathrm{Tr}(\cdot)$ denotes the trace of a matrix, and
$\mathrm{Tr}_{n}(\cdot)$ denotes the partial trace of the $n$-th subsystem.

##  Appendix A Problem Transformation

Recall the problem of minimizing the mean squared estimation error of fidelity
in scenarios with arbitrary noise, i.e.,

######  $\mathscr{P}$\- 1 (Error minimization for arbitrary states):

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{arb}}}{N\choose
M}^{\\!-1\\!}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{]}$
(26a) subject to
$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{F}\big{]}=0,\;\;\forall\bm{\rho}_{\mathrm{all}}\in{{{\cal{S}}}_{\mathrm{arb}}}$
(26b)

In this section, we will prove that in order to solve $\mathscr{P}$-1, it
suffices to consider the scenario with independent noise.

###  A1 Sufficiency of considering classically correlated noise

We first show that to solve $\mathscr{P}$-1, it is sufficient to consider a
problem with no entanglement among different qubit pairs. This problem is
given by $\mathscr{P}$-2.

######  $\mathscr{P}$\- 2 (Error minimization for separable states):

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{sp}}}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{]}$
(27a) subject to
$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{F}\big{]}=0,\;\;\forall\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{sp}}$
(27b)

where ${{\cal{S}}}_{\mathrm{sp}}$ denotes the set of states
$\bm{\rho}_{\mathrm{all}}$ that are separable among all qubit pairs.

We construct a probabilistic rotation operation as follows.

######  Definition A.1 (Probabilistic bilateral rotation):

def:T The operation ${\cal{T}}$ acts independently on each qubit pair. For
each pair, ${\cal{T}}$ rotates both qubits first along the $x$-axis for
$180^{\circ}$ with probability 0.5, then along the $y$-axis for $180^{\circ}$
with probability 0.5. The Kraus operators of the first and second
probabilistic rotations are

$\displaystyle\bm{T}_{x,1}$
$\displaystyle=\frac{\mathbb{I}_{4}}{\sqrt{2}},\quad\bm{T}_{x,2}=-\frac{\bm{\sigma}_{x}\otimes\bm{\sigma}_{x}}{\sqrt{2}},\quad\mbox{
and}$ (28a) $\displaystyle\bm{T}_{y,1}$
$\displaystyle=\frac{\mathbb{I}_{4}}{\sqrt{2}},\quad\bm{T}_{y,2}=-\frac{\bm{\sigma}_{y}\otimes\bm{\sigma}_{y}}{\sqrt{2}},$
(28b)

respectively.

The following lemma shows the equivalence of $\mathscr{P}$-1 and
$\mathscr{P}$-2.

######  Lemma A.1 (Equivalence of $\mathscr{P}$-1 and $\mathscr{P}$-2):

lem:sp2arb If a measurement operation ${\cal{O}}^{*}$ is optimal in
$\mathscr{P}$-2, the composite operation
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}$ is optimal in
$\mathscr{P}$-1.

###### Proof.

The four Bell states $\\{|\Phi^{\pm}\rangle,|\Psi^{\pm}\rangle\\}$ form a
basis for a qubit pair. Therefore, the state of each qubit pair
$n\in{\cal{N}}$ can be written as

$\displaystyle\bm{\rho}_{n}=\sum_{k\in{\cal{K}}_{n}}c_{k,n}|\phi_{k}\rangle\langle\psi_{k}|,$
(29)

where $|\phi_{k}\rangle,|\psi_{k}\rangle$ are Bell states, i.e.,
$|\Phi^{\pm}\rangle$, $|\Psi^{\pm}\rangle$, and ${\cal{K}}_{n}$ is the set of
all terms with non-zero coefficient $c_{k,n}\in\mathbb{C}$ . Given (29), the
fidelity of qubit pair $n$ is given by

$\displaystyle f_{n}=\sum_{k\in{\cal{K}}_{n}}$
$\displaystyle\Big{(}c_{k,n}\mathds{1}\big{(}|\phi_{k}\rangle=|\psi_{k}\rangle=|\Psi^{-}\rangle\big{)}\Big{)}$
(30)

where $\mathds{1}(\cdot)$ is the indicator function.

For a Bell state $|\phi\rangle\in\\{|\Phi^{\pm}\rangle$,
$|\Psi^{\pm}\rangle\\}$,

$\displaystyle\bm{\sigma}_{x}\otimes\bm{\sigma}_{x}|\phi\rangle$
$\displaystyle=\left\\{\begin{array}[]{rl}|\phi\rangle&\mbox{ if
}|\phi\rangle\in\\{|\Phi^{+}\rangle$, $|\Psi^{+}\rangle\\}\\\
-|\phi\rangle&\mbox{ if }|\phi\rangle\in\\{|\Phi^{-}\rangle$,
$|\Psi^{-}\rangle\\}\end{array}\right.$ (31c)
$\displaystyle\bm{\sigma}_{y}\otimes\bm{\sigma}_{y}|\phi\rangle$
$\displaystyle=\left\\{\begin{array}[]{rl}|\phi\rangle&\mbox{ if
}|\phi\rangle\in\\{|\Phi^{-}\rangle$, $|\Psi^{+}\rangle\\}\\\
-|\phi\rangle&\mbox{ if }|\phi\rangle\in\\{|\Phi^{+}\rangle$,
$|\Psi^{-}\rangle\\}\end{array}\right.$ (31f)

According to (28) and (31), for Bell states
$|\phi\rangle,|\psi\rangle\in\\{|\Phi^{\pm}\rangle$, $|\Psi^{\pm}\rangle\\}$,

$\displaystyle{\cal{T}}(|\phi\rangle\langle\psi|)$
$\displaystyle=\left\\{\begin{array}[]{ll}|\phi\rangle\langle\psi|&\mbox{ if
}|\phi\rangle=|\psi\rangle\\\ 0&\mbox{ if
}|\phi\rangle\neq|\psi\rangle\end{array}\right.$ (34)

By substituting (34) into (30), it is clear that the rotation ${\cal{T}}$ does
not change the fidelity of any qubit pair.

Consider a composite operation in which the rotation ${\cal{T}}$ is performed
on the sampled qubit pairs $n\in{\cal{M}}$ before the measurement ${\cal{O}}$.
Subsequently, this rotation is performed on the unsampled qubit pairs
$n\in{\cal{N}}\backslash{\cal{M}}$. According to the analysis described in the
previous paragraph, the rotation ${\cal{T}}$ on the unsampled qubit pairs does
not affect the measurement outcome $\bm{r}$ nor the average fidelity of the
unsampled qubit pairs $\bar{f}$. In this sense, the considered composite
operation is equivalent to the operation
$\hat{{\cal{O}}}={\cal{O}}\circ{\cal{T}}$, i.e., both the rotation and the
measurement are performed only on the sampled qubit pairs. Moreover, since the
rotation ${\cal{T}}$ on the unsampled qubit pairs is commutable with the
measurement ${\cal{O}}$, the operation $\hat{{\cal{O}}}$ is also equivalent to
an operation in which the rotation ${\cal{T}}$ is performed on all qubit pairs
before the measurement ${\cal{O}}$. Given the above two equivalences, when
analyzing the performance of operation $\hat{{\cal{O}}}$, we consider the
operation in which the rotation is performed on all qubit pairs before the
measurement.

An arbitrary state of all $N$ qubit pairs can be expressed in Bell basis as
follows.

$\displaystyle\bm{\rho}_{\mathrm{all}}=\sum_{k\in{\cal{K}}}c_{k}\otimes^{n\in{\cal{N}}}|\phi_{k,n}\rangle\langle\psi_{k,n}|,$
(35)

where $|\phi_{k,n}\rangle,|\psi_{k,n}\rangle$ are Bell states, i.e.,
$|\Phi^{\pm}\rangle$, $|\Psi^{\pm}\rangle$, and ${\cal{K}}$ is the set of all
terms with non-zero coefficient $c_{k}\in\mathbb{C}$. Substituting (34) into
(35), we find that after performing the rotation ${\cal{T}}$ on all qubit
pairs, their joint state is

$\displaystyle{\cal{T}}(\bm{\rho}_{\mathrm{all}})=\sum_{k\in{\cal{K}}}c_{k}\otimes^{n\in{\cal{N}}}\mathds{1}\big{(}|\phi_{k,n}\rangle=|\psi_{k,n}\rangle\big{)}|\phi_{k,n}\rangle\langle\psi_{k,n}|.$
(36)

Equation (36) shows that after performing ${\cal{T}}$ on all qubit pairs, the
state of all qubit pairs is a composition of product states and therefore
separable.

Define the function $e({\cal{S}},{\cal{O}},{\cal{D}})$ as the worst-case
squared estimation error for states in the set ${\cal{S}}$ by using the
measurement operator ${\cal{O}}$ and the estimator ${\cal{D}}$, i.e.

$\displaystyle
e({\cal{S}},{\cal{O}},{\cal{D}})=\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{|}{\cal{M}},{\cal{O}},{\cal{D}}\big{]}.$
(37)

The objective functions of $\mathscr{P}$-1 and $\mathscr{P}$-2 can be
rewritten as

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({{\cal{S}}}_{\mathrm{arb}},{\cal{O}},{\cal{D}}),\quad\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}}),$
(38)

respectively.

Denote ${\cal{D}}^{*}$ as the estimator used with the measurement operation
${\cal{O}}^{*}$ to achieve the minimum mean squared error. The following
inequalities involving the objective functions of $\mathscr{P}$-1 and
$\mathscr{P}$-2 can be derived:

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,$
$\displaystyle e({{\cal{S}}}_{\mathrm{arb}},{\cal{O}},{\cal{D}})$
$\displaystyle\leqslant$ $\displaystyle
e({{\cal{S}}}_{\mathrm{arb}},\hat{{\cal{O}}}^{*},{\cal{D}}^{*})$ (39a)
$\displaystyle\leqslant$ $\displaystyle
e({\cal{S}}_{\mathrm{sp}},{{\cal{O}}}^{*},{\cal{D}}^{*})$ (39b)
$\displaystyle=$
$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}}),$
(39c)

where (39b) holds because rotation ${\cal{T}}$ converts an arbitrary state to
a separable state, and (39c) holds because ${{\cal{O}}}^{*},{\cal{D}}^{*}$ is
the optimal solution to $\mathscr{P}$-2.

Moreover, because ${{\cal{S}}}_{\mathrm{arb}}\supset{\cal{S}}_{\mathrm{sp}}$,

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({{\cal{S}}}_{\mathrm{arb}},{\cal{O}},{\cal{D}})\geqslant\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}}).$
(40)

According to (39) and (40), one can get that

$\displaystyle\begin{split}\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({{\cal{S}}}_{\mathrm{arb}},{\cal{O}},{\cal{D}})&=e({{\cal{S}}}_{\mathrm{arb}},\hat{{\cal{O}}}^{*},{\cal{D}}^{*})\\\
&=\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}}).\end{split}$
(41)

The first equality in (41) shows that $\hat{{\cal{O}}}^{*}$ is optimal for
$\mathscr{P}$-1. This completes the proof of lem:sp2arb. ∎

###  A2 Sufficiency of considering independent noise

We next show that to solve $\mathscr{P}$-2, it is sufficient to consider a
problem in which there is no correlation between different qubit pairs. This
problem is given by $\mathscr{P}$-3.

######  $\mathscr{P}$\- 3 (Error minimization for independent states):

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}\,)^{2}\big{]}$
(42a) subject to
$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{f}\,\big{]}=0,\;\;\forall\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}$
(42b)

where ${{\cal{S}}}_{\mathrm{id}}$ denotes the set of states
$\bm{\rho}_{\mathrm{all}}$ in which the state $\bm{\rho}_{n}$ of every qubit
pair $n$, $n\in{\cal{N}}$, is independent, i.e., $\bm{\rho}_{\mathrm{all}}$
can be expressed as

$\displaystyle\bm{\rho}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\rho}_{n}.$
(43)

In the case of (43), the average fidelity of the unsampled pairs, $\bar{f}$,
is deterministic for each sample set ${\cal{M}}$. Thus, lowercase letter
$\bar{f}$ is used in (42).

The following lemma shows that if a measurement operation ${\cal{O}}^{*}$ is
optimal in scenarios with independent states, it is also optimal in scenarios
with classically correlated states.

######  Lemma A.2 (Equivalence of $\mathscr{P}$-2 and $\mathscr{P}$-3):

lem:id2sp If a measurement operation ${\cal{O}}^{*}$ is optimal in
$\mathscr{P}$-3, it is also optimal in $\mathscr{P}$-2.

###### Proof.

A separable state $\bm{\rho}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{sp}}$ can be
expressed as

$\displaystyle\bm{\rho}_{\mathrm{all}}=\sum_{k\in{\cal{K}}}p_{k}\otimes^{n\in{\cal{N}}}\bm{\rho}_{k,n},$
(44)

where $p_{k}$ is the probability of the ensemble in case $k$, with
$p_{k}\geqslant 0$, $\sum_{k\in{\cal{K}}}p_{k}=1$, and $\bm{\rho}_{k,n}$ is
the density matrix of qubit pair $n$ in case $k$. Denote

$\displaystyle\bm{\rho}^{(k)}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\rho}_{k,n},$
(45)

and denote the fidelity of $\bm{\rho}_{k,n}$ by $f_{k,n}$. Then
$\bm{\rho}^{(k)}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{id}}$, $\forall
k\in{\cal{K}}$.

Denote $\check{f}(r)$ as the estimated fidelity given the measurement outcome
$r$, and denote $\bar{f}(\bm{\rho}_{\mathrm{all}},{\cal{M}},r)$ as the average
fidelity of the unsampled qubit pairs given the state
$\bm{\rho}_{\mathrm{all}}$, sample set ${\cal{M}}$ and measurement outcome
$r$. Given (44), the following inequalities hold for every estimation protocol
$\\{{\cal{O}}$, ${\cal{D}}\\}$ and every state
$\bm{\rho}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{sp}}$.

$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F})^{2}\big{]}$
$\displaystyle=\sum_{{\cal{M}}}\sum_{r}\mathrm{Pr}(r|{\cal{M}})\big{(}\check{f}(r)-\bar{f}(\bm{\rho}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(46a)
$\displaystyle=\sum_{{\cal{M}}}\sum_{r}\mathrm{Pr}(r|{\cal{M}})\big{(}\check{f}(r)-$
$\displaystyle\hskip
36.98857pt\sum_{k}\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(46b)
$\displaystyle\leqslant\sum_{{\cal{M}}}\sum_{r}\sum_{k}\mathrm{Pr}(r|{\cal{M}})\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)$
$\displaystyle\hskip
81.09035pt\big{(}\check{f}(r)-\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(46c)
$\displaystyle=\sum_{k}p_{k}\sum_{{\cal{M}}}\sum_{r}\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}})$
$\displaystyle\hskip
81.09035pt\big{(}\check{f}(r)-\bar{f}(\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}},r)\big{)}^{2}$
(46d)
$\displaystyle=\sum_{k}p_{k}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f})^{2}\big{|}\bm{\rho}^{(k)}_{\mathrm{all}}\big{]},$
(46e)
$\displaystyle\leqslant\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f})^{2}\big{]},$
(46f)

where (46c) holds because $x^{2}$ is a convex function and

$\displaystyle\begin{split}\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)&\geqslant
0,\quad\forall k\in{\cal{K}},\\\
\sum_{k\in{\cal{K}}}\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)&=1,\end{split}$
(47)

(46d) holds because according to Bayes’ theorem

$\displaystyle\mathrm{Pr}(r|{\cal{M}})\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}},r)$
$\displaystyle=\mathrm{Pr}(\bm{\rho}^{(k)}_{\mathrm{all}}|{\cal{M}})\mathrm{Pr}(r|\bm{\rho}^{(k)}_{\mathrm{all}},{\cal{M}})$
$\displaystyle=p_{k}\mathrm{Pr}({\cal{M}},r|\bm{\rho}^{(k)}_{\mathrm{all}}),$
(48)

and (46f) holds because
$\bm{\rho}^{(k)}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{id}}$, $p_{k}\geqslant
0$, $\forall k\in{\cal{K}}$, and $\sum_{k}p_{k}=1$.

Recall the worst-case squared estimation error function
$e({\cal{S}},{\cal{O}},{\cal{D}})$ defined in (37), and denote ${\cal{D}}^{*}$
as the estimator used with the measurement operation ${\cal{O}}^{*}$ to
achieve the minimum mean squared error. In this case, the following
inequalities involving the objective functions of $\mathscr{P}$-2 and
$\mathscr{P}$-3 can be derived:

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,$
$\displaystyle e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}})$
$\displaystyle\leqslant$ $\displaystyle
e({\cal{S}}_{\mathrm{sp}},{{\cal{O}}}^{*},{\cal{D}}^{*})$ (49a)
$\displaystyle\leqslant$ $\displaystyle
e({\cal{S}}_{\mathrm{id}},{{\cal{O}}}^{*},{\cal{D}}^{*})$ (49b)
$\displaystyle=$
$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{id}},{\cal{O}},{\cal{D}}),$
(49c)

where (49b) is true because that (46) holds for every estimation protocol
$\\{{\cal{O}}$, ${\cal{D}}\\}$ and every state
$\bm{\rho}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{sp}}$, and (49c) holds because
$\\{{\cal{O}}^{*},{\cal{D}}^{*}\\}$ is the optimal solution to
$\mathscr{P}$-3.

Moreover, because ${\cal{S}}_{\mathrm{sp}}\supset{\cal{S}}_{\mathrm{id}}$,

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}})\geqslant\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{id}},{\cal{O}},{\cal{D}}).$
(50)

According to (49) and (50),

$\displaystyle\begin{split}\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{sp}},{\cal{O}},{\cal{D}})&=e({\cal{S}}_{\mathrm{sp}},{\cal{O}}^{*},{\cal{D}}^{*})\\\
&=\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{id}},{\cal{O}},{\cal{D}})\end{split}$
(51)

The first equality in (51) shows that ${{\cal{O}}}^{*}$ is optimal for
$\mathscr{P}$-2. This completes the proof of lem:id2sp. ∎

###  A3 Sufficiency of considering the sampled qubit pairs

In a third step, we show that in the case of independent noise, to minimize
the estimation error w.r.t. the average fidelity of the unsampled qubit pairs,
it is sufficient to minimize the corresponding value of the sampled qubit
pairs. To this end, transform $\mathscr{P}$-3 into $\mathscr{P}$-4.

######  $\mathscr{P}$\- 4 (Error minimization for sampled qubit pairs):

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\;\;$
$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}$
(52a) subject to
$\displaystyle\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{|}\bm{\rho}_{{\cal{M}}}\big{]}=0,$
$\displaystyle\qquad\forall\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),\;{\cal{M}}\subset{\cal{N}}$
(52b)

where $\bm{\rho}_{{\cal{M}}}$ is the state of all sampled qubit pairs, and
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})$ denotes the set of $N$
qubit pair states with independent noise and fidelity composition
$\bm{f}_{\mathrm{all}}=\\{f_{n},n\in{\cal{N}}\\}$, i.e.,

$\displaystyle\bm{\rho}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\rho}_{n},$
(53)

in which $\bm{\rho}_{n}$ is the state of the $n$-th qubit pair,

$\displaystyle f_{n}=\langle\Psi^{-}|\bm{\rho}_{n}|\Psi^{-}\rangle,\quad
n\in{\cal{N}},$ (54)

is the fidelity of the $n$-th qubit pair, and

$\displaystyle\bar{f}_{{\cal{M}}}=\frac{1}{M}\sum_{n\in{\cal{M}}}f_{n}$ (55)

is the average fidelity of the sampled qubit pairs.

The following lemma shows that a measurement operation ${\cal{O}}^{*}$ which
is optimal for $\mathscr{P}$-4 is also optimal for $\mathscr{P}$-3.

######  Lemma A.3 (Equivalence of $\mathscr{P}$-3 and $\mathscr{P}$-4):

lem:id-sample If a measurement operation ${\cal{O}}^{*}$ is optimal in
$\mathscr{P}$-4 for all compositions of fidelity, i.e.,
$\forall\,{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$,
it is also optimal in $\mathscr{P}$-3.

###### Proof.

Because the sample set ${\cal{M}}$ is drawn completely at random,

$\displaystyle\sum_{{\cal{M}}}\bar{f}-\bar{f}_{{\cal{M}}}=0,\quad\forall\bm{\rho}_{\mathrm{all}}\in{\cal{S}}_{\mathrm{id}}.$
(56)

According to (56), (42b) is equivalent to

$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{]}=0,\quad\forall\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}.$
(57)

(57) indicates that any estimation protocol $\\{{\cal{O}},{\cal{D}}\\}$ that
satisfies (52b) for all
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$
and ${\cal{M}}\subset{\cal{N}}$ also satisfies (42b). In the following, we
prove the converse statement by contradiction.

Suppose there is an estimation protocol $\\{{\cal{O}},{\cal{D}}\\}$ that
satisfies (57) but does not satisfy (52b). In this case, there must exist some
$\bm{\rho}_{{\cal{M}}}$ such that

$\displaystyle\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{|}\bm{\rho}_{{\cal{M}}}\big{]}\neq
0.$ (58)

Denote $m\in{\cal{M}}$ as one of the sampled qubit pairs, and denote $l$ as
the number of sampled qubit pairs whose state is the same as that of the
$m$-th pair, i.e.

$\displaystyle\sum_{n\in{\cal{M}}}\mathds{1}(\bm{\rho}_{n}=\bm{\rho}_{m})=l,$
(59)

and denote the state $\bm{\rho}_{{\cal{M}}}$ that satisfies (58) by
$\bm{\rho}^{(l)}$. Because $m\in{\cal{M}}$, it is clear that $l\geqslant 1$.

Subsequently, we consider the state

$\displaystyle\bm{\rho}_{\mathrm{all}}=\bm{\rho}^{(l)}\otimes(\otimes^{N-M}\bm{\rho}_{m}).$
(60)

With the state defined in (62), the sampled set ${\cal{M}}$ has at least $l$
number of qubit pairs in the state $\bm{\rho}_{m}$. When the number of sampled
qubit pairs in state $\bm{\rho}_{m}$ is equal to $l$, the joint state of the
sampled qubit pairs is equal to $\bm{\rho}^{(l)}$. Thus, according to (57) and
(58), there must exist a sample set $\tilde{{\cal{M}}}$ such that

$\displaystyle\begin{split}\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{\tilde{{\cal{M}}}}\big{|}\bm{\rho}_{\tilde{{\cal{M}}}}\big{]}&\neq
0,\quad{\mbox{and}}\\\
\sum_{n\in\tilde{{\cal{M}}}}\mathds{1}(\bm{\rho}_{n}=\bm{\rho}_{m})&=\tilde{l}\geqslant
l+1.\end{split}$ (61)

Denote the state $\bm{\rho}_{\tilde{{\cal{M}}}}$ by $\bm{\rho}^{(\tilde{l})}$.
Next, consider the state

$\displaystyle\bm{\rho}_{\mathrm{all}}=\bm{\rho}^{(\tilde{l})}\otimes(\otimes^{N-M}\bm{\rho}_{m})$
(62)

and repeat the analysis above. Because $\tilde{l}\geqslant l+1$, by repeating
this analysis for at most $M-l$ times, it can be obtained that state
$\bm{\rho}^{(M)}=\otimes^{M}\bm{\rho}_{m}$ does not satisfy the unbiased
constraint, i.e.,

$\displaystyle\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{\tilde{{\cal{M}}}}\big{|}\bm{\rho}^{(M)}\big{]}$
$\displaystyle\neq 0.$ (63)

However, according to (63), (57) does not hold for the state
$\bm{\rho}_{\mathrm{all}}=\otimes^{N}\bm{\rho}_{m}$. This contradiction shows
that any estimation protocol $\\{{\cal{O}},{\cal{D}}\\}$ that satisfies (42b)
also satisfies (52b).

Using the strengthened unbiased constraint (52b), the estimation error in
$\mathscr{P}$-3 can be decomposed as follows:

$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f})^{2}\big{]}$
$\displaystyle=\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}}+\bar{f}_{{\cal{M}}}-\bar{f})^{2}\big{]}$
(64a)
$\displaystyle=\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}+2\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})(\bar{f}_{{\cal{M}}}-\bar{f})\big{]}$
$\displaystyle\hskip
11.38109pt+\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\bar{f}_{{\cal{M}}}-\bar{f})^{2}\big{]}$
(64b)
$\displaystyle=\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}+2\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{|}\bm{\rho}_{{\cal{M}}}\big{]}(\bar{f}_{{\cal{M}}}-\bar{f})$
$\displaystyle\hskip
11.38109pt+\sum_{{\cal{M}}}(\bar{f}_{{\cal{M}}}-\bar{f})^{2}$ (64c)
$\displaystyle=\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}+\sum_{{\cal{M}}}(\bar{f}_{{\cal{M}}}-\bar{f})^{2},$
(64d)

where (64c) holds because in cases with independent noise, the average
fidelity of sampled qubit pairs, $\bar{f}_{{\cal{M}}}$, and that of unsampled
qubit pairs, $\bar{f}$, are deterministic given each sample set ${\cal{M}}$;
(64d) is true due to (52b).

(64) decomposes the estimation error into two parts, i.e., the estimation
error w.r.t. the average fidelity of the sampled qubit pairs

$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]},$
(65)

and the deviation between the average fidelity of sampled and unsampled qubit
pairs

$\displaystyle\sum_{{\cal{M}}}(\bar{f}_{{\cal{M}}}-\bar{f})^{2}.$ (66)

The value of (66) is determined by the fidelity composition of all qubit
pairs, i.e.,

$\displaystyle\bm{f}_{\mathrm{all}}=\\{f_{n},n\in{\cal{N}}\\},$ (67)

and not affected by the estimation protocol $\\{{\cal{O}}$, ${\cal{D}}\\}$.
Therefore, for every fidelity composition $\bm{f}_{\mathrm{all}}$, minimizing
the estimation error

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f})^{2}\big{]}$
(68)

is equivalent to

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}.$
(69)

Hence, if a protocol $\\{{\cal{O}}^{*}$, ${\cal{D}}^{*}\\}$ is optimal in
$\mathscr{P}$-4 for all
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$,
it is also the optimal solution to (68) for all
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$.
Furthermore, because

$\displaystyle{{\cal{S}}}_{\mathrm{id}}=\bigcup_{\bm{f}_{\mathrm{all}}}{{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),$
(70)

protocol $\\{{\cal{O}}^{*}$, ${\cal{D}}^{*}\\}$ minimizes

$\displaystyle\max_{\bm{\rho}_{\mathrm{all}}\in{{\cal{S}}}_{\mathrm{id}}}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}\,)^{2}\big{]}.$
(71)

Therefore, $\\{{\cal{O}}^{*}$, ${\cal{D}}^{*}\\}$ is also an optimal solution
to $\mathscr{P}$-3. This completes the proof of lem:id-sample. ∎

The following theorem summarizes the results of this section.

######  Theorem A.1 (Generality of optimality with independent noise):

thm:gen-opt-id If a measurement operation ${\cal{O}}^{*}$ is optimal in
$\mathscr{P}$-4 for all
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$,
then a composite measurement operation
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}$ is optimal in
$\mathscr{P}$-1, where the operation ${\cal{T}}$ is defined as in def:T.

###### Proof.

The theorem is a direct consequence of Lemmas LABEL:lem:sp2arb,
LABEL:lem:id2sp, and LABEL:lem:id-sample. ∎

##  Appendix B Operation Construction

In this section, we will first derive a lower bound of the estimation error,
then based on the conditions for achieveing this lower bound, construct an
optimal fidelity estimation protocol.

###  B1 Lower bound of the estimation error

We will first further simplify $\mathscr{P}$-4. (lem:id-w), then characterize
the limit of separable operators (lem:sep-ent) and finally determine the
lowest feasible bound of the estimation error (thm:min).

The state of a qubit pair $\bm{\rho}_{n}\in{\cal{H}}^{4\times 4}$ has several
parameters other than fidelity. This property complicates the Fisher
information analysis of $\mathscr{P}$-4. To overcome this challenge, we
further simplify $\mathscr{P}$-4 to an equivalent one, $\mathscr{P}$-5, in
which the fidelity composition $\bm{f}_{\mathrm{all}}$ is sufficient to
parameterize the state of the qubit pairs.

######  $\mathscr{P}$\- 5 (Error minimization for Werner states):

Given that $\bm{\rho}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\sigma}_{n}$,

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\quad$
$\displaystyle\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}$
(72) subject to
$\displaystyle\mathbb{E}_{R}\big{[}\check{F}-\bar{f}_{{\cal{M}}}\big{|}{\cal{M}}\big{]}=0,\;\forall{\cal{M}}\subset{\cal{N}},$
(73)

where $\bm{\sigma}_{n}$ is the Werner state with fidelity $f_{n}$, i.e.,

$\displaystyle\bm{\sigma}_{n}=f_{n}|\Psi^{-}\rangle\langle\Psi^{-}|+\frac{1-f_{n}}{3}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|).$
(74)

######  Lemma B.1 (Equivalence of $\mathscr{P}$-4 and $\mathscr{P}$-5):

lem:id-w With the optimal estimation protocol $\\{{\cal{O}},{\cal{D}}\\}$, the
objective functions of $\mathscr{P}$-4 and $\mathscr{P}$-5 have the same
value.

###### Proof.

Recall the function of the worst-case squared estimation error
$e({\cal{S}},{\cal{O}},{\cal{D}})$ defined in (37), and denote
${\cal{S}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}})=\\{\otimes^{n\in{\cal{N}}}\bm{\sigma}_{n}\\}$.
The objective functions of $\mathscr{P}$-4 and $\mathscr{P}$-5 can be
rewritten as

$\displaystyle\begin{split}&\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}}),\mbox{
and }\\\
&\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}}),\end{split}$
(75)

respectively.

Denote $\\{{\cal{O}}^{*},{\cal{D}}^{*}\\}$ as the optimal solution to
$\mathscr{P}$-5, and denote the random bilateral rotation operation proposed
in [34] by ${\cal{B}}$. Define the composition operation
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ(\otimes^{M}{\cal{B}})$. In this case,
we have that

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,$
$\displaystyle
e({{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}})$
$\displaystyle\leqslant$ $\displaystyle
e({{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),\hat{{\cal{O}}}^{*},{\cal{D}}^{*})$
(76a) $\displaystyle\leqslant$ $\displaystyle
e({{\cal{S}}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}}),{{\cal{O}}}^{*},{\cal{D}}^{*})$
(76b) $\displaystyle=$
$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{{\cal{S}}}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}}),$
(76c)

where (76b) holds because the operation ${\cal{B}}$ transforms a general qubit
pair state $\bm{\rho}_{n}$ to a Werner state $\bm{\sigma}_{n}$ with the same
fidelity, and (76c) holds because $\\{{\cal{O}}^{*},{\cal{D}}^{*}\\}$ is the
optimal solution to $\mathscr{P}$-2.

Moreover, because
${\cal{S}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}})\subset{\cal{S}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})$,

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}})\leqslant\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}}).$
(77)

From (76) and (77),

$\displaystyle\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{w}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}})=\underset{{\cal{O}},{\cal{D}}}{\mathrm{minimize}}\,e({\cal{S}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}}),{\cal{O}},{\cal{D}}),$
(78)

which proves lem:id-w. ∎

The next lemma characterizes the limit of separable operators when measuring
maximally entangled qubit pairs.

######  Lemma B.2 (Limit of separable operators):

lem:sep-ent $|\Phi\rangle$ is a maximally entangled state of a qubit pair.
$\bm{M}=\bm{M}^{\mathrm{(A)}}\otimes\bm{M}^{\mathrm{(B)}}$ is a separable
operator, where $\bm{M}^{\mathrm{(X)}}\succcurlyeq\bm{0}$,
$\mathrm{X}\in\\{\mathrm{A,B}\\}$. In this case,

$\displaystyle
0\leqslant\frac{\mathrm{Tr}\big{(}|\Phi\rangle\langle\Phi|\bm{M}^{\mathrm{(AB)}}\big{)}}{\mathrm{Tr}\big{(}(\mathbb{I}_{4}-|\Phi\rangle\langle\Phi|)\bm{M}^{\mathrm{(AB)}}\big{)}}\leqslant
1.$ (79)

###### Proof.

We define

$\displaystyle\bm{\rho}=\frac{\bm{M}^{\mathrm{(AB)}}}{\mathrm{Tr}\big{(}\bm{M}^{\mathrm{(AB)}}\big{)}}.$
(80)

Since $\bm{M}^{\mathrm{(X)}}\succcurlyeq\bm{0}$,
$\mathrm{X}\in\\{\mathrm{A,B}\\}$, $\bm{\rho}$ is the density matrix of a
separable state of a qubit pair. For this state, its fidelity w.r.t. every
maximally entangled state lies in the interval $[0,\frac{1}{2}]$ [36, 37],
i.e.,

$\displaystyle\mathrm{Tr}(|\Phi\rangle\langle\Phi|\bm{\rho})\in[0,\frac{1}{2}].$
(81)

Consequently,

$\displaystyle\frac{\mathrm{Tr}(|\Phi\rangle\langle\Phi|\bm{\rho})}{\mathrm{Tr}\big{(}(\mathbb{I}_{4}-|\Phi\rangle\langle\Phi|)\bm{\rho}\big{)}}=\frac{\mathrm{Tr}(|\Phi\rangle\langle\Phi|\bm{\rho})}{1-\mathrm{Tr}(|\Phi\rangle\langle\Phi|\bm{\rho})}\in[0,1].$
(82)

According to (80) and (82), (79) is obtained. This completes the proof of
lem:sep-ent. ∎

######  Remark 3 (The role of inequality (79)):

To measure the fidelity w.r.t. a state $|\Phi\rangle\langle\Phi|$, it is most
efficient to use $|\Phi\rangle\langle\Phi|$ and
$\mathbb{I}_{4}-|\Phi\rangle\langle\Phi|$ as measurement operators to ensure
that the distribution of the measurement outcome is maximally sensitive to the
changes in fidelity.

Since the target state $|\Psi^{-}\rangle$ is entangled, separable operations
cannot realize the measurement operators mentioned above. To increase their
efficiency, separable measurement operators should be designed to best mimic
the ideal operator $|\Psi^{-}\rangle\langle\Psi^{-}|$. The inequality (79)
characterizes the best alignment between separable operators and the target
state. Consequently, (79) is the critical constraint that upper bounds the
efficiency of separable operators in fidelity estimation. $\square$

Based on the above results, the following lemma characterizes a lower bound
for the estimation error in $\mathscr{P}$-4.

######  Lemma B.3 (Lower bound for the estimation error):

thm:min The mean squared estimation error, i.e., the objective function of
$\mathscr{P}$-4 divided by $N\choose M$, is no less than

$\displaystyle\sum_{n\in{\cal{N}}}\frac{(2f_{n}+1)(1-f_{n})}{2MN}.$ (83)

###### Proof.

According to lem:id-w, the minimum value of the objective function of
$\mathscr{P}$-4 is equal to that of $\mathscr{P}$-5. Therefore, the following
analysis lower bounds the objective function of $\mathscr{P}$-5.

In $\mathscr{P}$-5,
$\bm{\rho}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\sigma}_{n}$, i.e., the
qubit pairs are in independent Werner states. In this case, for each sampled
set ${\cal{M}}$, the fidelity composition of the sampled qubit pairs,

$\displaystyle\bm{f}_{{\cal{M}}}=\\{f_{n},n\in{\cal{M}}\\},$ (84)

is the unknown fixed parameter that determines the distribution of the
measurement outcome $R$. According to the unbiased constraint (52b) and the
fact that $F_{{\cal{M}}}=\frac{1}{M}\sum_{n\in{\cal{M}}}f_{n}$,

$\displaystyle\frac{\partial\mathbb{E}_{R}\big{[}\check{F}\big{]}}{\partial\bm{f}_{{\cal{M}}}}=\frac{\bm{1}_{M}}{M},$
(85)

where $\bm{1}_{M}$ denotes the $1\times M$ all-ones vector. In this case,
according to the Cramér-Rao bound [30, 31],

$\displaystyle\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}\geqslant\frac{\partial\mathbb{E}_{R}\big{[}\check{F}\big{]}}{\partial\bm{f}_{{\cal{M}}}}\big{(}{\bm{I}}_{R}(\bm{f}_{{\cal{M}}})\big{)}^{-1}\bigg{(}\frac{\partial\mathbb{E}_{R}\big{[}\check{F}\big{]}}{\partial\bm{f}_{{\cal{M}}}}\bigg{)}^{T},$
(86)

where ${\bm{I}}_{R}(\bm{f}_{{\cal{M}}})$ is the $M\times M$ Fisher information
matrix of the measurement outcome $R$ evaluated at point $\bm{f}_{{\cal{M}}}$.
The elements of ${\bm{I}}_{R}(\bm{f}_{{\cal{M}}})$ are specified as

$\displaystyle
I_{n,m}(\bm{f}_{{\cal{M}}})=\mathbb{E}_{R}\bigg{[}\frac{\partial}{\partial
f_{n}}\log{{\cal{P}}}(R;\bm{f}_{{\cal{M}}})\Big{(}\frac{\partial}{\partial
f_{m}}\log{{\cal{P}}}(R;\bm{f}_{{\cal{M}}})\Big{)}^{T}\bigg{]},$ (87)

where $n,m\in{\cal{M}}$, and ${{\cal{P}}}(r;\bm{f}_{{\cal{M}}})$ is the
distribution of measurement outcome $r$ given the fidelity composition
$\bm{f}_{{\cal{M}}}$.

According to [38, Prop. 1], the reciprocal of the diagonal elements of a
Fisher information matrix lower bounds the inverse of that matrix, i.e.

$\displaystyle\big{(}{\bm{I}}_{R}(\bm{f}_{{\cal{M}}})\big{)}^{-1}\succcurlyeq\mathrm{diag}\big{(}I^{-1}_{n,n}(\bm{f}_{{\cal{M}}}),n\in{\cal{M}}\big{)},$
(88)

where $\succcurlyeq$ denotes the matrix inequality, and $\mathrm{diag}(\cdot)$
denotes the diagonal matrix. Substituting (85) and (88) into (86), we get

$\displaystyle\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}\geqslant\sum_{n\in{\cal{M}}}\frac{I^{-1}_{n,n}(\bm{f}_{{\cal{M}}})}{M^{2}}.$
(89)

Given that the state of qubit pairs
$\bm{\rho}_{\mathrm{all}}=\otimes^{n\in{\cal{N}}}\bm{\sigma}_{n}$, and
measurement operator

$\displaystyle\bm{M}_{r}=\sum_{k}\otimes^{n\in{\cal{M}}}(\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}),$
(90)

the distribution of the measurement outcome can be expressed as the following.

$\displaystyle{{\cal{P}}}(r;\bm{f}_{{\cal{M}}})$
$\displaystyle=\mathrm{Tr}\big{(}\otimes^{n\in{\cal{M}}}\bm{\sigma}_{n}\bm{M}_{r}\big{)}$
$\displaystyle=\sum_{k}\mathrm{Tr}\big{(}\otimes^{n\in{\cal{M}}}(\bm{\sigma}_{n}\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k})\big{)}$
$\displaystyle=\sum_{k}\prod_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\sigma}_{n}\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}.$
(91)

To characterize the effect of fidelity $f_{n}$ on the distribution of the
measurement outcome, define

$\displaystyle\begin{split}a_{r,n}&=\sum_{k}\mathrm{Tr}\big{(}|\Psi^{-}\rangle\langle\Psi^{-}|\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}\\\
&\hskip
0.99585pt\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}\big{(}\bm{\sigma}_{m}\bm{M}^{\mathrm{(A)}}_{r,m,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,m,k}\big{)},\\\
b_{r,n}&=\sum_{k}\mathrm{Tr}\big{(}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|)\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}\\\
&\hskip
0.99585pt\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}\big{(}\bm{\sigma}_{m}\bm{M}^{\mathrm{(A)}}_{r,m,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,m,k}\big{)}.\end{split}$
(92)

It is evident that the value of $f_{n}$ has no effect on $a_{r,n}$ and
$b_{r,n}$, i.e.

$\displaystyle\frac{\partial a_{r,n}}{\partial f_{n}}=\frac{\partial
b_{r,n}}{\partial f_{n}}=0,\;\forall r,n.$ (93)

According to (74) and (91), the distribution of the measurement outcome can be
rewritten as

$\displaystyle{\cal{P}}(r|\bm{f}_{{\cal{M}}})$
$\displaystyle=f_{n}\sum_{k}\mathrm{Tr}\big{(}|\Psi^{-}\rangle\langle\Psi^{-}|\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}$
$\displaystyle\hskip
11.38109pt\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}\big{(}\bm{\sigma}_{m}\bm{M}^{\mathrm{(A)}}_{r,m,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,m,k}\big{)}$
$\displaystyle\hskip
11.38109pt+\frac{1-f_{n}}{3}\sum_{k}\mathrm{Tr}\big{(}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|)\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}$
$\displaystyle\hskip
11.38109pt\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}\big{(}\bm{\sigma}_{m}\bm{M}^{\mathrm{(A)}}_{r,m,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,m,k}\big{)}$
$\displaystyle=f_{n}a_{r,n}+\frac{1-f_{n}}{3}b_{r,n}.$ (94)

According to (87), (93), and (94),

$\displaystyle I_{n,n}(\bm{f}_{{\cal{M}}})$
$\displaystyle=\sum_{r}{\cal{P}}(r|f_{n})\Big{(}\frac{\partial}{\partial
f_{n}}\log{{\cal{P}}}(r|f_{n})\Big{)}^{2}$
$\displaystyle=\sum_{r}\frac{\big{(}a_{r,n}-\frac{1}{3}b_{r,n}\big{)}^{2}}{f_{n}a_{r,n}+\frac{1-f_{n}}{3}b_{r,n}}.$
(95)

According to the property of POVM, i.e.
$\sum_{r}\bm{M}_{r}=\mathbb{I}_{4^{M}}$, it can be obtained that

$\displaystyle\sum_{r}a_{r,n}$
$\displaystyle=\mathrm{Tr}\Big{(}|\Psi^{-}\rangle\langle\Psi^{-}|\otimes\big{(}\otimes^{m\in{\cal{M}}\backslash\\{n\\}}\bm{\sigma}_{m}\big{)}\sum_{r}\bm{M}_{r}\Big{)}$
$\displaystyle=\mathrm{Tr}\Big{(}|\Psi^{-}\rangle\langle\Psi^{-}|\otimes\big{(}\otimes^{m\in{\cal{M}}\backslash\\{n\\}}\bm{\sigma}_{m}\big{)}\Big{)}$
$\displaystyle=\mathrm{Tr}(|\Psi^{-}\rangle\langle\Psi^{-}|)\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}(\bm{\sigma}_{m})$
$\displaystyle=1.$ (96)

Similarly,

$\displaystyle\sum_{r}b_{r,n}$
$\displaystyle=\mathrm{Tr}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|)\prod_{m\in{\cal{M}}\backslash\\{n\\}}\mathrm{Tr}(\bm{\sigma}_{m})$
$\displaystyle=3.$ (97)

Applying lem:sep-ent, we get

$\displaystyle 0$
$\displaystyle\leqslant\mathrm{Tr}\big{(}|\Psi^{-}\rangle\langle\Psi^{-}|\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)}$
$\displaystyle\leqslant\mathrm{Tr}\big{(}(\mathbb{I}_{4}-|\Psi^{-}\rangle\langle\Psi^{-}|)\bm{M}^{\mathrm{(A)}}_{r,n,k}\otimes\bm{M}^{\mathrm{(B)}}_{r,n,k}\big{)},\;\forall
r,n,k$ (98)

Substituting (98) into (92), one obtains that

$\displaystyle 0\leqslant a_{r,n}\leqslant b_{r,n},\quad\forall r,n.$ (99)

Define

$\displaystyle
I_{r,n}(a_{r,n},{b}_{r,n})=\frac{\big{(}a_{r,n}-\frac{1}{3}{b}_{r,n}\big{)}^{2}}{f_{n}a_{r,n}+\frac{1-f_{n}}{3}{b}_{r,n}},$
(100)

then because

$\displaystyle\frac{\partial^{2}I_{r,n}}{\partial^{2}a_{r,n}}=\frac{6{b}^{2}_{r,n}}{\big{(}(1-f_{n})b_{r,n}+3f_{n}a_{r,n}\big{)}^{3}}\geqslant
0,$ (101)

the function $I_{r,n}$ is convex w.r.t. $a_{r,n}$. Therefore, according to
(99),

$\displaystyle I_{r,n}(a_{r,n},b_{r,n})$
$\displaystyle\quad\leqslant\frac{b_{r,n}-a_{r,n}}{b_{r,n}}I_{r,n}(0,b_{r,n})+\frac{a_{r,n}}{b_{r,n}}I_{r,n}(b_{r,n},b_{r,n})$
$\displaystyle\quad=\frac{1}{3(1-f_{n})}(b_{r,n}-a_{r,n})+\frac{4}{3(2f_{n}+1)}a_{r,n}.$
(102)

Substituting (96), (97), and (102) into (95), we obtain that

$\displaystyle I_{n,n}(\bm{f}_{{\cal{M}}})$
$\displaystyle=\sum_{r}I_{r,n}(a_{r,n},b_{r,n})$
$\displaystyle\leqslant\frac{1}{3(1-f_{n})}\sum_{r}(b_{r,n}-b_{r,n})+\frac{4}{3(2f_{n}+1)}\sum_{r}b_{r,n}$
$\displaystyle=\frac{2}{3(1-f_{n})}+\frac{4}{3(2f_{n}+1)}$
$\displaystyle=\frac{2}{(2f_{n}+1)(1-f_{n})}.$ (103)

Substituting (103) into (89), the mean squared estimation error is lower
bounded as below.

$\displaystyle{N\choose
M}^{-1}\sum_{{\cal{M}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{f}_{{\cal{M}}})^{2}\big{]}$
$\displaystyle\geqslant{N\choose
M}^{-1}\sum_{{\cal{M}}}\sum_{n\in{\cal{M}}}\frac{I_{n,n}^{-1}(\bm{f}_{{\cal{M}}})}{M^{2}}$
$\displaystyle\geqslant{N\choose M}^{-1}\sum_{n\in{\cal{N}}}{N-1\choose
M-1}\frac{(2f_{n}+1)(1-f_{n})}{2M^{2}}$
$\displaystyle=\sum_{n\in{\cal{N}}}\frac{(2f_{n}+1)(1-f_{n})}{2MN}.$ (104)

With (104), (83) is obtained, which completes the proof of thm:min. ∎

###  B2 Achieving the minimum estimation error

This subsection describes the measurement operation used to achieve the
minimum estimation error.

According to the proof of thm:min, a necessary condition for achieving the
minimum estimation error is that the inequality in (102) is balanced. To this
end, the projection of a measurement operator onto the target state, i.e.,
$a_{r,n}$ defined in (92), must balance either of the two inequalities in
(99). The estimation protocol is built according to this principle.
Specifically, we consider bilateral local Pauli measurements in the same
basis. When both nodes make measurements in the $u$-basis, $u\in\\{x,y,z\\}$,
the operators corresponding to the asymmetric and symmetric measurement
results, $\bm{M}_{u,0}$ and $\bm{M}_{u,1}$, are respectively given by

$\displaystyle\bm{M}_{x,0}$
$\displaystyle=\left|+-\right>\\!\left<+-\right|+\left|-+\right>\\!\left<-+\right|$
$\displaystyle=|\Psi^{-}\rangle\langle\Psi^{-}|+|\Phi^{-}\rangle\langle\Phi^{-}|,$
(105a) $\displaystyle\bm{M}_{x,1}$
$\displaystyle=\left|++\right>\\!\left<++\right|+\left|--\right>\\!\left<\--\right|$
$\displaystyle=|\Psi^{+}\rangle\langle\Psi^{+}|+|\Phi^{+}\rangle\langle\Phi^{+}|,$
(105b) $\displaystyle\bm{M}_{y,0}$
$\displaystyle=\left|\times\odot\right>\\!\left<\times\odot\right|+\left|\odot\times\right>\\!\left<\odot\times\right|$
$\displaystyle=|\Psi^{-}\rangle\langle\Psi^{-}|+|\Phi^{+}\rangle\langle\Phi^{+}|,$
(105c) $\displaystyle\bm{M}_{y,1}$
$\displaystyle=\left|\times\times\right>\\!\left<\times\times\right|+\left|\odot\odot\right>\\!\left<\odot\odot\right|$
$\displaystyle=|\Psi^{+}\rangle\langle\Psi^{+}|+|\Phi^{-}\rangle\langle\Phi^{-}|,$
(105d) $\displaystyle\bm{M}_{z,0}$
$\displaystyle=\left|01\right>\\!\left<01\right|+\left|10\right>\\!\left<10\right|$
$\displaystyle=|\Psi^{-}\rangle\langle\Psi^{-}|+|\Psi^{+}\rangle\langle\Psi^{+}|,$
(105e) $\displaystyle\bm{M}_{z,1}$
$\displaystyle=\left|00\right>\\!\left<00\right|+\left|11\right>\\!\left<11\right|$
$\displaystyle=|\Phi^{-}\rangle\langle\Phi^{-}|+|\Phi^{+}\rangle\langle\Phi^{+}|,$
(105f)

where $\left|+\right>=\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}$,
$\left|-\right>=\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}$,
$\left|\times\right>=\frac{\left|0\right>+i\left|1\right>}{\sqrt{2}}$, and
$\left|\odot\right>=\frac{\left|0\right>-i\left|1\right>}{\sqrt{2}}$.

In (105), the operators $\bm{M}_{u,0}$, $u\in\\{x,y,z\\}$ balance the second
inequality in (99), and the operators $\bm{M}_{u,1}$, $u\in\\{x,y,z\\}$
balance the first inequality in (99). The following two lemma confirms the
optimality of the proposed measurement operator.

######  Lemma B.4 (Unbiased estimator):

lem:unbia Given the measurements made in Protocol 1, the following estimated
fidelity

$\displaystyle\check{f}=1-\frac{3\varepsilon_{{\cal{M}}}}{2}$ (106)

satisfies (52b), where the QBER $\varepsilon_{{\cal{M}}}$ is expressed as

$\displaystyle\varepsilon_{{\cal{M}}}=\frac{\sum_{n\in{\cal{M}}}r_{n}}{M},$
(107)

in which $r_{n}$ is the measurement result of qubit $n$.

###### Proof.

We define the following four terms:

$\displaystyle\begin{split}f^{(0)}=\frac{1}{M}\sum_{n\in{\cal{M}}}\mathrm{Tr}(\bm{\rho}_{n}|\Psi^{-}\rangle\langle\Psi^{-}|),\\\
f^{(1)}=\frac{1}{M}\sum_{n\in{\cal{M}}}\mathrm{Tr}(\bm{\rho}_{n}|\Psi^{+}\rangle\langle\Psi^{+}|),\\\
f^{(2)}=\frac{1}{M}\sum_{n\in{\cal{M}}}\mathrm{Tr}(\bm{\rho}_{n}|\Phi^{-}\rangle\langle\Phi^{-}|),\\\
f^{(3)}=\frac{1}{M}\sum_{n\in{\cal{M}}}\mathrm{Tr}(\bm{\rho}_{n}|\Phi^{+}\rangle\langle\Phi^{+}|).\end{split}$
(108)

In this case, $\bar{f}_{{\cal{M}}}=f^{(0)}$. Moreover, as the Bell states form
a basis of $\mathbb{C}^{4}$,

$\displaystyle\sum_{i=0}^{3}f^{(i)}=\frac{1}{M}\sum_{n\in{\cal{M}}}\mathrm{Tr}(\bm{\rho}_{n})=1.$
(109)

Given the distribution of $A_{n}$, i.e., $\Pr[A_{n}=u]=\frac{1}{3}$,
$u\in\\{x,y,z\\}$, and the expression of the measurement operators (105), the
following expression can be obtained:

$\displaystyle\mathbb{E}\bigg{[}\frac{\sum_{n\in{\cal{M}}}R_{n}\mathds{1}(A_{n}=x)}{M}\bigg{|}\bar{f}_{{\cal{M}}}\bigg{]}$
$\displaystyle=\frac{1}{M}\sum_{n\in{\cal{M}}}\Pr[A_{n}=x]\mathbb{E}\big{[}R_{n}\big{|}A_{n}=x,\bar{f}_{{\cal{M}}}\,\big{]}$
$\displaystyle=\frac{1}{3M}\sum_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\rho}_{n}(\mathbb{I}_{4}-\bm{M}_{x,0})\big{)}$
$\displaystyle=\frac{1}{3M}\bigg{(}\sum_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\rho}_{n}|\Psi^{+}\rangle\langle\Psi^{+}|\big{)}+\sum_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\rho}_{n}|\Phi^{+}\rangle\langle\Phi^{+}|\big{)}\bigg{)}$
$\displaystyle=\frac{f^{(1)}+f^{(3)}}{3}.$ (110)

Similar to (110), one can obtain that

$\displaystyle\mathbb{E}\bigg{[}\frac{\sum_{n\in{\cal{M}}}R_{n}\mathds{1}(A_{n}=y)}{M}\bigg{|}\bar{f}_{{\cal{M}}}\bigg{]}$
$\displaystyle=\frac{1}{3M}\sum_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\rho}_{n}(\mathbb{I}_{4}-\bm{M}_{y,0})\big{)}$
$\displaystyle=\frac{f^{(1)}+f^{(2)}}{3},$ (111)
$\displaystyle\mathbb{E}\bigg{[}\frac{\sum_{n\in{\cal{M}}}R_{n}\mathds{1}(A_{n}=z)}{M}\bigg{|}\bar{f}_{{\cal{M}}}\bigg{]}$
$\displaystyle=\frac{1}{3M}\sum_{n\in{\cal{M}}}\mathrm{Tr}\big{(}\bm{\rho}_{n}(\mathbb{I}_{4}-\bm{M}_{z,0})\big{)}$
$\displaystyle=\frac{f^{(2)}+f^{(3)}}{3}.$ (112)

Substituting (109)–(112) into (106), yields

$\displaystyle\mathbb{E}\big{[}\check{F}\big{|}\bar{f}_{{\cal{M}}}\,\big{]}$
$\displaystyle=1-\frac{3}{2}\mathbb{E}\big{[}{\cal{E}}_{{\cal{M}}}\big{|}\bar{f}_{{\cal{M}}}\big{]}$
$\displaystyle=1-\frac{3}{2}\mathbb{E}\bigg{[}\frac{\sum_{a\in\\{x,y,z\\}}\sum_{n\in{\cal{M}}}R_{n}\mathds{1}\\{A_{n}=a\\}}{M}\bigg{|}\bar{f}_{{\cal{M}}}\bigg{]}$
$\displaystyle=1-\frac{3}{2}\bigg{(}\sum_{i=1}^{3}\frac{2f^{(i)}}{3}\bigg{)}$
$\displaystyle=f^{(0)}=\bar{f}_{{\cal{M}}},$ (113)

where $\check{F}$ and ${{\cal{E}}}_{{\cal{M}}}$ are the random variable form
of $\check{f}$ and $\varepsilon_{{\cal{M}}}$, respectively. (113) shows that
the estimator given in (106) satisfies (52b). This completes the proof of
lem:unbia. ∎

Next, lem:opt-id proves the optimality of the proposed measurement operation
in scenarios with independent noise.

######  Lemma B.5 (Optimality with independent noise):

lem:opt-id Protocol 1 achieves the minimum estimation error in
$\mathscr{P}$-4.

###### Proof.

By repeating the derivation from (110) to (113) for qubit pair $n$, the
following expression can be obtained

$\displaystyle\mathrm{Pr}(R_{n}=1)=\frac{2}{3}(1-f_{n}).$ (114)

Hence, the variance of $R_{n}$ is given by

$\displaystyle\mathbb{V}\big{[}R_{n}\big{]}$
$\displaystyle=\mathrm{Pr}(R_{n}=1)(1-\mathrm{Pr}(R_{n}=1))$
$\displaystyle=\frac{(2f_{n}+1)(2-2f_{n})}{9}$ (115)

In the case of independent noise, the measurement outcomes $R_{n}$,
$n\in{\cal{M}}$ on different qubit pairs are independent. Therefore, according
to (106) and (107)

$\displaystyle\mathbb{V}\big{[}\check{F}\big{|}{\cal{M}}\big{]}$
$\displaystyle=\frac{9}{4M^{2}}\sum_{n\in{\cal{M}}}\mathbb{V}\big{[}R_{n}\big{]}$
$\displaystyle=\sum_{n\in{\cal{M}}}\frac{(2f_{n}+1)(1-f_{n})}{2M^{2}}.$ (116)

According to Lemma LABEL:lem:unbia, $\check{F}$ satisfies (52b), hence

$\displaystyle\mathbb{E}_{R}\big{[}(\check{F}-\bar{F}_{{\cal{M}}})^{2}\big{|}{\cal{M}}\big{]}=\mathbb{V}\big{[}\check{F}\big{|}{\cal{M}}\big{]}.$
(117)

As the sample set ${\cal{M}}$ is selected completely at random, (116) and
(117) indicate that for all
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$,

$\displaystyle{N\choose
M}^{-1}\sum_{{\cal{M}}\subset{\cal{N}}}\mathbb{E}_{R}\big{[}(\check{F}-\bar{F}_{{\cal{M}}})^{2}\big{]}$
$\displaystyle={N\choose
M}^{-1}\sum_{{\cal{M}}\subset{\cal{N}}}\sum_{n\in{\cal{M}}}\frac{(2f_{n}+1)(1-f_{n})}{2M^{2}}$
$\displaystyle={N\choose M}^{-1}\sum_{n\in{\cal{N}}}{N-1\choose
M-1}\frac{(2f_{n}+1)(1-f_{n})}{2M^{2}}$
$\displaystyle=\sum_{n\in{\cal{N}}}\frac{(2f_{n}+1)(1-f_{n})}{2MN}.$ (118)

According to thm:min, the estimation error of $\mathscr{P}$-4 is no less than
(118). This aspect shows that Protocol 1 is optimal in $\mathscr{P}$-4 for all
fidelity compositions
${{\cal{S}}}_{\mathrm{id}}(\bm{f}_{\mathrm{all}})\subset{{\cal{S}}}_{\mathrm{id}}$.
This completes the proof of lem:opt-id. ∎

Finally, thm:opt summarizes the results of this section.

######  Theorem B.1 (Optimal estimation protocol):

thm:opt Protocol 1 is optimal for $\mathscr{P}$-1.

###### Proof.

Denote the measurement operation and estimator of Protocol 1 by
${\cal{O}}^{*}$ and ${\cal{D}}^{*}$, respectively. According to lem:opt-id and
thm:gen-opt-id, the estimation protocol
$\\{\hat{{\cal{O}}}^{*},{\cal{D}}^{*}\\}$ is optimal for $\mathscr{P}$-1,
where the composite measurement operation
$\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}$.

Recall the following property of the operation ${\cal{T}}$ given in (34)

$\displaystyle{\cal{T}}(|\phi\rangle\langle\psi|)$
$\displaystyle=\left\\{\begin{array}[]{ll}|\phi\rangle\langle\psi|&\mbox{ if
}|\phi\rangle=|\psi\rangle\\\ 0&\mbox{ if
}|\phi\rangle\neq|\psi\rangle\end{array}\right.,$ (121)

where $|\phi\rangle,|\psi\rangle$ are Bell states
$\\{|\Phi^{\pm}\rangle,|\Psi^{\pm}\rangle\\}$. Given (121) and the fact that
Bell states form a basis of ${\cal{H}}^{4}$, the Kraus operators of
${\cal{T}}$ processing one qubit pair can be expressed as

$\displaystyle\bm{T}_{\phi}$
$\displaystyle=|\phi\rangle\langle\phi|,\quad\mbox{where}\quad\phi\in\\{\Phi^{\pm},\Psi^{\pm}\\}.$
(122)

In this case, (105) and (122), operation ${\cal{T}}$ does not change the
operators of ${\cal{O}}^{*}$, i.e.,

$\displaystyle\bm{M}_{u,r}=\sum_{\phi\in\\{\Phi^{\pm},\Psi^{\pm}\\}}\bm{T}^{\dagger}_{\phi}\bm{M}_{u,r}\bm{T}_{\phi},\;\;\forall\,u\in\\{x,y,z\\},\,r\in\\{0,1\\},$
(123)

where † is the Hermitian transpose. (123) shows that the composite measurement
operation $\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}$ is equivalent to
${\cal{O}}^{*}$, i.e.,

$\displaystyle\hat{{\cal{O}}}^{*}={\cal{O}}^{*}\circ{\cal{T}}={\cal{O}}^{*}.$
(124)

According to (124), the estimation protocol
$\\{{\cal{O}}^{*},{\cal{D}}^{*}\\}$ of Protocol 1 is optimal for
$\mathscr{P}$-1. This proves thm:opt. ∎

## References

  * Wehner  _et al._ [2018] S. Wehner, D. Elkouss, and R. Hanson, Quantum internet: A vision for the road ahead, Science 362 (2018).
  * Kimble [2008] H. J. Kimble, The quantum internet, Nature 453, 1023 (2008).
  * Castelvecchi [2018] D. Castelvecchi, The quantum internet has arrived (and it hasn’t), Nature 554, 289 (2018).
  * Pant  _et al._ [2019] M. Pant, H. Krovi, D. Towsley, L. Tassiulas, L. Jiang, P. Basu, D. Englund, and S. Guha, Routing entanglement in the quantum internet, npj Quantum Information 5, 25 (2019).
  * Arnon-Friedman  _et al._ [2018] R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, Practical device-independent quantum cryptography via entropy accumulation, Nature Communications 9, 459 (2018).
  * Avesani  _et al._ [2018] M. Avesani, D. G. Marangon, G. Vallone, and P. Villoresi, Source-device-independent heterodyne-based quantum random number generator at 17 gbps, Nature Communications 9, 5365 (2018).
  * Lee and Hoban [2018] C. M. Lee and M. J. Hoban, Towards device-independent information processing on general quantum networks, Phys. Rev. Lett. 120, 020504 (2018).
  * Schwonnek  _et al._ [2021] R. Schwonnek, K. T. Goh, I. W. Primaatmaja, E. Y. Z. Tan, R. Wolf, V. Scarani, and C. C. W. Lim, Device-independent quantum key distribution with random key basis, Nature Communications 12, 2880 (2021).
  * Li  _et al._ [2021] M.-H. Li, X. Zhang, W.-Z. Liu, S.-R. Zhao, B. Bai, Y. Liu, Q. Zhao, Y. Peng, J. Zhang, Y. Zhang, W. J. Munro, X. Ma, Q. Zhang, J. Fan, and J.-W. Pan, Experimental realization of device-independent quantum randomness expansion, Phys. Rev. Lett. 126, 050503 (2021).
  * Pirandola  _et al._ [2020] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. S. Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, Advances in quantum cryptography, Adv. Opt. Photon. 12, 1012 (2020).
  * Körber  _et al._ [2018] M. Körber, O. Morin, S. Langenfeld, A. Neuzner, S. Ritter, and G. Rempe, Decoherence-protected memory for a single-photon qubit, Nature Photonics 12, 18 (2018).
  * Yin  _et al._ [2017] J. Yin, Y. Cao, Y.-H. Li, S.-K. Liao, L. Zhang, J.-G. Ren, W.-Q. Cai, W.-Y. Liu, B. Li, H. Dai, G.-B. Li, Q.-M. Lu, Y.-H. Gong, Y. Xu, S.-L. Li, F.-Z. Li, Y.-Y. Yin, Z.-Q. Jiang, M. Li, J.-J. Jia, G. Ren, D. He, Y.-L. Zhou, X.-X. Zhang, N. Wang, X. Chang, Z.-C. Zhu, N.-L. Liu, Y.-A. Chen, C.-Y. Lu, R. Shu, C.-Z. Peng, J.-Y. Wang, and J.-W. Pan, Satellite-based entanglement distribution over 1200 kilometers, Science 356, 1140 (2017).
  * Humphreys  _et al._ [2018] P. C. Humphreys, N. Kalb, J. P. J. Morits, R. N. Schouten, R. F. L. Vermeulen, D. J. Twitchen, M. Markham, and R. Hanson, Deterministic delivery of remote entanglement on a quantum network, Nature 558, 268 (2018).
  * Pompili  _et al._ [2021] M. Pompili, S. L. N. Hermans, S. Baier, H. K. C. Beukers, P. C. Humphreys, R. N. Schouten, R. F. L. Vermeulen, M. J. Tiggelman, L. dos Santos Martins, B. Dirkse, S. Wehner, and R. Hanson, Realization of a multinode quantum network of remote solid-state qubits, Science 372, 259 (2021).
  * Liu  _et al._ [2020] H.-Y. Liu, X.-H. Tian, C. Gu, P. Fan, X. Ni, R. Yang, J.-N. Zhang, M. Hu, J. Guo, X. Cao, X. Hu, G. Zhao, Y.-Q. Lu, Y.-X. Gong, Z. Xie, and S.-N. Zhu, Drone-based entanglement distribution towards mobile quantum networks, National Science Review 7, 921 (2020).
  * West  _et al._ [2010] J. R. West, D. A. Lidar, B. H. Fong, and M. F. Gyure, High fidelity quantum gates via dynamical decoupling, Phys. Rev. Lett. 105, 230503 (2010).
  * Bason  _et al._ [2011] M. G. Bason, M. Viteau, N. Malossi, P. Huillery, E. Arimondo, D. Ciampini, R. Fazio, V. Giovannetti, R. Mannella, and O. Morsch, High-fidelity quantum driving, Nature Physics 8, 147 (2011).
  * Arroyo-Camejo  _et al._ [2014] S. Arroyo-Camejo, A. Lazariev, S. W. Hell, and G. Balasubramanian, Room temperature high-fidelity holonomic single-qubit gate on a solid-state spin, Nature Communications 5, 4870 EP (2014).
  * Zhang  _et al._ [2021] X. Zhang, M. Luo, Z. Wen, Q. Feng, S. Pang, W. Luo, and X. Zhou, Direct fidelity estimation of quantum states using machine learning, Phys. Rev. Lett. 127, 130503 (2021).
  * Somma  _et al._ [2006] R. D. Somma, J. Chiaverini, and D. J. Berkeland, Lower bounds for the fidelity of entangled-state preparation, Phys. Rev. A 74, 052302 (2006).
  * Gühne  _et al._ [2007] O. Gühne, C.-Y. Lu, W.-B. Gao, and J.-W. Pan, Toolbox for entanglement detection and fidelity estimation, Phys. Rev. A 76, 030305 (2007).
  * Flammia and Liu [2011] S. T. Flammia and Y.-K. Liu, Direct fidelity estimation from few pauli measurements, Phys. Rev. Lett. 106, 230501 (2011).
  * Zhu and Hayashi [2019] H. Zhu and M. Hayashi, Optimal verification and fidelity estimation of maximally entangled states, Phys. Rev. A 99, 052346 (2019).
  * Kalb  _et al._ [2017] N. Kalb, A. A. Reiserer, P. C. Humphreys, J. J. W. Bakermans, S. J. Kamerling, N. H. Nickerson, S. C. Benjamin, D. J. Twitchen, M. Markham, and R. Hanson, Entanglement distillation between solid-state quantum network nodes, Science 356, 928 (2017).
  * Tomamichel  _et al._ [2012] M. Tomamichel, C. C. W. Lim, N. Gisin, and R. Renner, Tight finite-key analysis for quantum cryptography, Nature Communications 3, 634 (2012).
  * Pfister  _et al._ [2018] C. Pfister, M. A. Rol, A. Mantri, M. Tomamichel, and S. Wehner, Capacity estimation and verification of quantum channels with arbitrarily correlated errors, Nature Communications 9, 27 (2018).
  * Bagan  _et al._ [2006] E. Bagan, M. A. Ballester, R. D. Gill, R. Muñoz Tapia, and O. Romero-Isart, Separable measurement estimation of density matrices and its fidelity gap with collective protocols, Phys. Rev. Lett. 97, 130501 (2006).
  * De Greve  _et al._ [2013] K. De Greve, P. L. McMahon, L. Yu, J. S. Pelc, C. Jones, C. M. Natarajan, N. Y. Kim, E. Abe, S. Maier, C. Schneider, M. Kamp, S. Höfling, R. H. Hadfield, A. Forchel, M. M. Fejer, and Y. Yamamoto, Complete tomography of a high-fidelity solid-state entangled spin–photon qubit pair, Nature Communications 4, 2228 EP (2013).
  * Bock  _et al._ [2018] M. Bock, P. Eich, S. Kucera, M. Kreis, A. Lenhard, C. Becher, and J. Eschner, High-fidelity entanglement between a trapped ion and a telecom photon via quantum frequency conversion, Nature Communications 9, 1998 (2018).
  * Cramér [1999] H. Cramér,  _Mathematical Methods of Statistics_ (Princeton University Press, Princeton, New Jersey, U.S., 1999).
  * Rao [1994] C. R. Rao,  _Selected Papers of C.R. Rao_ (John Wiley & Sons, New York, U.S., 1994).
  * Paris [2009] M. G. A. Paris, Quantum estimation for quantum technology, International Journal of Quantum Information 07, 125 (2009).
  * Šafránek [2018] D. Šafránek, Simple expression for the quantum fisher information matrix, Phys. Rev. A 97, 042322 (2018).
  * Bennett  _et al._ [1996] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, Purification of noisy entanglement and faithful teleportation via noisy channels, Phys. Rev. Lett. 76, 722 (1996).
  * Horodecki  _et al._ [2009] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865 (2009).
  * Horodecki and Horodecki [1996] R. Horodecki and M. Horodecki, Information-theoretic aspects of inseparability of mixed states, Phys. Rev. A 54, 1838 (1996).
  * Horodecki  _et al._ [1997] M. Horodecki, P. Horodecki, and R. Horodecki, Inseparable two spin-$\frac{1}{2}$ density matrices can be distilled to a singlet form, Phys. Rev. Lett. 78, 574 (1997).
  * Bobrovsky  _et al._ [1987] B. Z. Bobrovsky, E. Mayer-Wolf, and M. Zakai, Some Classes of Global Cramer-Rao Bounds, The Annals of Statistics 15, 1421 (1987).

  *[w.r.t.]: with respect to
  *[POVM]: positive operator-valued measure
  *[i.i.d.]: independent and identically distributed
  *[QBER]: quantum bit error rate