# Single-shot labeling of quantum observables

Nidhin Sudarsanan Ragini  Mario Ziman  RCQI, Institute of Physics, Slovak
Academy of Sciences, Dúbravská cesta 9, 84511 Bratislava, Slovakia

###### Abstract

We identify and study a particular class of distinguishability problems for
quantum observables (POVMs), in which observables with permuted effects are
involved, which we call as the labeling problem. Consequently, we identify the
binary observables those can be “labeled” perfectly. In this work, we study
these problems in the single-shot regime.

##  I Introduction

The lack of understanding of the individual action performed by a measurement
apparatus is the essence of most of quantum controversies. Quantum theory
provides a way to describe its probabilistic aspects for all practical
purposes. In particular, when one is interested to predict the statistics of
observed outcomes, each measurement outcome is fully determined by a positive
operator known as effect (see for example [1]). An effect itself does not
explain the physics, or form of the recorded event, but captures the
probabilities of its occurrence. In order to describe measurement statistics,
we assign labels and effects for all outcomes. While effects associated with
the measurement apparatus can be verified experimentally, the choice of labels
cannot be tested by the measurement apparatus itself.

In this paper, we consider the situation when the mathematical description of
effects is known; However, their connection to the labels are lost. The
question of outcomes’ labeling we are going to address is the task of
assigning a mathematical description to the unlabeled outcomes, assuming the
effects forming the observable are known. For example, consider a black box
with green and red diodes. Each time the measurement is accomplished one of
them shines and outcome is recorded. We know the meaurement apparatus is
designed to decide whether the measured atom is in its excited, or its ground
state. It is not perfect and the associated effects are
$E=\eta\outerproduct{e}{e}$ and
$G=(1-\eta)\outerproduct{e}{e}+\outerproduct{g}{g}$, respectively. The
parameter $\eta$ quantifies the imperfections in registration of excited
state. Now, is it possible to identify how the colors and effects are paired?
How many measurement runs are needed? It is straightforward to realize that
measuring the atom prepared in the ground state can lead only to outcome
described by the effect $G$. Therefore, the diode that shines in this
situation is necessarily described by the effect $G$. The task of outcome
labeling is accomplished and the labels (shining diodes) are identified with
effects.

It turns out that this question is a special case of the discrimination
problem whose origin stems from the seminal work of Helstrom [2], who
investigated the discrimination problem for quantum states. In particular, in
its simplest form we are given a black box device known to be either A or B.
Our task is to design an experiment enabling us to conclude whether A or B in
a single run of the experiment. The conclusions might be of various relevance
or significance. One of the measure is their averaged error probability, known
to justify operationally the choice of trace norm as the measure of
statistical distance between A and B [2]. The outcome labeling problem of
$n$-valued measurement aims to discriminate among $n!$ permutations of
different labelings, as such, among $n!$ devices. Unfortunately, very little
is known about decision problems beyond the binary case.

The performance of measurements is crucial for the successful development of
quantum technologies (see e.g. Ref. [3]). Therefore, the elementary, as well
as, foundational question of discrimination of quantum measurements has
attracted researchers and various versions and aspects of the problem has been
studied in Refs.[4, 5, 6, 7, 8, 9]. In all of them, either the labeling is
assumed to be known, or the equivalence classes ignoring the labelings are
considered as descriptions of unknown (and unlabeled) measurement devices. The
question of assigning unknown labels was not addressed explicitly. The closest
is the work in Ref. [10], where authors analyzed the minimum-error
discrimination of two SIC POVMs - one of them being an arbitrary, but fixed
permutation of the other. The question of labeling is about identification of
the permutation, however, in the mentioned paper the permutation is fixed,
thus, the problem is a binary decision problem that can be investigated in
single shot settings. However, the labeling problem for SIC POVM aims to
distinguish among $d^{2}!$ different permutations ($d$ is the Hilbert space
dimension of the measured system).

The paper is organized as follows. In Section II the general problem of
labeling is formulated. The Section III is focused on perfect labeling for
single shot settings. Minimum error labeling and unambiguous labeling are
studied in Sections IV and Section V, respectively. The Section VI introduces
the concept of antilabeling and the main results are summarized in Section
VII.

##  II Formulation of labeling problem

###  II.1 Mathematical tools

The mutually exclusive outcomes $x_{1},\dots,x_{n}$ of $n$-valued quantum
measurements are represented by effects, i.e. positive operators
$M_{1},\dots,M_{n}$, respectively, satisfying the normalization
$M_{1}+\cdots+M_{n}=I$. For most of the situations we can safely say the
measurements are collection of effects, however, rigorously, the measurements
are mappings assigning effects for particular outcomes. Let us denote by
$\Omega$ the ordered set of outcome labels $\Omega:=\\{x_{1},\cdots,x_{n}\\}$
and by $\mathcal{E}(\mathcal{H})$ the set of all effects. Then, a quantum
measurement is described by an observable, as a normalised positive operator-
valued measure (POVM) $\mathsf{M}:\Omega\to\mathcal{E}(\mathcal{H})$ with
$\mathsf{M}(x_{j})=M_{j}$. Alternatively, we can think of observables as
measure-and-prepare channels $\mathcal{M}$ transforming input states of the
measured system $\varrho$ into output states (effectively probability
distributions) of $n$-dimensional systems

$\mathcal{M}(\rho)=\sum_{x_{k}\in\Omega}\text{Tr}[\rho
M_{k}]\outerproduct{x_{k}}{x_{k}}\,.$ (1)

Once we have the channel form, the Choi-Jamiolkowski isomorphism [11, 12]
between completely positive maps and positive operators associates the
observable $\mathsf{M}$ with a positive operator

$\mathfrak{M}=(\mathcal{I}\otimes\mathcal{M})[\Psi_{+}]=\sum_{k}M_{k}^{\top}\otimes\outerproduct{x_{k}}{x_{k}}\,,$
(2)

where $\Psi_{+}$ is the (unnormalized) maximally entangled state on
$\mathcal{H}\otimes\mathcal{H}$ defined by
$\Psi_{+}:=\outerproduct{\psi_{+}}{\psi_{+}}$ with
$\ket{\psi_{+}}:=\sum_{j=1}^{d}\ket{j}\otimes\ket{j}$ and
$\ket{1},\dots,\ket{d}$ form an orthonormal basis of $\mathcal{H}$.

The mathematical framework describing the measurements of processes was
introduced and developed in Refs. [13, 14, 15]. The most general single-shot
experiment measuring the properties of quantum processes (channels) is
illustrated in Fig. 1. In particular, the channel under consideration
$\mathcal{M}$ acts on the subsystem of a bipartite test state $\varrho$ and,
subsequently, the output is measured by a bipartite test observable
$\mathsf{F}$ leading to outcome $\alpha$. Suppose the input subsystem of the
channel is associated with the Hilbert space $\mathcal{H}$ and its output is
associated with Hilbert space $\mathcal{K}$, thus, the channel $\mathcal{M}$
transforms operators $\mathcal{L}(\mathcal{H})$ into
$\mathcal{L}(\mathcal{K})$. Further, let us denote by $\mathcal{H}_{\rm anc}$
the Hilbert space associated with the anciliary subsystem, thus, the test
state $\varrho$ is a density operator from $\mathcal{L}(\mathcal{H}_{\rm
anc}\otimes\mathcal{H})$ and $F_{\alpha}\in\mathcal{L}(\mathcal{H}_{\rm
anc}\otimes\mathcal{K})$ is the effect associated with the outcome $\alpha$ of
the test observable $\mathsf{F}$. The outcome $\alpha$ occurs with probability
$p_{\alpha}=\text{tr}\left[(\mathcal{I}\otimes\mathcal{M})[\varrho]F_{\alpha}\right]$.

Figure 1: To measure a channel $\mathcal{M}$, we send a test state $\rho$
through an extended channel and perform a test observable $\mathsf{F}$ on the
evolved state. We can identify that the pair of state and observable
constitute the measurement procedure event and, as such, determines a quantum
tester $\mathsf{T}$. The reduced subsystems entering the unknown chanel is in
the state $\xi^{\top}$, where the transposition is used just to obtain simpler
expressions in the other formulas.

For any state $\varrho$ the Choi-Jamiolkowski isomorphism defines a completely
positive linear map
$\mathcal{R}_{\varrho}:\mathcal{L}(\mathcal{H}\otimes\mathcal{H})\to\mathcal{L}(\mathcal{H}_{\rm
anc}\otimes\mathcal{H})$ such that
$\varrho=(\mathcal{R}_{\varrho}\otimes\mathcal{I})[\Psi_{+}]$ (see Ref. [15]).
Using its dual $\mathcal{R}^{*}_{\rho}$ we obtain
$p_{\alpha}=\text{tr}\left[(\mathcal{I}\otimes\mathcal{M})(\mathcal{R}_{\varrho}\otimes\mathcal{I})[\Psi_{+}]F_{\alpha}\right]=\text{tr}\left[(\mathcal{I}\otimes\mathcal{M})[\Psi_{+}](\mathcal{R}^{*}_{\varrho}\otimes\mathcal{I})[F_{\alpha}]\right]$.
In the last expression we may identify the Choi-Jamiolkowski representation
$\mathfrak{M}$ of the tested channel $\mathcal{M}$ and introduce the so-called
_process effect_
$\mathsf{T}_{\alpha}=(\mathcal{R}^{*}_{\varrho}\otimes\mathcal{I})[F_{\alpha}]$
determining the probability of outcome $\alpha$ for any channel $\mathcal{M}$.
As a result we obtain the description of the process measurement by so-called
_tester_ being a collection of positive operators
$\mathsf{T}_{1},\dots,\mathsf{T}_{m}$
($\mathsf{T}_{\alpha}\in\mathcal{L}(\mathcal{H}\otimes\mathcal{K})$)
satisfying the normalization $\mathsf{T}_{1}+\cdots+\mathsf{T}_{m}=\xi\otimes
I$, where $\xi=(\text{tr}_{\mathcal{K}}[\rho])^{\top}$ is the transposition of
the reduced state of the subsystem passing through the unknown channel
$\mathcal{M}$. We recover Born-like formula $p_{\alpha}={\rm
tr}[\mathfrak{M}\mathsf{T}_{\alpha}]$ for the outcome probabilities.

Let us stress that for testing channels of measure-and-prepare form (Eq. 2)
the tester operators can be assumed, without loss of generality, to be of the
form
$\mathsf{T}_{\alpha}=\sum_{k}\mathsf{H}_{k}^{(\alpha)}\otimes\outerproduct{x_{k}}{x_{k}}$
[7], where for all $k$, the normalization
$\sum_{\alpha}\mathsf{H}_{k}^{(\alpha)}=\xi$ is satisfied and all
$\mathsf{H}_{k}^{(\alpha)}\in\mathcal{L}(\mathcal{H})$ are positive operators.

###  II.2 Labeling problem

The question of labeling takes place when the information on the mapping
$x_{k}\mapsto M_{k}$ is lost, but the collection of effects is known. If all
the effects are different, then for $n$-valued observable there are $n!$
different permutations how the outcomes can be paired with the effects.
Therefore, the goal of labeling problem is to discriminate among $n!$
permutations. Let us fix the order of effects and denote by
$\mathsf{M}_{\sigma}$ the observable obtained by $\sigma$ permutation. The
result of labeling is the identification of $\sigma$. In what follows we will
assume that all the permutations are equally likely, thus the apriori
information on $\sigma$ is represented by probability distribution
$\pi(\sigma)=1/n!$.

In the language of measure-and-prepare channels the labeling takes the form of
discrimination among channels, whose actions are given by
$\mathcal{M}_{\sigma}(A)=\sum_{k}{\rm
tr}[A\mathsf{M}_{k}]\outerproduct{x_{\sigma(k)}}{x_{\sigma(k)}}=P_{\sigma}\mathcal{M}_{\rm
id}(A)P_{\sigma}^{\dagger}$, where
$P_{\sigma}=\sum_{k}\ket{x_{\sigma(k)}}\bra{x_{k}}$ is the permutation
operator and ${\rm id}$ stands for the indentity permutation. Consequently for
the associated Choi operators it holds $\mathfrak{M}_{\sigma}=(I\otimes
P_{\sigma})\mathfrak{M}_{\rm{id}}(I\otimes P_{\sigma})^{\dagger}$. Let us
denote by $\mathsf{T}_{1},\dots\mathsf{T}_{m}$ ($m=n!$) the operators forming
the tester used to discriminate $\mathfrak{M}_{1},\dots,\mathfrak{M}_{m}$,
respectively. The performance is characterized by conditional probabilities
$p(\sigma|\sigma^{\prime})=\rm{tr}[\mathfrak{M}_{\sigma}\mathsf{T}_{\sigma^{\prime}}]$.
Intuitively, the closer this conditional probability is to
$\delta_{\sigma\sigma^{\prime}}$ the better, but there are various ways how to
quantify the performance. Most common one is the average error probability
$p_{\rm error}=1-\frac{1}{n!}\sum_{\sigma}p(\sigma|\sigma)$, where
$\frac{1}{n!}\sum_{\sigma}p(\sigma|\sigma)$ is the corresponding average
success probability. Minimizing this function one finds minimum error
labeling. Introducing additional inconclusive outcome $\mathsf{T}_{\rm
inconclusive}$ and demanding $p(\sigma|\sigma^{\prime})=0$ whenever
$\sigma\neq\sigma^{\prime}$ is known as unambigous labeling, for which the
conclusions are error-free, but the labeling fails with probability $p_{\rm
failure}=\frac{1}{n!}{\rm
tr}[\sum_{\sigma}\mathfrak{M}_{\sigma}\mathsf{T}_{\rm inconclusive}]$. When
$p_{\rm error}=p_{\rm failure}=0$ we speak about perfect labeling.

##  III Perfect labeling

Perfect discrimination of two quantum channels in single use,
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, corresponds to the scenario when
there is no error in each of the conclusions associated with the
discrimination task. That is, the average error
$p_{\text{e}}=\mu\text{Tr}\\{\mathfrak{M}_{1}\mathsf{T}_{2}\\}+(1-\mu)\text{Tr}\\{\mathfrak{M}_{2}\mathsf{T}_{1}\\}=0$,
where $\mu$ characterizes the a priori bias between the channels. In our case
there is no bias, thus both labelings are equally likely and $\mu=1/2$. The
condition itself (independently of $\mu$) translates to existence of testers
$\\{\mathsf{T}_{1},\mathsf{T}_{2}\\}$ with normalisation $\xi\otimes I$
satisfying [16, 15] the identity

$\mathfrak{M}_{1}(\xi\otimes I)\mathfrak{M}_{2}=O\,$ (3)

for some normalisation $\xi$. Let us recall this condition is necessary and
sufficient for the single-shot perfect distinguishability of quantum channels
and is replacing the orthogonality condition $\varrho_{1}\varrho_{2}=O$ for
perfect discrimination of two quantum states. In this section we will evaluate
the validity of this condition for the labeling problem.

###  III.1 Binary measurements

Let us start with the labeling of so-called binary observables characterized
by pair of effects $M_{1}$ and $M_{2}=I-M_{1}$. There are only two
permutations of outcomes determining observables $\mathsf{M}_{12}$ and
$\mathsf{M}_{21}$ associated with the following Choi operators

$\displaystyle\mathfrak{M}_{12}=M_{1}^{\top}\otimes\outerproduct{1}{1}+M_{2}^{\top}\otimes\outerproduct{2}{2}\,,$
(4)
$\displaystyle\mathfrak{M}_{21}=M_{1}^{\top}\otimes\outerproduct{2}{2}+M_{2}^{\top}\otimes\outerproduct{1}{1}\,.$
(5)

######  Theorem 1.

A binary observable associated with effects $M_{1},M_{2}$ ($M_{1}\neq M_{2}$)
can be perfectly labeled in a single-shot if and only if at least one of the
effect operators is rank deficient.

###### Proof.

If $M_{1}=M_{2}$, then the observable is labeled (in fact $M_{1}=M_{2}=1/2I$,
where $I$ is identity on $d$-dimensional system). If $M_{1}\neq M_{2}$, the
perfect discrimination condition $\mathfrak{M}_{12}(\xi\otimes
I)\mathfrak{M}_{21}=O$ implies

$M_{1}^{\top}\,\xi\,M_{2}^{\top}=O\,.$ (6)

Suppose both operators $M_{1}$, $M_{2}$ are invertible, then also their
transpositions are invertible and we may apply inverse operators to obtain
$\xi=O$ contradicting the assumption $\xi$ is a density operator. That is, no
binary observable with full rank effects can satisfy the perfect
discrimination condition. On the contrary, suppose that there exists at least
one state vector $\ket{\varphi}$ such that $M_{1}\ket{\varphi}=0$, or
$M_{2}\ket{\varphi}=0$. Then
$M_{1}^{\top}\outerproduct{\varphi}{\varphi}M_{2}^{\top}=0$, thus, the perfect
discrimination condition holds. ∎

This result is clear. If the measurement device is used only once at most one
of the outcomes is recorded. The purity of successful probe state
$\xi=\outerproduct{\varphi}{\varphi}$ implies the potential auxiliary system
is uncorrelated, rendering it irrelevant for labeling. Consequently, a single
click can only reveal some information about the recorded outcome. And, this
information is “negative” in the following sense. Recording an outcome implies
the effect is not the one having the vector $\varphi$ in its kernel. For
example, if $M_{1}\ket{\varphi}=0$, then the recorded outcome is not described
by the effect $M_{1}$. In the considered binary case this implies the
unrecorded outcome can be associated with $M_{1}$ and the recorded one with
$M_{2}$.

###  III.2 Non-binary measurements

We refer to an observable with more than two outcomes as non-binary. The
“negative” logic used to label binary observables cannot be extended to non-
binary ones. Knowing the recorded outcome is not described by an effect
$M_{1}$ does not help in general to identify neither the recorded, nor the
unrecorded outcomes. It is straightforward to see that the recording of a
single outcome of the unlabeled device cannot reveal information about all the
outcomes. As such, we can formulate the following theorem.

######  Theorem 2.

Perfect labeling of a non-binary observable with effects $M_{1},\dots,M_{n}$
(all different, i.e. $M_{j}\neq M_{k}$ for all $j\neq k$) requires at least
$(n-1)$ uses of the measurement device.

###### Proof.

Using the device once we record exactly one outcome that can be the subject of
labeling. In general, only recorded outcomes can be labeled, thus, $n$-valued
observable demands at least $n-1$ uses. ∎

Let us note that by identifying $n-1$ outcomes of the considered observable we
obtain a binary observable described by effects $X_{1}=M_{1}$ and
$X_{2}=M_{2}+\cdots+M_{n}$. This “binarisation” is a purely abstract
construction, because for the unlabeled device itself we do not know which
outcomes are identified. However, if it happens the conditions of Theorem 1
are met and $X_{2}$ is rank deficient, then we can label the outcome of non-
binary observable associated with $M_{1}$. In the second use of the device we
may choose a different binarisation and potentially label a different outcome.
Altogether there are $n$ different binarisations of this form, but exploiting
$n-1$ of them is sufficient to accomplish the goal of perfect labeling.

Let us stress that the condition that all the effects are different is
important. The situation might be different if some of the outcomes are
described by the same effects. In what follows we will show an example of non-
binary observable for which all outcomes can be labeled in single shot.
Consider an observable with effects $M_{1}=\outerproduct{\varphi}{\varphi}$
and
$M_{2}=M_{3}=\dots=M_{n}=\frac{1}{n-1}(I-\outerproduct{\varphi}{\varphi})\equiv
M_{1}^{\perp}$. Using the probe state $\ket{\varphi}$, the recorded outcome is
necessarily associated with the effect $M_{1}$, but simultaneously, the
remaining effects are described by the effect $M_{1}^{\perp}$. One use of the
observable is sufficient to accomplish perfect labeling. It is straightforward
to design similar pathological examples of $n$-valued observables that can be
perfectly labeled in $m$ uses for all $m\leq n$. But for generic observables
the number of outcomes determines the number of required uses to completely
label all the outcomes.

It also follows the single shot setting allows for partial labeling of the
recorded outcome. For example, consider an unlabeled observable with effects
$M_{1},\dots,M_{n}$ with $m$ identical effects, i.e.
$M_{1}=M_{2}=\cdots=M_{m}$ for $m<n$ (in case $m=n$ the outcomes are labeled).
Assume $\tilde{M}=M_{1}+\cdots+M_{m}=mM_{1}$ has eigenvalue one, then there
exist a vector state $\ket{\varphi}$ such that
$\tilde{M}\ket{\varphi}=\ket{\varphi}$. That is, if the state $\ket{\varphi}$
is measured, then necessarily the recorded outcome is associated with effect
$M_{1}$ and the task of partial labeling is accomplished. Let us note that
using the same state $\ket{\varphi}$ also in second use does not guarantee
labeling of another unlabeled outcome.

######  Proposition 1.

An effect $E\in\\{M_{1},\dots,M_{n}\\}$ can be partially labeled in a single
use of the observable, if and only if there are $1\leq m\leq n$ outcomes $j$
such that $M_{j}=E$ and the largest eigenvalue of the effect $E$ equals $1/m$.

###### Proof.

Let $\ket{\varphi}$ be eigenvector associated with the eigenvalue $1/m$. Then
the probability observing any of the outcomes $M_{j}\neq E$ equals
$\bra{\varphi}(\sum_{j:M_{j}\neq
E}M_{j})\ket{\varphi}=\bra{\varphi}(I-mE)\ket{\varphi}=0$. In other words,
only outcomes associated with $E$ can be recorded. Therefore, the observed
outcome is labeled by the effect $E$. ∎

##  IV Minimum-error labeling

In this section we will study limitations of single shot labeling for general
observables. That is, we will quantify optimal success probability for
labeling given the observable is binary and used only once, that is
encapsulated as the following the theorem.

######  Theorem 3.

The optimal minimum error probability for labeling a binary observable
associated with the effects $\\{M_{1},M_{2}\\}$ is given by

$\displaystyle p_{\text{e}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-||M_{1}-M_{2}||_{2})\,.$ (7)

###### Proof.

Consider a binary observable with effects $M_{1},M_{2}$. Following Eq.(4) we
denote by $\mathfrak{M}_{12}$ and $\mathfrak{M}_{21}$ the Choi operators
associated with two possible labelings. Let us denote by $\mathsf{T}_{12}$ and
$\mathsf{T}_{21}$ the elements of tester associated with the labelings
$\\{M_{1},M_{2}\\}$ and $\\{M_{2},M_{1}\\}$, respectively, and satisfying the
normalisation condition $\mathsf{T}_{12}+\mathsf{T}_{21}=\xi\otimes I$, where
$\xi$ is a density operator. The average error probability reads

$p_{\text{e}}=\frac{1}{2}\text{tr}[\mathsf{T}_{12}\mathfrak{M}_{21}]+\frac{1}{2}\text{tr}[\mathsf{T}_{21}\mathfrak{M}_{12}]\,.$
(8)

Using the definitions and tester’s normalization we obtain

$\displaystyle p_{\text{e}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\text{tr}\left[\mathsf{T}_{12}(\mathfrak{M}_{21}-\mathfrak{M}_{12})+(\xi\otimes
I)\mathfrak{M}_{12}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\text{tr}[\mathsf{T}_{12}((M_{1}^{T}-M_{2}^{T})\otimes(\outerproduct{1}{1}-\outerproduct{2}{2}))]+\frac{1}{2}\,.$

In the spectral form
$M_{1}^{T}-M_{2}^{T}=\sum_{x}\mu_{x}\ket{\omega_{x}}\bra{\omega_{x}}$, where
$\mu_{x}$ are real eigenvalues and $\ket{\omega_{x}}$ are the associated
eigenvectors. It follows the operator
$(M_{1}^{T}-M_{2}^{T})\otimes(\outerproduct{1}{1}-\outerproduct{2}{2})$ has
$2d$ eigenvalues $\pm\mu_{x}$ (including multiplicities) and error probability
equals

$\displaystyle p_{\text{e}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\sum_{x}\mu_{x}\bra{\omega_{x}\otimes
1}\mathsf{T}_{12}\ket{\omega_{x}\otimes 1}$
$\displaystyle\qquad-\frac{1}{2}\sum_{x}\mu_{x}\bra{\omega_{x}\otimes
2}\mathsf{T}_{12}\ket{\omega_{x}\otimes 2}$

In order to minimize the error probability we need to suppress positive terms
and maximize the negative one. The negativity, or positivity of the terms
depends solely on the value of $\mu_{x}$, because the operator
$\mathsf{T}_{12}$ is positive. We know there is one positive and one negative
term for each nonzero $|\mu_{x}|$. Set $\mathsf{T}_{12}$ to vanish on all
positive terms, i.e. $\mathsf{T}_{12}\ket{\omega_{x}\otimes j}=0$ if
$(-1)^{(j-1)}\mu_{x}$ is positive. Then,

$\displaystyle p_{\text{e}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}-\frac{1}{2}\sum_{x}|\mu_{x}|\bra{\omega_{x}\otimes
j_{x}}\mathsf{T}_{12}\ket{\omega_{x}\otimes j_{x}}\,,$

where $j_{x}=1$ if $\mu_{x}<0$ and $j_{x}=2$ if $\mu_{x}>0$. Due to
normalisation $\mathsf{T}_{12}\leq\xi\otimes I$, it follows
$\bra{\omega_{x}\otimes j}\mathsf{T}_{12}\ket{\omega_{x}\otimes
j}\leq\bra{\omega_{x}}\xi\ket{\omega_{x}}$. The numbers
$\bra{\omega_{x}}\xi\ket{\omega_{x}}$ define a probability, thus, the values
$q_{k}=\bra{\omega_{x}\otimes j_{x}}\mathsf{T}_{12}\ket{\omega_{x}\otimes
j_{x}}$ form a subnormalized probability distribution. Our goal is to maximize
the expression $\sum_{x}|\omega_{x}|q_{x}$ over subnormalized probability
distributions. It turns out, the maximum is achieved when
$\mathsf{T}_{12}=\ket{\omega_{x}\otimes j_{x}}\bra{\omega_{x}\otimes j_{x}}$
associated with the largest eigenvalue $|\mu_{x}|$. That is, the minimum error
probability equals

$\displaystyle p_{\text{e}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-\max_{x}|\mu_{x}|)=\frac{1}{2}(1-||M_{1}-M_{2}||_{2})\,,$
(9)

where $||\cdot||_{2}$ is the operator 2-norm defined as
$||X||_{2}=\sup_{\varphi\neq
0}\innerproduct{X\varphi}{X\varphi}/\innerproduct{\varphi}{\varphi}=\lambda_{\max}$,
where $\lambda_{\max}$ denotes the largest singular value of $X$.

∎

Because of the normalisation $M_{1}+M_{2}=I$ the identity
$M_{1}-M_{2}=2M_{1}-I$ holds. It follows the eigenvalues and eigenvectors of
$M_{1}$, $M_{2}$ and $M_{1}-M_{2}$ are related. Indeed, all the operators
mutually commute, because $[M_{1},M_{2}]=0$, hence, they share the same system
of eigenvectors. Let us denote by $\lambda_{x}$ the eigenvalues of $M_{1}$ and
$\kappa_{x}$ the eigenvalues of $M_{2}$. Then $\lambda_{x}+\kappa_{x}=1$ and
$\mu_{x}=\lambda_{x}-\kappa_{x}=2\lambda_{x}-1$. Consequently, the maximal
value of $|\mu_{x}|$ is achieved either for the maximal, or the minimal values
of $\lambda_{x}$. Let us denote by $\lambda_{\max}$ and $\lambda_{\min}$ the
maximal and the minimal eigenvalue of $M_{1}$. Let us stress that the minimal
eigenvalue of $M_{1}$ is the maximal one for $M_{2}$ and vice versa. It
follows the largest of the distances of the minimal and the maximal eigenvalue
from $1/2$ (being the value for which $\mu=0$) determines the value of the
minimum error probability. In particular, $|\mu_{x}|=1$ (perfect labeling)
only if either $\lambda_{\min}=0$, or $\lambda_{\max}=1$. The binary
observables with all the eigenvalues of $M_{1}$ close to $1/2$ are the ones
for which the minimum error is the largest, thus, the labeling is least
reliable.

The optimal labeling procedure consists of preparation of the state
$\ket{\omega_{x}}$ being the eigenvector of $M_{1}$ associated with the
maximal, or minimal eigenvalue $\lambda_{x}$ maximizing the value of
$|\mu_{x}|$. The effect $M_{1}$ is recorded with probability
$\lambda_{x}=\bra{\omega_{x}}M_{1}\ket{\omega_{x}}$ and the effect $M_{2}$
with probability $\kappa_{x}=\bra{\omega_{x}}M_{2}\ket{\omega_{x}}$. If
$\lambda_{x}>\kappa_{x}$, then we conclude the recorded outcome is $M_{1}$ and
unrecorded one is $M_{2}$. In this case the probability $\kappa_{x}$
characterizes the error and indeed introducing
$|\mu_{x}|=\lambda_{x}-\kappa_{x}$ into Eq. (9) we obtain
$p_{\text{e}}=(1-(\lambda_{x}-\kappa_{x}))/2=\kappa_{x}$. Similarly, if
$\lambda_{x}<\kappa_{x}$ we have $|\mu_{x}|=\kappa_{x}-\lambda_{x}$ and
$p_{\text{e}}=\lambda_{x}$, thus, the recorded outcome is labeled by the
effect $M_{2}$ and the unrecorded by $M_{1}$. In other words, in the optimal
minimum error labeling procedure we label the effect with the largest
eigenvalue by performing the unlabeled measurement on the associated
eigenvector state $\ket{\omega_{x}}$.

For nonbinary observables we are meeting with the same basic limitation.
Single shot can reveal the identity of unrecorded outcomes only if they are
described by an identical effect. In general, we can talk about error
probability for the question of partial labeling. That is, we use the
unlabeled measurement device once and label the recorded outcome by one of the
effects $M_{1},\dots,M_{n}$ forming the $n$-outcome observable. Suppose
$M_{x}\in\\{M_{1},\dots,M_{n}\\}$ is chosen to be the label for the recorded
outcome. Then $p_{\text{e}}=\sum_{j\neq x}{\rm tr}[\omega M_{j}]={\rm
tr}\left[\omega\sum_{j\neq x}M_{j}\right]={\rm tr}[\omega(I-M_{x})]=1-{\rm
tr}[\omega M_{x}]$ is the probability of error for labeling the recorded
outcome by $M_{x}$. It is minimized if $\tr{\omega M_{x}}$ is maximal. Finding
$\lambda_{\max}=\max_{j}||M_{j}||$, where $||\cdot||$ is the operator norm
that equals to the largest eigenvalue of $M_{j}$, we obtain the minimum error
probablity reads $p_{\text{e}}=1-\lambda_{\max}$ and
$\omega=\ket{\omega_{\max}}\bra{\omega_{\max}}$, where $\ket{\omega_{\max}}$
is the eigenvector associated with the eigenvalue $\lambda_{\max}$. Let us
denote by $M_{\max}$ the effect with eigenvalue $\lambda_{\max}$. In the
optimal partial labeling procedure the outcome recorded in the measurement of
$\ket{\omega_{\max}}$ is labeled by $M_{\max}$.

###  IV.1 Example: Biased coin-tossing binary observables

This family is formed by trivial effects $M_{1}=qI$ and $M_{2}=(1-q)I$. The
formula for minimum error probability implies $p_{\rm e}=1-\lambda_{\max}$,
where $\lambda_{\max}$ is the largest eigenvalue of $M_{1}$ and $M_{2}$.
Assuming $1/2\leq q\leq 1$ we have $\lambda_{\max}=q$. Interestingly, the
minimum error for this trivial observable can achieve any value including
perfect discrimination between $O$ and $I$ when $q=1$. For unbiased coin-
tossing observable ($q=1/2$) the minimum error equals 1/2. Nevertheless, this
is not completely correct. In particular, for unbiased situation no
verification is needed as both outcomes are described by the same effect and
there is nothing unknown about the labels. That is, contrary to the minimum-
error formula, but in accordance with the Theorem 1, the labeling in this case
is trivially free of any error.

##  V Unambiguous labeling

The discrimination procedure is unambiguous if so-called no-error conditions
are satisfied and inconclusive result is allowed. For the case of labeling of
binary observables this means

$\text{tr}[\mathfrak{M}_{12}\mathsf{T}_{21}]=\text{Tr}[\mathfrak{M}_{21}\mathsf{T}_{21}]=0\,,$
(10)

with the normalization
$\mathsf{T}_{12}+\mathsf{T}_{21}+\mathsf{T}_{?}=\xi\otimes I$. The operator
$\mathsf{T}_{?}$ is identified with the inconclusive result when no labeling
is made. The performance of unamiguous labeling is evaluated by the so-called
failure probability

$p_{\rm f}=\frac{1}{2}{\rm
tr}[\mathsf{T}_{?}(\mathfrak{M}_{12}+\mathfrak{M}_{21})]=\frac{1}{2}{\rm
tr}[\mathsf{T}_{?}]$ (11)

associated with the occurence of inconclusive result. The goal is to design a
tester $\mathsf{T}_{12},\mathsf{T}_{21},\mathsf{T}_{?}$ such that the failure
probability is minimized. A nontrivial solution is possible if the no-error
conditions can be satisfied for nonzero operators
$\mathsf{T}_{12},\mathsf{T}_{21}$. It follows $\mathfrak{M}_{12}$, or
$\mathfrak{M}_{21}$ must have nonempty kernels. This is possible only if at
least one of the effects $M_{1},M_{2}$ is rank deficient. However, Theorem 1
implies such observable can be perfectly labeled, thus $\mathsf{T}_{?}=O$
($p_{\rm f}=0$) and for binary observables the unambigous labeling reduces to
perfect labeling.

For nonbinary measurements the no-error conditions also require that at least
one of the effects is rank deficient. However, the single use of the unlabeled
measurement device does not provide sufficient information for the unamiguous
labeling of all effects. We may be able to label partially a particular effect
$E$, but all the situations are covered by Theorem 1. It follows the
unambigous effect labeling is always perfect in a sense the recorded results
are always conclusive.

##  VI Antilabeling

Analyzing the unambiguous labeling for non-binary measurements we can observe
the following. Although the no-error conditions do not allow us to label the
rank deficient effects $E$, we can still use the corresponding state
$\ket{\varphi}$, for which $E\ket{\varphi}=0$ as the probe state. It is
straightforward to see that recorded outcome cannot be labeled by the effect
$E$, because its probability in this case vanishes. Instead of assigning a
label for the recorded outcome we may exclude all the labels
$E\in\\{M_{1},\dots,M_{n}\\}$, for which $M_{j}\ket{\varphi}=0$.

This type of discrimination tasks was named antidistinguishability [17] and
following this we will call this process antilabeling. For binary case, it
trivially coincides with labeling, however, for non-binary case the question
is open. Since in this study we are focused only to single-shot protocols the
antilabeling can be also achieved only partially. That is, not all effects can
be excluded in single run of the experiment. The question of partial
antilabeling reduces to antilabeling of some fixed effect
$E\in\\{M_{1},\dots,M_{n}\\}$. Rank-deficiency is necessary and sufficient for
partial antilabeling of such effects. Let us stress that this is not the case
for the question of partial labeling.

Consider rank-one non-binary measurements, i.e.
$M_{j}=q_{j}\ket{\varphi_{j}}\bra{\varphi_{j}}$, such that
$\ket{\varphi_{j}}\neq\ket{\varphi_{k}}$ if $j\neq k$. In general, these
effects cannot be partially labeled unless $q_{j}=1$ for some $j$. However,
all of them can be partially antilabeled. It is sufficient to choose a probe
state $\ket{\varphi_{j}^{\perp}}$ and the recorded outcome cannot be described
by the effect $M_{j}=q_{j}\ket{\varphi_{j}}\bra{\varphi_{j}}$. It means the
recorded outcome is antilabeled not to be $M_{j}$. If there are more $M_{k}$
such that $M_{k}\ket{\varphi_{j}^{\perp}}=0$, then all such effects are also
antilabeled and we may conclude the recorded outcome is not labeled by any of
those effects $M_{k}$.

##  VII Summary

In this work, we introduced the problem of measurement labeling being a
special instance of discrimination problem. We completely characterized the
various form of labeling question given the unlabeled measurement device is
used only once (single-shot). In particular, we showed that perfect labeling
exist for binary observables if the effects are rank deficient (Theorem 1 ).
For non-binary measurements the perfect labeling generally requires more uses
of the measurement device (Theorem 2), however, we characterize the
measurements for which single shot is sufficient. The Proposition 1 speficies
conditions when single shot reveals partial information about the observed
outcomes, thus, perfectly labels particular outcomes. Further, we evaluated
the minimum-error probability for the case of binary measurements. We found
(Eq.(9)) it is proportional to 2-norm of the difference between effects
forming the observable, thus by the largest eigenvalue of the effects.
Unambiguous labeling for binary measurements reduces to perfect one. The case
of nonbinary measurements motivated us to introduce the concept of
antilabeling that excludes labels of the recorded outcomes instead of
identifying them.

The problem of labeling is a specific question that is not only of
foundational interest. Naturally, it refers to situations when the identity of
labels is not available, but how one can lost this type of information? It is
unlikely someone will question the description of detectors, for which clicks
simply means the particle is detected. However, detectors are used in more
sophisticated experiments to measure quantum properties of systems. In fact,
we typically combine many devices and clicks of different detectors, or their
combinations constitute different (more abstract) outcomes. The risk of
forgetting the labels does not originate in the physics itself, but in its
users. The labeling serves as a relatively simple tool to operationally
retrieve the identity of outcomes without the necessity to access (sometimes
invasively) the details of experimental setup.

## Acknowledgements

Authors acknowledges the support of projects APVV-22-0570 (DEQHOST) and VEGA
2/0183/21 (DESCOM). N.S.R. acknowledges Sk Sazim and Seyed Arash Ghoreishi for
discussions and providing insights into selected calculations. The same author
acknowledges Nana Siddhartha Yenamandala, and Leevi Leppäjärvi and Oskari
Kerppo for discussions regarding antidiscrimination.

## References

  * [1] T. Heinosaari and M. Ziman, The mathematical language of quantum theory: from uncertainty to entanglement, (Cambridge University Press, 2011).
  * [2] C. W. Helstrom, Quantum detection and estimation theory, J. Stat. Phys. 1, 231–252 (1969). https://doi.org/10.1007/BF01007479
  * [3] T. Heinosaari, D. Reitzner, A. Toigo, Anticipative measurements in hybrid quantum-classical computation, Phys. Rev. A 107, 032612 (2023)
  * [4] Z. Ji, Y. Feng, R. Duan, and M. Ying, Identification and distance measures of measurement apparatus, Phys. Rev. Lett. 96, 200401 (2006).
  * [5] M. Ziman and T. Heinosaari, Discrimination of quantum observables using limited resources, Phys. Rev. A 77, 042321 (2008).
  * [6] M. Ziman, T. Heinosaari, and M. Sedlák, Unambiguous comparison of quantum measurements, Phys. Rev. A 80, 052102 (2009).
  * [7] M. Sedlák and M. Ziman, Optimal single-shot strategies for discrimination of quantum measurements, Phys. Rev. A 90, 052312 (2014).
  * [8] Z. Puchala, L. Pawela, A. Krawiec, and R. Kukulski, Strategies for optimal single-shot discrimination of quantum measurements, Phys. Rev. A 98, 042103 (2018).
  * [9] Z. Puchala, L. Pawela, A. Krawiec, R. Kukulski, and M. Oszmaniec, Multiple-shot and unambiguous discrimination of von Neumann measurements, Quantum 5, 425 (2021).
  * [10] A. Krawiec, L. Pawela, and Z. Puchala, Discrimination of POVMs with rank-one effects, Quantum Inf. Processing 19, 1 (2020)
  * [11] M.-D. Choi, Completely positive linear maps on complex matrices, Linear algebra and its applications 10, 285 (1975).
  * [12] A. Jamiolkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Reports on Mathematical Physics 3, 275 (1972).
  * [13] G. Gutoski and J. Watrous, Toward a general theory of quantum games, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (2007) pp. 565–574.
  * [14] G. Chiribella, G. M. D’Ariano, P. Perinotti, Quantum Circuits Architecture, Phys. Rev. Lett. 101, 060401 (2008).
  * [15] M. Ziman, Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments, Phys. Rev. A 77, 062112 (2008).
  * [16] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Memory effects in quantum channel discrimination, Phys. Rev. Lett. 101, 180501 (2008).
  * [17] T. Heinosaari and O. Kerppo, Antidistinguishability of pure quantum states, J. Phys. A: Math. Theor. 51, 365303 (2018).