# Storage and retrieval of von Neumann measurements

Paulina Lewandowska<EMAIL_ADDRESS>Institute of Theoretical and
Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice,
Poland  Ryszard Kukulski  Institute of Theoretical and Applied Informatics,
Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland  Łukasz Pawela
Institute of Theoretical and Applied Informatics, Polish Academy of Sciences,
Bałtycka 5, 44-100 Gliwice, Poland  Zbigniew Puchała  Institute of Theoretical
and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100
Gliwice, Poland

###### Abstract

This work examines the problem of learning an unknown von Neumann measurement
of dimension $d$ from a finite number of copies. To obtain a faithful
approximation of the given measurement we are allowed to use it $N$ times. Our
main goal is to estimate the asymptotic behavior of the maximum value of the
average fidelity function $F_{d}$ for a general $N\rightarrow 1$ learning
scheme. We show that $F_{d}=1-\Theta\left(\frac{1}{N^{2}}\right)$ for
arbitrary but fixed dimension $d$. In addition to that, we compared various
learning schemes for $d=2$. We observed that the learning scheme based on
deterministic port-based teleportation is asymptotically optimal but performs
poorly for low $N$. In particular, we discovered a parallel learning scheme,
which despite its lack of asymptotic optimality, provides a high value of the
fidelity for low values of $N$ and uses only two-qubit entangled memory
states.

##  I Introduction

In the general approach of storage and retrieval (SAR) of quantum operations,
we want to approximate a given, unknown operation, which we were able to
perform $N$ times experimentally. Such a scheme is called $N\rightarrow 1$
_learning scheme._ This strategy usually consists of preparing some initial
quantum state, applying the unknown operation $N$ times, which allows us to
store the unknown operation for later use, and finally, a retrieval operation
that applies an approximation of the black box on some arbitrary quantum
state. Additionally, each application of the operation contained within the
black box can be followed by some arbitrary processing operations. If that is
the case, the optimal strategy should also contain their description. The
scheme is optimal when it achieves the highest possible fidelity of the
approximation [1, 2].

The obstacle standing in the way of achieving unit fidelity lies in the no-
cloning theorem [3] and even further, the no-programming theorem [4]. It
states that a general processor, which performs a program based on some input
state is not possible. There is no doubt that programmable devices would
represent an instrumental piece of quantum technology. Hence, their
approximate realizations are of common interest [5, 6, 7, 8, 9]. Nevertheless,
one should keep in mind the difference between programming and learning. A
learning protocol can be used to generate a program, but the program does not
have to be generated by learning. Although, in some cases, the performances of
programming and learning are equal [7].

The seminal work in this field was the paper by Bisio and Chiribella [10]. It
was devoted to learning an unknown unitary transformation. Therein, the
authors focused on storing the unitary operation in a quantum memory while
having limited resources. They proved that unitary operations could be learned
optimally in the parallel scheme, meaning there is no additional processing
after using the unknown unitary transformation. Hence, all the required uses
of the black box can be performed in parallel. They also provide an upper
bound on the fidelity of $N\rightarrow 1$ learning scheme that is equal
$1-\Theta\left(\frac{1}{N^{2}}\right)$. A probabilistic version of SAR (PSAR)
problem was also considered in [11, 12]. There, they showed the optimal
success probability of $N\rightarrow 1$ PSAR of unitary channels on
$d$-dimensional quantum systems is equal to $N/(N-1+d^{2})$.

It is worth mentioning that the SAR of unitary operations is also closely
related to port-based teleportation (PBT) [13, 14]. One may take the PBT
protocol to define a learning scheme. In particular, the entanglement fidelity
of the deterministic PBT protocol matches the fidelity of learning unitary
operations [10, 15]. Similarly, the probability of successful teleportation is
equal to the performance of PSAR [11]. Finally, the task of learning unknown
operations fits into the paradigm of quantum machine learning, when both the
data and the algorithms are quantum [16, 17, 18, 19, 20, 21, 22].

Subsequent works build upon these results but focus on different classes of
operations, for example, the von Neumann measurements [23]. In contrast to
previous works, they showed that, in general, the optimal algorithm for
quantum measurement learning cannot be parallel and found the optimal learning
algorithm for arbitrary von Neumann measurements for the case $1\rightarrow 1$
and $2\rightarrow 1$. Nevertheless, a general optimal scheme $N\rightarrow 1$
of measurement learning still remains an open problem, even for low-
dimensional quantum systems. Hence, despite some partial results, the
investigation of SAR for von Neumann measurements is still an open question.

In this work, we address the unsolved problem of learning an unknown von
Neumann measurement defined in [23]. We focus on $N\rightarrow 1$ learning
scheme of von Neumann measurements. We investigate a value of the average
fidelity in the asymptotic regime. By using the deterministic PBT protocol we
state a lower bound which behaves as $1-\Theta\left(\frac{1}{N^{2}}\right)$.
Moreover, we provide an upper bound for the average fidelity function, which
matches the lower bound and hence provides a solution to the problem.

Additionally, we compare different learning schemes for the qubit case.
Although, the learning scheme based on PBT is asymptotically optimal, it can
be outperformed for low values of $N$. To show this, we introduce a scheme,
which we call _pretty good learning scheme_ (PGLS). This scheme is a
particular case of a parallel learning scheme which uses only two-qubit
entangled memory states. The fidelity function calculated for the pretty good
learning scheme is uniform over all qubit von Neumann measurements and behaves
as $1-\Theta\left(\frac{1}{N}\right)$.

This paper is organized as follows. In Section II we formulate the problem of
von Neumann measurement learning. In Section II.1 we introduce necessary
mathematical concepts. Our main result is then presented in Section II.2
(Theorem 1). To prove this theorem, we first address the case of lower bound
(Section III.1), and subsequently, upper bound (Section III.2). In Section IV
we compare the performance of different learning schemes for a qubit case. In
particular, we introduce the pretty good learning scheme and present numerical
results about the most efficient parallel and adaptive learning schemes.
Finally, Section V concludes the article with a summary of the main results.
In the Appendix, we provide technical details of proofs.

##  II Problem formulation

This section presents the formulation of the problem of learning an unknown
von Neumann measurement. We provide an overview of a learning scheme in Fig.
1, along with its description in Subsection II.2.

###  II.1 Mathematical framework

Let us introduce the following notation. Consider a $d$-dimensional complex
Euclidean space $\mathbb{C}^{d}$ and denote it by $\mathcal{H}_{d}$. Let
$\mathrm{M}(\mathcal{H}_{d_{1}},\mathcal{H}_{d_{2}})$ be the set of all
matrices of dimension $d_{1}\times d_{2}$. As a shorthand we put
$\mathrm{M}(\mathcal{H}_{d})\coloneqq\mathrm{M}(\mathcal{H}_{d},\mathcal{H}_{d})$.
The set of quantum states defined on space $\mathcal{H}_{d}$, that is the set
of positive semidefinite operators having unit trace, will be denoted by
$\Omega(\mathcal{H}_{d})$. We will also need a linear mapping transforming
$\mathrm{M}(\mathcal{H}_{d_{1}})$ into $\mathrm{M}(\mathcal{H}_{d_{2}})$ as
$\mathcal{T}:\mathrm{M}(\mathcal{H}_{d_{1}})\mapsto\mathrm{M}(\mathcal{H}_{d_{2}}).$
There exists a bijection between introduced linear mappings $\mathcal{T}$ and
set of matrices $\mathrm{M}(\mathcal{H}_{d_{1}d_{2}})$, known as the Choi-
Jamiołkowski isomorphism [24, 25]. Its explicit form is
$\text{T}=\sum_{i,j=0}^{d_{1}-1}\mathcal{T}(\outerproduct{i}{j})\otimes\outerproduct{i}{j}$.
We will denote linear mappings with calligraphic font
$\mathcal{L},\SS,\mathcal{T}$ etc., whereas the corresponding Choi-
Jamiołkowski matrices as plain symbols: $L,S,T$ etc. Moreover, we introduce
the vectorization operation of a matrix
$X\in\mathrm{M}(\mathcal{H}_{d_{1}},\mathcal{H}_{d_{2}})$, defined by
$\left|\left.{X}\right\rangle\\!\right\rangle\coloneqq\sum_{i=0}^{d_{2}-1}\left(X\ket{i}\right)\otimes\ket{i}$.

A general quantum measurement (POVM) $\mathcal{Q}$ can be viewed as a set of
positive semidefinite operators $\mathcal{Q}=\\{Q_{i}\\}_{i}$ such that
$\sum_{i}Q_{i}={\rm 1l}$. These operators are usually called effects. The von
Neumman measurements, $\mathcal{P}_{U}$, are a special subclass of
measurements whose all effects are rank-one projections given by
$\mathcal{P}_{U}=\\{P_{U,i}\\}_{i=0}^{d-1}=\\{U\outerproduct{i}{i}U^{\dagger}\\}_{i=0}^{d-1}$
for some unitary matrix $U\in\mathrm{M}(\mathcal{H}_{d})$.

Quantum channels are completely positive and trace preserving (CPTP) linear
maps. Generally, $\mathcal{C}$ is a quantum channel which maps
$\mathrm{M}(\mathcal{H}^{(in)})$ to $\mathrm{M}(\mathcal{H}^{(out)})$ if its
Choi-Jamiołkowski operator $C$ is a positive semidefinite and
$\tr_{\mathcal{H}^{(out)}}(C)={\rm 1l}$, where $\tr_{\mathcal{H}^{(out)}}$
denotes a partial trace over the output system $\mathcal{H}^{(out)}$. Given a
von Neumann measurement $\mathcal{P}_{U}$, it can be seen as a measure-and-
prepare quantum channel
$\mathcal{P}_{U}(\rho)=\sum_{i}\tr\left(P_{U,i}\rho\right)\outerproduct{i}{i}$,
$\rho\in\Omega(\mathcal{H}_{d})$. The Choi matrix of $\mathcal{P}_{U}$ is
$P_{U}=\sum_{i}\outerproduct{i}{i}\otimes\overline{P_{U,i}},$ which will be
utilized throughout this work. Finally, we will use the notation $\Phi_{U}$ to
indicate unitary channel given by $\Phi_{U}(X)=UXU^{\dagger}$ and the shortcut
$\mathcal{I}_{d}\coloneqq\Phi_{{\rm 1l}_{d}}$ for the identity channel.

###  II.2 Learning setup

Figure 1: Schematic representations of the setup for learning of von Neumann
measurements $\mathcal{P}_{U}$ in the $N\rightarrow 1$ scheme.

Imagine we are given a black box with the promise that it contains some von
Neumann measurement, $\mathcal{P}_{U}$, parameterized by a unitary matrix $U$.
The exact value of $U$ is unknown to us. We are allowed to use the black box
$N$ times. Our goal is to prepare some initial memory state $\sigma$, some
intermediate processing channels $\mathcal{C}_{1},\ldots,\mathcal{C}_{N-1}$
and a measurement $\mathcal{R}$ such that we are able to approximate
$\mathcal{P}_{U}$ on an arbitrary state $\rho$. This approximation will be
denoted throughout this work as $\mathcal{Q}_{U}$. We would like to point out
that, generally, $\mathcal{Q}_{U}$ will _not_ be a von Neumann measurement.

The initial memory state $\sigma$ and entire sequence of processing channels
$\\{\mathcal{C}_{i}\\}$ can be viewed as _storing_ the unknown operation and
will be denoted as $\SS$ whereas the measurement $\mathcal{R}$ we will call as
_retrieval_. During the storing stage, we apply $\SS$ on $N$ copies of
$\mathcal{P}_{U}$. As a result, the initial memory state $\sigma$ is
transferred to the memory state $\sigma_{\mathcal{P}_{U},\SS}$. After that, we
measure an arbitrary quantum state $\rho$ and the memory state
$\sigma_{\mathcal{P}_{U},\SS}$ by using $\mathcal{R}$. Equivalently, we can
say that during retrieval stage, we apply the measurement $\mathcal{Q}_{U}$ on
the state $\rho$. The entire learning scheme will be denoted by $\mathcal{L}$
and considered as a triple
$\mathcal{L}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N-1},\mathcal{R}\right)$.
We emphasize that the procedure allows us to use as much quantum memory as
necessary.

As a measure of quality of approximating a von Neumann measurement
$\mathcal{P}_{U}=\\{P_{U,i}\\}_{i}$ with a POVM
$\mathcal{Q}_{U}=\\{Q_{U,i}\\}_{i}$ we choose the fidelity function [1], which
is defined as follows

$\mathcal{F}_{d}(\mathcal{P}_{U},\mathcal{Q}_{U})\coloneqq\frac{1}{d}\sum_{i}\tr(P_{U,i}Q_{U,i}),$
(1)

where $d$ is the dimension of the measured system. Note that in the case when
$\mathcal{P}_{U}$ is a von Neumann measurement we obtain the value of fidelity
function $\mathcal{F}_{d}$ belongs to the interval $[0,1]$ and equals one if
and only if $P_{U,i}=Q_{U,i}$ for all $i$. As there is no prior information
about $\mathcal{P}_{U}$ provided, we assume that $U$ is sampled from a
distribution pertaining to the Haar measure. Therefore, considering a von
Neumann measurement $\mathcal{P}_{U}$ and its approximation $\mathcal{Q}_{U}$
we introduce the _average fidelity function_ [26] with respect to Haar measure
as

$\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})\coloneqq\int_{U}dU\mathcal{F}_{d}(\mathcal{P}_{U},\mathcal{Q}_{U}).$
(2)

Our main goal is to maximize $\mathcal{F}_{d}^{\text{avg}}$ over all possible
learning schemes
$\mathcal{L}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N-1},\mathcal{R}\right)$.
We introduce the notation of the maximum value of the average fidelity
function

$F_{d}\coloneqq\max_{\mathcal{L}}\mathcal{F}_{d}^{\text{avg}}(\mathcal{L}).$
(3)

In this work, we analyze the asymptotic behavior of $F_{d}$ with $N\to\infty$.
Our main result can be summarized as the following theorem.

######  Theorem 1.

Let $F_{d}$ be the maximum value of the average fidelity function, defined in
Eq. (3) for $N\rightarrow 1$ learning scheme of von Neumann measurements.
Then, for arbitrary but fixed dimension $d$ we obtain

$F_{d}=1-\Theta\left(\frac{1}{N^{2}}\right).$ (4)

##  III Fidelity bounds

This section provides a sketch of the proof of Theorem 1, along with a general
intuition behind our result. The full proofs are postponed to the Appendix A,
B and C due to their technical nature.

###  III.1 Lower bound

The proof of the lower bound for $F_{d}$ is constructive. We will construct
the learning scheme $\mathcal{L}$ of von Neumann measurements, which achieves
the scaling
$\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})=1-\Theta\left(\frac{1}{N^{2}}\right)$.

Figure 2:  Schematic representation of DPBT for $N=2$. In this case, the
output label $i=2$ of the measurement $\mathcal{Q}$ determines the partial
trace of the first system of the remaining quantum state.

The construction is based on deterministic port-based teleportation (DPBT)
[13, 14, 27, 28, 15]. In this scheme (see Fig. 2), two individuals – Alice and
Bob, share an entangled state
$\outerproduct{\psi}{\psi}_{A,B}\in\Omega(\mathcal{H}_{d^{N}}^{(A)}\otimes\mathcal{H}_{d^{N}}^{(B)})$.
Bob perceives his compound system $\mathcal{H}_{d^{N}}^{(B)}$ as a tensor
product of $N$ systems (ports) of the form
$\mathcal{H}_{d^{N}}^{(B)}=\mathcal{H}_{d}^{(1)}\otimes\cdots\otimes\mathcal{H}_{d}^{(N)}$.
Their goal is to teleport an unknown state $\rho\in\mathcal{H}_{d}^{(in)}$
from Alice to Bob in a way that this state appears in one of Bob’s ports. To
achieve this, Alice performs appropriate measurement
$\mathcal{Q}=\\{Q_{i}\\}_{i=1}^{N}$ on
$\rho\otimes\outerproduct{\psi}{\psi}_{A}$, receives one of the labels
$\\{1,\ldots,N\\}$ and communicates this label to Bob. By using the label $i$,
Bob chooses $i$-th system of his state $\outerproduct{\psi}{\psi}_{B}$ as the
one which contains the state $\rho$. The output of this procedure can be
written as

$\sum_{i=1}^{N}\tr_{\mathcal{H}_{d}^{(in)}\otimes\mathcal{H}_{d^{N}}^{(A)}\otimes\mathcal{H}_{d^{N-1}}^{(\bar{B}_{i})}}\left((Q_{i}\otimes{\rm
1l}_{d^{N}})(\rho\otimes\outerproduct{\psi}{\psi}_{A,B})\right),$ (5)

where
$\mathcal{H}_{d^{N-1}}^{(\bar{B}_{i})}\coloneqq\mathcal{H}_{d}^{(1)}\otimes\cdots\otimes\mathcal{H}_{d}^{(i-1)}\otimes\mathcal{H}_{d}^{(i+1)}\otimes\cdots\otimes\mathcal{H}_{d}^{(N)}$.
In short, the output of this procedure will be denoted as $\mathcal{T}(\rho)$,
where $\mathcal{T}$ is a channel describing DPBT, depending on the choice of
$\outerproduct{\psi}{\psi}_{A,B}$ and $\mathcal{Q}$. It is known [15], that
the best teleportation procedure $\mathcal{T}_{0}$ approximates
$\mathcal{I}_{d}$ with the entanglement fidelity

$F_{*}\coloneqq\frac{1}{d^{2}}\tr\left(T_{0}\left|\left.{{{\rm
1l}_{d}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{{\rm
1l}_{d}}}\right.\right|\right)=1-\Theta\left(\frac{1}{N^{2}}\right).$ (6)

Figure 3: Schematic representation of the learning scheme for $N=2$ based on
DPBT. In this case, the label $i=2$ of the measurement $\mathcal{Q}_{0}$
indicates that the output of the learning procedure equals $j_{i}=j_{2}$.

We can use DPBT to construct a learning scheme (see Fig. 3). Let
$\outerproduct{\psi_{0}}{\psi_{0}}_{A,B}$ and $\mathcal{Q}_{0}$ realize the
optimal teleportation strategy $\mathcal{T}_{0}$. We take
$\sigma=\outerproduct{\psi_{0}}{\psi_{0}}_{A,B}$ as an initial memory state
and consider a parallel learning scheme [10] with $N$ copies of the von
Neumann measurement $\mathcal{P}_{U}$. The result of the storage is a memory
state
$\sigma_{\mathcal{P}_{U},S}=\left(\mathcal{I}_{d^{N}}\otimes\mathcal{P}_{U}^{\otimes
N}\right)(\sigma)$, which consists of the remaining quantum state $\tau$, and
a tuple of measurements’ results
$(j_{1},\ldots,j_{N})\in\\{0,\ldots,d-1\\}^{N}$. The retrieval $\mathcal{R}$
is a composition of a measurement $\mathcal{Q}_{0}$ and classical
postprocessing. In details, first, we apply $\mathcal{Q}_{0}$ on
$\rho\otimes\tau$ to obtain the label $i\in\\{1,\ldots,N\\}$. Second, we
return the result $j_{i}$ as the output of $\mathcal{R}$. This procedure
determines a learning scheme $\mathcal{L}$ which achieves the average fidelity

$\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})=1-\Theta\left(\frac{1}{N^{2}}\right).$
(7)

We postponed the details of the proof to Appendix A.

###  III.2 Upper bound

To show the upper bound for $F_{d}$, we will construct a different learning
scheme based on the learning of unitary maps. It will provide the desired
inequality, at first for $d=2$, then for arbitrary $d$.

######  Lemma 1.

For $d=2$ the maximum value of the average fidelity function defined in Eq.
(3) is upper bounded by

$F_{2}\leq 1-\Theta\left(\frac{1}{N^{2}}\right).$ (8)

The complete proof of Lemma 1 is shown in Appendix B. As in the previous
section, here we will only sketch the key steps.

Figure 4:  Schematic representation of the setup, which we use to calculate
the upper bound for $F_{2}$. In this scenario, we are given $N$ copies of a
unitary channel $\Phi_{\bar{U}}$ in parallel. Our objective is to approximate
the von Neumann measurement $\mathcal{P}_{U}$.

Let us consider a new learning scheme presented in Fig. 4 for $d=2$. In this
scheme, we are given $N$ copies of unitary channel $\Phi_{\bar{U}}$, which we
can use in parallel. We want to approximate the measurement $\mathcal{P}_{U}$,
but using the black box with the unitary channel $\Phi_{\bar{U}}$ inside. We
will choose the appropriate initial memory state $\ket{\psi}$ and retrieval
binary measurement $\mathcal{R}=\\{R_{0},R_{1}\\}$. We use the same measures
of quality as before, namely $\mathcal{F}_{2}$ defined in Eq. (1) and
$\mathcal{F}_{2}^{\text{avg}}$ defined in Eq. (2). The goal is to maximize the
value of the average fidelity function, which in this case, we will denote as
$\widetilde{F_{2}}$. In the Appendix B.1 we derived the formula for
$\widetilde{F_{2}}$, which is given by

$\begin{split}&\widetilde{F_{2}}=\\\
&\max_{\mathcal{R},\outerproduct{\psi}{\psi}}\int_{U}dU\sum_{i=0}^{1}\frac{\tr\left[R_{i}\left(P_{U,i}\otimes\left(\Phi_{{\overline{U}}^{\otimes
N}}\otimes\mathcal{I}\right)(\outerproduct{\psi}{\psi})\right)\right]}{2}.\end{split}$
(9)

Calculating the value of $\widetilde{F_{2}}$ is the crux of the proof, because
we managed to show that $F_{2}\leq\widetilde{F_{2}}$ (see Lemma 3 in Appendix
B). We derived the thesis of Lemma 1 by achieving the inequality
$\widetilde{F_{2}}\leq 1-\Theta\left(\frac{1}{N^{2}}\right).$

The proof of the upper bound for arbitrary $d$ relies on the qubit case. Let
us take the optimal learning scheme $\mathcal{L}$ such that it achieves
$\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})=F_{d}$ and satisfies the following
commutation relation

$[L,{\rm 1l}_{d}\otimes U\otimes({\rm 1l}_{d}\otimes\bar{U})]^{\otimes N}]=0$
(10)

for any unitary matrix $U\in\mathrm{M}(\mathcal{H}_{d})$. We can use
$\mathcal{L}$ to construct a learning scheme $\mathcal{L}^{\prime}$ of qubit
von Neumann measurements, such that it holds
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}^{\prime})\geq dF_{d}-(d-1)$. It
directly implies that $F_{d}\leq 1-\Theta\left(\frac{1}{N^{2}}\right).$ We
postponed the technical details to Appendix C.

######  Corollary 1.

There is no perfect learning scheme for von Neumann measurements, _i.e._ for
any $N\in\mathbb{N}$ the value of $F_{d}<1$.

##  IV Qubit case

In this subsection we investigate more deeply the behavior of
$\mathcal{F}_{2}^{\text{avg}}$ for different types of learning schemes
$\mathcal{L}$.

###  IV.1 Pretty good learning scheme

The first scheme which we analyze will be called the _pretty good learning
scheme_. Despite its lack of optimality, it provides a relatively high value
for the average fidelity function asymptotically behaving as
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PGLS})=1-\Theta\left(\frac{1}{N}\right)$.
This scheme employs a simple storage strategy, which uses only two-qubit
entangled memory states and the learning process is done in parallel.
Moreover, the achieved value of the fidelity function is uniform over all
qubit von Neumann measurements.

Let us consider a parallel learning scheme with $N$ copies of the von Neumann
measurement $\mathcal{P}_{U}$. A sketch of our scheme is shown in Fig. 5 and
here we present the algorithm describing the procedure:

Figure 5: Schematic representations of the pretty good learning scheme for
$N=3$. In the learning process we obtained three labels: $0,1,0$. As labels
“$0$” are in majority, we reject the label “$1$” and the associated quantum
part.

  1. 1.

We prepare the initial memory state $\sigma$ as a tensor product of $N$
maximally entangled states
$\ket{\omega}\coloneqq\frac{1}{\sqrt{2}}\left|\left.{{\rm
1l}_{2}}\right\rangle\\!\right\rangle$.

  2. 2.

We partially measure each state $\ket{\omega}$ using $\mathcal{P}_{U}$,
obtaining the state
$(\mathcal{P}_{U}\otimes\mathcal{I}_{2})(\outerproduct{\omega}{\omega}).$

  3. 3.

For each measurement $\mathcal{P}_{U}$, we obtain one of two possible
measurement results: “$0$” or “$1$”. In consequence, we get $N_{0}$ outcomes
“$0$” and $N_{1}$ outcomes “$1$”, $N_{0}+N_{1}=N$. The state of the remaining
quantum part is equal to $\overline{P_{U,0}}^{\otimes
N_{0}}\otimes\overline{P_{U,1}}^{\otimes N_{1}}$ (up to permutation of
subsystems). Without loss of a generality (w.l.o.g.), we may assume that
$N_{0}\geq N_{1}$.

  4. 4.

By majority vote we reject minority report, _i.e._ we reject all outcomes
“$1$” and quantum states associated with them. As a result the memory state is
given by $\sigma_{\mathcal{P}_{U},\SS}=\overline{P_{U,0}}^{\otimes N_{0}}$.

  5. 5.

We prepare an arbitrary state $\rho\in\Omega(\mathcal{H}_{2})$.

  6. 6.

We perform a binary retrieval measurement $\mathcal{R}=\\{R,{\rm 1l}-R\\}$ on
$\rho\otimes\sigma_{\mathcal{P}_{U},\SS}$.

To construct the effect $R$, let us fix $N_{0}$ and let $n=N_{0}-1$. We
introduce the family of Dicke states [29]. The Dicke state $\ket{D_{k}^{n}}$
is the $n$-qubit state, which is equal to the superposition state of all
${n\choose k}$ basis states of weight $k$. For example,
$\ket{D_{1}^{3}}=\frac{1}{\sqrt{3}}\left(\ket{100}+\ket{010}+\ket{001}\right)$.
Let us also define

$s_{n}(k,m)\coloneqq\sum_{i=0}^{k}\sum_{j=0}^{n-k}\delta_{i+j-m}{k\choose
i}{n-k\choose j}(-1)^{n-k-j}$ (11)

being the convolution of binomial coefficients. Consider the effect $R$ of the
form

$R=\sum_{k=0}^{n}\outerproduct{R_{k}}{R_{k}},$ (12)

where
$\ket{R_{k}}\coloneqq\frac{\left|\left.{M_{k}}\right\rangle\\!\right\rangle}{||M_{k}||_{2}}$
and matrices
$M_{k}\in\mathrm{M}\left(\mathcal{H}_{2},\mathcal{H}_{2^{n+1}}\right)$ are
given by

$M_{k}=\sum_{m=0}^{n+1}\frac{s_{n}(k,n-m)\ket{0}+s_{n}(k,n+1-m)\ket{1}}{\sqrt{n+1\choose
m}}\bra{D_{m}^{n+1}}$ (13)

for $k=0,\ldots,n$. The proof that $R$ is a valid effect is relegated to Lemma
11 in Appendix D. In this learning scheme the approximation
$\mathcal{Q}_{U}=\\{Q_{U,0},{\rm 1l}_{2}-Q_{U,0}\\}$ is determined by relation
$\tr\left(\rho
Q_{U,0}\right)=\tr\left(\left(\rho\otimes\overline{P_{U,0}}^{\otimes
N_{0}}\right)R\right)$. Basing on Lemma 12 in Appendix D, the effect $Q_{U,0}$
has the form

$\begin{split}Q_{U,0}=\frac{N_{0}}{N_{0}+1}P_{U,0}.\end{split}$ (14)

Provided we observed $N_{0}$ outcomes “$0$”, we have that
$\mathcal{F}_{2}(\mathcal{P}_{U},\mathcal{Q}_{U})=\frac{2N_{0}+1}{2N_{0}+2}$,
where $N_{0}$ satisfies $N_{0}\geq\lceil{\frac{N}{2}}\rceil$. Note, that the
value of $\mathcal{F}_{2}(\mathcal{P}_{U},\mathcal{Q}_{U})$ does not depend on
the choice of $U$. The average fidelity function
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PGLS})$ defined for the pretty good
learning scheme of qubit von Neumann measurements satisfies

$\begin{split}&\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PGLS})=\\\
&\begin{cases}\frac{1}{2^{N}}\sum\limits_{l=k}^{N}2{{N}\choose{l}}\frac{2l+1}{2l+2},&N=2k-1,\\\
\frac{1}{2^{N}}\left({{N}\choose{k}}\frac{2k+1}{2k+2}+\sum\limits_{l=k+1}^{N}2{{N}\choose{l}}\frac{2l+1}{2l+2}\right),&N=2k.\end{cases}\end{split}$
(15)

In the asymptotic regime, we may simplify the calculations to obtain

$\begin{split}\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PGLS})\geq\frac{2\lceil{\frac{N}{2}}\rceil+1}{2\lceil{\frac{N}{2}}\rceil+2}=1-\Theta\left(\frac{1}{N}\right).\end{split}$
(16)

######  Corollary 2.

In the pretty good learning scheme
$\mathcal{L}_{PGLS}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N-1},\mathcal{R}\right)$
the initial state $\sigma$ is defined as a product of $N$ copies of maximally
entangled state $\ket{\omega}$, processing channels
$\\{\mathcal{C}_{i}\\}_{i=1}^{N-1}$ are responsible for majority voting and
the measurement $\mathcal{R}=\\{R,{\rm 1l}-R\\}$ is defined by Eq.(12).

Finally, averaging the construction of $\mathcal{Q}_{U}$ over all possible
combinations of measurements’ results $\\{0,1\\}^{N}$ leads to the following
approximation of $\mathcal{P}_{U}$.

######  Corollary 3.

The approximation $\mathcal{Q}_{U}$ is a convex combination of the original
measurement $\mathcal{P}_{U}$ and the maximally depolarizing channel
$\Phi_{*}$. More precisely,

$\mathcal{Q}_{U}=p_{0}\mathcal{P}_{U}+(1-p_{0})\Phi_{*},$ (17)

where $p_{0}=2\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PGLS})-1$.

In the pretty good learning scheme, to keep the calculation simple, we assumed
that the retrieval measurement $\mathcal{R}$ uses a memory state that is a
tensor product of $N_{0}$ copies of the same state ($\overline{P_{U,0}}$ or
$\overline{P_{U,1}}$). The same approach was investigated in the paper [30],
where the value of the average fidelity function was originally derived
$\mathcal{F}_{2}(\mathcal{P}_{U},\mathcal{Q}_{U})=\frac{2N_{0}+1}{2N_{0}+2}$.
However, one may improve the learning scheme by using all available output
states $\overline{P_{U,0}}$ and $\overline{P_{U,1}}$. In that case, we expect
to obtain a higher value of the fidelity function. Such an intuition was
confirmed by Gisin and Popescu [31], who proved that a memory state
$\overline{P_{U,0}}\otimes\overline{P_{U,1}}$ encodes more information of the
effect $P_{U,0}$, than a state $\overline{P_{U,0}}\otimes\overline{P_{U,0}}$.

###  IV.2 Learning based on port-based teleportation

We have observed in Section III.1 that learning scheme based on DPBT achieves
the average fidelity
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{DPBT})=1-\Theta\left(\frac{1}{N^{2}}\right).$
More precisely, from the proof presented in Appendix A, we get
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{DPBT})=\frac{1}{3}+\frac{2}{3}F_{*}$,
where $F_{*}$ is the entanglement fidelity of DPBT protocol. For $d=2$ it is
known [14] that $F_{*}=\cos^{2}\left(\frac{\pi}{N+2}\right)$. Hence,

$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{DPBT})=\frac{1}{3}+\frac{2}{3}\cos^{2}\left(\frac{\pi}{N+2}\right).$
(18)

The learning scheme can also be constructed using probabilistic port-based
teleportation (PPBT) (see for instance [15]). This protocol works similarly to
$\mathcal{L}_{DPBT}$ presented in Fig. 3. The difference is that the final
measurement $\mathcal{Q}_{0}$ returns a label $i\in\\{0,\ldots,N\\}$, where
the label $i>0$ indicates the success of the teleportation procedure – the
initial state is in $i$-th port and the label $i=0$ indicates the protocol’s
failure. The result from [27] says that the corresponding optimal probability
of success teleportation is $p_{0}=\frac{N}{N+3}$. That means the
approximation $\mathcal{Q}_{U}$ achieved by the learning scheme
$\mathcal{L}_{PPBT}$is given by

$\mathcal{Q}_{U}=p_{0}\mathcal{P}_{U}+(1-p_{0})\Phi_{*},$ (19)

which implies

$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{PPBT})=\frac{2N+3}{2N+6}.$ (20)

###  IV.3 Numerical investigation

In is generally difficult to find an optimal procedure for quantum operations
learning. It is worth mentioning that the parallel learning schemes match
adaptive ones for $N=1,2$ but for $N\geq 3$ adaptive strategies achieve slight
advantage [23].

In the numerical analysis, we compared average fidelity for the optimal
parallel learning strategy $\mathcal{L}_{\text{Parallel}}$ with the optimal
adaptive strategy $\mathcal{L}_{\text{Adaptive}}$. The scheme
$\mathcal{L}_{\text{Adaptive}}$ is also the best possible scheme available,
which is causally structured that is
$\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{Adaptive}})=F_{2}$.

$\begin{array}[]{l|c|c|c|c|c}N&1&2&3&4&5\\\
\hline\cr\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{Adaptive}})&0.7499&0.8114&0.8684&0.8968&0.9189\\\
\hline\cr\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{Parallel}})&0.7499&0.8114&0.8676&0.8955&0.9187\\\
\hline\cr\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{DPBT}})&0.5000&0.6667&0.7697&0.8333&0.8745\\\
\hline\cr\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{PGLS}})&0.7500&0.7917&0.8438&0.8625&0.8854\\\
\hline\cr\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}_{\text{PPBT}})&0.6250&0.7000&0.7500&0.7857&0.8125\\\
\hline\cr\end{array}$

To optimize this problem we used the Julia programming language along with
quantum package QuantumInformation.jl[32] and SDP optimization via SCS solver
[33, 34] with a precision $\epsilon=10^{-8}$. The code is available on GitHub
[35].

We compare the results obtained in this section in the Figure 6.

Figure 6: The average fidelity function (dimensionless)
$\mathcal{F}_{2}^{\text{avg}}$ calculated for $N\rightarrow 1$ learning
scheme: optimal adaptive strategy, $\mathcal{L}_{\text{Adaptive}}$ (numerical
value, blue squares); optimal parallel scheme, $\mathcal{L}_{\text{Parallel}}$
(numerical value, red crosses); learning scheme based on DPBT,
$\mathcal{L}_{\text{DPBT}}$ (green pentagons); pretty good learning scheme,
$\mathcal{L}_{\text{PGLS}}$ (orange diamonds); learning scheme based on PPBT,
$\mathcal{L}_{\text{PPBT}}$ (gray circles).

##  V Conclusions and discussion

In this work, we studied the problem of learning an unknown von Neumann
measurement of dimension $d$ from a finite number of copies. Our goal was to
find the asymptotic behavior of the maximum value for the average fidelity
function $F_{d}$. This value was maximized over all possible learning schemes,
and the average was taken over all von Neumann measurements. By using the
deterministic PBT protocol, we were able to state the lower bound
$1-\Theta\left(\frac{1}{N^{2}}\right)$, which matched the obtained upper bound
and hence, solved the given problem.

In the qubit case, we introduced a scheme called the pretty good learning
scheme. This scheme was a particular case of a parallel learning protocol, and
it used only two-qubit entangled memory states. The average fidelity function
calculated for the pretty good learning scheme behaved as
$1-\Theta\left(\frac{1}{N}\right)$. Moreover, we compared the performance of
different learning schemes: adaptive, parallel, based on DPBT, based on PPBT
and the pretty good learning scheme for the qubit case. Although, the learning
scheme based on PBT were asymptotically optimal, we showed that the pretty
good learning scheme outperforms it for low values of $N$.

This work paves the way toward a complete description of the capabilities of
von Neumann measurement learning schemes. One potential way forward is the
probabilistic storage and retrieval approach, widely studied for unitary
operations and phase rotations in [11, 12]. According to our numerical
results, the probability of retrieval of a quantum measurement in a parallel
scheme is exactly $N/(N+3)$, which corresponds to the value obtained in [11]
for unitary channels, while adaptive strategies for quantum measurements
learning to provide slightly higher probability, starting from $N\geq 3$.

## Acknowledgments

We would like to thank the anonymous reviewer for insightful comments and
suggestions, especially for introducing us the concept of port-based
teleportation, which provided the asymptotically optimal lower bound for the
fidelity value. This work was supported by the project „Near-term quantum
computers Challenges, optimal implementations and applications” Grant No.
POIR.04.04.00-00-17C1/18-00, which is carried out within the Team-Net
programme of the Foundation for Polish Science co-financed by the European
Union under the European Regional Development Fund. Paulina Lewandowska and
Ryszard Kukulski are holders of European Union scholarship through the
European Social Fund, grant InterPOWER (POWR.03.05.00-00-Z305).

## References

  * [1] M. Raginsky, “A fidelity measure for quantum channels,” Physics Letters A, vol. 290, no. 1-2, pp. 11–18, 2001.
  * [2] V. P. Belavkin, G. M. D’Ariano, and M. Raginsky, “Operational distance and fidelity for quantum channels,” Journal of Mathematical Physics, vol. 46, no. 6, p. 062106, 2005.
  * [3] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” Nature, vol. 299, no. 5886, pp. 802–803, 1982.
  * [4] M. A. Nielsen and I. L. Chuang, “Programmable quantum gate arrays,” Physical Review Letters, vol. 79, no. 2, p. 032324, 1997.
  * [5] V. Bužek and M. Hillery, “Quantum copying: Beyond the no-cloning theorem,” Physical Review A, vol. 54, no. 3, p. 1844, 1996.
  * [6] M. Hillery, V. Bužek, and M. Ziman, “Probabilistic implementation of universal quantum processors,” Physical Review A, vol. 65, no. 2, p. 022301, 2002.
  * [7] Y. Yang, R. Renner, and G. Chiribella, “Optimal universal programming of unitary gates,” Physical Review Letters, vol. 125, no. 21, p. 210501, 2020\.
  * [8] M. Gschwendtner, A. Bluhm, and A. Winter, “Programmability of covariant quantum channels,” Quantum, vol. 5, p. 488, 2021.
  * [9] A. Peres and P. F. Scudo, “Unspeakable quantum information,” arXiv preprint quant-ph/0201017, 2002.
  * [10] A. Bisio, G. Chiribella, G. M. D’Ariano, S. Facchini, and P. Perinotti, “Optimal quantum learning of a unitary transformation,” Physical Review A, vol. 81, no. 3, p. 032324, 2010.
  * [11] M. Sedlák, A. Bisio, and M. Ziman, “Optimal probabilistic storage and retrieval of unitary channels,” Physical Review Letters, vol. 122, no. 17, p. 170502, 2019.
  * [12] M. Sedlák and M. Ziman, “Probabilistic storage and retrieval of qubit phase gates,” Physical Review A, vol. 102, no. 3, p. 032618, 2020.
  * [13] S. Ishizaka and T. Hiroshima, “Asymptotic teleportation scheme as a universal programmable quantum processor,” Physical Review Letters, vol. 101, no. 24, p. 240501, 2008.
  * [14] S. Ishizaka and T. Hiroshima, “Quantum teleportation scheme by selecting one of multiple output ports,” Physical Review A, vol. 79, no. 4, p. 042306, 2009.
  * [15] M. Christandl, F. Leditzky, C. Majenz, G. Smith, F. Speelman, and M. Walter, “Asymptotic performance of port-based teleportation,” Communications in Mathematical Physics, vol. 381, no. 1, pp. 379–451, 2021.
  * [16] M. Sasaki and A. Carlini, “Quantum learning and universal quantum matching machine,” Physical Review A, vol. 66, no. 2, p. 022303, 2002.
  * [17] G. Sentís, J. Calsamiglia, R. Munoz-Tapia, and E. Bagan, “Quantum learning without quantum memory,” Scientific Reports, vol. 2, no. 1, pp. 1–8, 2012.
  * [18] V. Dunjko, J. M. Taylor, and H. J. Briegel, “Quantum-enhanced machine learning,” Physical Review Letters, vol. 117, no. 13, p. 130501, 2016.
  * [19] A. Monras, G. Sentís, and P. Wittek, “Inductive supervised quantum learning,” Physical Review Letters, vol. 118, no. 19, p. 190503, 2017.
  * [20] U. Alvarez-Rodriguez, L. Lamata, P. Escandell-Montero, J. D. Martín-Guerrero, and E. Solano, “Supervised quantum learning without measurements,” Scientific Reports, vol. 7, no. 1, pp. 1–9, 2017.
  * [21] M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko, “Quantum boltzmann machine,” Physical Review X, vol. 8, no. 2, p. 021050, 2018.
  * [22] G. Sentís, A. Monras, R. Munoz-Tapia, J. Calsamiglia, and E. Bagan, “Unsupervised classification of quantum data,” Physical Review X, vol. 9, no. 4, p. 041029, 2019.
  * [23] A. Bisio, G. M. D’Ariano, P. Perinotti, and M. Sedlák, “Quantum learning algorithms for quantum measurements,” Physics Letters A, vol. 375, no. 39, pp. 3425–3434, 2011.
  * [24] M.-D. Choi, “Completely positive linear maps on complex matrices,” Linear Algebra and its Applications, vol. 10, no. 3, pp. 285–290, 1975.
  * [25] A. Jamiołkowski, “Linear transformations which preserve trace and positive semidefiniteness of operators,” Reports on Mathematical Physics, vol. 3, no. 4, pp. 275–278, 1972.
  * [26] A. Bisio, G. Chiribella, G. D’Ariano, and P. Perinotti, “Quantum networks: general theory and applications,” Acta Physica Slovaca, vol. 61, no. 3, pp. 273–390, 2011.
  * [27] M. Studziński, S. Strelchuk, M. Mozrzymas, and M. Horodecki, “Port-based teleportation in arbitrary dimension,” Scientific reports, vol. 7, no. 1, pp. 1–11, 2017.
  * [28] M. Mozrzymas, M. Studziński, S. Strelchuk, and M. Horodecki, “Optimal port-based teleportation,” New Journal of Physics, vol. 20, no. 5, p. 053006, 2018.
  * [29] C. S. Mukherjee, S. Maitra, V. Gaurav, and D. Roy, “Preparing dicke states on a quantum computer,” IEEE Transactions on Quantum Engineering, vol. 1, pp. 1–17, 2020.
  * [30] J. Fiurášek, M. Dušek, and R. Filip, “Universal measurement apparatus controlled by quantum software,” Physical Review Letters, vol. 89, no. 19, p. 190401, 2002.
  * [31] N. Gisin and S. Popescu, “Spin flips and quantum information for antiparallel spins,” Physical Review Letters, vol. 83, no. 2, p. 432, 1999.
  * [32] P. Gawron, D. Kurzyk, and Ł. Pawela, “QuantumInformation.jl—a julia package for numerical computation in quantum information theory,” PLOS ONE, vol. 13, p. e0209358, dec 2018.
  * [33] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic optimization via operator splitting and homogeneous self-dual embedding,” Journal of Optimization Theory and Applications, vol. 169, pp. 1042–1068, June 2016.
  * [34] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, “SCS: Splitting conic solver, version 3.2.1.” https://github.com/cvxgrp/scs, Nov. 2021.
  * [35] https://github.com/iitis/storage-and-
retrieval-of-von-Neumann-measurements.  Permanent link to code/repository,
Accessed: 2022-09-21.

  * [36] J. Watrous, The Theory of Quantum Information.  Cambridge University Press, 2018.

##  Appendix A Proof of lower bound

######  Lemma 2.

Let us fix $d\in\mathbb{N}$ and let $\mathcal{L}$ be a parallel learning
scheme based on the DPBT protocol introduced in Section III.1. It holds that

$\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})=1-\Theta\left(\frac{1}{N^{2}}\right).$
(21)

###### Proof.

Let $\outerproduct{\psi_{0}}{\psi_{0}}$ and
$\mathcal{Q}_{0}=\\{Q_{0,i}\\}_{i=1}^{N}$ be a realization of the optimal
teleportation strategy $\mathcal{T}_{0}$, such that [15]

$F_{*}=\frac{1}{d^{2}}\tr\left(T_{0}\left|\left.{{{\rm
1l}_{d}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{{\rm
1l}_{d}}}\right.\right|\right)=1-\Theta\left(\frac{1}{N^{2}}\right).$ (22)

Let us introduce the operations
$\mathcal{Q}_{0,i}(\sigma)=\sqrt{Q_{0,i}}\sigma\sqrt{Q_{0,i}}$. Then, the
approximation $\mathcal{Q}_{U}$ acting on an arbitrary state $\rho$ can be
expressed as

$\begin{split}\mathcal{Q}_{U}(\rho)&=\sum_{i=1}^{N}\tr_{\mathcal{H}_{d}^{(in)}\otimes\mathcal{H}_{d^{N}}^{(A)}\otimes\mathcal{H}_{d^{N-1}}^{(\bar{B}_{i})}}\left(\left(\mathcal{Q}_{0,i}\otimes\mathcal{P}_{U}^{\otimes
N}\right)(\rho\otimes\outerproduct{\psi_{0}}{\psi_{0}})\right)\\\
&=\mathcal{P}_{U}\left(\sum_{i=1}^{N}\tr_{\mathcal{H}_{d}^{(in)}\otimes\mathcal{H}_{d^{N}}^{(A)}\otimes\mathcal{H}_{d^{N-1}}^{(\bar{B}_{i})}}\left(\left(\mathcal{Q}_{0,i}\otimes\mathcal{I}_{d^{N}}\right)(\rho\otimes\outerproduct{\psi_{0}}{\psi_{0}})\right)\right)=\mathcal{P}_{U}(\mathcal{T}_{0}(\rho)).\end{split}$
(23)

Let $J_{\Delta}=\sum_{i=0}^{d-1}\outerproduct{i}{i}\otimes\outerproduct{i}{i}$
be the Choi matrix of the completely dephasing channel $\Delta$. By using the
equality
$\mathcal{F}_{d}(\mathcal{P}_{U},\mathcal{Q}_{U})=\frac{1}{d}\tr(P_{U}Q_{U})$
we obtain

$\begin{split}\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})&=\frac{1}{d}\int_{U}dU\tr(P_{U}Q_{U})=\frac{1}{d}\int_{U}dU\tr\left((U\otimes\overline{U})J_{\Delta}(U\otimes\overline{U})^{\dagger}T_{0}\right)\\\
&=\frac{1}{d}\tr\left(\frac{1}{d+1}({\rm 1l}_{d^{2}}+\left|\left.{{{\rm
1l}_{d}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{{\rm
1l}_{d}}}\right.\right|)T_{0}\right)=\frac{1}{d+1}+\frac{d}{d+1}F_{*}\\\
&=1-\Theta\left(\frac{1}{N^{2}}\right),\end{split}$ (24)

which completes the proof. ∎

##  Appendix B Proof of Lemma 1

Figure 7:  The schematic representation of a learning scheme
$\mathcal{L}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N-1},\mathcal{R}\right)$.

Let $d=2$ and let us fix $N\in\mathbb{N}$. In the $N\rightarrow 1$ learning
scheme of single-qubit von Neumann measurements we have access to $N$ copies
of a given measurement $\mathcal{P}_{U}$, which is parameterized by some
unitary matrix $U\in\mathrm{M}(\mathcal{H}_{2})$. Let us consider a general
single-qubit von Neumann measurement learning scheme $\mathcal{L}$, which is
depicted in Fig. 7. The Choi-Jamiołkowski representation of $\mathcal{L}$ is
given as $L=\sum_{i=0}^{1}\outerproduct{i}{i}\otimes L_{i}$, where
$\ket{i}\in\mathcal{H}_{2}^{(out)}$. The result of composition of all copies
of $\mathcal{P}_{U}$ and the scheme $\mathcal{L}$ is a measurement
$\mathcal{Q}_{U}=\\{Q_{U,0},Q_{U,1}\\}$, which is an approximation of
$\mathcal{P}_{U}$. To define the effects $Q_{U,i}$ we use the link product
[26] in the following way $\tr(\rho
Q_{U,i})=\tr\left(L_{i}^{\top}\left(\rho\otimes P_{U}^{\otimes
N}\right)\right)$ for $\rho\in\Omega(\mathcal{H}_{2})$ and $i=0,1$. Thus, we
can calculate the fidelity defined in Eq. (1) between $\mathcal{P}_{U}$ and
$\mathcal{Q}_{U}$

$\mathcal{F}_{2}(\mathcal{P}_{U},\mathcal{Q}_{U})=\frac{1}{2}\sum_{i=0}^{1}\tr(P_{U,i}Q_{U,i})=\frac{1}{2}\sum_{i=0}^{1}\tr\left[L_{i}^{\top}\left(P_{U,i}\otimes
P_{U}^{\otimes N}\right)\right].$ (25)

Finally, we can express the maximum value of the average fidelity function
$F_{2}$ defined in Eq. (3) as

$F_{2}=\max_{\mathcal{L}}\int_{U}dU\frac{1}{2}\sum_{i=0}^{1}\tr\left[L_{i}^{\top}\left(P_{U,i}\otimes
P_{U}^{\otimes N}\right)\right].$ (26)

In the following subsections we will upper bound $F_{2}$ by using this
simplified maximization formula.

###  B.1 Measurement learning via parallel storage of unitary transformations

Figure 8: Schematic representation of the setup, which we use to upper bound
$F_{2}$. In this scenario, we are given $N$ copies of unitary channel
$\Phi_{\bar{U}}$ in parallel. Our objective is to approximate the von Neumann
measurement $\mathcal{P}_{U}$.

In this section we consider a new learning scheme, presented in Fig. 8. In
this scheme, we are given $N$ copies of a unitary channel, $\Phi_{\bar{U}}$,
which we can use in parallel. Our goal is to approximate the measurement
$\mathcal{P}_{U}$ using the black box with the unitary channel
$\Phi_{\bar{U}}$ inside. To achieve this, we choose an initial memory state
$\ket{\psi}\in\mathcal{X}\otimes\mathcal{Y}$ and a retrieval binary
measurement $\mathcal{R}=\\{R_{0},R_{1}\\}$, such that
$R_{i}\in\mathrm{M}(\mathcal{Z}\otimes\mathcal{X}\otimes\mathcal{Y})$, where
$\mathcal{Z}=\mathcal{H}_{2}^{(in)},\mathcal{X}=\mathcal{H}_{2^{N}}$ and
$\mathcal{Y}=\mathcal{H}_{2^{N}}$. We maximize the value of the average
fidelity function, which will be denoted as $\widetilde{F_{2}}$. To calculate
$\widetilde{F_{2}}$ we may observe that for a given
$\rho\in\Omega(\mathcal{Z})$, the probability that outcome $i$ occurs is equal
$\tr\left(R_{i}\left(\rho\otimes({\bar{U}}^{\otimes N}\otimes{\rm
1l}_{a})\outerproduct{\psi}{\psi}({U^{\top}}^{\otimes N}\otimes{\rm
1l}_{a})\right)\right)$, where $a\coloneqq 2^{N}$. Therefore, we obtain

$\widetilde{F_{2}}=\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\int_{U}dU\frac{1}{2}\sum_{i=0}^{1}\tr\left[R_{i}\left((U\otimes{\bar{U}}^{\otimes
N}\otimes{\rm
1l}_{a})(\outerproduct{i}{i}\otimes\outerproduct{\psi}{\psi})(U^{\dagger}\otimes{U^{\top}}^{\otimes
N}\otimes{\rm 1l}_{a})\right)\right].$ (27)

######  Lemma 3.

Let $F_{2}$ be the fidelity function defined in Eq. (26) and
$\widetilde{F_{2}}$ be the fidelity function defined in Eq. (27). Then, it
holds that $F_{2}\leq\widetilde{F_{2}}$.

###### Proof.

First, we observe that each von Neumann measurement $\mathcal{P}_{U}$ can be
written as a composition of the completely dephasing channel $\Delta$ given by
$\Delta(X)=\sum_{i=0}^{1}\bra{i}X\ket{i}\outerproduct{i}{i}$, and a unitary
channel $\Phi_{U^{\dagger}}$. Equivalently, that means
$P_{U}=(\Delta\otimes\mathcal{I}_{2})\left(\left|\left.{{U^{\dagger}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\dagger}}}\right.\right|\right)$.
Due to the fact that the channel $\Delta$ is self-adjoint, we obtain

$\tr\left[L_{i}^{\top}\left(P_{U,i}\otimes P_{U}^{\otimes
N}\right)\right]=\tr\left[\left((\mathcal{I}_{2}\otimes(\Delta\otimes\mathcal{I}_{2})^{\otimes
N})(L_{i})\right)^{\top}\left(P_{U,i}\otimes\left|\left.{{U^{\dagger}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\dagger}}}\right.\right|^{\otimes
N}\right)\right].$ (28)

Note that
$\sum_{i=0}^{1}\outerproduct{i}{i}\otimes(\mathcal{I}_{2}\otimes(\Delta\otimes\mathcal{I}_{2})^{\otimes
N})(L_{i})$ represents the composition of the learning scheme $\mathcal{L}$
and $N$ copies of channels $\Delta$. If we omit processing channels $\Delta$,
we get the following upper bound on $F_{2}$ defined in Eq. (26)

$\begin{split}F_{2}&\leq\max_{\mathcal{L}}\int_{U}dU\frac{1}{2}\sum_{i=0}^{1}\tr\left[L_{i}^{\top}\left(P_{U,i}\otimes\left|\left.{{U^{\dagger}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\dagger}}}\right.\right|^{\otimes
N}\right)\right]\\\
&=\frac{1}{2}\max_{\mathcal{L}}\int_{U}dU\tr\left[L^{\top}\left(({\rm
1l}_{2}\otimes U)J_{\Delta}({\rm 1l}_{2}\otimes
U^{\dagger})\otimes\left|\left.{{U^{\dagger}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\dagger}}}\right.\right|^{\otimes
N}\right)\right],\end{split}$ (29)

where $J_{\Delta}$ is Choi-Jamiołkowski representation of $\Delta$. Observe
that the maximal value of the integral in above equation is achievable by
networks $\mathcal{L}$ which satisfy the following commutation relation

$[L,{\rm 1l}_{2}\otimes\bar{U}\otimes({\rm 1l}_{2}\otimes U)^{\otimes N}]=0,$
(30)

for any unitary matrix $U$. To argue this fact, for any $\mathcal{L}$ one can
define a learning network $\tilde{\mathcal{L}}$ given by

$\tilde{L}=\int_{U}dU\left(({\rm 1l}_{2}\otimes\bar{U})\otimes({\rm
1l}_{2}\otimes U)^{\otimes N}\right)L\left(({\rm 1l}_{2}\otimes
U^{\top})\otimes({\rm 1l}_{2}\otimes U^{\dagger})^{\otimes N}\right).$ (31)

It is not difficult to see that $\tilde{L}$ is a correctly defined Choi-
Jamiołkowski representation of a quantum learning network [26, Theorem 2.5],
which satisfies the relation Eq. (30). Moreover, for both $L$ and $\tilde{L}$
the value of the integral in Eq. (29) remains the same.

Figure 9: Schematic representations of the right-hand side of Eq. (29). With
probability $1/2$ we prepare one of basis states $\ket{0}$ or $\ket{1}$ and
calculate the probability that we obtain output $i$. Eq. (29) is then the
cumulative probability that provided the state $\outerproduct{i}{i}$ we
measure $i$. The learning scheme $\mathcal{L}$ is given as
$\mathcal{L}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N},\mathcal{R}\right)$
and the storage $\SS$ (marked with a dashed line) is defined as a composition
of an initial memory state $\sigma$ and processing channels
$\\{\mathcal{C}_{i}\\}_{i=1}^{N}$.

Let us divide $\mathcal{L}$ into a storage network $\SS$ and a retrieval
measurement $\mathcal{R}$, as shown in Fig. 9. We introduce the input space
$\mathcal{X}_{I}\coloneqq\bigotimes_{i=1}^{N}\mathcal{H}_{2}^{(2k)}$ (denoted
with numbers $2,4,\ldots,2N$ on Fig. 9) and the output space
$\mathcal{X}_{O}\coloneqq\bigotimes_{i=1}^{N}\mathcal{H}_{2}^{(2k-1)}$
(denoted with numbers $1,3,\ldots,2N-1$). Additionally, we define spaces
$\mathcal{H}_{2}^{(in)},\mathcal{H}_{2}^{(out)}$ and $\mathcal{H}_{s}$. The
space $\mathcal{H}_{s}$ has arbitrary dimension $s$, but not smaller than the
dimension of $\mathcal{X}_{I}\otimes\mathcal{X}_{O}$. The storage $\SS$ can be
realized as a sequence of isometry channels followed by a partial trace
operation [26, Theorem 2.6]. Therefore, by moving the partial trace operation
to the retrieval part, $\mathcal{R}$, we may assume that the storage $\SS$
consists of an initial pure state followed by a sequence of isometry channels.
In consequence, the Choi-Jamiołkowski matrix of $\SS$ has the form
$S=\left|\left.{{X}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{X}}\right.\right|$.
There exists an isometry
$V\in\mathrm{M}\left(\mathcal{H}_{s},\mathcal{X}_{I}\otimes\mathcal{X}_{O}\right)$,
such that $X=\sqrt{\tr_{\mathcal{H}_{s}}S}V^{\top}$. In this notation, $S$ is
the solution of $S=({\rm 1l}_{4^{N}}\otimes
V)\left|\left.{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right.\right|({\rm
1l}_{4^{N}}\otimes V)^{\dagger}.$ Hence, the isometry channel $V\cdot
V^{\dagger}$ can be treated as a postprocessing of the storage $\SS$ and also
viewed as a part of the retrieval $\mathcal{R}$. In summary, after all
changes, the storage $\SS$ is of the form
$S=\left|\left.{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right.\right|$.
By using the normalization property [26, Theorem 2.5] for the network
presented in Fig. 9, we obtain $\tr_{\mathcal{H}_{2}^{(out)}}L={\rm
1l}_{2}\otimes\tr_{\mathcal{H}_{s}}S.$ Therefore, using the property Eq. (30)
we have

$[\tr_{\mathcal{H}_{s}}S,({\rm 1l}_{2}\otimes U)^{\otimes N}]=0.$ (32)

Let us define the memory state $\sigma_{\Phi_{U^{\dagger}},\SS}$ as an
application of the storage $\SS$ on $N$ copies of $\Phi_{U^{\dagger}}$. Then,
we have

$\begin{split}\sigma_{\Phi_{U^{\dagger}},\SS}&=\tr_{\mathcal{X}_{I}\otimes\mathcal{X}_{O}}\left[\left|\left.{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right.\right|\left(\left|\left.{{U^{\top}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\top}}}\right.\right|^{\otimes
N}\otimes{\rm 1l}_{4^{N}}\right)\right]\\\
&=\tr_{\mathcal{X}_{I}\otimes\mathcal{X}_{O}}\left[\left|\left.{{({\rm
1l}_{2}\otimes U^{\dagger})^{\otimes
N}\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{({\rm
1l}_{2}\otimes U^{\dagger})^{\otimes
N}\sqrt{\tr_{\mathcal{H}_{s}}S}}}\right.\right|\left(\left|\left.{{{\rm
1l}_{2}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{{\rm
1l}_{2}}}\right.\right|^{\otimes N}\otimes{\rm 1l}_{4^{N}}\right)\right]\\\
&=\left({\rm 1l}_{2}\otimes\bar{U}\right)^{\otimes
N}\outerproduct{\psi}{\psi}\left({\rm 1l}_{2}\otimes U^{\top}\right)^{\otimes
N},\end{split}$ (33)

where the last equality uses the property Eq. (32) and introduced
$\ket{\psi}\coloneqq\left(\left\langle\\!\left\langle{{\rm
1l}_{2}}\right.\right|^{\otimes N}\otimes{\rm
1l}_{4^{N}}\right)\left|\left.{\sqrt{\tr_{\mathcal{H}_{s}}S}}\right\rangle\\!\right\rangle$.
It means that an arbitrary storage strategy $\SS$, which has access to $N$
copies of a unitary channel $\Phi_{U^{\dagger}}$ can be replaced with parallel
storage strategy of $N$ copies of a unitary channel $\Phi_{\bar{U}}$. By
exploiting this property to Eq. (29) we obtain

$\begin{split}F_{2}&\leq\frac{1}{2}\max_{\mathcal{L}}\int_{U}dU\tr\left[L^{\top}\left(({\rm
1l}_{2}\otimes U)J_{\Delta}({\rm 1l}_{2}\otimes
U^{\dagger})\otimes\left|\left.{{U^{\dagger}}}\right\rangle\\!\right\rangle\\!\\!\left\langle\\!\left\langle{{U^{\dagger}}}\right.\right|^{\otimes
N}\right)\right]\\\
&=\frac{1}{2}\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\SS\end{subarray}}\int_{U}dU\sum_{i=0}^{1}\tr\left[R_{i}(U\outerproduct{i}{i}U^{\dagger}\otimes\sigma_{\Phi_{U^{\dagger}},\SS})\right]\\\
&=\frac{1}{2}\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}_{I}\otimes\mathcal{X}_{O})\end{subarray}}\int_{U}dU\sum_{i=0}^{1}\tr\left[R_{i}\left(U\outerproduct{i}{i}U^{\dagger}\otimes({\rm
1l}_{2}\otimes\bar{U})^{\otimes N}\outerproduct{\psi}{\psi}({\rm
1l}_{2}\otimes U^{\top})^{\otimes
N}\right)\right]=\widetilde{F_{2}}.\end{split}$ (34)

∎

###  B.2 Objective function simplification

The aim of this section is to simplify the maximization of the fidelity
function $\widetilde{F_{2}}$ defined in Eq. (27). Let us consider a binary
measurement $\mathcal{R}=\\{R_{0},R_{1}\\}$ taken from the maximization domain
in Eq. (27). It holds that $R_{0}+R_{1}={\rm 1l}_{2^{2N+1}}$, and hence we may
write

$\begin{split}\widetilde{F_{2}}&=\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\int_{U}dU\frac{1}{2}\sum_{i=0}^{1}\tr\left[R_{i}\left((U\otimes{\bar{U}}^{\otimes
N}\otimes{\rm
1l}_{a})(\outerproduct{i}{i}\otimes\outerproduct{\psi}{\psi})(U^{\dagger}\otimes{U^{\top}}^{\otimes
N}\otimes{\rm 1l}_{a})\right)\right]\\\
&=\frac{1}{2}+\frac{1}{2}\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\int_{U}dU\tr\left[R_{0}\left((U\otimes{\bar{U}}^{\otimes
N}\otimes{\rm
1l}_{a})(\sigma_{z}\otimes\outerproduct{\psi}{\psi})(U^{\dagger}\otimes{U^{\top}}^{\otimes
N}\otimes{\rm 1l}_{a})\right)\right]\\\
&=\frac{1}{2}+\frac{1}{2}\max_{\begin{subarray}{c}\mathcal{R}=\\{R_{0},R_{1}\\}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\tr\left[\int_{U}dU(U^{\dagger}\otimes{U^{\top}}^{\otimes
N}\otimes{\rm 1l}_{a})R_{0}(U\otimes\bar{U}^{\otimes N}\otimes{\rm
1l}_{a})(\sigma_{z}\otimes\outerproduct{\psi}{\psi})\right],\end{split}$ (35)

where $\sigma_{z}=\outerproduct{0}{0}-\outerproduct{1}{1}$. Observe that,
taking the average value of the matrix $R_{0}$ over the unitary group
$\\{U\otimes\bar{U}^{\otimes N}\otimes{\rm 1l}_{a}\\}_{U}$ is equivalent to
taking $R$ such that $0\leq R\leq{\rm 1l}_{2^{2N+1}}$ and
$[R,U\otimes\bar{U}^{\otimes N}\otimes{\rm 1l}_{a}]=0$ for any qubit unitary
matrix $U$. Equivalently, we may write $[R^{\top_{\mathcal{Z}}},U^{\otimes
N+1}\otimes{\rm 1l}_{a}]=0$, where $\cdot^{\top_{\mathcal{Z}}}$ represents the
partial transposition over subsystem $\mathcal{Z}$. According to [36, Theorem
7.15] the matrix $R^{\top_{\mathcal{Z}}}$ commutes with $U^{\otimes
N+1}\otimes{\rm 1l}_{a}$ if and only if it is of the form

$R^{\top_{\mathcal{Z}}}=\sum_{\pi}W_{\pi}\otimes M_{\pi},$ (36)

where matrices $W_{\pi}\in\mathrm{M}(\mathcal{Z}\otimes\mathcal{X})$ represent
subsystem permutation matrices acting on $N+1$ qubit systems, according to the
equation

$W_{\pi}\ket{b_{0},b_{1},\ldots,b_{N}}=\ket{b_{\pi(0)},b_{\pi(1)},\ldots,b_{\pi(N)}},\,b_{k}\in\\{0,1\\}.$
(37)

The matrices $M_{\pi}$ belong to the set $\mathrm{M}(\mathcal{Y})$ and the
index $\pi$ goes over all permutations of the set $\\{0,\ldots,N\\}$. Hence,
we may simplify calculation of $\widetilde{F_{2}}$

$\widetilde{F_{2}}=\frac{1}{2}+\frac{1}{2}\max_{\begin{subarray}{c}R:\,\,0\leq
R\leq{\rm 1l}_{2^{2N+1}}\\\ R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\tr\left[R(\sigma_{z}\otimes\outerproduct{\psi}{\psi})\right].$
(38)

To simplify the calculation of $\widetilde{F_{2}}$ even further, we introduce
the following notation of basis states defined on $N+1$ qubit system with
fixed weight. We enumerate qubit subsystems with numbers $0,1,\ldots,N$. For
any subset $A_{k}\subset\\{1,\ldots,N\\}$, such that $|A_{k}|=k$ we define:

$\mathcal{H}_{2^{N}}\ni\ket{A_{k}}\coloneqq\bigotimes_{i=1}^{N}(\delta(i\in
A_{k})\ket{1}+\delta(i\not\in A_{k})\ket{0}).$ (39)

Consider the following subspaces of the $N+1$ qubit space:

$\mathcal{H}^{(k)}\coloneqq\text{span}\left(\ket{0}\ket{A_{k}},\ket{1}\ket{A_{k+1}}:A_{k},A_{k+1}\subset\\{1,\ldots,N\\}\right)$
(40)

for $k=-1,\ldots,N$, where the vectors exist if and only if the expression is
well-defined (for instance, the vectors $\ket{A_{-1}},\ket{A_{N+1}}$ do not
exist). In this notation, subspaces $\mathcal{H}^{(k)}$ constitute a
decomposition of $N+1$ qubit space,
$\mathcal{H}_{2^{N+1}}=\bigoplus_{k=-1}^{N}\mathcal{H}^{(k)}$. One may
observe, that the matrix $R$ appearing in the maximization domain of Eq. (38)
is block diagonal in the introduced decomposition (in the partition
$\mathcal{Z}\otimes\mathcal{X}/\mathcal{Y}$). For such retrieval $R$, let us
consider

$H_{R}=\tr_{\mathcal{Z}}\left(R(\sigma_{z}\otimes{\rm 1l}_{4^{N}})\right).$
(41)

Observe that the matrix $H_{R}$ is block diagonal in the decomposition

$\mathcal{H}_{2^{N}}=\bigoplus_{k=0}^{N}\text{span}(\ket{A_{k}}:A_{k}\subset\\{1,\ldots,N\\}).$
(42)

Hence, we will write $H_{R}$ as

$H_{R}=\bigoplus_{k=0}^{N}H_{R,k}.$ (43)

Utilizing the above observations, the maximization problem Eq. (38) can be
written as

$\begin{split}\widetilde{F_{2}}&=\frac{1}{2}+\frac{1}{2}\max_{\begin{subarray}{c}R:\,\,0\leq
R\leq{\rm 1l}\\\ R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes M_{\pi}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\tr\left[R(\sigma_{z}\otimes\outerproduct{\psi}{\psi})\right]=\frac{1}{2}+\frac{1}{2}\max_{\begin{subarray}{c}R:\,\,0\leq
R\leq{\rm 1l}\\\ R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes M_{\pi}\\\
\outerproduct{\psi}{\psi}\in\Omega(\mathcal{X}\otimes\mathcal{Y})\end{subarray}}\bra{\psi}H_{R}\ket{\psi}\\\
&=\frac{1}{2}+\frac{1}{2}\max_{k=0,\ldots,N}\max_{\begin{subarray}{c}R:\,\,0\leq
R\leq{\rm 1l}\\\ R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\end{subarray}}\lambda_{1}(H_{R,k})\end{split}$ (44)

where $\lambda_{1}(\cdot)$ stands for the largest eigenvalue and we used
shortcut ${\rm 1l}={\rm 1l}_{2^{2N+1}}$. Finally, we observe that
$H_{R}=-(\sigma_{x}^{\otimes N}\otimes{\rm 1l}_{a})H_{R}(\sigma_{x}^{\otimes
N}\otimes{\rm 1l}_{a})$, where
$\sigma_{x}=\outerproduct{0}{1}+\outerproduct{1}{0}$. It implies that
$H_{R,k}$ is unitarily equivalent to $-H_{R,N-k}$ for any $k$. We use this
fact to write the final simplification of $\widetilde{F_{2}}$. The following
lemma sums up all the considerations presented in this section.

######  Lemma 4.

For the fidelity function $\widetilde{F_{2}}$ defined in Eq. (27) it holds
that

$\widetilde{F_{2}}=\frac{1}{2}+\frac{1}{2}\max_{k=0,\ldots,\lfloor
N/2\rfloor}\max_{\begin{subarray}{c}R:\,\,0\leq R\leq{\rm 1l}\\\
R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\end{subarray}}\|H_{R,k}\|_{\infty}.$ (45)

###  B.3 Technical lemmas

In the following lemma we will observe that optimization problem in Eq. (45)
can be reduced to the case $k\in\mathbb{N},N=2k$.

######  Lemma 5.

Let $N\in\mathbb{N}$ and take $k$, such that $k\leq N/2$. It holds that

$\max_{\begin{subarray}{c}R:\,\,0\leq R\leq{\rm 1l}\\\
R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\end{subarray}}\|H_{R,k}\|_{\infty}\leq\max_{\begin{subarray}{c}\widetilde{R}:\,\,0\leq\widetilde{R}\leq{\rm
1l}\\\
\widetilde{R}=\sum_{\pi}\widetilde{W}_{\pi}^{\top_{\mathcal{Z}}}\otimes\widetilde{M}_{\pi}\end{subarray}}\|\widetilde{H}_{\widetilde{R},N-k}\|_{\infty},$
(46)

where the matrix $\widetilde{R}$ is defined for $\widetilde{N}=2(N-k)$ and
hence the number of systems on which the matrix $\widetilde{W}_{\pi}$ acts is
$\widetilde{N}+1$.

###### Proof.

Let us fix $R$ such that $0\leq R\leq{\rm 1l}$ and
$R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes M_{\pi}$. Define

$\widetilde{R}\coloneqq\sum_{\pi}\left(W_{\pi}^{\top_{\mathcal{Z}}}\otimes{\rm
1l}_{2^{N-2k}}\right)\otimes\left(M_{\pi}\otimes{\rm 1l}_{2^{N-2k}}\right).$
(47)

We see that matrix $\widetilde{R}$ is in the maximization domain of the right-
hand side of Eq. (46). Then, we have
$\widetilde{H}_{\widetilde{R}}=\tr_{\mathcal{Z}}\left(\widetilde{R}(\sigma_{z}\otimes{\rm
1l})\right)=\bigoplus_{l}\widetilde{H}_{\widetilde{R},l}$. The matrix
$\widetilde{H}_{\widetilde{R},N-k}$ is defined on the space spanned by the
vectors $\ket{A_{N-k}}\in\mathcal{H}_{2^{\widetilde{N}}}$ for
$A_{N-k}\subset\\{1,\ldots,\widetilde{N}\\}$. These vectors can be expressed
in the form $\ket{A_{N-k}}=\ket{B_{i}}\ket{B_{N-k-i}},$ where
$\ket{B_{i}}\in\mathcal{H}_{2^{N}}$ for $B_{i}$ such that $|B_{i}|=i$,
$B_{i}\subset\\{1,\ldots,N\\}$, and
$\ket{B_{N-k-i}}\in\mathcal{H}_{2^{N-2k}}$,
$B_{N-k-i}\subset\\{N+1,\ldots,\widetilde{N}\\}$. Then, we have

$\begin{split}(\bra{A_{N-k}}\otimes{\rm
1l})\widetilde{H}_{\widetilde{R},N-k}(\ket{A^{\prime}_{N-k}}\otimes{\rm
1l})=\innerproduct{B_{N-k-i}}{B^{\prime}_{N-k-i^{\prime}}}\left(\bra{B_{i}}\otimes{\rm
1l}\right)H_{R}\left(\ket{B^{\prime}_{i^{\prime}}}\otimes{\rm
1l}\right)\otimes{\rm 1l}.\end{split}$ (48)

The non-zero blocks exist if and only if $i=i^{\prime}$ and
$B_{N-k-i}=B^{\prime}_{N-k-i^{\prime}}$, so

$\widetilde{H}_{\widetilde{R},N-k}=\bigoplus_{i=k}^{N-k}\bigoplus_{\begin{subarray}{c}B_{N-k-i}:\\\
B_{N-k-i}\subset\\{N+1,\ldots,\widetilde{N}\\}\end{subarray}}H_{R,i}\otimes{\rm
1l}.$ (49)

That means

$\|\widetilde{H}_{\widetilde{R},N-k}\|_{\infty}=\max_{i=k,\ldots,N-k}\|H_{R,i}\|_{\infty}\geq\|H_{R,k}\|_{\infty}.$
(50)

∎

In the next lemma we will find the upper bound for Eq. (45) in the case $N=2k$
for $k\in\mathbb{N}$.

######  Lemma 6.

Let $k\in\mathbb{N}$ and $N=2k$. For matrices $R$ and $H_{R,k}$ defined in
Subsection B.2 we have

$\max_{\begin{subarray}{c}R:\,\,0\leq R\leq{\rm 1l}\\\
R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\end{subarray}}\|H_{R,k}\|_{\infty}\leq
1-\Theta\left(\frac{1}{k^{2}}\right).$ (51)

###### Proof.

Let us fix $R$ such that $0\leq R\leq{\rm 1l}$ and
$R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes M_{\pi}$. Through the rest of
the proof, by $B_{l}$ we denote subsets of $\\{1,\ldots,2k\\}$, such that
$|B_{l}|=l$, for $l=0,\ldots,2k$. Following the notation introduced in
Subsection B.2, we define four types of vectors:

  1. 1.

$\ket{+_{A_{k}}}=x\ket{0}\ket{A_{k}}+\sum\limits_{\begin{subarray}{c}B_{k+1}:\\\
|B_{k+1}\cap A_{k}|=k\end{subarray}}\ket{1}\ket{B_{k+1}}$,

  2. 2.

$\ket{-_{A_{k}}}=x\ket{1}\ket{A_{k}}+\sum\limits_{\begin{subarray}{c}B_{k-1}:\\\
|B_{k-1}\cap A_{k}|=k-1\end{subarray}}\ket{0}\ket{B_{k-1}}$,

  3. 3.

$\ket{\oplus_{A_{k}}}=\sum\limits_{\begin{subarray}{c}B_{k+1}:\\\ |B_{k+1}\cap
A_{k}|=1\end{subarray}}\ket{1}\ket{B_{k+1}}$,

  4. 4.

$\ket{\ominus_{A_{k}}}=\sum\limits_{\begin{subarray}{c}B_{k-1}:\\\
|B_{k-1}\cap A_{k}|=0\end{subarray}}\ket{0}\ket{B_{k-1}}$,

for each $A_{k}\subset\\{1,\ldots,2k\\}$ and some $x>0$. Now we define the
following matrices:

  1. 1.

$I_{+}=\sum_{A_{k}}\outerproduct{+_{A_{k}}}{A_{k}}$,

  2. 2.

$I_{-}=\sum_{A_{k}}\outerproduct{-_{A_{k}}}{A_{k}}$,

  3. 3.

$I_{\oplus}=\sum_{A_{k}}\outerproduct{\oplus_{A_{k}}}{A_{k}}$,

  4. 4.

$I_{\ominus}=\sum_{A_{k}}\outerproduct{\ominus_{A_{k}}}{A_{k}}$.

For arbitrary $A_{k},A^{\prime}_{k}\subset\\{1,\ldots,2k\\}$ we have

  1. 1.

$\innerproduct{+_{A_{k}}}{+_{A^{\prime}_{k}}}=x^{2}\delta(A_{k}=A^{\prime}_{k})+|\\{B_{k+1}:|B_{k+1}\cap
A_{k}|=k,|B_{k+1}\cap A^{\prime}_{k}|=k\\}|,$

  2. 2.

$\innerproduct{-_{A_{k}}}{-_{A^{\prime}_{k}}}=x^{2}\delta(A_{k}=A^{\prime}_{k})+|\\{B_{k-1}:|B_{k-1}\cap
A_{k}|=k-1,|B_{k-1}\cap A^{\prime}_{k}|=k-1\\}|,$

  3. 3.

$\innerproduct{\oplus_{A_{k}}}{\oplus_{A^{\prime}_{k}}}=|\\{B_{k+1}:|B_{k+1}\cap
A_{k}|=1,|B_{k+1}\cap A^{\prime}_{k}|=1\\}|,$

  4. 4.

$\innerproduct{\ominus_{A_{k}}}{\ominus_{A^{\prime}_{k}}}=|\\{B_{k-1}:|B_{k-1}\cap
A_{k}|=0,|B_{k-1}\cap A^{\prime}_{k}|=0\\}|.$

We can observe that if $A_{k}=A^{\prime}_{k}$, then the above inner products
are $x^{2}+k$, $x^{2}+k$, $k$, $k$, respectively. If $|A_{k}\cap
A^{\prime}_{k}|=k-1$ then all the inner products are equal to one. Finally, if
$|A_{k}\cap A^{\prime}_{k}|<k-1$ then we obtain all the inner products are
equal to zero. We note two useful facts about matrices
$I_{+},I_{-},I_{\oplus},I_{\ominus}$. Firstly, we have

$I_{+}^{\dagger}I_{+}+I_{\oplus}^{\dagger}I_{\oplus}=I_{-}^{\dagger}I_{-}+I_{\ominus}^{\dagger}I_{\ominus}.$
(52)

Secondly, one can show that

$\|I_{+}^{\dagger}I_{+}+I_{\oplus}^{\dagger}I_{\oplus}\|_{\infty}=x^{2}+2k+2k^{2}.$
(53)

As far as the first equality is straightforward, to show the second one, note
that for each $A_{k}$ there is exactly $k^{2}$ sets $A^{\prime}_{k}$ such that
$|A_{k}\cap A^{\prime}_{k}|=k-1$. This means that by the Birkhoff’s Theorem we
can express $I_{+}^{\dagger}I_{+}+I_{\oplus}^{\dagger}I_{\oplus}$ in the basis
given by vectors $\ket{A_{k}}$ as
$I_{+}^{\dagger}I_{+}+I_{\oplus}^{\dagger}I_{\oplus}=(x^{2}+2k){\rm
1l}+2\sum_{i=1}^{k^{2}}\Pi_{i},$ where $\Pi_{i}$ are permutation matrices. By
the triangle inequality we have that the spectral norm is no greater than
$x^{2}+2k+2k^{2}$. By taking the normalized vector
$\ket{x}\propto\sum_{A_{k}}\ket{A_{k}}$ we get
$\bra{x}\left(I_{+}^{\dagger}I_{+}+I_{\oplus}^{\dagger}I_{\oplus}\right)\ket{x}=x^{2}+2k+2k^{2}.$

To state the upper bound for $\|H_{R,k}\|_{\infty}$ we will use the definition
of $H_{R}$ from Eq. (41) and the decomposition from Eq. (43). For a given
$A_{k},A_{k}^{\prime}\subset\\{1,\ldots,2k\\}$ we have that

$\begin{split}(\bra{A_{k}}\otimes{\rm
1l}_{a})H_{R,k}(\ket{A^{\prime}_{k}}\otimes{\rm
1l}_{a})=\sum_{\begin{subarray}{c}\pi:\\\
\pi(A_{k})=A^{\prime}_{k}\end{subarray}}M_{\pi}-\sum_{\begin{subarray}{c}\pi:\\\
\pi(0,A_{k})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}=\sum_{\begin{subarray}{c}\pi:\\\
\pi(0)\neq 0,\\\
\pi(A_{k})=A^{\prime}_{k}\end{subarray}}M_{\pi}-\sum_{\begin{subarray}{c}\pi:\\\
\pi(0)\neq 0,\\\
\pi(0,A_{k})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}.\end{split}$ (54)

Let us now define

$\begin{split}G_{R,k}&=(I_{+}^{\dagger}\otimes{\rm 1l}_{a})R(I_{+}\otimes{\rm
1l}_{a})+(I_{\oplus}^{\dagger}\otimes{\rm 1l}_{a})R(I_{\oplus}\otimes{\rm
1l}_{a})-(I_{-}^{\dagger}\otimes{\rm 1l}_{a})R(I_{-}\otimes{\rm
1l}_{a})-(I_{\ominus}^{\dagger}\otimes{\rm 1l}_{a})R(I_{\ominus}\otimes{\rm
1l}_{a}).\end{split}$ (55)

Taking $A_{k},A_{k}^{\prime}\subset\\{1,\ldots,2k\\}$ we have:

$\begin{split}&(\bra{A_{k}}\otimes{\rm
1l}_{a})G_{R,k}(\ket{A^{\prime}_{k}}\otimes{\rm 1l}_{a})\\\
=&\left(x^{2}\sum_{\begin{subarray}{c}\pi:\\\
\pi(A_{k})=A^{\prime}_{k}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B^{\prime}_{k+1},\pi:\\\
|B^{\prime}_{k+1}\cap A^{\prime}_{k}|=k,\\\
\pi(0,A_{k})=B^{\prime}_{k+1}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B_{k+1},\pi:\\\
|B_{k+1}\cap A_{k}|=k,\\\
\pi(B_{k+1})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}+\sum_{\begin{subarray}{c}B_{k+1},B^{\prime}_{k+1},\pi:\\\
|B_{k+1}\cap A_{k}|=k,\\\ |B^{\prime}_{k+1}\cap A^{\prime}_{k}|=k,\\\
\pi(0,B_{k+1})=0,B^{\prime}_{k+1}\end{subarray}}M_{\pi}+\sum_{\begin{subarray}{c}B_{k+1},B^{\prime}_{k+1},\pi:\\\
|B_{k+1}\cap A_{k}|=1,\\\ |B^{\prime}_{k+1}\cap A^{\prime}_{k}|=1,\\\
\pi(0,B_{k+1})=0,B^{\prime}_{k+1}\end{subarray}}M_{\pi}\right)\\\
-&\left(x^{2}\sum_{\begin{subarray}{c}\pi:\\\
\pi(0,A_{k})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B^{\prime}_{k-1},\pi:\\\
|B^{\prime}_{k-1}\cap A^{\prime}_{k}|=k-1,\\\
\pi(A_{k})=0,B^{\prime}_{k-1}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B_{k-1},\pi:\\\
|B_{k-1}\cap A_{k}|=k-1,\\\
\pi(0,B_{k-1})=A^{\prime}_{k}\end{subarray}}M_{\pi}+\sum_{\begin{subarray}{c}B_{k-1},B^{\prime}_{k-1},\pi:\\\
|B_{k-1}\cap A_{k}|=k-1,\\\ |B^{\prime}_{k-1}\cap A^{\prime}_{k}|=k-1,\\\
\pi(B_{k-1})=B^{\prime}_{k-1}\end{subarray}}M_{\pi}+\sum_{\begin{subarray}{c}B_{k-1},B^{\prime}_{k-1},\pi:\\\
|B_{k-1}\cap A_{k}|=0,\\\ |B^{\prime}_{k-1}\cap A^{\prime}_{k}|=0,\\\
\pi(B_{k-1})=B^{\prime}_{k-1}\end{subarray}}M_{\pi}\right).\end{split}$ (56)

This can be simplified to

$\begin{split}&(\bra{A_{k}}\otimes{\rm
1l}_{a})G_{R,k}(\ket{A^{\prime}_{k}}\otimes{\rm 1l}_{a})\\\
=&\left(x^{2}\sum_{\begin{subarray}{c}\pi:\\\
\pi(A_{k})=A^{\prime}_{k}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B^{\prime}_{k+1},\pi:\\\
|B^{\prime}_{k+1}\cap A^{\prime}_{k}|=k,\\\
\pi(0,A_{k})=B^{\prime}_{k+1}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B_{k+1},\pi:\\\
|B_{k+1}\cap A_{k}|=k,\\\
\pi(B_{k+1})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}\right)\\\
-&\left(x^{2}\sum_{\begin{subarray}{c}\pi:\\\
\pi(0,A_{k})=0,A^{\prime}_{k}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B^{\prime}_{k-1},\pi:\\\
|B^{\prime}_{k-1}\cap A^{\prime}_{k}|=k-1,\\\
\pi(A_{k})=0,B^{\prime}_{k-1}\end{subarray}}M_{\pi}+x\sum_{\begin{subarray}{c}B_{k-1},\pi:\\\
|B_{k-1}\cap A_{k}|=k-1,\\\
\pi(0,B_{k-1})=A^{\prime}_{k}\end{subarray}}M_{\pi}\right).\end{split}$ (57)

Let us write the above as $(\bra{A_{k}}\otimes{\rm
1l}_{a})G_{R,k}(\ket{A^{\prime}_{k}}\otimes{\rm
1l}_{a})=\sum_{\pi}c_{\pi}M_{\pi}$, where $c_{\pi}$ are some constants. For
each $\pi$, let us determine the value of $c_{\pi}$:

  * •

For $\pi$ such that $\pi(0)=0,\pi(A_{k})=A_{k}^{\prime}$ we have
$c_{\pi}=x^{2}-x^{2}=0$.

  * •

For $\pi$ such that $\pi(0)=0,\pi(A_{k})\neq A_{k}^{\prime}$ we have
$c_{\pi}=0$.

  * •

For $\pi$ such that $\pi(0)\neq 0,\pi(A_{k})=A_{k}^{\prime}$ we have
$c_{\pi}=x^{2}+x+x=x^{2}+2x$.

  * •

For $\pi$ such that $\pi(0)\neq 0,\pi(A_{k})\neq
A_{k}^{\prime},\pi(0,A_{k})\neq 0,A_{k}^{\prime}$ there exists
$a_{0}\not\in\\{0\\}\cup A_{k}$, such that $\pi(a_{0})\in\\{0\\}\cup
A^{\prime}_{k}$. Therefore, we consider two sub-cases:

    * –

If for each $a\not\in\\{0\\}\cup A_{k}$ it holds $\pi(a)\not\in
A^{\prime}_{k}$, then $\pi(a_{0})=0$, $\pi(0)\in A^{\prime}_{k}$ and
$A^{\prime}_{k}\subset\pi(0,A_{k})$. Then, $c_{\pi}=x-x=0$.

    * –

If $\pi(a_{0})\in A^{\prime}_{k}$, then we have two options:

      * *

If $\pi(a_{0},A_{k})=0,A^{\prime}_{k}$, then $c_{\pi}=x-x=0$.

      * *

If $\pi(a_{0},A_{k})\neq 0,A^{\prime}_{k}$, then $c_{\pi}=0$.

  * •

For $\pi$ such that $\pi(0)\neq 0,\pi(0,A_{k})=0,A_{k}^{\prime}$ we have
$c_{\pi}=-x^{2}-x-x=-(x^{2}+2x)$.

Therefore, we can see that $G_{R,k}=(x^{2}+2x)H_{R,k}$. Then, utilizing Eq.
(52), Eq. (53) and Eq. (55) we get

$-(x^{2}+2k+2k^{2}){\rm 1l}\leq G_{R,k}\leq(x^{2}+2k+2k^{2}){\rm 1l},$ (58)

and finally we obtain
$\|H_{R,k}\|_{\infty}\leq\frac{x^{2}+2k+2k^{2}}{x^{2}+2x}.$ Minimizing over
$x>0$, we get for $x\approx 2k^{2}$ that $\|H_{R,k}\|_{\infty}\leq
1-\Theta(1/k^{2})$, which finishes this case of the proof. ∎

###  B.4 Proof of Lemma 1

###### Proof of Lemma 1.

We have the following sequence of conclusions

$\begin{array}[]{rlcl}F_{2}&\leq\widetilde{F_{2}}&&\mbox{(by
Eq.\leavevmode\nobreak\ \eqref{eq:fidelity-appendix}, Eq.\leavevmode\nobreak\
\eqref{eq:fidelity-new-appendix}, Lemma\leavevmode\nobreak\ \ref{lemma-
unitary-transformation})}\\\
&=\frac{1}{2}+\frac{1}{2}\max\limits_{k=0,\ldots,\lfloor
N/2\rfloor}\max\limits_{\begin{subarray}{c}R:\,\,0\leq R\leq{\rm 1l}\\\
R=\sum_{\pi}W_{\pi}^{\top_{\mathcal{Z}}}\otimes
M_{\pi}\end{subarray}}\|H_{R,k}\|_{\infty}&&\mbox{(by
Lemma\leavevmode\nobreak\ \ref{lemma-simply})}\\\
&\leq\frac{1}{2}+\frac{1}{2}\max\limits_{k=0,\ldots,\lfloor
N/2\rfloor}\max\limits_{\begin{subarray}{c}\widetilde{R}:\,\,0\leq\widetilde{R}\leq{\rm
1l}\\\
\widetilde{R}=\sum_{\pi}\widetilde{W}_{\pi}^{\top_{\mathcal{Z}}}\otimes\widetilde{M}_{\pi}\end{subarray}}\|\widetilde{H}_{\widetilde{R},N-k}\|_{\infty}&&\mbox{(by
Lemma\leavevmode\nobreak\ \ref{lemma-last})}\\\
&\leq\frac{1}{2}+\frac{1}{2}\max\limits_{k=0,\ldots,\lfloor
N/2\rfloor}1-\Theta\left(\frac{1}{(N-k)^{2}}\right)&&\mbox{(by
Lemma\leavevmode\nobreak\ \ref{lemma-k-2k})}\\\
&=1-\Theta\left(\frac{1}{N^{2}}\right).&&\end{array}$

∎

##  Appendix C Proof of upper bound

######  Lemma 7.

The maximum value of the average fidelity function, defined in Eq. (3) is
upper bounded by

$F_{d}\leq 1-\Theta\left(\frac{1}{N^{2}}\right).$ (59)

###### Proof.

The thesis is true for $d=2$ which follows from Lemma 1. Let us fix
$d\in\mathbb{N}$. Take the optimal learning scheme $\mathcal{L}$ such that it
achieves $\mathcal{F}_{d}^{\text{avg}}(\mathcal{L})=F_{d}$. Without loss of
the generality we assume that $\mathcal{L}$ satisfies

$[L,{\rm 1l}_{d}\otimes U\otimes({\rm 1l}_{d}\otimes\bar{U})]^{\otimes N}]=0$
(60)

for any unitary matrix $U\in\mathrm{M}(\mathcal{H}_{d})$. Then, for any $U$,
we have

$F_{d}=\mathcal{F}_{d}(\mathcal{P}_{U},\mathcal{Q}_{U})\leq\frac{d-1}{d}+\frac{1}{d}\min_{i}\tr(P_{U,i}Q_{U,i}).$
(61)

Moreover, for $j_{1}\neq j_{2}$ it holds

$\tr(P_{U,j_{1}}Q_{U,j_{2}})\leq\tr(P_{U,j_{1}}({\rm 1l}_{d}-Q_{U,j_{1}}))\leq
1-\min_{i}\tr(P_{U,i}Q_{U,i}).$ (62)

Now, we use $\mathcal{L}$ to construct a new learning scheme
$\mathcal{L}^{\prime}$ of qubit von Neumann measurements in the following way.

Let $\Pi\in\mathrm{M}(\mathcal{H}_{d})$ be a projector onto $\ket{0},\ket{1}$
and define an isometry matrix
$V=\sum_{i=0}^{1}\outerproduct{i}{i}\in\mathrm{M}(\mathcal{H}_{d},\mathcal{H}_{2})$.
Having access to unknown qubit von Neumann measurement $\mathcal{P}_{U}$ we
may use it to implement von Neumann measurement $\mathcal{P}_{U\oplus{\rm
1l}_{d-2}}$ acting on $\Omega(\mathcal{H}_{d})$. To do that, we take
$\sigma\in\Omega(\mathcal{H}_{d})$ and measure it in the following way

$\outerproduct{0}{0}\otimes\Pi\sigma\Pi+\outerproduct{1}{1}\otimes\sum_{i=2}^{d-1}\tr(\sigma\outerproduct{i}{i})\outerproduct{i}{i}.$
(63)

If on the first system we measure “$0$”, then we can project the state
$V^{\dagger}(\Pi\sigma\Pi)V$ into $\Omega(\mathcal{H}_{2})$ and measure it by
using $\mathcal{P}_{U}$. Otherwise, we do nothing. As a result we implemented
the measurement of the form

$\sum_{i=0}^{1}\tr(V^{\dagger}\sigma
VU\outerproduct{i}{i}U^{\dagger})\outerproduct{i}{i}+\sum_{i=2}^{d-1}\tr(\sigma\outerproduct{i}{i})\outerproduct{i}{i}=\mathcal{P}_{U\oplus{\rm
1l}_{d-2}}(\sigma).$ (64)

During the retrieval stage, we project the input state
$\rho\in\Omega(\mathcal{H}_{2})$ into $V\rho V^{\dagger}$. Moreover, as the
output of $\mathcal{L}$ is a classical label “$0$”, $\ldots$, “$d-1$”, to
finalize the construction of $\mathcal{L}^{\prime}$, all the labels “$1$”,
$\ldots$, “$d-1$” are returned as “$1$”.

For a given unitary matrix $U\in\mathrm{M}(\mathcal{H}_{2})$ and the learning
network $\mathcal{L}^{\prime}$ we may calculate

$\begin{split}\mathcal{F}_{2}(\mathcal{P}_{U},\mathcal{Q}_{U})&=\frac{1}{2}\left(\tr(VP_{U,0}V^{\dagger}Q_{U\oplus{\rm
1l}_{d-2},0})+\tr(VP_{U,1}V^{\dagger}({\rm 1l}_{d}-Q_{U\oplus{\rm
1l}_{d-2},0}))\right)\\\ &\geq\frac{1}{2}\min_{i}\tr(P_{U\oplus{\rm
1l}_{d-2},i}Q_{U\oplus{\rm 1l}_{d-2},i})+\frac{1}{2}\left(1-\tr(P_{U\oplus{\rm
1l}_{d-2},1}Q_{U\oplus{\rm 1l}_{d-2},0})\right)\\\
&\geq\min_{i}\tr(P_{U\oplus{\rm 1l}_{d-2},i}Q_{U\oplus{\rm 1l}_{d-2},i})\geq
dF_{d}-(d-1).\end{split}$ (65)

Therefore, we get

$dF_{d}-(d-1)\leq\mathcal{F}_{2}^{\text{avg}}(\mathcal{L}^{\prime})\leq
F_{2}\leq 1-\Theta\left(\frac{1}{N^{2}}\right),$ (66)

which ends the proof. ∎

##  Appendix D Pretty good learning scheme

The pretty good learning scheme
$\mathcal{L}_{PGLS}=\left(\sigma,\\{\mathcal{C}_{i}\\}_{i=1}^{N-1},\mathcal{R}\right)$
consists of the initial state $\sigma$, which is a tensor product of $N$
copies of the maximally entangled state
$\ket{\omega}=\frac{1}{\sqrt{2}}\left|\left.{{\rm
1l}_{2}}\right\rangle\\!\right\rangle$, processing channels
$\\{\mathcal{C}_{i}\\}_{i=1}^{N-1}$ that are responsible for majority voting
(see Section IV.1) and the measurement $\mathcal{R}=\\{R,{\rm 1l}-R\\}$. To
construct the effect $R$, we fix $N_{0}\in\mathbb{N}$ and take $n=N_{0}-1$.
Let us define

$s_{n}(k,m)\coloneqq\sum_{i=0}^{k}\sum_{j=0}^{n-k}\delta_{i+j-m}{k\choose
i}{n-k\choose j}(-1)^{n-k-j},$ (67)

being the convolution of binomial coefficients. We consider the effect $R$ of
the form

$\begin{split}R&=\sum_{k=0}^{n}\outerproduct{R_{k}}{R_{k}},\quad\text{ such
that}\ket{R_{k}}=\frac{\left|\left.{M_{k}}\right\rangle\\!\right\rangle}{||M_{k}||_{2}},\\\
\mathrm{M}(\mathcal{H}_{2},\mathcal{H}_{2^{n+1}})\ni
M_{k}&=\sum_{m=0}^{n+1}\frac{s_{n}(k,n-m)\ket{0}+s_{n}(k,n+1-m)\ket{1}}{\sqrt{n+1\choose
m}}\bra{D_{m}^{n+1}},\end{split}$ (68)

for $k=0,\ldots,n$.

######  Lemma 8.

Let $\ket{x}=\left[\begin{array}[]{cc}a\\\ b\end{array}\right]$,
$a,b\in\mathbb{C}$. Then, we have $M_{k}\ket{x}^{\otimes
n+1}=(a+b)^{k}(a-b)^{n-k}\ket{x}$.

###### Proof.

Direct calculations reveal

$\begin{split}M_{k}\ket{x}^{\otimes
n+1}&=\left[\begin{array}[]{cc}\sum_{m=0}^{n}{n+1\choose
n-m}\cdot\frac{s_{n}(k,m)}{{n+1\choose n-m}}a^{m+1}b^{n-m}\\\
\sum_{m=0}^{n}{n+1\choose n+1-m}\cdot\frac{s_{n}(k,m)}{{n+1\choose
n+1-m}}a^{m}b^{n+1-m}\end{array}\right]=\sum_{m=0}^{n}s_{n}(k,m)a^{m}b^{n-m}\ket{x}\\\
&=(a+b)^{k}(a-b)^{n-k}\ket{x}.\end{split}$ (69)

∎

To prove that $R$ is a valid effect, let us now define

$M\coloneqq\left[s_{n}(k,m)\right]_{k,m=0}^{n}$ (70)

and a diagonal matrix

$D\coloneqq\sum_{m=0}^{n}\frac{1}{{n\choose m}}\outerproduct{m}{m}.$ (71)

######  Lemma 9.

With the notation given above, it holds that $M^{2}=2^{n}{\rm 1l}_{n+1}$.

###### Proof.

First, observe that
$\mathbb{C}^{n+1}=\text{span}\left([x^{k}]_{k=0}^{n}:x\in\mathbb{C}\right).$
Let us take any vector of the form $\ket{x}\coloneqq[x^{k}]_{k=0}^{n}$, where
$x\in\mathbb{C}$. We have

$\begin{split}M\ket{x}&=\left[\sum_{m=0}^{n}s_{n}(k,m)x^{m}\right]_{k=0}^{n}=\left[(x+1)^{k}(x-1)^{n-k}\right]_{k=0}^{n}=(x-1)^{n}\left[\left(\frac{x+1}{x-1}\right)^{k}\right]_{k=0}^{n}.\end{split}$
(72)

Finally, we calculate

$\begin{split}M^{2}\ket{x}&=(x-1)^{n}\left(\frac{x+1}{x-1}-1\right)^{n}\left[\left(\frac{\frac{x+1}{x-1}+1}{\frac{x+1}{x-1}-1}\right)^{k}\right]_{k=0}^{n}=2^{n}\ket{x}.\end{split}$
(73)

∎

######  Lemma 10.

Using the notation presented above, we have the following equation
$MD=(MD)^{\top}$.

###### Proof.

We will show that $\bra{k}MD\ket{m}=\bra{m}MD\ket{k}$ for any
$m,k=0,\ldots,n$. W.l.o.g. we can assume that $k<m$. On the one hand, it holds
that

$\begin{split}\bra{k}MD\ket{m}&=\frac{s_{n}(k,m)}{\binom{n}{m}}=\sum_{\begin{subarray}{c}i=0,\ldots,k\\\
j=0,\ldots,n-k\\\
i+j=m\end{subarray}}\frac{(-1)^{n-k-j}\binom{k}{i}\binom{n-k}{j}}{\binom{n}{m}}=\sum_{i=\max\left(0,m+k-n\right)}^{k}\frac{(-1)^{n-k-m+i}\binom{k}{i}\binom{n-k}{m-i}}{\binom{n}{m}}\\\
&=(-1)^{n-k-m}\sum_{i=\max\left(0,m+k-n\right)}^{k}(-1)^{i}\frac{k!m!(n-k)!(n-m)!}{n!i!(k-i)!(m-i)!(n-k-m+i)!}.\end{split}$
(74)

On the other hand, we can calculate

$\begin{split}\bra{m}MD\ket{k}&=\frac{s_{n}(m,k)}{\binom{n}{k}}=\sum_{\begin{subarray}{c}i=0,\ldots,m\\\
j=0,\ldots,n-m\\\
i+j=k\end{subarray}}\frac{(-1)^{n-m-j}\binom{m}{i}\binom{n-m}{j}}{\binom{n}{k}}=\sum_{i=\max\left(0,m+k-n\right)}^{k}\frac{(-1)^{n-k-m+i}\binom{m}{i}\binom{n-m}{k-i}}{\binom{n}{k}}\\\
&=(-1)^{n-k-m}\sum_{i=\max\left(0,m+k-n\right)}^{k}(-1)^{i}\frac{k!m!(n-k)!(n-m)!}{n!i!(k-i)!(m-i)!(n-k-m+i)!},\end{split}$
(75)

which gives us the desired equality and completes the proof. ∎

######  Lemma 11.

The operator $R$ defined in Eq. (68) satisfies $0\leq R\leq{\rm 1l}_{2^{n+2}}$
and therefore $\mathcal{R}=\\{R,{\rm 1l}-R\\}$ is a valid POVM.

###### Proof.

Let us fix $N_{0}\in\mathbb{N}$ and take $n=N_{0}-1$. Let us consider a matrix
$X\coloneqq\frac{n+2}{n+1}MDM^{\top}$. On the one hand, by using Lemma 9 and
Lemma 10, we get

$X=\frac{n+2}{n+1}\left(MD\right)^{\top}M^{\top}=\frac{n+2}{n+1}D(M^{2})^{\top}=\frac{n+2}{n+1}2^{n}D.$
(76)

On the other hand, we have

$\begin{split}\tr\left(M_{k}^{\dagger}M_{k^{\prime}}\right)&=\sum_{m=0}^{n}\frac{s_{n}(k,m)s_{n}(k^{\prime},m)}{{n+1\choose
n-m}}+\sum_{m=0}^{n}\frac{s_{n}(k,m)s_{n}(k^{\prime},m)}{{n+1\choose
n+1-m}}\\\
&=\sum_{m=0}^{n}s_{n}(k,m)s_{n}(k^{\prime},m)\left[\frac{1}{{n+1\choose
n-m}}+\frac{1}{{n+1\choose n-m+1}}\right]\\\
&=\frac{n+2}{n+1}\sum_{m=0}^{n}\frac{s_{n}(k,m)s_{n}(k^{\prime},m)}{{n\choose
m}}=\bra{k}X\ket{k^{\prime}}.\end{split}$ (77)

Therefore, for all $k\not=k^{\prime}$ we get
$\tr\left(M_{k}^{\dagger}M_{k^{\prime}}\right)=0$. According to the definition
Eq. (68), we get $\innerproduct{R_{k}}{R_{k^{\prime}}}=\delta_{k,k^{\prime}}$,
which gives us $0\leq R\leq{\rm 1l}_{2^{n+2}}$.

∎

######  Lemma 12.

Let us fix $N_{0}\in\mathbb{N}$. The approximation
$\mathcal{Q}_{U}=\\{Q_{U,0},{\rm 1l}_{2}-Q_{U,0}\\}$ of the von Neumann
measurement $\mathcal{P}_{U}$ obtained in the pretty good learning scheme is
of the form

$\begin{split}Q_{U,0}=\frac{N_{0}}{N_{0}+1}P_{U,0}.\end{split}$ (78)

###### Proof.

Given a unitary matrix $U$ we take $P_{U,0}=\outerproduct{x}{x}$ for some unit
vector $\ket{x}\in\mathcal{H}_{2}$. Let us decompose the $(n+2)$-qubit space
in the following way $\mathcal{H}_{2^{n+2}}=\mathcal{Z}\otimes\mathcal{X}$,
where $\mathcal{Z}=\mathcal{H}_{2}$ and $\mathcal{X}=\mathcal{H}_{2^{n+1}}$.
In the proof of Lemma 11 we defined the matrix $X=\frac{n+2}{n+1}MDM^{\top}$
and showed that $X=\frac{n+2}{n+1}2^{n}D$, and
$\tr\left(M_{k}^{\dagger}M_{k^{\prime}}\right)=\bra{k}X\ket{k^{\prime}}$.
Therefore, for any $k=0,\ldots,n$ we have
$\|M_{k}\|_{2}^{2}=\frac{n+2}{n+1}\frac{2^{n}}{{n\choose k}}$. Due to this
fact and by Lemma 8, we may express the effect $Q_{U,0}$ as

$\begin{split}Q_{U,0}&=\tr_{\mathcal{X}}\left(\left({\rm
1l}_{2}\otimes\overline{P_{U,0}}^{\otimes n+1}\right)R\right)=\left({\rm
1l}_{2}\otimes\overline{\bra{x}}^{\otimes n+1}\right)R\left({\rm
1l}_{2}\otimes\overline{\ket{x}}^{\otimes
n+1}\right)=\sum_{k=0}^{n}\frac{1}{\|M_{k}\|_{2}^{2}}M_{k}\outerproduct{x}{x}^{\otimes
n+1}M_{k}^{\dagger}\\\
&=\sum_{k=0}^{n}\frac{1}{\|M_{k}\|_{2}^{2}}|a+b|^{2k}|a-b|^{2(n-k)}\outerproduct{x}{x}=\frac{n+1}{n+2}\sum_{k=0}^{n}\frac{{n\choose
k}}{2^{n}}|a+b|^{2k}|a-b|^{2(n-k)}\outerproduct{x}{x}\\\
&=\frac{n+1}{n+2}\frac{(|a+b|^{2}+|a-b|^{2})^{n}}{2^{n}}\outerproduct{x}{x}=\frac{n+1}{n+2}\outerproduct{x}{x},\end{split}$
(79)

which completes the proof. ∎