# Quantum-Secured Space-Air-Ground Integrated Networks: Concept, Framework,
and Case Study

Minrui Xu, Dusit Niyato, Zehui Xiong, Jiawen Kang, Xianbin Cao, Xuemin Sherman
Shen, and Chunyan Miao Minrui Xu, Dusit Niyato, and Chunyan Miao are with the
School of Computer Science and Engineering, Nanyang Technological University,
Singapore (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>ascymiao@ntu.edu.sg).Zehui Xiong is with the Pillar of Information Systems
Technology and Design, Singapore University of Technology and Design,
Singapore 487372, Singapore (e-mail: zehui_xiong@sutd.edu.sg).Jiawen Kang is
with the School of Automation, Guangdong University of Technology, China
(e-mail: kavinkang@gdut.edu.cn).Xianbin Cao is with the School of Electronic
and Information Engineering, Beihang University, Beijing 100191, China.
(e-mail: xbcao@buaa.edu.cn).Xuemin Sherman Shen is with the Department of
Electrical and Computer Engineering, University of Waterloo, Waterloo, ON,
Canada, N2L 3G1 (e-mail: sshen@uwaterloo.ca).

###### Abstract

In the upcoming 6G era, existing terrestrial networks have evolved toward
space-air-ground integrated networks (SAGIN), providing ultra-high data rates,
seamless network coverage, and ubiquitous intelligence for communications of
applications and services. However, conventional communications in SAGIN still
face data confidentiality issues. Fortunately, the concept of Quantum Key
Distribution (QKD) over SAGIN is able to provide information-theoretic
security for secure communications in SAGIN with quantum cryptography.
Therefore, in this paper, we propose the quantum-secured SAGIN which is
feasible to achieve proven secure communications using quantum mechanics to
protect data channels between space, air, and ground nodes. Moreover, we
propose a universal QKD service provisioning framework to minimize the cost of
QKD services under the uncertainty and dynamics of communications in quantum-
secured SAGIN. In this framework, fiber-based QKD services are deployed in
passive optical networks with the advantages of low loss and high stability.
Moreover, the widely covered and flexible satellite- and UAV-based QKD
services are provisioned as a supplement during the real-time data
transmission phase. Finally, to examine the effectiveness of the proposed
concept and framework, a case study of quantum-secured SAGIN in the Metaverse
is conducted where uncertain and dynamic factors of the secure communications
in Metaverse applications are effectively resolved in the proposed framework.

###### Index Terms:

Quantum key distribution, space-air-ground integrated networks, Metaverse

##  I Introduction

The growing interest in the sixth generation (6G) wireless networks,
particularly the comprehensive connectivity and trustworthiness offered by
space-air-ground integrated networks (SAGIN) [1], is pushing the current
communication infrastructure to its limits. However, secure communications of
SAGIN are under serious threats in the post-quantum era. Currently, symmetric-
key cryptography and public-key cryptography are used to protect the
confidentiality of sensitive data in SAGIN, which are no longer considered
safe with the advent of quantum computers [2]. For example, the integer
factorization and discrete logarithm problems can be easily compromised by a
quantum computer that is advanced in computational power and quantum
algorithms (e.g., Shor’s algorithm). Fortunately, data channels of SAGIN can
be secured by quantum cryptography, which uses quantum key distribution (QKD)
to provision secret cryptographic keys via quantum channels and key management
channels [3]. In the post-quantum era, communications in quantum-secured SAGIN
are expected to achieve the information-theoretic security with the guarantees
of the principles of quantum physics, as guaranteed by the quantum no-cloning
theorem and the Heisenberg’s uncertainty principle [4].

In quantum-secured SAGIN, the concept of QKD over SAGIN typically allows two
remote QKD nodes to exchange quantum bits (qubits) which encode classical bits
on quantum states, such as photons, through optical fibers or free space [4].
As shown in Fig. 1, the optical fiber-based QKD is a mature option based on
the wavelength-division multiplexing (WDM) technique to transmit qubits and
bits in the same fiber with a low loss and high stability. However, since
qubits are more vulnerable to propagation impairments and cannot be readily
amplified, the optical fiber-based QKD has limited distance requirements as
its secret-key rate decreases exponentially when the distance increases.
Therefore, as an alternative option, QKD via free space [5, 6, 7], e.g.,
satellite-based QKD and unmanned aerial vehicle (UAV)-based QKD, is more
effective to transmit qubits with advantages of wide coverage and high
flexibility. As a result, the concept of QKD over SAGIN, which comprises
optical fiber-based QKD from the terrestrial layer, satellite-based QKD from
the space layer, and UAV-based QKD from the aerial layer, provides a feasible
solution for quantum-secured SAGIN.

Although quantum-secured SAGIN is feasible through the concept of QKD over
SAGIN, an efficient service provisioning framework is still necessary to
manage and control QKD resources for optimizing the provisioning cost. To this
end, a universal framework is proposed to offer secret-key distribution
services to QKD nodes with security requests, i.e., secure communication
requests, which may contain different secret-key sizes, rates, and updating
periods [4]. By optimizing the deployment of QKD resources, such as QKD nodes
and links, the framework can cost-effectively provision QKD services. In
detail, the framework provides optical fiber-based QKD services statically
with a fixed and relatively low cost. However, only the stationary QKD
services may not be sufficient to secure the transmission of confidential data
in dynamic communication environments. Therefore, the uncertainty in secure
communication environments necessitates the provisioning of satellite- and
UAV-based QKD services, according to the real-time secure communication
requests flexibly with high cost.

To verify the effectiveness of the aforementioned concept and framework, the
Metaverse [8] is used as a use case where users and Metaverse applications
transmit data via quantum-secured SAGIN. The data generated and transmitted by
the Metaverse applications, such as extended reality (XR), digital twin, and
artificial intelligence (AI), are often communication-heavy, high-frequent,
and asynchronous. For example, Metaverse users receive immersive experiences
with their avatars in the 3D worlds of the Metaverse through XR, including
augmented reality (AR), virtual reality (VR), and mixed reality (MR). Since
each user can control multiple avatars in the Metaverse simultaneously, the
number of avatars in the Metaverse cannot be accurately predicted by the QKD
service provisioning framework. Second, due to the continuously varying
importance of the real-world environment, the transmission speed and update
frequency of the digital twins in the Metaverse also fluctuate. Third, the
number of AI models in the Metaverse also varies depending on the amount of AI
data and computational power (e.g., the number of workers in federated
learning [3]). Through the stochastic programming of QKD services, the
proposed universal framework is expected to resolve the uncertainty issues in
security requests and to minimize the provisioning cost. The experimental
results demonstrate that although providing QKD services for Metaverse
applications in quantum-secured SAGIN is an intricate problem, the proposed
stochastic programming model can still optimize the required cost of QKD
service provisioning.

Figure 1: The concept of QKD over SAGIN in quantum-secured SAGIN.

The main contributions of this article are summarized as follows:

  * •

We highlight the feasibility of the quantum-secured SAGIN through the concept
of QKD that we present. To the best of our knowledge, this is the first work
to propose a quantum-secured SAGIN where the QKD services can holistically
secure communications between space, air, and ground nodes using quantum
cryptography.

  * •

We propose a universal service provisioning framework to realize the concept
of QKD over SAGIN. With uncertain communications and security requirements in
quantum-secured SAGIN being taken into account, the proposed framework can
provide flexible QKD services while minimizing the provisioning cost in
quantum-secured SAGIN.

  * •

As a case study, we are pioneering in examining the effectiveness of quantum-
secured SAGIN and its service provisioning framework in supporting Metaverse
applications. By considering the uncertain factors in the communications of
Metaverse applications, the proposed framework can achieve an optimal
provisioning solution for QKD services. The experimental results show that the
proposed framework outperforms the existing baseline methods while addressing
the uncertainty of communication environments with the varying number of
avatars, digital twins, and AI models.

##  II The Concept of QKD over SAGIN and the Quantum-secured SAGIN

###  II-A The Basic Concept of QKD

QKD has recently been introduced as a provable secure key distribution
solution that can address many potential attacks, such as eavesdropping
attacks, in traditional key distribution schemes [9]. In practice, QKD is
often adopted in the setup phase of secure communications between two nodes
connected with QKD logical links for transmitting confidential data. During
the setup of secure communications between two QKD nodes, they first need to
agree on a global secret cryptographic key (i.e., a sequence of bits) via QKD
links, where any eavesdropping or hijacking behaviors during key agreement
process can be perceived due to the quantum no-cloning theorem [2]. Therefore,
in QKD logical links, their raw local secret keys are encoded as certain
quantum states of photons and transmitted in quantum channels while the
exchanged classical key information is verified and processed in the key
management channels.

###  II-B QKD over SAGIN

TABLE I: Summary of different QKD services in quantum-secured SAGIN QKD types |  Transmission media |  QKD protocols |  QKD resources |  Distance (km)
---|---|---|---|---
Optical fiber-based QKD |  Optical fibers |  Prepare-and-measure/ Entanglement-based QKD protocols |  Quantum transceivers, trusted/untrusted repeaters, quantum routers, quantum memory, QKD links |  $\sim$ 100
Satellite-based QKD |  Free space |  Entanglement-based QKD protocols |  Trusted quantum satellites, quantum memory, QKD links |  $\sim$ 1000
UAV-based QKD |  Free space |  Entanglement-based QKD protocols |  Trusted quantum UAVs, quantum memory, mobile QKD links |  $\sim$ 1

####  II-B1 Optical fiber-based QKD services

Existing conventional passive optical networks (PON) provide the maturest
implementation scenario for fiber-based QKD in the terrestrial layer. With the
WDM technique, qubits and bits can be transmitted together in the same optical
fiber with low loss and high stability. As the optical fiber-based QKD is
established upon the existing PON, its components are co-located with the
backbone nodes in PON. There are three types of QKD nodes in optical-based
QKD, i.e., quantum transmitters/receivers (transceivers), trusted/untrusted
repeaters, and quantum routers. Firstly, each quantum transceiver is a pair of
QKD equipment, including a quantum transmitter and a quantum receiver, that
can convert bits of local secret keys into qubits and convert qubits into bits
of global secret keys, respectively, via prepare-and-measure protocols, e.g.,
Bennett-Brassard-1984 (BB84), Grosshans-Grangier-2002 (GG02) [9]. Then, the
received secure keys are saved by their respective local key managers.
Extending from the above point-to-point scenario, optical fiber-based QKD with
trusted repeaters can distribute secret keys in a hop-by-hop manner to improve
the key distribution distance. Furthermore, in the measurement-device-
independent (MDI)-QKD protocol [10], untrusted repeaters typically have better
security than other prepare-and-measure protocols requiring only trusted
repeaters, which can remove the security infrastructure at the measurement
side. Therefore, the untrusted repeater can even be controlled by an
eavesdropper without compromising the safety of QKD. Therefore, MDI-QKD
protocols are capable of improving the secure distance and efficiency of QKD
considerably. Different from prepare-and-measure protocols, entanglement-based
protocols, such as Bennett-Brassard-Mermin-1992 (BBM92) [6], implement quantum
routers with quantum memory to distribute secret keys via quantum entanglement
of photons over different quantum channels. Between two adjacent quantum
routers, each external link is established where one of the qubits in a Bell
pair should be sent to the other quantum router of this external link, and
hence one unit of quantum memory on each router needs to be occupied [11].
Then, quantum routers perform entanglement swapping to measure the qubits and
route the result to the destination router via the internal link of an
entanglement connection. For the optical fiber-based QKD services in the
terrestrial layer, quantum transceivers and QKD links of trusted/untrusted
repeaters as well as quantum memory of quantum routers are collectively
regarded as QKD resources in provisioning QKD services over SAGIN.

####  II-B2 Satellite-based QKD services

Different from the optical fiber-based QKD in the terrestrial layer, the
satellite-based QKD in the space layer can provision QKD services to ground
QKD nodes from low earth orbit (LEO) satellites via free space [12]. Due to
scattering and absorption of polarized photons and other factors, the
requirements of trusted/untrusted repeaters to extend the coverage of optical
fiber-based QKD place an obstacle to developing metropolitan-level QKD
networks. Fortunately, satellite-based QKD in the space layer is a promising
scheme to distribute secret keys to ground QKD nodes via free space with less
atmospheric attenuation. China sent its first quantum satellite, called
Micius, into space in 2016 and completed an experimental satellite-to-ground
QKD in good weather and night conditions. In June 2020, Micius experimentally
demonstrated that satellite-based QKD could achieve a secret-key rate of 0.12
bits per second between two ground QKD nodes separated by 1120 km [6]. In
satellite-based QKD, satellites with are regarded as fully trusted quantum
relays to establish entanglement connections between a pair of ground QKD
nodes with polarization beam splitters to extend the coverage of optical
fiber-based QKD.

####  II-B3 UAV-based QKD services

Since satellites are orbit-limited and weather-constraint that are not able to
satisfy all the security requests on the ground, trusted UAVs carrying quantum
equipment can provide a reconfigurable solution to serve ground QKD nodes
regardless of their weather conditions. By transmitting quantum information as
“flying quantum bits”, UAVs in the aerial layer can secure communications in
SAGIN with a high degree of mobility and flexibility [12]. Specifically, two
UAVs can achieve mobile entanglement distribution via free-space quantum
channels and key management channels, with one distributing entangled photons
and the other acting as a relay node. However, beam-diffraction, which depends
on the beam aperture and the link distance, limits the distance of the UAV-
based QKD via free space. To address these issues, multiple UAVs can form
swarms or chains, to distribute the quantum entanglement collaboratively for
lossless propagation within the Rayleigh length limit. The experimental
results in [7] show that UAV-based QKD can achieve high-performance quantum
entanglement between two ground QKD nodes with polarization beam splitters at
a distance of about 1 km. Due to the inexpensive and flexible nature of UAV
swarms and chains, UAV-based QKD can provide reconfigurable QKD services in an
economical manner.

###  II-C Establishing Secure Communications in Quantum-secured SAGIN

In quantum-secured SAGIN, a pair of two QKD nodes can establish secure
communications via QKD links for transmitting confidential data. As shown in
Table I, If QKD nodes are directly or indirectly connected via optical fibers,
they can continuously receive secret keys from optical fiber-based QKD
services. Otherwise, QKD nodes can require the QKD services via free space
from quantum satellites or quantum UAVs. On the one hand, satellite-based QKD
services can distribute quantum entanglement in global coverage but are
limited by the orbits of satellites and the weather conditions of ground
nodes. On the other hand, UAV-based QKD can provision reconfigurable QKD
services regardless of the location and weather condition of ground nodes.
Through the concept of QKD over SAGIN, the quantum-secured SAGIN is feasible
with unparalleled mobility, flexibility, and reconfigured by provisioning the
QKD services via optical fibers, satellites, and UAVs synergistically.

##  III The Universal QKD Service Provisioning Framework in Quantum-secured
SAGIN

Figure 2: Different types of QKD resources in quantum-secured SAGIN. TCs,
quantum transceivers; QTs, MDI-QKD transmitters; QRs, MDI-QKD receivers.

###  III-A Provisioning Static QKD Services via Optical Fiber-based QKD

In the terrestrial layer of the quantum-secured SAGIN, optical fiber-based QKD
is able to provision static QKD services by allocating QKD resources in terms
of QKD nodes, e.g., quantum transceivers, trusted/untrusted repeaters, quantum
routers, and QKD links, as shown in Fig. 2. In quantum-secured SAGIN,
cryptographic applications initiate requests for QKD services to the QKD
global manager. After receiving these QKD service requests, the QKD global
manager sends instructions to the optical fiber-based QKD controller. If the
secret keys in the local key managers of the requesting QKD nodes are
sufficient to satisfy these requests, then the optical fiber-based QKD
controller configures the QKD nodes and lets them provide the secret key to
the cryptographic applications. However, since the coverage of optical fiber-
based QKD services is limited and fixed, the optical fiber-based QKD services
are not able to provide sufficient secret keys to well handle the uncertainty
and dynamics in secure communications of QKD nodes.

###  III-B Provisioning Dynamic QKD Services via Satellite- and UAV-based QKD

Fortunately, satellite- and UAV-based QKD services can supplement the required
secret keys for QKD nodes to resolve the uncertain security requests in their
communications with high coverage and flexibility. On the one hand, when the
secret keys are not enough in the terrestrial layer, the satellite-based QKD
controller can configure LEO satellites to distribute the required QKD
services via satellite-based QKD in the space layer. Although satellite-based
QKD services are real-time and have global coverage, they are orbit-limited
and constrained by the weather conditions of the ground nodes. Therefore, on
the other hand, UAV-based QKD in the aerial layer may be a practical
alternative to provision QKD services at various times, locations, and weather
conditions. According to the instructions from the QKD global manager during
the data transmission phase, the UAV-based QKD controller can deploy UAV
swarms or chains to provide QKD services in mobile quantum networks [12].

###  III-C Challenges of Provisioning QKD Services in Quantum-secured SAGIN

####  III-C1 Efficient Routing for QKD Services

To provide efficient QKD services in quantum-secured SAGIN, many practical
challenges are required to be solved. First and foremost is the problem of
point-to-point routing in optical fiber-based QKD in the terrestrial layer.
Unlike routing in traditional backbone networks, optical fiber-based QKD
requires nodes on the path of secure communications to be fully active and
have enough secret keys. As shown in Fig. 1, there are two relaying nodes for
the current optical fiber-based QKD, i.e., trusted/untrusted repeaters and
quantum routers. In optical fiber-based QKD services with trusted/untrusted
repeaters, the nodes are connected with the intermediate of trusted/untrusted
repeaters and the secret keys as well as key management information through
QKD links and the encrypted message are transmitted through public data
channels. Each QKD link is always connected in a point-to-point fashion. At
the same time, there are a variable number of intermediate nodes in public
data channels, regardless of whether they are trusted. In optical fiber-based
QKD services with quantum routers, each quantum router has a number of quantum
memories for storing a finite number of quantum bits and a certain number of
quantum entangled links per variable. Unlike the store-and-forward mechanism
of trusted repeaters, the motivation of the implementation of quantum routers
is to apply the quantum entanglement of photons to transmit quantum signals
over different quantum channels. In other words, multiple quantum memory are
connected together and the measurement of one of the quantum memory can change
the quantum states of the other quantum memory. Even when a considerable
distance separates the photons, they still establish a joint quantum system.
For optical fiber-based QKD services, each distribution of the secret key
information consumes a certain amount of quantum resources of QKD nodes. Since
the quantum resources in each node are limited, the secret keys of each QKD
node are also limited. The purpose of efficient routing for QKD services is to
minimize the secret key consumption, i.e., the number of hops transmitted,
while satisfying the secure communication requests [13].

####  III-C2 Uncertainty and Dynamics of Secure Communication Environments in
Quantum-secured SAGIN

Quantum-secured SAGIN still needs an effective dynamic resource management
scheme to enhance the efficiency in provisioning QKD services. The
communication security in quantum-secured SAGIN is guaranteed by secret keys.
The encryption operation of QKD nodes cannot be implemented without the secret
keys in their local key managers, and thus the encrypted communication link is
temporarily invalid. Although one-time pad encryption can provide information-
theoretically secure (ITS) communication, due to the limited secret key
provided by optical fiber-based QKD services, the requirement for the one-time
pad to have an encryption key of equal length to the plaintext is difficult to
achieve [9]. Therefore, the current solution of quantum-secured SAGIN
generally updates the secret keys periodically to ensure a certain level of
secure communications. Nevertheless, before the transmission of confidential
data, the data rate is unpredictable and QKD services provisioned by optical
fiber-QKD are fixed and undersubscribed. Therefore, allocating satellite- and
UAV-based QKD services to compensate for the secret key shortage is
challenging to resolve the uncertainty and dynamics of secure communication
environments.

##  IV Case Study: Metaverse in Quantum-secured SAGIN

Figure 3: The universal QKD service provisioning framework with two-stage
stochastic programming for Metaverse application in quantum-secured SAGIN.

As illustrated in Fig. 3, in this case study of Metaverse in quantum-secured
SAGIN, we first provide an overview of Metaverse and highlight the
requirements for secure interoperations of Metaverse applications. To provide
QKD services for Metaverse applications, we develop the system model,
provisioning options, and serving phases for QKD over SAGIN. Finally, we
describe the uncertainty of Metaverse applications and propose an optimization
solution to provide QKD services cost-effectively.

###  IV-A Metaverse Applications

The Metaverse, considered as the successor to the mobile Internet, is a set of
interoperable 3D worlds where people can telepresent themselves to work, play,
and socialize [14]. In the Metaverse, applications/users provide seamless
interoperations with other applications/users by constantly communicating with
each other. As shown in Fig. 3, interoperations between XR and digital twin
are required to provide life-like, multi-sensory, immersive telepresence and
teleoperation between users and the real world. AI can be used to accelerate
physical/virtual synchronization in the digital twin, and AI can then use the
sensory data to improve the accuracy of AI models. In addition, Metaverse
users enter the Metaverse in the form of avatars and interact with the
Metaverse’s intelligent avatars while using their private data to create
personalized AI models. However, the embodied experiences provided by
Metaverse applications make Metaverse users more vulnerable to threats of
unsafe interoperability, such as unreliable virtual/physical synchronization,
untrustworthy AI training and inference, and sensitive data leakage.
Especially, in the post-quantum era, quantum computing is believed to be the
cornerstone of the Metaverse applications and can be used for XR rendering,
digital twin scientific calculations, and AI model training. However, quantum
computing can compromise the secure interoperations of Metaverse applications
based on traditional symmetric-key cryptography and public-key cryptography.
Fortunately, QKD can provide information-theoretically secure interoperations
for Metaverse applications. Moreover, QKD over SAGIN can secure the
interoperations of Metaverse applications in a timely and global manner via
quantum-secured SAGIN.

###  IV-B System model, Provisioning Options, and Serving Phases

To provision the QKD services to Metaverse applications, the system model of
quantum-secured SAGIN includes data nodes, QKD nodes and edges [15]. Here,
data nodes are co-located with the QKD nodes. Edges in quantum-secured SAGIN
are QKD links, e.g., optical fibers and entanglement connections, depending on
the equipment of QKD nodes. For optical fiber-based QKD, each QKD node
consists of a local key manager, and one or more transceivers of MDI-QKD.
Between a pair of QKD nodes linked with optical fiber, a QKD link with
multiple trusted/untrusted repeaters can be deployed for global secret key
generation. Each trusted repeater consists of two or more QKD transceivers, a
local key manager, and security infrastructure, while each untrusted repeater
consists of two or more QKD transceivers but with a higher security level.
Between a pair of QKD nodes, quantum routers with a small amount of quantum
memory can establish entanglement connections for entanglement swapping. For
satellite- and UAV-based QKD, trusted quantum satellites and trusted quantum
UAVs act as quantum relays.

The QKD global manager can offer secure communications of Metaverse
applications in quantum-secured SAGIN with two provisioning options, i.e., QKD
via optical fiber and QKD via free space. In general, the option of QKD via
optical fiber provides QKD services through optical fiber-based QKD, while the
option of QKD via free space provides QKD-supported secure communication
services through satellite- and UAV-based QKD. However, the QKD via free space
is more dynamic and its use can be on a short-term on-demand basis. It is
important to note here that these provisioning options are similar to that of
other network and cloud services available commercially, i.e., reservation and
on-demand subscription plans.

QKD service provisioning in quantum-secured SAGIN is divided into three
serving phases by the QKD global manager, i.e., QKD via optical fibers, data
transmission, and QKD via free space. First, in the phase of optical fiber-
based QKD phase, the QKD global manager follows the option of QKD via optical
fiber to instruct the optical fiber-based QKD controller to deploy optical
fiber-based QKD services. As this should be done on a long-term basis, this
option could be done without knowing the secure communication requirements of
Metaverse applications. Then, when the option of QKD via optical fiber is
determined, quantum-secured SAGIN enters the data transmission phase. As the
QKD via optical fiber is more stable and can be done on a long-term
reservation basis, the secret keys provided by optical fiber-based QKD
services are static. During the data transmission phase, if the security
requirements of Metaverse applications incurs more secret keys which cannot be
provided only by optical fiber-based QKD services, the Metaverse applications
can request additional QKD services from the QKD global manager in the option
of QKD via free space and then obtain more secret-key rate from the QKD via
free space option. In this phase, the QKD global manager sends instructions to
the satellite- and UAV-based QKD controllers to configure QKD services for
Metaverse applications requiring extra QKD services. For the same secret-key
rate, the provisioning cost of QKD via optical fibers is typically less than
that of QKD via free space, e.g., due to the network operating costs. The QKD
global manager aims to satisfy the security requests of Metaverse applications
while minimizing the provisioning cost of QKD services.

###  IV-C Uncertainty of Metaverse Applications in Quantum-secured SAGIN

Under uncertainty of secure interoperations of Metaverse applications, the
secret key rate of required QKD services by Metaverse applications is not
precisely known when the option of QKD via optical fibers is made. Moreover,
since the data transmission rates in the Metaverse fluctuate over time, the
Metaverse applications cannot predict the required QKD services precisely. For
example, due to the fact that AI data quantity and quality generated in
Metaverse applications are varying over time, the frequency and size of
updates to AI models are uncertain. Second, the number of digital twins is
unpredictable and the synchronizing sizes and frequencies are varying
according to the changing importance of the real-world environment. Third, the
number of avatars in the Metaverse is dynamic, as each user can have multiple
avatars simultaneously in different virtual 3D worlds. In general, the
probability distribution of uncertainty can be partially fitted by statistical
processes and machine learning.

###  IV-D The Proposed Optimization Solution Approach

In the deterministic programming model for QKD service provisioning in
quantum-secured SAGIN, the required secret keys in QKD services of Metaverse
applications are assumed to be exactly known by the QKD global manager.
However, due to the aforementioned challenges in the QKD service provisioning
framework and uncertain factors of secure communication environments in
Metaverse applications, the QKD service requests for secure communications
cannot be predicted precisely and fulfilled perfectly. Thus, the stochastic
programming with two-stage QKD service provisioning is proposed. The first
stage defined the number of optical fiber-based QKD services provisioned in
the terrestrial layer, while the second stage defines the number of satellite-
and UAV-based QKD services deployed in the space layer and the aerial layer.
The stochastic programming model can be formulated as the minimization of
provisioning cost including two parts, where the first part is the
provisioning cost of optical fiber-based QKD services according to the option
of QKD via optical fibers and the second part is the expected provisioning
cost of the option of QKD via free space under the set of possible realized
data transmission requests of Metaverse applications. The constraints of the
stochastic programming model for QKD over SAGIN are flow conservation, the
required number of wavelengths, transmission path uniqueness, wavelength
continuity, wavelength capacity, and wavelength uniqueness [15] under the
uncertainty of secure communication environments in Metaverse applications.

###  IV-E Experimental Results

(a) Cost structure.

(b) Performance comparison.

Figure 4: The cost structure and performance comparison of stochastic
programming for secure communications of Metaverse applications in quantum-
secured SAGIN.

The experiments are performed on the USNET topology with 24 nodes [9]. The
distance between each pair of QKD nodes in optical fiber-based QKD is set to
80 km and the distance between each pair of UAVs in UAV-based QKD is set to 1
km. The required secret keys of Metaverse applications are set to the
equivalent level. To simplify the evaluation, the uncertainty is reformulated
as all the Metaverse applications have the equivalent requested size of secret
keys that is determined by the amount of scenarios. For each scenario, the
probability distribution of secret keys requirements follows a Poisson process
with an average of the number of scenarios (set to ten) divided by three. The
default number of Metaverse applications is set to 200. Finally, the
reservation cost values, with a unit denoting a unit of normalized monetary,
of QKD transmitters, QKD receivers, local key manager, security
infrastructure, MUX/DEMUX components, and optical fiber, are 1500, 2250, 1200,
150, 300, and 1, respectively. The on-demand cost values, with a unit
representing a normalized monetary unit, of QKD transmitters, QKD receivers,
securet-key buffers, security infrastructure, UAVs, and satellites are 6000,
9000, 3000, 500, 20, and 20000, respectively. QKD devices are relatively
expensive, however, a small secret key can accomplish the encryption of a
large amount of confidential data e.g., a 256-bit secret key can be used to
encrypt 64 GiB data in AES-256-GSM. Furthermore, new quantum infrastructures
are required to be deployed for QKD service provisioning which will be the
fundamental deployment of the upcoming quantum Internet [2].

Based on the aforementioned experimental settings, the cost structure of
stochastic programming of QKD services in quantum-secured SAGIN is first
studied. As illustrated in Fig. 4(a), the first phase, the second phase, and
the overall provisioning costs vary as the number of reserved QKD services
increases. As expected, the first phase provisioning cost linearly increases
as the number of reserved QKD services rises. Nevertheless, during the data
transmission, the second phase cost decreases as the number of reserved QKD
services increases, so that less on-demand compensation is required for
Metaverse applications. In this way, the optimized provisioning plan can be
determined by the minimization of overall cost, e.g., when the size of secret
keys provided by optical-based QKD services equals to four as illustrated in
Fig. 4(a). Through cost analysis in QKD service provisioning framework, the
optimal provisioning plan can not easily be obtained due to the uncertainty in
the secure interoperations of Metaverse applications. For example, the optimal
QKD service provisioning solution is not the place where the cost curves of
the two phases of service are intersected. Therefore, a stochastic programming
model for QKD over SAGIN is essential to achieve the minimized service
provisioning cost.

In the experiments, two baseline algorithms, i.e., the quantum backbone
network (QBN) model with expected value formulation (QBN-EVF) provisioning and
the QBN with random (QBN-Random) provisioning, developed in [9], are used for
the compassion of the stochastic programming model. In QBN-EVF, the QKD
services provisioned in the first phase are fixed by the expectation of the
requested security requests, which is an approximate model. Similarly, in the
QBN-Random model, the secret keys provisioned by the optical fiber-based QKD
services are generated uniformly from zero to the number of scenarios,
indicating a random model. The provisioning costs of QBN-Random, QBN-EVF, and
stochastic programming for different number of security requests in Metaverse
applications are shown in Fig. 4(b). We can observe that as the number of
Metaverse applications increases, the provisioning costs of all three models
increase accordingly. Moreover, the performance difference in provisioning
cost among the three models is also larger as the number of Metaverse
applications increases. In particular, the provisioning cost of QBN-EVF is
slightly higher than that of the stochastic programming model, while the
provisioning cost of QBN-Random is 50% higher.

##  V Conclusion

In this article, we have highlighted the feasibility of quantum-secured SAGIN
through the conceptualization of QKD over SAGIN. We have presented the concept
of QKD over SAGIN, where optical fiber-based QKD, satellite-based QKD, and
UAV-based QKD services are provisioned collaboratively to secure
communications in SAGIN. To realize the concept of QKD over SAGIN, we have
proposed a universal QKD service provisioning framework which is expected to
cater flexible and cost-efficient QKD services in quantum-secured SAGIN.
Finally, we have examined the proposed concept and framework by using
Metaverse applications as a case study. The experimental results have
demonstrated that proposed methods can minimize the provisioning cost under
uncertain secure communication environments.

## References

  * [1] H. Cui, J. Zhang, Y. Geng, Z. Xiao, T. Sun, N. Zhang, J. Liu, Q. Wu, and X. Cao, “Space-air-ground integrated network (sagin) for 6g: Requirements, architecture and challenges,” China Communications, vol. 19, no. 2, pp. 90–108, 2022.
  * [2] C. Wang, A. Rahman, R. Li, M. Aelmans, and K. Chakraborty, “Application Scenarios for the Quantum Internet,” Internet-Draft draft-irtf-qirg-quantum-internet-use-cases-10, Internet Engineering Task Force, Mar. 2022.  Work in Progress.
  * [3] A. Huang, Y. Liu, T. Chen, Y. Zhou, Q. Sun, H. Chai, and Q. Yang, “Starfl: Hybrid federated learning architecture for smart urban computing,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 12, no. 4, pp. 1–23, 2021.
  * [4] M. Mehic, M. Niemiec, S. Rass, J. Ma, M. Peev, A. Aguado, V. Martin, S. Schauer, A. Poppe, C. Pacher, et al., “Quantum key distribution: a networking perspective,” ACM Computing Surveys (CSUR), vol. 53, no. 5, pp. 1–41, 2020.
  * [5] S.-K. Liao, W.-Q. Cai, W.-Y. Liu, L. Zhang, Y. Li, J.-G. Ren, J. Yin, Q. Shen, Y. Cao, Z.-P. Li, et al., “Satellite-to-ground quantum key distribution,” Nature, vol. 549, no. 7670, pp. 43–47, 2017.
  * [6] J. Yin, Y.-H. Li, S.-K. Liao, M. Yang, Y. Cao, L. Zhang, J.-G. Ren, W.-Q. Cai, W.-Y. Liu, S.-L. Li, et al., “Entanglement-based secure quantum cryptography over 1,120 kilometres,” Nature, vol. 582, no. 7813, pp. 501–505, 2020.
  * [7] H.-Y. Liu, X.-H. Tian, C. Gu, P. Fan, X. Ni, R. Yang, J.-N. Zhang, M. Hu, J. Guo, X. Cao, et al., “Optical-relayed entanglement distribution using drones as mobile nodes,” Physical Review Letters, vol. 126, no. 2, p. 020503, 2021.
  * [8] M. Xu, W. C. Ng, W. Y. B. Lim, J. Kang, Z. Xiong, D. Niyato, Q. Yang, X. S. Shen, and C. Miao, “A full dive into realizing the edge-enabled metaverse: Visions, enabling technologies, and challenges,” arXiv preprint arXiv:2203.05471, 2022.
  * [9] Y. Cao, Y. Zhao, Q. Wang, J. Zhang, S. X. Ng, and L. Hanzo, “The evolution of quantum key distribution networks: On the road to the qinternet,” IEEE Communications Surveys & Tutorials, 2022.
  * [10] H.-K. Lo, M. Curty, and B. Qi, “Measurement-device-independent quantum key distribution,” Physical review letters, vol. 108, no. 13, p. 130503, 2012\.
  * [11] Y. Zhao and C. Qiao, “Redundant entanglement provisioning and selection for throughput maximization in quantum networks,” in IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pp. 1–10, IEEE, 2021.
  * [12] H.-Y. Liu, X.-H. Tian, C. Gu, P. Fan, X. Ni, R. Yang, J.-N. Zhang, M. Hu, J. Guo, X. Cao, et al., “Drone-based entanglement distribution towards mobile quantum networks,” National science review, vol. 7, no. 5, pp. 921–928, 2020.
  * [13] M. Mehic, P. Fazio, S. Rass, O. Maurhart, M. Peev, A. Poppe, J. Rozhon, M. Niemiec, and M. Voznak, “A novel approach to quality-of-service provisioning in trusted relay quantum key distribution networks,” IEEE/ACM Transactions on Networking, vol. 28, no. 1, pp. 168–181, 2019.
  * [14] Y. Wang, Z. Su, N. Zhang, D. Liu, R. Xing, T. H. Luan, and X. Shen, “A survey on metaverse: Fundamentals, security, and privacy,” arXiv preprint arXiv:2203.02662, 2022.
  * [15] Y. Cao, Y. Zhao, J. Li, R. Lin, J. Zhang, and J. Chen, “Hybrid trusted/untrusted relay-based quantum key distribution over optical backbone networks,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 9, pp. 2701–2718, 2021.


# Operational relevance of resource theories of quantum measurements

Michał Oszmaniec<EMAIL_ADDRESS>Tanmoy Biswas  Institute of
Theoretical Physics and Astrophysics, National Quantum Information Centre,
Faculty of Mathematics, Physics and Informatics, University of Gdansk, Wita
Stwosza 57, 80-308 Gdańsk, Poland

###### Abstract

For any resource theory it is essential to identify tasks for which resource
objects offer advantage over free objects. We show that this identification
can always be accomplished for resource theories of quantum measurements in
which free objects form a convex subset of measurements on a given Hilbert
space. To this aim we prove that every resourceful measurement offers
advantage for some quantum state discrimination task. Moreover, we give an
operational interpretation of robustness, which quantifies the minimal amount
of noise that must be added to a measurement to make it free. Specifically, we
show that this geometric quantity is related to the maximal relative advantage
that a resourceful measurement offers in a class of minimal-error state
discrimination (MESD) problems. Finally, we apply our results to two classes
of free measurements: incoherent measurements (measurements that are diagonal
in the fixed basis) and separable measurements (measurements whose effects are
separable operators). For both of these scenarios we find, in the asymptotic
setting in which the dimension or the number of particles increase to
infinity, the maximal relative advantage that resourceful measurements offer
for state discrimination tasks.

###  1 Introduction

Resource theories [1] constitute a powerful toolbox to study physical systems
in the presence of limitations resulting from experimental or operational
constrains on the ability to address and manipulate physical systems. This
mathematical framework is general enough to encompass both classical and
quantum physics, or even more general theories [2]. In recent years it has
been successfully applied to classical and quantum thermodynamics [3, 4],
processing of quantum information in distributed scenarios [5, 6],
contextuality [7], nonlocality [8], steering [9] and, last but not least,
magic state distillation paradigm of quantum computation [10]. On the general
level, all resource theories are defined by specifying _free objects_ and
_free operations_. Free objects form a subset of the set of all objects
relevant for the physical situation in question. Likewise, free operations
form a subclass of all relevant physical transformations. Typically objects
that are not free are called _resource objects_. The specific choice of free
objects and free operations depends on the physical context. For example, in
entanglement theory the relevant resource theory is based on the principle of
locality: set of free objects consists of separable states while free
operations are all local operations assisted by classical communication
(LOCC).

For any resource theory it is desirable to give operational interpretation of
resource objects i.e to identify a task for which a given resource object
would prove advantageous over all free objects. The main purpose of this work
is to provide such interpretations for resource theories in which a set of
free objects consists of convex subset of the set of quantum measurements
(POVMs) on a relevant Hilbert space. We realize this goal by showing, that in
this setting for every resourceful measurement $\mathbf{M}$ there an instance
of minimal-error quantum state discrimination game for which $\mathbf{M}$
gives greater success probability then all free measurements. Quantum state
discrimination [11, 12] is a popular quantum information subroutine that finds
applications in different areas of quantum information science including
quantum communication [13], quantum metrology [14], nonlocality [15] or
quantum computation [16]. We push our operational interpretation further by
proving the quantitative relation between the relative advantage of
resourceful measurement for state discrimination and the geometric measure of
resourcefulness called robustness [17, 18], which quantifies the minimal
amount of noise that has to be added to a POVM to make it free. Previously,
the measure robustness was introduced [19] to mathematically quantify
entanglement. Leter, it was employed in the general resource- theoretic
framework [20, 21, 1].

We apply our general results to two classes of free measurements: incoherent
measurement and separable measurements. Incoherent measurements are POVM
analogues of incoherent states [22, 23, 24] and can be understood as
measurements originating from a single projective measurement (in the fixed
basis) followed by arbitrary classical post-processing. Separable measurements
[25, 26, 27, 28], on the other hand, are POVMs on composite quantum systems
whose effects are separable operators. This class contains the set of LOCC
measurements [29, 30] i.e. measurements that can be implemented via local
measurements and LOCC operations. For both incoherent and separable
measurements we focus on the asymptotic setting in which the dimension of the
system or the number of particles involved go to infinity. In this regime we
identify, for both classes of measurements, the maximal relative advantage
that resourceful measurements can offer for quantum state discrimination
tasks.

Traditionally, operational interpretations of quantum resources were developed
case-by-case for different resource theories [31, 32, 33, 34, 35, 36]. A
recent paper [18] gave an unified treatment of this problem for all quantum
resource theories in which the set of free objects is convex subset of the set
of quantum states. Specifically, the authors of this work showed that in this
context all resource states offer advantage for some sub-channel
discrimination problem (this result was previously obtained for resource
theories of entanglement [37], coherence [38], steering [39] and asymmetry
[40]). Our results are complementary to [18], as they give the operational
interpretation of _all convex resource theories of quantum measurements_.
Moreover, our work greatly generalizes some of the results of [17], where the
analogous analysis was presented for the case where free measurements
consisted of maximally uninformative measurements i.e. measurements that do
not recover any information about the measured quantum states.

So far, research in quantum resource theories focussed mainly on quantum
states while quantum measurements, despite their importance, did not receive
much attention. Previously, resource-theoretic perspective was applied in the
context of measurement incompatibility [41, 42], measurement simulability via
projective measurements [43, 44], and simulability in the more general
scenarios [42, 45]. We believe that our results, especially previously
unexplored quantitative relation between state discrimination and robustness,
provide new quantitative tools to study the restricted classes of POVMs and,
more generally, quantum resource theories concentrated around quantum
measurements.

###  2 Notation and main concepts

Throughout the paper we will be interested in POVMs on finite dimensional
Hilbert space $\mathcal{H}\approx\mathbb{C}^{d}$. Such generalized
measurements (POVMs) can be understood as tuples
$\mathbf{M}=\left(M_{1},\ldots,M_{n}\right)$ of non-negative operators on
$\mathbb{C}^{d}$ satisfying $\sum_{i=1}^{n}M_{i}=\mathbbm{1}$, where $n$ is
the number of outcomes and $\mathbbm{1}$ is the identity on $\mathbb{C}^{d}$.
The operators $M_{i}$ are called the effects of POVM $\mathbf{M}$. According
to Born’s rule, when a POVM $\mathbf{M}$ is measured on a quantum state $\rho$
the probability of obtaining the outcome $i$ is given by
$p_{i}=\operatorname{tr}\left(M_{i}\rho\right)$. We denote the set of POVMs on
$\mathbb{C}^{d}$ with $n$ outcomes by $\mathcal{P}\left(d,n\right)$. This set
has a natural convex structure [46]: given two POVMs
$\mathbf{M},\mathbf{N}\in\mathcal{P}\left(d,n\right)$, their convex
combination $p\mathbf{M}+(1-p)\mathbf{N}$ is the POVM with $i$-th effect given
by $\left[p\mathbf{M}+\left(1-p\right)\mathbf{N}\right]_{i}\coloneqq
pM_{i}+(1-p)N_{i}$. The operation of taking convex combinations of
measurements can be operationally realized as performing POVMs $\mathbf{M}$
and $\mathbf{N}$ with certain probabilities and then combining the outcomes.

Our operational interpretation of _resourcefullness_ of quantum measurements
will be based on the task of minimal-error state discrimination [11, 12]. The
purpose of this task is to optimally distinguish quantum states states
generated by the ensemble $\mathcal{E}=\\{q_{i},\rho_{i}\\}_{i=1}^{n}$, where
$\\{q_{i}\\}_{i=1}^{n}$ is a probability distribution and
$\\{\rho_{i}\\}_{i=1}^{n}$ is a collection of quantum states. The success
probability of identifying the states generated by $\mathcal{E}$ via a
measurement $\mathbf{M}\in\mathcal{P}(d,n)$ is given by

$p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})=\sum_{i=1}^{n}q_{i}\operatorname{tr}(M_{i}\rho_{i})\
.$ (1)

One is often interested in choosing the measurement $\mathbf{M}$, such that
$p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})$ is maximized. However, if only a
restricted class of measurements $\mathcal{F}\subset\mathcal{P}(d,n)$ is
allowed, the maximum $p_{\mathrm{succ}}$ may not be achieved.

###  3 Convex resource theories of measurements and measurement robustness

We now give a minimal formulation of a resource theory of measurements, under
the assumption of convexity. In our treatment we will focus on a set of
quantum measurements $\mathcal{F}$ and a class of free operations 111Of
course, the full treatment of resource theory of measurements requires to take
into account more complicated aspects such as composability. We plan to
address such questions in the future work. $\mathcal{O}$. We first assume (i)
that the set of free measurements $\mathcal{F}$ is a convex and closed subset
of $n$-outcome measurements on $\mathbb{C}^{d}$ i.e
$\mathcal{F}\subset\mathcal{P}(d,n)$, for some suitable Hilbert space
$\mathcal{H}\approx\mathbb{C}^{d}$. Second, we assume that the class of free
operations $\mathcal{O}$ consists of mappings
$\varphi:\mathcal{P}(d,n)\rightarrow\mathcal{P}(d,n)$ that (ii) preserve the
set of free measurements i.e. for all $\mathbf{N}\in\mathcal{F}$ we have
$\varphi(\mathbf{N})\in\mathcal{F}$ and (iii) are convex-linear i.e.
$\varphi(p\mathbf{M}+(1-p)\mathbf{M}^{\prime})=p\varphi(\mathbf{M})+(1-p)\varphi(\mathbf{M}^{\prime})$
for all measurements $\mathbf{M},\mathbf{M}^{\prime}\in\mathcal{P}(d,n)$.

Figure 1:  A figure demonstrating some of the key ideas of the paper. The blue
part denotes the of all free measurements $\mathcal{F}$ while orange part
denotes the set of all $n$ outcome measurements on $\mathbb{C}^{d}$ that are
not free. (i) Illustration of Theorem 1: for any $\mathbf{M}\notin\mathcal{F}$
there always exists a hyperplane $\mathbf{W}$ which separates any POVM
$\mathbf{M}\notin\mathcal{F}$ in a sense
$\langle\mathbf{M}.\mathbf{W}\rangle>\langle\mathbf{F}.\mathbf{W}\rangle$ for
all $\mathbf{F}\in\mathcal{F}$. By Theorem 1, every separating hyperlane can
be rewritten in terms of a state discrimination problem for the ensemble of
quantum states $\mathcal{E}$ such that for all free measurements $\mathbf{F}$
we have
$p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})>p_{\mathrm{succ}}(\mathcal{E},\mathbf{F})$.
(ii) Geometric explanation of Robustness: the straight line represents convex
combinations $\frac{\mathbf{M}+s\mathbf{N}}{1+s}$. For a given POVMs
$\mathbf{M}$ and $\mathbf{N}$ there exist the minimal value $s_{\ast}$
(depending on $\mathbf{N}$ for a fixed $\mathbf{M}$) such that
$\frac{\mathbf{M}+s\mathbf{N}}{1+s}$ becomes free. The robustness
$R_{\mathcal{F}}(\mathbf{M})$ is defined as the minimum $s_{\ast}$,
considering all possible POVM $\mathbf{N}\in\mathcal{P}(d,n)$.

_Justification of assumptions:_ The convexity of $\mathcal{F}$ can be
justified by the fact that, as argued before, convex combination of
measurements can be realised by a purely classical process. The compactness of
$\mathcal{F}$ is a technical assumption that allows us to formally state our
results. However, in basically any physically interesting case the class of
free measurements $\mathcal{F}$ can be viewed as a set of convex combinations
(convex hull) of a compact set of "primitive" measurements
$\mathcal{F}^{\prime}$, and hence is naturally compact. Finally, convex
linearity of free operations follows from linearity of quantum mechanics while
preservation of the $\mathcal{F}$ by free operation is also natural -
operations that are considered free should not be able to create resourceful
measurement. In particular, in many cases the set $\mathcal{F}$ contains (a)
classical post-processing i.e. operation of the form
$\mathcal{Q}(\mathbf{M})=\mathbf{M}^{\prime}$, where
$M^{\prime}_{i}=\sum_{j}q(i|j)M_{i}$, for some stochastic matrix
$\mathcal{Q}_{ij}=q(i|j)$, and (b) unitary symmetries of the set
$\mathcal{F}$.

For every set of free measurements $\mathcal{F}$ it is possible to introduce a
geometric measure quantifying the minimum amount of noise which has to be
added to a given POVM $\mathbf{M}$ to make it free. In analogy to previous
works [19, 18, 17] we will call this quantifier _robustness_ and denote it by
$R_{\mathcal{F}}$. It is formally defined in the following way (See Fig. 1):

$R_{\mathcal{F}}(\mathbf{M}):=\min\bigg{\\{}s|\ \exists\mathbf{N}\text{ such
that }\frac{\mathbf{M}+s\mathbf{N}}{1+s}\in\mathcal{F}\bigg{\\}}\ .$ (2)

The robustness enjoys a number of natural properties as stated by the
following proposition.

######  Proposition 1 (Properties of robustness).

Let $\mathcal{F}\subset\mathcal{P}(d,n)$ be a closed convex set of free
measurements. The robustness $R_{\mathcal{F}}$ satisfies the following
properties: (i) Faithfulness: $R_{\mathcal{F}}(\mathbf{M})\geq 0$ and
$R_{\mathcal{F}}(\mathbf{M})>0$ iff $\mathbf{M}\notin\mathcal{F}$, (ii)
Convexity: $R_{\mathcal{F}}(p\mathbf{M}_{1}+(1-p)\mathbf{M}^{\prime})\leq
pR_{\mathcal{F}}(\mathbf{M})+(1-p)R_{\mathcal{F}}(\mathbf{M}^{\prime})$ ,
(iii) Monotonicity under free operations:
$R_{\mathcal{F}}\left[\varphi(\mathbf{M})\right]\leq
R_{\mathcal{F}}(\mathbf{M})$ for all free operations $\varphi\in\mathcal{O}$.

The proof of the above follows directly form the definitions of the concepts
involved and we defer it to the Appendix.

###  4 Main results

In this part we give our main results concerning the operational
interpretation of resourceful measurements for a class of quantum state
discrimination tasks.

######  Theorem 1 (Minimal-error state discrimination
can certify resource character of measurements).

For any resourceful POVM $\mathbf{M}\notin\mathcal{F}$, there exist an
ensemble $\mathcal{E}_{\mathbf{M}}=\\{p_{i},\rho_{i}\\}$ such that

$p_{\mathrm{succ}}(\mathcal{E}_{\mathbf{M}},\mathbf{M})>\max_{\mathbf{N}\in\mathcal{F}}p_{\mathrm{succ}}(\mathcal{E}_{\mathbf{M}},\mathbf{N})\
.$ (3)

###### Proof.

We begin the proof by noting that $\mathcal{P}(d,n)$ is a convex subset of
$(\mathrm{Herm}(\mathcal{H}))^{\times n}$ where
$\mathcal{H}\approx\mathbb{C}^{d}$ is a $d$\- dimensional Hilbert space and
$\mathrm{Herm}(\mathcal{H})$ is the set of hermitian operator from
$\mathcal{H}$ to itself. The space $(\mathrm{Herm}(\mathcal{H}))^{\times n}$
can be regarded as $nd^{2}$ dimensional real vector space with the inner
product defined by
$\langle\textbf{A},\textbf{B}\rangle=\sum_{i=1}^{n}\operatorname{tr}(A_{i}B_{i})$,
where $\textbf{A},\textbf{B}\in(\mathrm{Herm}(\mathcal{H}))^{\times n}$. We
have assumed that $\mathcal{F}$ is a compact set and hence, due to hyperplane
separation theorem (see Fig. 1), for any $\mathbf{M}\notin\mathcal{F}$, there
exists a tuple of Hermitian operators
$\mathbf{W}=\left(W_{1},W_{2},....W_{n}\right)$ such that
$\sum_{i=1}^{n}\operatorname{tr}(W_{i}M_{i})>0$ while for all
$\mathbf{N}\in\mathcal{F}$ we have $\sum_{i}\operatorname{tr}(W_{i}N_{i})\leq
0$. We now define $\tilde{W_{i}}\coloneqq W_{i}+|\lambda|\mathbb{I}$, where
$\lambda$ is the smallest eigenvalue of operators $\\{W_{i}\\}$. We note that
for every $i$ the operator $\tilde{W_{i}}$ is positive-semi-definite and
moreover
$\sum_{i}\operatorname{tr}(\tilde{W_{i}}N_{i})<\sum_{i}\operatorname{tr}(\tilde{W_{i}}M_{i})$.
Using this we construct the ensemble
$\mathcal{E}_{\mathbf{M}}=\bigg{\\{}\frac{\operatorname{tr}(\tilde{W_{i}})}{\sum_{i}\operatorname{tr}(\tilde{W_{i}})},\frac{\tilde{W_{i}}}{\operatorname{tr}(\tilde{W_{i}})}\bigg{\\}}$,
for which the inequality (3) holds. ∎

The above result shows the qualitative advantage of resourceful measurements
for a class of state-discrimination tasks. In what follows we show a natural
way to quantify this advantage. In Theorem 2 below we show that under the same
assumptions as above, the robustness $\mathbb{R}_{\mathcal{F}}(\mathbf{M})$ is
related to the maximal relative advantage that a resourceful measurement
$\mathbf{M}$ offers for MESD. To prove this result we will use the following
technical Lemma that can be regarded as dual characterisation of measurement
robustness. Its proof relies on duality of semi-infinite convex optimization
programs [47] and we present it in the Appendix.

######  Lemma 1.

Let $\mathbf{M}$ $\in$ $\mathcal{P}(d,n)$ and
$\mathcal{F}\subset\mathcal{P}(d,n)$ be a compact convex set of free
measurements. Then, the generalized robustness $R_{\mathcal{F}}(\mathbf{M})$
can be expressed as the following optimisation problem.

maximize $\displaystyle\sum_{i=1}^{n}\operatorname{tr}(Z_{i}M_{i})-1$ (4)
subject to $\displaystyle Z_{i}\geq 0,\;i=1,\ldots,n\ ,$
$\displaystyle\sum_{i=1}^{n}Tr(Z_{i}N_{i})\leq
1\;\forall\mathbf{N}\in\mathcal{F}$

We are now ready to state and prove our main result.

######  Theorem 2 (Operational interpretation of robustness in terms of
quantum state discrimination).

For any class of free measurements $\mathcal{F}$ and any POVM
$\mathbf{M}\in\mathcal{P}(d,n)$ the generalized robustness can be expressed as

$R_{\mathcal{F}}(\mathbf{M})=\max_{\mathcal{E}}\frac{p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})}{{\max_{\mathbf{N}\in\mathcal{F}}}p_{\mathrm{succ}}(\mathcal{E},\mathbf{N})}-1,$
(5)

where the outer optimisation is over $n$ element ensembles of quantum states.

###### Proof.

We begin by showing that LHS(5) $\geq$ RHS(5). From the definition of
generalized robustness from (2) it follows that for each effect $M_{i}$ of
POVM $\mathbf{M}\in\mathcal{P}(d,n)$ it holds that
$M_{i}+\mathcal{R}_{\mathcal{F}}(\mathbf{M})M^{\prime}_{i}=(1+\mathcal{R}_{\mathcal{F}}(\mathbf{M}))N^{\prime}_{i}$,
where $M^{\prime}_{i}$ are the effects of POVM
$\mathbf{M}^{\prime}\in\mathcal{P}(d,n)$ and $N^{\prime}_{i}$ are the effects
of POVM $\mathbf{N}^{\prime}\in\mathcal{F}$. Therefore, we have
$M_{i}\leq(1+\mathcal{R}_{\mathcal{F}}(\mathbf{M}))N^{\prime}_{i}$ for every
$i\in\\{1,n\\}$ and therefore

$\displaystyle
p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})\leq(1+\mathcal{R}_{\mathcal{F}}(\mathbf{M}))p_{\mathrm{succ}}(\mathcal{E},\mathbf{N}^{\prime})$
(6)
$\displaystyle\leq(1+\mathcal{R}_{\mathcal{F}}(\mathbf{M}))\max_{\mathbf{N}\in\mathcal{F}}p_{\mathrm{succ}}(\mathcal{E},\mathbf{N})\
,$

where the second inequality follows from $\mathbf{N}^{\prime}\in\mathcal{F}$.

To show LHS(5) $\leq$ RHS(5), we use the dual characterization of the
generalized robustness from Lemma 1. Let
$\left(Z^{\ast}_{1},...,Z^{\ast}_{n}\right)$ be the optimal tuple for which
(4) is maximized. We now define

$\mathcal{E}_{\ast}\coloneqq\bigg{\\{}\frac{\operatorname{tr}(Z^{\ast}_{i})}{\sum_{i}\operatorname{tr}(Z^{\ast}_{i})},\frac{Z^{\ast}_{i}}{\operatorname{tr}(Z^{\ast}_{i})}\bigg{\\}}\
.$ (7)

Simple algebraic manipulations give
$\mathcal{R}_{\mathcal{F}}(\mathbf{M})+1=\bigg{(}\sum_{i=1}^{n}\operatorname{tr}(Z^{\ast}_{i})\bigg{)}p_{\mathrm{succ}}(\mathcal{E}_{\ast},\mathbf{M})$.
On the other hand from (4) it follows that $\forall\mathbf{N}\in\mathcal{F}$
we have
$p_{\mathrm{succ}}(\mathcal{E}_{\ast},\mathbf{N})\leq\frac{1}{\sum_{i}\operatorname{tr}(Z_{i}^{\ast})}$.
Using these two properties we obtain

$\frac{p_{\mathrm{succ}}(\mathcal{E}_{\ast},\mathbf{M})}{\max_{\mathbf{N}\in\mathcal{F}}p_{\mathrm{succ}}(\mathcal{E}_{\ast},\mathbf{N})}\geq\mathcal{R}_{\mathcal{F}}(\mathbf{M})+1\
.$ (8)

By combining (6) and (8) we complete the proof. ∎

Importantly, Theorems 1 and 2 are valid _for all_ convex and compact sets of
free measurements $\mathcal{F}$. In particular, we can directly apply them to
the measurements that are simulable by projective measurements [43, 44] or
$k$-outcome measurements [42, 45]. In what follows, we will consider
application of our results to two other classes of free measurements:
incoherent measurements and separable measurements. We will focus on obtaining
the maximal relative advantage for MESD that can be obtained in these
scenarios by resourceful measurements.

####  4.1 Incoherent measurements

Quantum coherence or superposition is one of the salient nonclassical aspects
of quantum theory. Recently, this feature of quantum theory was investigated
thoroughly form the resource-theoretic perspective [23, 24]. Moreover, quantum
coherence has been identified as resource for a number of quantum information
processing tasks like quantum channel discrimination [37], designing quantum
algorithms [48], quantum metrology [14] and quantum thermodynamics [3].
Finally, there is a plethora of works on quantification of quantum coherence
of quantum states [23, 49] and operations [50, 51] and on giving operational
interpretation to some quantifiers [35, 36].

Here we propose to introduce a concept of coherence to the realm of POVMs.
Specifically, we define the class of _incoherent measurements_
$\mathcal{IC}(d,n)$ consisting of $n$-outcome measurements S on
$\mathbb{C}^{d}$, whose effects are diagonal in a particular orthogonal basis
$\\{|i\rangle\\}$. In what follows, for the sake of simplicity, we assume
$n\geq d$. Incoherent measurements constitute a POVM analogues of the set of
_incoherent states_. More formally, the effects of incoherent measurements S
can be expressed as $S_{i}=\sum_{j=1}^{d}q(i|j)|j\rangle\langle j|$, where
$i\in[n]$. In is now easy to see that incoherent measurements can always be
obtained via classical post-processing of projective measurements in the
standard basis.

One way to quantify the coherence present in a POVM is the robustness
$R_{\mathcal{IC}}(\mathbf{M})$ with respect to the set of incoherent
measurements. Importantly, $R_{\mathcal{IC}}(\mathbf{M})$ satisfies a number
of natural properties stated in Lemma 1. Here, the class of free operations
$\mathcal{O}_{\mathcal{IC}}$ can be chosen to contain all diagonal unitaries
and classical post-processing 222In fact all quantum channels $\Lambda$ such
that $\Lambda^{\ast}$ is an incoherent channel also preserve
$\mathcal{IC}(n,d)$.. By applying Theorem 2 directly to this setting we get
that robustness $R_{\mathcal{IC}}(\mathbf{M})$, can be identified as the
maximal relative advantage of $\mathbf{M}$ for a suitable state discrimination
problem. In the following we will take the complemenary approach based on
semi-definite programming [52]. From the definition of incoherent measurements
it follows that $R_{\mathcal{IC}}(\mathbf{M})$ can be casted as the following
semi-definite program (SDP)

minimize $\displaystyle s$ (9) s.t
$\displaystyle\frac{M_{a}+sN_{a}}{1+s}=\sum_{i}q(a|i)|i\rangle\langle
i|\;\forall a\ ,$ $\displaystyle N_{a}\geq
0,\;a=1,\ldots,n.\;\;\sum_{a}N_{a}=\mathbb{I}\ ,$
$\displaystyle\sum_{a}q(a|i)(1+s)=b\;\;\forall i\ .$

Taking the dual problem we get the following auxiliary result whose proof we
defer to the Appendix.

######  Lemma 2 (Dual characterization of robustness w.r.t. incoherent
measurement).

Robustness of a POVM $\mathbf{M}\in\mathcal{P}(d,n)$ w.r.t set of incoherent
measurement $\mathcal{IC}(d,n)$, i.e, $R_{\mathcal{IC}}(\mathbf{M})$ can be
expressed as the solution of optimization problem given by

maximize $\displaystyle\sum_{a=1}^{n}\operatorname{tr}(Z_{a}M_{a})-1$ (10)
subject to $\displaystyle\forall i,a\;\;Z_{a}\geq 0\;\;\;\;\langle
i|Z_{a}|i\rangle=\langle i|Z_{n}|i\rangle\ ,$
$\displaystyle\operatorname{tr}(Z_{n})=1\ .$

From the above we get a physical characterization of ensembles of states that
suffice to capture the maximal advantage of coherent measurements over the
incoherent ones.

######  Proposition 2 (Alternative characterisation of robustness for
incoherent measurements).

Let $\mathbf{M}\in\mathcal{P}(d,n)$. We have the following equality

$R_{\mathcal{IC}}(\mathbf{M})=\max_{\mathcal{E}_{0}}\frac{p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{M})}{{\max_{\mathbf{N}\in\mathcal{IC}(d,n)}}p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{N})}-1,$
(11)

where the outer optimisation is over ensembles
$\mathcal{E}_{0}=\\{1/n,\sigma_{i}\\}_{i=1}^{n}$ consisting of states that
cannot be classically distinguished [53] (that is, for all $j\in[d]$ and for
all $i\in[n]$ we have $\langle j|\sigma_{i}|j\rangle=1/d$). Due to this
property of $\sigma_{i}$ for all incoherent measurements $\mathbf{N}$ we have
$p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{N})=1/n$.

###### Proof.

We observe that due to the assumed property of states $\sigma_{i}$ (for all
$k$ $\langle k|\sigma_{i}|k\rangle=1/d$), for any POVM
$\mathbf{N}\in\mathcal{IC}(d,n)$,
$\max_{\mathbf{N}\in\mathcal{IC}(d,n)}p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{N})=\frac{1}{n}$.
Then RHS of (11) is exactly the same as optimization problem given in (10)
which completes the proof. ∎

The above operational characterisation of $R_{\mathcal{IC}}$ allows us to
identify measurements with the greatest possible robustness (hence relative
advantage for MESD) in a given dimension $d$.

######  Proposition 3 (Maximal advantage of coherent measurements over
incoherent measurements).

The following equality holds

$\max_{\mathbf{M}\in P(d,n)}R_{\mathcal{IC}}(\mathbf{M})=\min\\{d,n\\}-1\ .$
(12)

Moreover, when $n\geq d$ the measurement $\mathbf{M}$ attains the maximal
value of $\mathbb{R}_{\mathcal{F}}$ if and only if its effects are
proportional to maximally coherent states i.e pure states of the form
$|\psi\rangle=(1/\sqrt{d})\sum_{j=1}^{d}\mathrm{exp}(i\theta_{j})|j\rangle$.

###### Proof.

From Lemma 2 it follows that
$R_{\mathcal{IC}}(\mathbf{M})+1=\sum_{i}\operatorname{tr}(M_{i}\sigma_{i})$,
where $\sigma_{i}$ cannot be classically distinguished. Since for any $\rho$
we have $\operatorname{tr}(M_{i}\rho)\leq\operatorname{tr}(M_{i})$ we obtain
$R_{\mathcal{IC}}(\mathbf{M})+1\leq\sum_{i}\operatorname{tr}(M_{i})=d$.
Moreover, if $n\geq d$ this bound can be easily saturated for projective
measurements in the Fourier basis
$|\tilde{j}\rangle=\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}\mathrm{exp}\left(\frac{i2\pi
jk}{d}\right)|k\rangle$ =with ensemble
$\mathcal{E}_{0}=\\{\frac{1}{d},|\tilde{j}\rangle\\}_{j=1}^{d}$.
For $n<d$, we will use (10) to get the missing upper bound. We first note that
since operators $M_{a}$ are upper bounded by $\mathbbm{1}$ we have
$\operatorname{tr}(Z_{a}M_{a})\leq\operatorname{tr}(Z_{a})=1$. Therefore ,
from (10) we can conclude that
$R_{\mathcal{IC}}(\mathbf{M})=\sum_{a}\operatorname{tr}(Z_{a}M_{a})\leq\sum_{a}\operatorname{tr}(Z_{a})=n$,
hence $R_{\mathcal{IC}}(\mathbf{M})\leq n-1$. Combining this with the previous
case we conclude $R_{\mathcal{IC}}(\mathbf{M})=\min\\{d,n\\}-1$.
Just like in the case $n\geq d$ we will proof the saturation of this bound
using Fourier transform of the original basis
$|\tilde{j}\rangle=\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}e^{\frac{i2\pi
jk}{d}}|k\rangle$. To prove the equality for the case $n<d$, we choose an
ensemble $\mathcal{\tilde{E}}$ uniformly distributed over first $n$
orthonormal states from ensemble $\mathcal{E}_{0}$, i.e,
$\mathcal{\tilde{E}}=\\{\frac{1}{n},|\tilde{j}\rangle\\}_{j=1}^{n}$ and an $n$
outcome POVM
$\tilde{\mathbf{M}}:=\bigg{\\{}\\{|\tilde{j}\rangle\langle\tilde{j}|\\}_{i=1}^{n-1},\mathbb{I}-\sum_{j=1}^{n-1}|\tilde{j}\rangle\langle\tilde{j}|\bigg{\\}}$.
For this particular case, again RHS of (11) reduce to $n-1$. Combining these
two cases we obtain
$\max_{\mathbf{M}\in\mathcal{P}(d,n)}R_{\mathcal{IC}}(\mathbf{M})=\min\\{d,n\\}-1\
$.

Now we will show that for $n\geq d$ any POVM for which (11) holds, have the
effects directly proportional to $|\psi\rangle\langle\psi|$ where
$|\psi\rangle=(1/\sqrt{d})\sum_{j=1}^{d}\mathrm{exp}(i\theta_{j})|j\rangle$.
This follows from the simple observation that for $n\geq d$, maximization of
(10) $\forall a$, $\operatorname{tr}(Z_{a}M_{a})=\operatorname{tr}(M_{a})$
requires that $Z_{a}=P_{\mathrm{Supp}(M_{a})}+B_{a}$, where
$\operatorname{tr}(B_{a}P_{\mathrm{Supp}(M_{a})})=0$. Moreover, to satisfy the
constraint of (10), $P_{\mathrm{Supp}(M_{a})}$ has to be one dimensional. This
implies only feasible solution will be

$\displaystyle M_{a}=\alpha_{a}\Pi_{a}\;\;\;\;Z_{a}=\Pi_{a},$ (13)

where $\Pi_{a}$ is rank one projector with trace 1. Then to be a valid POVM,

$\sum_{a}\alpha_{a}\Pi_{a}=\mathbbm{1}\Rightarrow\sum_{a}\alpha_{a}\langle
i|\Pi_{a}|i\rangle=1.$ (14)

Combining (14) and (10) we obtain $\langle i|\Pi_{a}|i\rangle=\frac{1}{d}$ for
every $a$. This leads to the conclusion that the POVM $\mathbf{M}$ with $n\geq
d$ outcomes and satisfying $R_{\mathcal{IC}}(\mathbf{M})=d-1$ must have
effects proportional to $|\psi\rangle\langle\psi|$ where
$|\psi\rangle=(1/\sqrt{d})\sum_{j=1}^{d}\mathrm{exp}(i\theta_{j})|j\rangle$. ∎

####  4.2 Separable measurements

We now turn our attention to the measurements that can be performed on a
composite quantum systems. In what follows we will study the maximal advantage
that entangled measurements can offer for MESD over so-called separable
measurements on multiparticle quantum systems. Separable measurements contain
the set of LOCC measurements and are relatively easy to characterize. For this
reason the maximal advantage with respect to separable measurements is in
general smaller then the advantage with respect to LOCC measurements.

Consider a biparticle quantum system
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. We define a POVM
$\mathbf{F}$ as separable if all its effects $\\{F_{k}\\}_{k=1}^{n}$ are
separable operators i.e. $F_{i}=\sum_{k}Q^{k}_{i}\otimes\tilde{Q}^{k}_{i}$
where $\\{Q^{k}_{i}\\}_{i=1}^{n}$ and $\\{\tilde{Q}^{k}_{i}\\}_{i=1}^{n}$ are
positive operators on $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ respectively.
The above definition can be easily extended to system of multiple qubits
$\mathcal{H}_{N}=(\mathbb{C}^{2})^{\otimes N}$. We denote the set of
biparticle separable measurements by $\mathrm{Sep}(AB)$ and separable
multiqubit measurements by $\mathrm{Sep}(N)$. Recall that we made the
dependence on number of outcomes $n$ implicit. In what follows we will assume
that $n$ is fixed and equals at least the dimension of the relevant Hilbert
space ($d_{A}d_{B}$ and $2^{N}$ respectively). It easily follows that
$\mathrm{Sep}(AB)$ and $\mathrm{Sep}(N)$ are convex compact subsets of
$\mathcal{P}(d,n)$ for suitable Hilbert spaces. The following Lemma gives the
comprehensive answer to the question about the maximal advantage for MESD that
entangled measurements can offer over separable measurements in both bipartite
and multiparty scenario.

######  Proposition 4 (Maximal advantage of entangled meaurements over
separable measurements).

Let $d_{A}$ and $d_{B}$ denote the dimensions of local spaces in the
biparticle Hilbert space $\mathcal{H}_{AB}$. Then, the following inequalities
hold

$\min\\{d_{A},d_{B}\\}-1\leq\max_{\mathbf{M}}R_{\mathrm{Sep}(AB)}(\mathbf{M})\leq\min\\{d_{A},d_{B}\\}\
,$ (15)

where the maximization is over all measurements on $\mathcal{H}_{AB}$.
Moreover, the maximal robustness of entangled qubit measurement increases
exponentially with the size of the system. Specifically, for sufficiently
large $N$ we have

$c\frac{2^{N}}{8N^{2}}-1\leq\max_{\mathbf{M}}R_{\mathrm{Sep}(N)}(\mathbf{M})\leq
2^{\frac{3}{2}N-1}-1\ ,$ (16)

where the maximization is over all measurements on $\mathcal{H}_{N}$ and
$c>0.7$.

###### Sketch of the proof.

The upper bounds in (15) and (16) follow from application of explicit
simulation strategy based on (global) depolarizing map $\Phi_{t}$. This map,
transforms effects of a measurement $\mathbf{M}$ as follows:
$\Phi_{t}(M_{i})=tM_{i}+(1-t)\frac{\operatorname{tr}(M_{i})}{d}\mathbbm{1}$.
It is easy to check that the resulting operators still form a POVM on a total
space. Because this map preserves traces of the effects we can write
$\Phi_{t}(M_{i})=\operatorname{tr}(\mathbf{M}_{i})\left(\Phi_{t}(\rho_{i})\right)$,
where $\rho_{i}=M_{i}/\operatorname{tr}(M_{i})$ is a quantum state. To get an
upper bound on the robustness of $\mathbf{M}$ it that suffices to find lower
bond on $t_{\ast}$ defined as the number for which _all states_ $\rho_{i}$
constructed from the effects of $M_{i}$ are separable. To find the upper bound
we can directly use the results from entanglement theory. Concretely, the
problem of how much "white noise" can be added to a quantum state before it
becomes separable quantum states has been studied before. Specifically the
maximal value of "random robustness" (minimal $s=1/t-1$ such that
$\Phi_{t}(\rho)$ is separable) equals $\min\\{d_{A},d_{B}\\}-1$ in the
biparticle scenario [19] and can be upper bounded by $2^{\frac{3}{2}N-1}-1$
for the multipartice case [54]. To obtain the lower bounds we use
characterization of the robustness MESD given in Eq.(5) by showing advantage
of entangled measurements over separable ones for particular uniform ensambles
of quantum states. for biparticle case we consider exnamble consisting of
orthogonal maximally states [29], while for multiparticle case we consider
ensemble consisting of $2^{N}$ iid random quantum states taken from the Haar
measure on $(\mathbb{C}^{2})^{\otimes N}$ [55] (see Appendix for details). ∎

######  Remark.

The above results complement existing results [56, 29, 57] on the relative
power of LOCC separable, and global state discrimination. Our focus was on the
advantage in discrimination of arbitrary ensembles of quantum states while
previously the emphasis was put mostly on ensembles consisting of two states
(for example in the context of quantum data hiding).

###  5 Open problems

We finish with giving possible directions of further study. First, it is
tempting to ask if non-free character of measurements can be certified in a
device-independent manner in prepare-and measure scenarios [58, 59]. Second
interesting problem concerns finding the maximal that resourceful POVMs
advantage for state discrimination problems for other important classes of
measurements such as LOCC measurements [29, 30] or projective-simulable
measurements [43, 44]. The potential lack of the increasing separation (as
$d\rightarrow\infty$) between projective and general POVMs will likely have
strong consequences for quantum information processing and Bell nonlocality.
Finally, it is natural to ask if analogous operational interpretations hold
also for other classes of quantum objects such as quantum channels or quantum
instruments.

We thank Zbigniew Puchała, Michał Horodecki, Paul Skrzypczyk and Sibasish
Ghosh, for interesting and stimulating discussions. We are grateful to Filip
Maciejewski for careful reading of the manuscript and his valuable comments.
We acknowledge the support of Homing programme of the Foundation for Polish
Science co-financed by the European Union under the European Regional
Development Fund.
Note added—- Upon the completion of this work we became aware of two works
[60, 61] that independently obtained results overlapping with Theorem 2
presented here. Moreover, similar methods were used in the context of
measurement incompatibility [62, 63].

### References

  * Chitambar and Gour [2018] E. Chitambar and G. Gour, arXiv:1806.06107 (2018).
  * Coecke  _et al._ [2016] B. Coecke, T. Fritz, and R. W. Spekkens, Information and Computation 250, 59 (2016).
  * Brandão  _et al._ [2013] F. G. S. L. Brandão, M. Horodecki, J. Oppenheim, J. M. Renes, and R. W. Spekkens, Phys. Rev. Lett. 111, 250404 (2013).
  * Goold  _et al._ [2016] J. Goold, M. Huber, A. Riera, L. del Rio, and P. Skrzypczyk, Journal of Physics A: Mathematical and Theoretical 49, 143001 (2016).
  * Vedral  _et al._ [1997] V. Vedral, M. B. Plenio, M. A. Rippin, and P. L. Knight, Phys. Rev. Lett. 78, 2275 (1997).
  * Horodecki  _et al._ [2009] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys. 81, 865 (2009).
  * Grudka  _et al._ [2014] A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, R. Horodecki, P. Joshi, W. Kłobus, and A. Wójcik, Phys. Rev. Lett. 112, 120401 (2014).
  * Barrett [2007] J. Barrett, Phys. Rev. A 75, 032304 (2007).
  * Gallego and Aolita [2015] R. Gallego and L. Aolita, Phys. Rev. X 5, 041008 (2015).
  * Veitch  _et al._ [2012] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New Journal of Physics 14, 113011 (2012).
  * Barnett and Croke [2009] S. M. Barnett and S. Croke, Adv. Opt. Photon. 1, 238 (2009).
  * Bae and Kwek [2015] J. Bae and L.-C. Kwek, J. Phys. A: Math. Gen. 48, 083001 (2015).
  * Brunner  _et al._ [2013] N. Brunner, M. Navascués, and T. Vértesi, Phys. Rev. Lett. 110, 150501 (2013).
  * Marvian and Spekkens [2016] I. Marvian and R. W. Spekkens, Phys. Rev. A 94, 052324 (2016).
  * Bae  _et al._ [2011] J. Bae, W.-Y. Hwang, and Y.-D. Han, Phys. Rev. Lett. 107, 170403 (2011).
  * Lomont [2005] C. Lomont, arxiv:0411037 (2005).
  * Skrzypczyk and Linden [2019] P. Skrzypczyk and N. Linden, Phys. Rev. Lett. 122, 140403 (2019).
  * Takagi  _et al._ [2018] R. Takagi, B. Regula, K. Bu, Z.-W. Liu, and G. Adesso, Phys. Rev. Lett. 122, 140402 (2019).
  * Vidal and Tarrach [1999] G. Vidal and R. Tarrach, Phys. Rev. A 59, 141 (1999).
  * Brandão and Gour [2015] F. G. S. L. Brandão and G. Gour, Phys. Rev. Lett. 115, 070503 (2015).
  * Regula [2017] B. Regula, Journal of Physics A: Mathematical and Theoretical 51, 045303 (2017).
  * Aberg [2006] J. Aberg, arXiv:quant-ph/0612146 (2006).
  * Baumgratz  _et al._ [2014] T. Baumgratz, M. Cramer, and M. B. Plenio, Phys. Rev. Lett. 113, 140401 (2014).
  * Streltsov  _et al._ [2017] A. Streltsov, G. Adesso, and M. B. Plenio, Rev. Mod. Phys. 89, 041003 (2017).
  * Bandyopadhyay and Nathanson [2013] S. Bandyopadhyay and M. Nathanson, Phys. Rev. A 88, 052313 (2013).
  * Watrous [2018] J. Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, 2018).
  * Bagan  _et al._ [2005] E. Bagan, M. A. Ballester, R. Muñoz Tapia, and O. Romero-Isart, Phys. Rev. Lett. 95, 110504 (2005).
  * Kargin [2004] V. Kargin, The Annals of Statistics 33, 959 (2004).
  * Nathanson [2005] M. Nathanson, J. Math. Phys. 46, 141 (2005).
  * Chitambar  _et al._ [2014] E. Chitambar, D. Leung, L. Mančinska, M. Ozols, and A. Winter, Communications in Mathematical Physics 328, 303 (2014).
  * D’Ariano  _et al._ [2001] G. M. D’Ariano, P. Lo Presti, and M. G. A. Paris, Phys. Rev. Lett. 87, 270404 (2001).
  * Horodecki and Oppenheim [2013] M. Horodecki and J. Oppenheim, Nat. Commun. 4 (2013), 10.1038/ncomms3059.
  * Spekkens  _et al._ [2009] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Phys. Rev. Lett. 102, 010401 (2009).
  * Cavalcanti  _et al._ [2017] D. Cavalcanti, P. Skrzypczyk, and I. Šupić, Phys. Rev. Lett. 119, 110501 (2017).
  * Winter and Yang [2016] A. Winter and D. Yang, Phys. Rev. Lett. 116, 120404 (2016).
  * Biswas  _et al._ [2017] T. Biswas, M. G. Diaz, and A. Winter, Proc. R. Soc. A 473 (2017), 10.1098/rspa.2017.0170.
  * Piani  _et al._ [2016a] M. Piani, M. Cianciaruso, T. R. Bromley, C. Napoli, N. Johnston, and G. Adesso, Phys. Rev. A 93, 042107 (2016a).
  * Napoli  _et al._ [2016] C. Napoli, T. R. Bromley, M. Cianciaruso, M. Piani, N. Johnston, and G. Adesso, Phys. Rev. Lett. 116, 150502 (2016).
  * Piani and Watrous [2015] M. Piani and J. Watrous, Phys. Rev. Lett. 114, 060404 (2015).
  * Piani  _et al._ [2016b] M. Piani, M. Cianciaruso, T. R. Bromley, C. Napoli, N. Johnston, and G. Adesso, Phys. Rev. A 93, 042107 (2016b).
  * Heinosaari  _et al._ [2015] T. Heinosaari, J. Kiukas, and D. Reitzner, Phys. Rev. A 92, 022115 (2015).
  * Guerini  _et al._ [2017] L. Guerini, J. Bavaresco, M. Terra Cunha, and A. Acín, J. Math. Phys. 58, 092102 (2017).
  * Oszmaniec  _et al._ [2017] M. Oszmaniec, L. Guerini, P. Wittek, and A. Acín, Phys. Rev. Lett. 119, 190501 (2017).
  * Oszmaniec  _et al._ [2018] M. Oszmaniec, F. B. Maciejewski, and Z. Puchała, arXiv:1807.08449 (2018).
  * Kleinmann and Cabello [2016] M. Kleinmann and A. Cabello, Phys. Rev. Lett. 117, 150401 (2016).
  * D’Ariano  _et al._ [2005] G. M. D’Ariano, P. L. Presti, and P. Perinotti, J. Phys. A: Math. Gen. 38, 5979 (2005).
  * Brandao [2005] F. G. Brandao, Phys. Rev. A 72, 022310 (2005).
  * Hillery [2016] M. Hillery, Phys. Rev. A 93, 012111 (2016).
  * Bischof  _et al._ [2018] F. Bischof, H. Kampermann, and D. Bruss, arXiv:1812.00018 (2018).
  * Theurer  _et al._ [2018] T. Theurer, D. Egloff, L. Zhang, and M. B. Plenio., arXiv:1806.07332 (2018).
  * Bera [2018] M. Bera, arXiv:1809.02578 (2018).
  * Vandenberghe and Boyd [1996] L. Vandenberghe and S. Boyd, SIAM Review 38, 49 (1996).
  * Korzekwa  _et al._ [2018] K. Korzekwa, S. Czachorski, Z. Puchała, and K. Zyczkowski, arXiv:1812.09083 (2018).
  * Gurvits and Barnum [2003] L. Gurvits and H. Barnum, Phys. Rev. A 68, 042312 (2003).
  * Montanaro [2007] A. Montanaro, Commun Math Phys 273, 619 (2007).
  * Hayden  _et al._ [2004] P. Hayden, D. Leung, P. W. Shor, and A. Winter, Communications in Mathematical Physics 250, 371 (2004).
  * Matthews  _et al._ [2009] W. Matthews, S. Wehner, and A. Winter, Communications in Mathematical Physics 291, 813 (2009).
  * Tavakoli  _et al._ [2018] A. Tavakoli, M. Smania, T. Vértesi, D. Rosset, and N. Brunner, arXiv:1811.12712 (2018).
  * Mironowicz and Pawłowski [2018] P. Mironowicz and M. Pawłowski, arXiv:1811.12872 (2018).
  * Uola  _et al._ [2018] R. Uola, T. Kraft, J. Shang, X.-D. Yu, and O. Guhne, Phys. Rev. Lett. 122, 130404 (2019).
  * R. and Regula [2019] R. Takagi. and B. Regula, arXiv:1901.08127 (2019).
  * Carmeli  _et al._ [2018] C. Carmeli, T. Heinosaari, and A. Toigo, Phys. Rev. Lett. 122, 13040 (2019).
  * Skrzypczyk  _et al._ [2019] P. Skrzypczyk, I. Šupić, and D. Cavalcanti, Phys. Rev. Lett. 122, 130403 (2019).
  * Cavalcanti and Skrzypczyk [2016] D. Cavalcanti and P. Skrzypczyk, Reports on Progress in Physics 80, 024001 (2016).
  * Gross  _et al._ [2009] D. Gross, S. T. Flammia, and J. Eisert, Phys. Rev. Lett. 102, 190501 (2009).

## Appendix

In what follows we give proofs that were omitted in the main part of the
manuscript. In Part A we give proofs concerning the general properties of the
robustness $R_{\mathcal{F}}$ and its dual formulation. In Part B we give
justifications of results specific to particular scenarios of incoherent and
separable measurements.

###  Appendix A Proofs of general results

For the convenience of the reader we first recall the definition of robustness
for general convex and compact subset of free measurements
$\mathcal{F}\subset\mathcal{P}(d,n)$

$R_{\mathcal{F}}(\mathbf{M}):=\min\bigg{\\{}s|\ \exists\mathbf{N}\text{ such
that }\frac{\mathbf{M}+s\mathbf{N}}{1+s}\in\mathcal{F}\bigg{\\}}\ .$ (17)

######  Proposition 1 (Properties of robustness).

Let $\mathcal{F}\subset\mathcal{P}(d,n)$ be a compact convex set of free
measurements. The robustness $R_{\mathcal{F}}$ satisfies the following
properties: (i) Faithfulness: $R_{\mathcal{F}}(\mathbf{M})\geq 0$ and
$R_{\mathcal{F}}(\mathbf{M})>0$ iff $\mathbf{M}\notin\mathcal{F}$, (ii)
Convexity: $R_{\mathcal{F}}(p\mathbf{M}+(1-p)\mathbf{M}^{\prime})\leq
pR_{\mathcal{F}}(\mathbf{M})+(1-p)R_{\mathcal{F}}(\mathbf{M}^{\prime})$ ,
(iii) Monotonicity under free operations:
$R_{\mathcal{F}}\left[\varphi(\mathbf{M})\right]\leq
R_{\mathcal{F}}(\mathbf{M})$ for all free operations $\varphi\in\mathcal{O}$.

###### Proof.

_(i) Faithfulness_. This property follows directly from the definition given
in Eq.(17).

_(ii) Convexity_. From the definition of the robustness (17) it follows that
for two POVMs $\mathbf{M},\mathbf{M}^{\prime}$ there exist POVMs
$\mathbf{N},\mathbf{N}^{\prime}\in\mathcal{P}(d,n)$, such that

$\displaystyle\mathbf{M}$
$\displaystyle=(1+R_{\mathcal{F}}(\mathbf{M}))\tilde{\mathbf{M}}-R_{\mathcal{F}}(\mathbf{M})\mathbf{N}\
,$ (18) $\displaystyle\mathbf{M}^{\prime}$
$\displaystyle=(1+R_{\mathcal{F}}(\mathbf{M}^{\prime}))\tilde{\mathbf{M}^{\prime}}-R_{\mathcal{F}}(\mathbf{M}^{\prime})\mathbf{N}^{\prime}\
,$ (19)

where $\mathbf{N},\mathbf{N}^{\prime}\in\mathcal{F}$. We therefore get that
for all $p\in[0,1]$

$\displaystyle
p\mathbf{M}+(1-p)\mathbf{M}^{\prime}=p[(1+R_{\mathcal{F}}(\mathbf{M}))\tilde{\mathbf{M}}-R_{\mathcal{F}}(\mathbf{M})\mathbf{N}]$
(20)
$\displaystyle+(1-p)[(1+R_{\mathcal{F}}(\mathbf{M}^{\prime}))\mathbf{M}^{\prime}-R_{\mathcal{F}}(\mathbf{M}^{\prime})\mathbf{N}^{\prime}]\
.$

After defining

$\displaystyle\tilde{r}$ $\displaystyle\coloneqq$ $\displaystyle
pR_{\mathcal{F}}(\mathbf{M})+(1-p)R_{\mathcal{F}}(\mathbf{M}^{\prime})\ ,$
(21) $\displaystyle\tilde{\mathbf{N}}$ $\displaystyle\coloneqq$
$\displaystyle\frac{pR_{\mathcal{F}}(\mathbf{M})\mathbf{N}+(1-p)R_{\mathcal{F}}(\mathbf{M}^{\prime})\mathbf{N}^{\prime}}{\tilde{r}}\
,$ (22) T $\displaystyle\coloneqq$
$\displaystyle\frac{p(\tilde{\mathbf{M}}+R_{\mathcal{F}}(\mathbf{M})\tilde{\mathbf{M}})+(1-p)(\tilde{\mathbf{M}^{\prime}}+R_{\mathcal{F}}(\mathbf{M}^{\prime})\tilde{\mathbf{M}^{\prime}})}{1+\tilde{r}}\
,$ (23)

we note that $\tilde{N}\in\mathcal{P}(d,n)$, while $\textbf{T}\in\mathcal{F}$.
We finally observe that

$p\mathbf{M}+(1-p)\mathbf{M}^{\prime}=(1+\tilde{r})\textbf{T}-\tilde{r}\tilde{\mathbf{N}}\
,$ (24)

which directly implies
$\tilde{r}=pR_{\mathcal{F}}(\mathbf{M})+(1-p)R_{\mathcal{F}}(\mathbf{M}^{\prime})\geq
R_{\mathcal{F}}(p\mathbf{M}+(1-p)\mathbf{M}^{\prime})$.

_(iii) Monotonicity under free operations_. From the definition we have that
for every $\mathbf{M}$ there exist $\mathbf{N}\in\mathcal{P}(d,n)$ and
$\tilde{\mathbf{M}}\in\mathcal{F}$ such that

$\mathbf{M}=(1+R_{\mathcal{F}}(\mathbf{M}))\tilde{\mathbf{M}}-R_{\mathcal{F}}(\mathbf{M})\mathbf{N}\
.$ (25)

Applying $\varphi$ to both sides of the above equality we obtain

$\varphi(\mathbf{M})=(1+R_{\mathcal{F}}(\mathbf{M}))\varphi(\tilde{\mathbf{M}})-R_{\mathcal{F}}(\mathbf{M})\varphi(\mathbf{N})\
.$ (26)

Since, by assumption, $\varphi(\tilde{\mathbf{M}})\in\mathcal{F}$, equation
(26) directly implies $R_{\mathcal{F}}\left[\varphi(\mathbf{M})\right]\leq
R_{\mathcal{F}}(\mathbf{M})$. ∎

######  Lemma 1.

Let $\mathbf{M}$ $\in$ $\mathcal{P}(d,n)$ and
$\mathcal{F}\subset\mathcal{P}(d,n)$ be a compact convex set of free
measurements. Then, the generalized robustness $R_{\mathcal{F}}(\mathbf{M})$
can be expressed as the following optimisation problem.

maximize $\displaystyle\sum_{i=1}^{n}\operatorname{tr}(Z_{i}M_{i})-1$ (27)
subject to $\displaystyle Z_{i}\geq 0,\;i=1,\ldots,n\ ,$
$\displaystyle\sum_{i=1}^{n}Tr(Z_{i}N_{i})\leq
1\;\forall\mathbf{N}\in\mathcal{F}\ .$

###### Proof.

Our proof starategy is the following. The problem in (27) belongs to the class
of semi-infinite optimisation problems [47]. We will compute its dual and
argue that there is no duality gap. Finally, the dual problem will turn out to
be equivalent to the original definition of robustness from (17). After simple
algebraic manipulations we obtain that (27) is equivalent to

$\displaystyle-\min_{\mathbf{X}}\bigg{\\{}\sum_{i}\operatorname{tr}(X_{i}M_{i})-1:\forall{i},\;X_{i}\leq
0,\ \forall\mathbf{N}\in\mathcal{F}\ \ \sum_{i}Tr(X_{i}N_{i})\geq-1\bigg{\\}}$
(28)
$\displaystyle=-\min_{\tilde{\mathbf{X}}}\bigg{\\{}\sum_{i}\operatorname{tr}(\tilde{X}_{i}M_{i}):\forall{i},\;X_{i}\leq\frac{\mathbb{I}}{d}\
\forall\mathbf{N}\in\mathcal{F}\ \ \sum_{i}Tr(\tilde{X}_{i}N_{i})\geq
0\bigg{\\}}\ .$

The Lagrangian corresponding to the last problem in (28) reads

$\displaystyle\mathcal{L}(\tilde{X},\textbf{G},\\{k(\mathbf{N})\\})=\sum_{i=1}^{n}\bigg{(}\operatorname{tr}(\tilde{X}_{i}M_{i})+\operatorname{tr}(X_{i}-\frac{I}{d})G_{i}-\int
d\mathbf{N}k(\mathbf{N})\operatorname{tr}(N_{i}X_{i})\bigg{)}\ ,$ (29)

where $\textbf{G}=(G_{1},\ldots,G_{n})$ and $k(\mathbf{N})$ are lagrange
multipliers which satisfy $G_{i}\geq 0$ $\forall{i}$ and $k\mathbf{N})\geq 0$
for almost all $\mathbf{N}\in\mathcal{F}$. To construct the dual problem to
(29) we minimize $\mathcal{L}(\tilde{X},\textbf{G},\\{k(\mathbf{N})\\})$ over
primal variables $\tilde{\mathbf{X}}$. Since the Lagrangian is affine function
of $\tilde{\textbf{X}}$, we obtain minimum equal to $\infty$ unless
$\textbf{G}+\mathbf{M}=\int k(\mathbf{N})\mathbf{N}d\mathbf{N}$. If the
condition holds then we obtain
$-\frac{1}{d}\sum_{i=1}^{n}\operatorname{tr}(G_{i})$. Hence we see that the
dual of the problem (27) can be written as

minimize $\displaystyle\frac{1}{d}\sum_{i=1}^{n}\operatorname{tr}(G_{i})$ (30)
subject to $\displaystyle\textbf{G}+\mathbf{M}=\int
k(\mathbf{N})\mathbf{N}d\mathbf{N}\ ,$ $\displaystyle G_{i}\geq 0\;\forall{i}\
,$ $\displaystyle k(\mathbf{N})\geq 0\;\;\;\forall{\mathbf{N}}\in\mathcal{F}\
.$

We note that the primal problem (27) posseses a strictly feasible points (for
example
$\mathbf{Z}=(\frac{\lambda\mathbbm{1}}{d},\ldots,\frac{\lambda\mathbbm{1}}{d}$,
for $\lambda\in(0,1)$), which follows from the assumption of the compactness
of $\mathcal{F}$ and the form of the constrains in (27). Finally, we conclude
the proof by noting that $\textbf{G}+\mathbf{M}=\int
k(\mathbf{N})\mathbf{N}d\mathbf{N}$ iff $\textbf{G}=s\mathbf{M}^{\prime}$
where $\mathbf{M}^{\prime}\in\mathcal{P}(d,n)$ and
$s=\sum_{i}\frac{\operatorname{tr}G_{i}}{d}$. ∎

###  Appendix B Proofs of results that concern particular classes of free
measurements

####  B.1 Incoherent measurements

From the definition of robustness (see Eq.(17)) and the definition of
incoherent measurements we obtain that $R_{\mathcal{IC}}(\mathbf{M})$ can be
cast as the following SDP program

minimize $\displaystyle s$ (31) s.t
$\displaystyle\frac{M_{a}+sN_{a}}{1+s}=\sum_{i}q(a|i)|i\rangle\langle
i|\;\forall a\ ,$ $\displaystyle N_{a}\geq
0,\;a=1,\ldots,n.\;\;\sum_{a}N_{a}=\mathbb{I}\ ,$
$\displaystyle\sum_{a}q(a|i)(1+s)=b\;\;\forall i\ .$

.

######  Lemma 2 (Dual characterization of robustness w.r.t. incoherent
measurement).

Robustness of a POVM $\mathbf{M}\in\mathcal{P}(d,n)$ w.r.t set of incoherent
measurement $\mathcal{IC}(d,n)$, i.e, $R_{\mathcal{IC}}(\mathbf{M})$ can be
expressed as the solution of optimization problem given by

maximize $\displaystyle\sum_{a=1}^{n}\operatorname{tr}(Z_{a}M_{a})-1$ (32)
subject to $\displaystyle\forall i,a\;\;Z_{a}\geq 0\;\;\;\;\langle
i|Z_{a}|i\rangle=\langle i|Z_{n}|i\rangle\ ,$
$\displaystyle\operatorname{tr}(Z_{n})=1\ .$

###### Proof.

Introducing variables $\tilde{q}(a|i):=(1+s)q(a|i)$ $\forall i$ and $\forall
a\in[1,(n-1)]$ we obtain an equivalent form of problem from (31)

minimize $\displaystyle b-1$ (33) subject to
$\displaystyle-\sum_{i}\tilde{q}(a|i)|i\rangle\langle i|+M_{a}\leq
0\;\;\;\forall a\in[1,(n-1)]\ ,$
$\displaystyle-b\mathbb{I}+\sum_{i}\sum_{a=1}^{n-1}\tilde{q}(a|i)|i\rangle\langle
i|+M_{n}\leq 0\ .$

To construct the dual of the optimization problem [64, 52] given in (33), we
start by writing down the Lagrangian associated with primal problem

$\mathcal{L}(\textbf{Z},\tilde{q}(a|i)):=(b-1)+\operatorname{tr}(Z_{n}(-b\mathbb{I}+\sum_{i}\sum_{a=1}^{n-1}\tilde{q}(a|i)|i\rangle\langle
i|\\\
+M_{n}))+\sum_{a=1}^{n-1}\operatorname{tr}(Z_{a}(-\sum_{i}\tilde{q}(a|i)|i\rangle\langle
i|+M_{a})\ ,$ (34)

where we have introduced $\textbf{Z}=(Z_{1},Z_{2},\ldots,Z_{n})$ as dual
variable (Lagrange multipliers). To ensure that the Lagrangian is always
smaller than the objective function whenever the constraints of the (33) are
satisfied, we impose $Z_{j}\geq 0$ and $\langle i|Z_{j}|i\rangle=\langle
i|Z_{n}|i\rangle$ $\forall{j\in[1,n]}$. To ensure that the Lagrangian is
independent of primal variables we have $\operatorname{tr}(Z_{n})=1$. Finally,
the corresponding dual problem which sets the upper bound for primal
optimization problem is given by

maximize $\displaystyle\sum_{a=1}^{n}\operatorname{tr}(Z_{a}M_{a})-1$ (35)
subject to $\displaystyle\forall i,a\;\;Z_{a}\geq 0\;\;\;\;\langle
i|Z_{a}|i\rangle=\langle i|Z_{n}|i\rangle\ ,$
$\displaystyle\operatorname{tr}(Z_{n})=1\ .$

By inspection one can conclude that strong duality holds, since
$\mathbf{Z}_{0}=(\frac{\mathbb{I}}{d},\ldots,\frac{\mathbb{I}}{d})$ satisfy
the constraints in (35) and is positive-definite. Therefore, the solutions
(33) and (35) are equal. ∎

####  B.2 Separable measurements

######  Proposition 4 (Maximal advantage of entangled measurements over
separable measurements).

Let $d_{A}$ and $d_{B}$ denote the dimensions of local spaces in the
biparticle Hilbert space $\mathcal{H}_{AB}$. Then, the following inequalities
hold

$\min\\{d_{A},d_{B}\\}-1\leq\max_{\mathbf{M}}R_{\mathrm{Sep}(AB)}(\mathbf{M})\leq\min\\{d_{A},d_{B}\\}\
,$ (36)

where the maximization is over all measurements on $\mathcal{H}_{AB}$.
Moreover, the maximal robustness of entangled qubit measurement increases
exponentially with the size of the system. Specifically, for sufficiently
large $N$ we have

$c\frac{2^{N}}{8N^{2}}\leq\max_{\mathbf{M}}R_{\mathrm{Sep}(N)}(\mathbf{M})\leq
2^{\frac{3}{2}N-1}-1\ ,$ (37)

where the maximization is over all measurements on $\mathcal{H}_{N}$ and
$c>0.7$.

###### Proof of lower bounds in Eq.(36) and Eq.(37).

Our strategy to prove the lower bounds is to construct ensembles $\mathcal{E}$
for which the relative advantage

$\frac{p_{\mathrm{succ}}(\mathcal{E},\mathbf{M})}{{\max_{\mathbf{N}\in
Sep(\mathcal{H}_{A}:\mathcal{H}_{B})}}p_{\mathrm{succ}}(\mathcal{E},\mathbf{N})}$
(38)

of some entangled measurement $\mathbf{M}$ over the separable ones will be
large. _(i) Biparticle case_ Let $D=min\\{d_{A},d_{B}\\}$. Following Nathanson
[29], we consider an uniform ensemble
$\mathcal{E}_{0}=\\{{\frac{1}{D^{2}},\Psi_{nm}\\}}_{n,m=1}^{d}$ consisting
orthogonal maximally entangled states from
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$,

$|\Psi_{nm}\rangle=\frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}e^{\frac{i2\pi
jn}{d}}|j\rangle\otimes|(j+m)\;\;\text{mod }d\rangle\ .$ (39)

Since vectors $|\Psi_{nm}\rangle$ are orthogonal, they can be distinguished
perfectly by measurement $\mathbf{M}_{0}$ whose effects are of the form
$M_{nm}=\Psi_{nm}+R_{nm}$, where $R_{nm}$ are operators orthogonal to states
$|\Psi_{nm}\rangle$. On the other hand there is a limit of distinguishability
of states from $E_{0}$ via separable measurements because of the well-known
property (see for example Lemma 2 of [25]) stating that for all biparticle
quantum states $|Psi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ and
positive separable operators $T$

$\operatorname{tr}(\Psi T)\leq\lambda^{2}\operatorname{tr}(T)\ ,$ (40)

where $\lambda$ is the greatest Schmidt coefficient of $|\Psi\rangle$. Let
$\mathbb{P}_{0}$ be a projector onto a subspace
$\tilde{H}_{AB}\subset\mathcal{H}_{AB}$ spanned by vectors
$|i\rangle|j\rangle$, where $i,j=0,\ldots,D-1$. Importantly, $\mathbb{P}_{0}$
is a separable operator. Applying inequality (40) to our problem we obtain
that for all $D$-outcome separable measurements $\mathbf{N}$ we can upper
bound $p_{\mathrm{succ}}$ as follows

$p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{N})=\frac{1}{D^{2}}\sum_{n,m=1}^{D}\operatorname{tr}(\Psi_{nm}N_{nm})=\frac{1}{D^{2}}\sum_{n,m=1}^{D}\operatorname{tr}(\Psi_{nm}\mathbb{P}_{0}N_{nm}\mathbb{P}_{0})\leq\frac{1}{D}\frac{1}{D^{2}}\sum_{n,m=1}^{D}\operatorname{tr}(\mathbb{P}_{0}N_{nm}\mathbb{P}_{0})=\frac{1}{D}\
,$ (41)

where we have used the separability of operators
$\mathbb{P}_{0}N_{nm}\mathbb{P}_{0}$ and the fact that states $\Psi_{nm}$ are
maximally entangled and hence $\lambda=1/\sqrt{D}$. Using the operational
interpretation of the robustness $R_{\mathrm{Sep}(AB}$ we conclude the proof
by observing that

$R_{\mathrm{Sep}(AB)}(\mathbf{M}_{0})\geq\frac{p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{M}_{0})}{\max{N\in\mathrm{Sep}(AB)}p_{\mathrm{succ}}(\mathcal{E}_{0},\mathbf{N})}-1\geq
D-1\ .$ (42)

_(ii)_ _Multiparticle case_ We proceed analogously to the biparticle case.
Consider a random uniform ensemble of $M=2^{N}$ Haar random, independant and
identically distributed pure states in $\mathcal{H}_{N}$,

$\mathcal{E}_{\mathrm{Haar}}=\left\\{{\frac{1}{2^{N}},\Psi_{i}}\right\\}_{i=1}^{2^{N}}\
.$ (43)

The above ensemble is random as states composing it are independent random
pure states i.e. $\Psi_{i}=U_{i}\Psi_{0}U^{\dagger}_{i}$, for $U_{i}$
distributed according to Haar measure on the group
$\mathrm{U}(\mathcal{H}_{N})$. In [55] it was shown that in the limit of large
$N$, for typical realizations of the ensemble $\mathcal{E}_{\mathrm{Haar}}$
the so-called pretty good measurement
$\mathbf{M}_{PGM}(\mathcal{E}_{\mathrm{Haar}})$ is capable to to distinguish
states from $\mathcal{E}_{\mathrm{Haar}}$ with success probability bounded
away form zero

$p_{\mathrm{succ}}(\mathcal{E}_{\mathrm{Haar}},\mathbf{M}_{PGM}(\mathcal{E}_{\mathrm{Haar}}))\geq
0.7\ .$ (44)

Importantly, since states $\Psi_{i}$ are Haar random, they are typically
highly entangled and this causes them to be indistinguishable by separable
measurements. To show this we will use a result that can be found in the proof
of Theorem 2 form [65], which states that for Haar random pure state $\Psi$
with probability $P\leq\mathrm{exp}(-N^{2})$

$\max_{\phi\in\mathrm{SEP}}\operatorname{tr}(\phi\Psi)\geq\frac{8N^{2}}{2^{N}}\
,$ (45)

where the maximum is over all separable pure states on $\mathcal{H}_{N}$. Now,
since states $\Psi_{i}$ are iid Haar-random, by the union bound, we get that
with probability $q\geq 1-2^{N}\mathrm{exp}(-N^{2})$, in the limit of large
dimensions

$\forall_{i}\
\max_{\phi\in\mathrm{SEP}}\operatorname{tr}(\phi\Psi_{i})\leq\frac{8N^{2}}{2^{N}}\
.$ (46)

The above bound (which holds with high probability as $N\rightarrow\infty$)
can be the used to upper bound the success probability of discrimination of
states from the the ensemble. Note that for every separable effect $N_{i}$ we
have
$\operatorname{tr}(\Psi_{i}N_{i})\leq\operatorname{tr}(N_{i})\max_{\phi\mathrm{SEP}}\operatorname{tr}(\phi\Psi_{i})\leq\operatorname{tr}(N_{i})\frac{8N^{2}}{2^{N}}$.
Using this we obtain

$p_{\mathrm{succ}}(\mathcal{E}_{\mathrm{Haar}},\mathbf{N})\leq\frac{1}{2^{N}}\sum_{i=1}^{2^{N}}\operatorname{tr}(N_{i})\frac{2^{N}}{8N^{2}}=\frac{8N^{2}}{2^{N}}\
.$ (47)

Finally, combining (44), (47), and the operational characterisation of
$R_{\mathrm{Sep}(N)}$ we obtain the desired lower bound by realizing that
there exist a realization of a random ensemble $\mathcal{E}_{\mathrm{Haar}}$
such that

$\max_{\mathbf{M}}R_{\mathrm{Sep}(N)}(\mathbf{M})\geq\frac{p_{\mathrm{succ}}(\mathcal{E}_{\mathrm{Haar}},\mathbf{M}_{PGM}(\mathcal{E}_{\mathrm{Haar}}))}{\max_{\mathbf{N}\in\mathrm{Sep}(N)}p_{\mathrm{succ}}(\mathcal{E}_{\mathrm{Haar}},\mathbf{N})}-1\geq
c\frac{2^{N}}{8N^{2}}-1\ .$ (48)

∎