# Computing Well-Covered Vector Spaces of Graphs
Using Modular Decomposition

Martin Milanič
FAMNIT and IAM, University of Primorska
<EMAIL_ADDRESS>
Nevena Pivač
FAMNIT and IAM, University of Primorska
<EMAIL_ADDRESS>
###### Abstract

A graph is well-covered if all its maximal independent sets have the same
cardinality. This concept was introduced by Plummer in 1970 and naturally
generalizes to the weighted case. Given a graph $G$, a real-valued vertex
weight function $w$ is said to be a well-covered weighting of $G$ if all its
maximal independent sets are of the same weight with respect to $w$. The set
of all well-covered weightings of a graph $G$ forms a vector space over the
field of real numbers, called the _well-covered vector space_ of $G$. Since
the problem of recognizing well-covered graphs is
$\mathsf{co}$-$\mathsf{NP}$-complete, the problem of computing the well-
covered vector space of a given graph is $\mathsf{co}$-$\mathsf{NP}$-hard.
Levit and Tankus showed in 2015 that the problem admits a polynomial-time
algorithm in the class of claw-free graphs. In this paper, we give two general
reductions for the problem, one based on anti-neighborhoods and one based on
modular decomposition, combined with Gaussian elimination. Building on these
results, we develop a polynomial-time algorithm for computing the well-covered
vector space of a given fork-free graph, generalizing the result of Levit and
Tankus. Our approach implies a polynomial-time recognition algorithm for the
class of well-covered fork-free graphs and also generalizes some known results
on cographs.

Keywords: weighted well-covered graph, well-covered vector space, modular
decomposition, Gaussian elimination, fork-free graph, cograph

MSC Codes (2020): 05C85 (Primary) 05C69, 05C75, 05C50, 15A03 (Secondary)

##  1 Introduction

An _independent set_ in a graph $G$ is a set of pairwise nonadjacent vertices.
An independent set in a graph $G$ is said to be maximum if it has maximum
cardinality and maximal if it is not contained in any larger independent set.
The problem of finding a maximum independent set in a given graph, known as
Maximum Independent Set, is one of the classical $\mathsf{NP}$-hard problems
[MR0378476]. While every maximum independent set in a graph is also a maximal
one, the opposite implication does not hold in general. If every maximal
independent set in a graph $G$ is also a maximum one, the graph $G$ is said to
be well-covered. Well-covered graphs were introduced by Plummer in 1970
[zbMATH03310754] and have been extensively studied in the literature (see
[MR1677797] for an introduction and [MR1254158] for a survey). One of the
motivations for the study of well-covered graphs stems from the fact that
Maximum Independent Set is solvable in linear time in the class of well-
covered graphs by a simple greedy algorithm that computes a maximal
independent set.

Two central research directions on well-covered graphs are the study of their
recognition and their characterizations in special graph classes. As proved
independently by Sankaranarayana and Stewart in 1992 [zbMATH00039777] and by
Chvátal and Slater in 1993 [zbMATH00434906], the recognition of well-covered
graphs is $\mathsf{co}$-$\mathsf{NP}$-complete. In Plummer’s survey from 1993
(see [MR1254158]) one can find results on various restrictions of the well-
coveredeness property defining special subclasses of well-covered graphs, as
well as an overview of the study of well-coveredeness versus the girth and the
maximum degree. After Plummer’s survey, the study of well-covered graphs
focused mostly on the recognition problem in special cases. In particular,
Caro, Sebő, and Tarsi showed that the recognition of well-covered graphs
remains $\mathsf{co}$-$\mathsf{NP}$-complete even for $K_{1,4}$-free graphs
[zbMATH00845871], Brown and Hoshino established
$\mathsf{co}$-$\mathsf{NP}$-completeness for the class of circulant graphs
[MR2739910], and a careful examination of the reduction due to Sankaranarayana
and Stewart [zbMATH00039777] shows that the problem remains
$\mathsf{co}$-$\mathsf{NP}$-complete in the class of weakly chordal graphs,
that is, graphs such that neither the graph nor its complement contain an
induced cycle of length at least five. On the positive side, Tankus and Tarsi
showed that the problem is polynomial-time solvable in the class of claw-free
graphs (see [zbMATH00934795, zbMATH01006762]). The well-coveredness property
can also be tested efficiently in the classes of bipartite graphs
[zbMATH03614795, zbMATH03799694], graphs with girth at least $5$
[zbMATH00130578], graphs without cycles of lengths $4$ and $5$
[zbMATH00682532], chordal graphs [zbMATH00845475], graphs of bounded degree
[zbMATH01200865], perfect graphs with bounded clique number [MR1264476],
various generalizations of the class of cographs [Klein2013, Araujo2019], and
graphs of bounded cliquewidth [MR3851408]. The problem has also been studied
from the parameterized complexity point of view, by Alves, Dabrowski, Faria,
Klein, Sau, and Souza [MR3851408] and Araújo, Costa, Klein, Sampaio, and Souza
[Araujo2019].

In this paper we focus on a weighted generalization of well-coveredness. If
every vertex of a graph $G$ is assigned a real number, that is, the _weight_
of a vertex, we speak about a _weighted graph_. Maximum Weight Independent Set
is the problem of computing an independent set of maximum weight in a given
weighted graph, where the weight of a set of vertices is defined as the sum of
the weights of its members. Given a graph $G$ and a weight function
$w:V(G)\to\mathbb{R}$, a graph $G$ is said to be _$w$ -well-covered_ if all
maximal independent sets in $G$ are of the same weight with respect to the
weight function $w$. The concept of $w$-well-covered graphs was introduced by
Caro, Ellingham, and Ramey in 1998 [zbMATH01200865], in the more general
context of weight functions mapping the vertices of a graph to the elements of
an abelian group (see also [zbMATH05029664]). Graphs that are $w$-well-covered
with respect to some _nonnegative_ weight function $w:V(G)\to\mathbb{R}_{+}$
that is not identically equal to $0$ are exactly the complements of the so-
called _stochastic_ graphs studied already in 1983 by Berge [zbMATH03813669],
and generalize the _equistable_ graphs introduced in 1980 by Payan [MR553649]
and defined as the graphs that admit a weight function
$w:V(G)\to\mathbb{R}_{+}$ such that a set $S\subseteq V(G)$ is a maximal
independent set if and only if the total weight of $S$ equals $1$.

Given a graph $G$, a _well-covered weighting_ of $G$ is any real-valued weight
function $w$ on the vertices of $G$ such that $G$ is $w$-well-covered. For
every graph $G$, the set ${\rm WCW}(G)$ of all well-covered weightings of $G$
forms a vector space over the field of real numbers (see [zbMATH01334515,
zbMATH05029664]); we refer to it as the _well-covered vector space_ of $G$.
Similar vector spaces can be defined for more general situations, for example
for hypergraphs and for vertex weight functions that assign to each vertex of
$G$ a value from some fixed field $\mathbb{F}$ (see Caro and Yuster
[zbMATH01334515] and Brown and Nowakowski [zbMATH05029664]). In this paper we
restrict our attention to the case of graphs and the field of real numbers.
Any system of equations representing the vector space ${\rm WCW}(G)$ will be
referred to as a _well-covering system_ of $G$. (Precise definitions will be
given in Section 2.) We consider the following problem.

Well-Covering System
Instance: A graph $G=(V,E)$. Question: Compute a well-covering system of $G$.

A graph is well-covered if and only if the vertex weight function that is
constantly equal to $1$ belongs to the well-covered vector space of the graph.
Therefore, since the problem of recognizing well-covered graphs is
$\mathsf{co}$-$\mathsf{NP}$-complete, the more general Well-Covering System
problem is $\mathsf{co}$-$\mathsf{NP}$-hard.

The _well-covered dimension_ of $G$ is denoted by ${\rm wcdim}(G)$ and defined
as the dimension of the well-covered vector space of $G$. Clearly, a graph $G$
has well-covered dimension equal to zero if and only if the only well-covered
weighting of $G$ is the identically zero function. Such graphs are known to
exist; for instance, the Petersen graph and any cycle with at least $8$
vertices are among them (see [zbMATH01200865, zbMATH01334515]). However, to
the best of our knowledge, the complexity of computing the well-covered
dimension of a graph is open, even in the special case of recognizing graphs
with positive well-covered dimension. Caro and Yuster proved that the well-
covered dimension of a tree is equal to the number of leaves [zbMATH01334515].
Brown and Nowakowski generalized this result to the class of chordal graphs
[zbMATH05029664] by showing that in this case the well-covered dimension
equals the number of simplicial cliques. They also showed that the well-
covered dimension can be computed in polynomial time for cographs, for graphs
with independence number at most two, and for chordal graphs. The well-covered
dimension of certain product graphs was studied by Birnbaum, Kuneli, McDonald,
Urabe, and Vega [MR3268692] and for Levi graphs of point-line configurations
by Hauschild, Ortis, and Vega [MR3404664].

Well-covered vector spaces of graphs containing no cycles of length $4$ were
studied by Brown, Nowakowski, and Zverovich [brown2007structure]. Well-
Covering System can be solved in polynomial time in classes of graphs of
bounded vertex degree, as shown by Caro, Ellingham, and Ramey
[zbMATH01200865], in the class of graphs with girth at least $7$, as shown by
Caro and Yuster [zbMATH01334515], and, as shown by Levit and Tankus, in the
class of claw-free graphs [levit2015weighted] and in the class of graphs
without cycles of lengths $4$, $5$, and $6$ [MR3325553].

### Our results and relation with existing works

In this paper, we give two general reductions for the Well-Covering System
problem, one based on modular decomposition and one based on anti-
neighborhoods. Building on these results, we develop a polynomial-time
algorithm for solving the problem in the class of fork-free graphs, thereby
generalizing the analogous result of Levit and Tankus on claw-free graphs
[levit2015weighted]. The algorithm decomposes a given fork-free graph $G$ into
a polynomial number of induced subgraphs of $G$ and recursively computes a
well-covering system for every graph $H$ constructed at some step of the
decomposition of $G$. To keep the well-covering systems polynomially bounded
in size, Gaussian elimination is applied at each step. In the base case, when
the subgraph $H$ cannot be decomposed further, we use a structural result on
fork-free graphs due to Lozin and Milanič [MR2373852, lozin2008polynomial]
(see also [MR4276974]) to infer that $H$ is claw-free; hence, in this case the
algorithm of Levit and Tankus applies.

The class of fork-free graphs generalizes the class of cographs, hence our
results generalize the result of Brown and Nowakowski [zbMATH05029664] that
the well-covered dimension of cographs can be computed in polynomial time.
Furthermore, our reduction involving modular decomposition generalizes the
analogous reduction for the (unweighted) well-covered graphs due to Klein, de
Mello, and Morgana [Klein2013], who used modular and primeval decompositions
to develop efficient algorithms for the problem of recognizing well-covered
graphs in several extensions of the class of cographs.

Our main result, a polynomial-time algorithm for computing a well-covering
system of a given fork-free graph, is another example of an application of the
structural result from [MR2373852, lozin2008polynomial] relating fork-free
graphs to claw-free graphs (the exact statement of the result is given in
LABEL:thm:fork-free). This result was first used for developing a polynomial-
time algorithm for Maximum Weight Independent Set in the class of fork-free
graphs [MR2373852, lozin2008polynomial]. More recently it has been used by
Dyer, Martin, Jerrum, Müller, and Vušković [MR4276974] for developing a fully
polynomial randomized approximation scheme (FPRAS) for the problem of counting
all weighted independent sets in a (fork, odd hole)-free graph [MR4276974] and
by Dębski, Lonc, Okrasa, Piecyk, and Rzążewski [debski2022computing] for
developing a polynomial-time algorithm for $W_{5}$-Coloring (a certain
homomorphism problem) in the class of fork-free graphs.

### Structure of the paper

In Section 2 we collect the necessary definitions and preliminaries, including
preliminaries on modular decomposition and precise definitions about well-
covering systems. In LABEL:sec:prime we show how to use modular decomposition,
combined with Gaussian elimination, to reduce the problem of computing a well-
covering system of a graph to the same problem on certain prime induced
subgraphs of the graph. In LABEL:sec:cographs we develop an algorithm for
computing a well-covering system of a given cograph that is faster than the
algorithm following from the main result of LABEL:sec:prime. In
LABEL:sec:anti-neighborhoods we show how to reduce the problem of computing a
well-covering system of a graph to the same problem on the subgraphs of a
given graph obtained by deleting the closed neighborhood of some vertex. In
LABEL:sec:fork-free we apply the results from LABEL:sec:prime and
LABEL:sec:anti-neighborhoods to develop a polynomial-time algorithm for
computing a well-covering system of a given fork-free graph. We conclude the
paper with a summary and some open problems in LABEL:sec:conclusion.

##  2 Preliminaries

Given a positive integer $n$, we denote by $[n]$ the set $\\{1,\ldots,n\\}$
(and $[0]:=\emptyset$). All graphs in this paper are finite, simple, and
undirected. Given a graph $G$, we denote by $V(G)$ the vertex set of $G$ and
by $E(G)$ the edge set of $G$. Two vertices $u$ and $v$ are adjacent in $G$ if
$uv\in E(G)$. The neighborhood of a vertex $v$ in $G$ is the set of all
vertices adjacent to $v$ in $G$ and it is denoted by $N_{G}(v)$. The closed
neighborhood of $v$ is defined as $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. Given a
subset $S$ of vertices in $G$, we denote by $G[S]$ the graph induced by $S$,
that is, the subgraph of $G$ with vertex set $S$ and edge set $\\{uv:u,v\in
S,uv\in E(G)\\}$. A _connected component_ of $G$ is a maximal connected
subgraph of $G$. The _complement_ of a graph $G=(V,E)$ is a graph
$\overline{G}$ with vertex set $V$ in which two distinct vertices are adjacent
if and only if they are nonadjacent in $G$. A _co-connected component_ , or
simply _co-component_ , of $G$ is the subgraph of $G$ induced by the vertex
set of a connected component of the complement of $G$. A graph is _co-
connected_ if its complement is connected. Given two disjoint subsets $A$ and
$B$ of $V(G)$, we say that $A$ and $B$ are _complete_ (resp., _anticomplete_)
to each other in $G$ if $\\{ab:a\in A,b\in B\\}\subseteq E(G)$ (resp.,
$\\{ab:a\in A,b\in B\\}\cap E(G)=\emptyset)$.

For integers $m,n\geq 0$ we denote by $K_{m,n}$ the _complete bipartite graph_
with parts of sizes $m$ and $n$, that is, the graph whose vertices can be
partitioned into two independent sets $A$ and $B$, such that $|A|=m$, $|B|=n$,
and $A$ and $B$ are complete to each other. A _claw_ is the graph $K_{1,3}$. A
_fork_ is the graph obtained from a claw by a single subdivision of one of its
edges, that is, the graph with vertex set
$\\{v_{1},v_{2},v_{3},v_{3},v_{5}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{3}v_{5}\\}$. By $P_{n}$ we denote the
$n$-vertex _path graph_ , that is, a graph whose vertices can be linearly
ordered so that two vertices are adjacent if and only if they appear
consecutively in the ordering. Given two graphs $G$ and $H$, the graph $G$ is
said to be _$H$ -free_ if it contains no induced subgraph isomorphic to $H$.

A _rooted tree_ is a pair $(T,r)$ where $T$ is a tree and $r\in V(T)$ is the
_root_ of $T$. Given two nodes $u$ and $v$ in a rooted tree $T$, we say that
$v$ is a _child_ (or _successor_) of $u$ if $uv\in E(T)$ and $u$ belongs to
the unique $v,r$-path in $T$. A _leaf_ of a rooted tree $T$ is a node without
any successors, while an _internal node_ of $T$ is a node that is not a leaf.
Note that if $T$ is a one-vertex rooted tree, then the unique vertex in $T$ is
both the root and a leaf of $T$, but it is not an internal node. Given a
rooted tree $T$, we denote by $\ell(T)$ the number of leaves of $T$ and by
$i(T)=|V(T)|-\ell(T)$ the number of internal nodes of $T$. We will need the
following well-known property of rooted trees. To keep the paper self-
contained, we include a proof.

######  Lemma 2.1.

Let $T$ be a tree in which each internal node has at least two successors.
Then $\ell(T)\geq i(T)+1$.

###### Proof.

By induction on $i(T)$. If $i(T)=0$, then the unique vertex in $T$ is a leaf
and the inequality holds. Let now $T$ be a tree with $i(T)\geq 1$ such that
each internal node of $T$ has at least two successors, and assume that every
tree $T^{\prime}$ with $i(T^{\prime})<i(T)$ in which each internal node has at
least two successors satisfies that $\ell(T^{\prime})\geq i(T^{\prime})+1$.
Let $r$ be the root of $T$ and let $d$ be the number of successors of $r$.
Since $i(T)\geq 1$, the root of $T$ is an internal node. Hence $d\geq 2$. Let
$T_{1},\ldots,T_{d}$ be the rooted trees obtained by the deletion of $r$ from
$T$, where for each $j\in[r]$, the root of $T_{j}$ is the unique successor of
$r$ in $T_{j}$. Then for all $j\in[r]$ we have that $i(T_{j})<i(T)$, and by
the induction hypothesis every $T_{j}$ satisfies that $\ell(T_{j})\geq
i(T_{j})+1$. Observe that every internal node of $T_{j}$, $j\in[d]$, is also
internal in $T$, and node $r$ is internal in $T$ as well, so we have
$i(T)=1+\sum_{j=1}^{d}i(T_{j})$. Since $\ell(T)=\sum_{j=1}^{d}\ell(T_{j})$, we
conclude that
$\ell(T)\geq\sum_{j=1}^{d}\left(i(T_{j})+1\right)=\sum_{j=1}^{d}i(T_{j})+d\geq(i(T)-1)+2=i(T)+1$,
which completes the proof. ∎

######  Corollary 2.2.

Let $T$ be a tree in which each internal node has at least two successors.
Then $|E(T)|\leq 2\ell(T)-2$.

###### Proof.

By Lemma 2.1, we have $\ell(T)\geq i(T)+1$. Therefore,
$|V(T)|=i(T)+\ell(T)\leq 2\ell(T)-1$ and consequently $|E(T)|=|V(T)|-1\leq
2\ell(T)-2$. ∎

###  2.1 Modular decomposition

Given a graph $G$ and a nonempty set $M\subseteq V(G)$, we say that $M$ is a
_module_ in $G$ if every vertex not in $M$ is either adjacent to all vertices
in $M$ or to none of them. If $M_{1}$ and $M_{2}$ are two disjoint modules in
a graph $G$, then either $G$ contains all possible edges between $M_{1}$ and
$M_{2}$ in $G$, or none of them. A module $M$ is _maximal_ if $M\subset V(G)$
and there is no module $M^{\prime}$ in $G$ with $M\subset M^{\prime}\subset
V(G)$. If $G$ and its complement are both connected, then any two maximal
modules in $G$ are disjoint; in particular, the set of maximal modules of $G$
forms a partition of $V(G)$. A module $M$ of a graph $G$ is said to be
_strong_ if for every other module $M^{\prime}$ in $G$ it holds that either
$M\cap M^{\prime}=\emptyset$, $M\subseteq M^{\prime}$, or $M^{\prime}\subseteq
M$. A graph $G$ is prime if each of its maximal strong modules is a singleton.

Every graph with at least two vertices has a unique partition of its vertex
set into maximal strong modules (see, e.g., [habib2010survey]). If $G$ is
disconnected, then the partition is given by the vertex sets of its
components; if the complement of $G$ is disconnected, then the partition is
given by the vertex sets of its co-components. The _representative graph_
$R(G)$ of $G$ is any induced subgraph of $G$ obtained by taking an arbitrary
but fixed vertex from each maximal strong module of $G$. Note that the
representative graph of $G$ depends on how the vertices from the maximal
strong modules are chosen; however, any two such graphs are isomorphic to each
other, which explains the notation $R(G)$. The representative graph of $G$ is
a special case of the following more general construction. Given a graph $G$
and an arbitrary partition $\mathcal{P}=\\{M_{1},\dots,M_{k}\\}$ of $V(G)$
into modules of $G$, we denote by $G/{\mathcal{P}}$ the corresponding
_quotient graph_ , which is the induced subgraph of $G$ obtained by taking one
vertex from each module $M_{j}\in\mathcal{P}$.

Partitioning the vertex set of a graph $G$ recursively into maximal strong
modules leads to the so-called _modular decomposition_ of $G$, represented
with the so-called _modular decomposition tree_. This is a rooted tree $T_{G}$
such that every node of $T_{G}$ is labeled with an induced subgraph $H_{t}$ of
$G$, and every internal node of $T_{G}$ is of one of the types parallel,
series, or prime. The tree $T_{G}$ is defined recursively as follows.

  * •

If $G$ is the one-vertex graph, then $T_{G}$ has one node $t$, labeled with
$H_{t}=G$, and $t$ is the root of $T_{G}$.

  * •

Otherwise, $T_{G}$ is the rooted tree obtained by creating a root node $r$,
labeling the root by the representative graph of $G$ (that is, setting
$H_{r}=R(G)$), and joining the root $r$ with edges to the roots of the modular
decomposition trees $T_{1},\ldots,T_{k}$ of the subgraphs of $G$ induced by
the maximal strong modules $M_{1},\ldots,M_{k}$ of $G$. The root node of $G$
is of type _parallel_ if $G$ is disconnected, _series_ if the complement of
$G$ is disconnected, and prime if both $G$ and its complement are connected.
Each internal node $t$ of $T_{G}$ with $t\neq r$ belongs to a unique tree
$T_{i}$ and its type in $T_{G}$ is the same as in $T_{i}$.

Given a graph $G$, the modular decomposition tree $T_{G}$ of $G$ can be
computed in linear time (see [MR1687819, MR2500307]). By construction, for
every node $t\in V(T_{G})$, the subtree of $T_{G}$ rooted at $t$ is the
modular decomposition tree of the subgraph $G_{t}$ of $G$ induced by the
vertices appearing in the one-vertex subgraphs labeling the leaves of this
subtree. Furthermore, if the node $t$ is of type prime, then the graph $H_{t}$
labeling the node is a prime graph.

###  2.2 Well-covering systems

A weighted graph is a pair $(G,w)$ where $G$ is a graph and
$w\in\mathbb{R}^{V(G)}$, that is, $w:V(G)\to\mathbb{R}$ is a real-valued
vertex weight function. Given a weighted graph $(G,w)$ and a set $S\subseteq
V(G)$, the weight of $S$ (with respect to $w$) is defined as $w(S)=\sum_{v\in
S}w(v)$. Given a set $S\subseteq V(G)$, we denote by $w_{S}$ the _restriction
of $w$ to $S$_, that is, the function $w_{S}:S\to\mathbb{R}$ defined by
setting $w_{S}(v)=w(v)$ for all $v\in S$.

Given a weighted graph $(G,w)$, we say that $w$ is a _well-covered weighting_
of $G$ and that $G$ is _$w$ -well-covered_ if all maximal independent sets in
$G$ have the same weight with respect to $w$, that is, for every two maximal
independent sets $I$ and $I^{\prime}$ in $G$, we have $w(I)=w(I^{\prime})$.
Recall that for every graph $G$, the set ${\rm WCW}(G)$ of all well-covered
weightings of $G$ forms a vector space over the field of real numbers, called
the _well-covered vector space_ of $G$. Since we only work with finite graphs,
the well-covered vector space ${\rm WCW}(G)$ is always finite-dimensional and
thus has a finite basis (an inclusion-wise maximal linearly independent set of
vectors); furthermore, all bases of ${\rm WCW}(G)$ have the same cardinality,
which is referred to as the well-covered dimension of $G$. Clearly, for every
graph $G$, its well-covered dimension is an integer between $0$ and $|V(G)|$.

Well-covered vector spaces of graphs can also be represented using systems of
linear equations. Let $G$ be a graph with $n$ vertices. Fix an arbitrary
ordering $v_{1},\ldots,v_{n}$ of the vertices of $G$ and an arbitrary ordering
$I_{1},\ldots,I_{k}$ of all maximal independent sets in $G$. By definition, a
weight function $w:V(G)\to\mathbb{R}$ is a well-covered weighting of $G$ if
and only if $w$ satisfies the following system of ${k\choose 2}$ equations:

$w(I_{i})-w(I_{j})=0\quad\textrm{for any two distinct }i,j\in[k]\textrm{ with
}i<j\,.$ (1)

To distinguish between vectors of abstract variables of a system and vectors
of their concrete real values, we use the following convention throughout the
paper. To each vertex $v\in V(G)$ we associate a variable $x_{v}$, and write
the systems of equations using such variable names. For example, following
this convention, the system (1) corresponds to the following homogeneous
linear system over the set of variables $\\{x_{v}:v\in V(G)\\}$:

$\sum_{v\in I_{i}}x_{v}-\sum_{v\in I_{j}}x_{v}=0\quad\textrm{for any two
distinct }i,j\in[k]\textrm{ with }i<j\,.$ (2)

This system can be compactly represented with a single matrix equation

$Ax=0_{r}$

where $r={k\choose 2}$, $A\in\mathbb{R}^{r\times n}$ is the coefficient
matrix, and the right-hand side $0_{r}$ is the all-zero vector in
$\mathbb{R}^{r}$. Thus, a column vector
$w=(w(v_{1}),\ldots,w(v_{n}))^{\top}\in\mathbb{R}^{n}$ belongs to the well-
covered vector space ${\rm WCW}(G)$ if and only if $Aw=0_{r}$.

There are many ways to represent the well-covered vector space of a given
graph $G$ with a linear system. For example, a system equivalent to (2) with
$k-1$ equations can be obtained by requiring that all maximal independents
sets have the same weight as an arbitrary but fixed maximal independent set,
say $I_{k}$:

$\sum_{v\in I_{i}}x_{v}-\sum_{v\in I_{k}}x_{v}=0\quad\textrm{for all
}i\in[k-1]\,.$ (3)

Another equivalent system, also with $k-1$ equations, is the following:

$\sum_{v\in I_{i}}x_{v}-\sum_{v\in I_{i+1}}x_{v}=0\quad\textrm{for all
}i\in[k-1]\,.$ (4)

A _well-covering system_ of $G$ is any system ${\cal S}$ of linear homogeneous
equations over a set $\\{x_{v}:v\in V(G)\\}$ of variables indexed by the
vertices of $G$ such that a column vector
$w=(w(v_{1}),\ldots,w(v_{n}))^{\top}\in\mathbb{R}^{n}$ belongs to the well-
covered vector space ${\rm WCW}(G)$ if and only if it satisfies all the
equations of the system. Given a well-covering system ${\cal S}$ of $G$, we
denote by $|{\cal S}|$ the _size_ of ${\cal S}$, that is, the number of
equations in ${\cal S}$. As shown by systems (2) and (3), the same graph can
admit well-covering systems of different sizes.

We will soon illustrate these concepts with a concrete example, but first let
us discuss two important remarks about properties of well-covering systems.

A remark on the size of well-covering systems. The number of maximal
independent sets in an $n$-vertex graph can be exponential in $n$.111For
example, the $2n$-vertex graph consisting of $n$ isolated edges has $2^{n}$
maximal independent sets. However, using Gaussian elimination it can be shown
that any well-covering system of an $n$-vertex graph admits a well-covering
subsystem of size at most $n$ (see LABEL:lem:reduced-well-covering).

Consider an arbitrary well-covering system ${\cal S}$ of an $n$-vertex graph
$G$ and let $r$ be the size of ${\cal S}$. Fix an arbitrary ordering of the
vertices of $G$ and an arbitrary ordering of the equations in ${\cal S}$. Let
$A\in\mathbb{R}^{r\times n}$ be the coefficient matrix of ${\cal S}$. We say
that a well-covering system ${\cal S}$ is _linearly independent_ if the rows
of the corresponding matrix $A$ are linearly independent over the field of
real numbers. In this case, the $r$ rows of $A$ form a basis of the orthogonal
complement of the vector space ${\rm WCW}(G)$, and hence by standard linear
algebra we have $r+{\rm wcdim}(G)=n$. In particular, in this case we have
$r\leq n$, and equality holds if and only if ${\rm wcdim}(G)=0$, that is, the
all-zero weighting is the only well-covered weighting of $G$.

A remark on the coefficients of well-covering systems. Since we consider the
well-covered vector space ${\rm WCW}(G)$ of a graph $G$ as a vector space over
the field of real numbers, any well-covering system of $G$ consists of linear
equations involving real numbers as coefficients. However, it often suffices
to work with well-covering systems whose coefficients belong to a particular
subset of the set of real numbers. We say that a well-covering system is
_unit_ if the matrix of the system has all the coefficients in the set
$\\{-1,0,1\\}$, _integer_ if the system consists of linear equations involving
only integer coefficients, and _rational_ if it consists of linear equations
involving only rational coefficients. Note that systems (2), (3), and (4) are
all unit. Furthermore, the well-covering systems of fork-free graphs
constructed by the algorithm given by our main result (LABEL:thm:main) are
also unit.

######  Example 2.3.

Let $G$ be the _bull graph_ , that is, the graph obtained from the $5$-vertex
path with vertices $v_{1},\ldots,v_{5}$ in order along the path by adding to
it the edge $v_{2}v_{4}$. Then $G$ has exactly three maximal independent sets:
$I_{1}=\\{v_{1},v_{4}\\}$, $I_{2}=\\{v_{2},v_{5}\\}$, and
$I_{3}=\\{v_{1},v_{3},v_{5}\\}$. Any well-covered weighting $w$ of $G$ must
satisfy that $w(I_{1})=w(I_{2})=w(I_{3})$, or equivalently,
$w(I_{1})-w(I_{3})=0$ and $w(I_{2})-w(I_{3})=0$. This yields the following
linearly independent unit well-covering system ${\cal S}$ of $G$ with size
$r=2$:


# Receiver-Device-Independent Quantum Key Distribution Protocols

Marie Ioannou  Department of Applied Physics University of Geneva, 1211
Geneva, Switzerland  Pavel Sekatski  Department of Applied Physics University
of Geneva, 1211 Geneva, Switzerland  Alastair A. Abbott  Department of Applied
Physics University of Geneva, 1211 Geneva, Switzerland  Univ. Grenoble Alpes,
Inria, 38000 Grenoble, France  Denis Rosset  Department of Applied Physics
University of Geneva, 1211 Geneva, Switzerland  Jean-Daniel Bancal  Department
of Applied Physics University of Geneva, 1211 Geneva, Switzerland  Université
Paris-Saclay, CEA, CNRS, Institut de physique théorique, 91191, Gif-sur-
Yvette, France  Nicolas Brunner  Department of Applied Physics University of
Geneva, 1211 Geneva, Switzerland

###### Abstract

We consider a receiver-device-independent (RDI) approach to quantum key
distribution. Specifically, we discuss protocols for a prepare-and-measure
scenario and present a detailed security analysis. The sender’s (Alice’s)
device is partially characterized, in the sense that we assume bounds on the
overlaps of the prepared quantum states. The receiver’s (Bob’s) device
requires no characterisation and can be represented as a black-box. Our
protocols are therefore robust to any attack on Bob, such as blinding attacks.
In particular, we show that a secret key can be established even when the
quantum channel has arbitrarily low transmission by considering RDI protocols
exploiting sufficiently many states. Finally, we discuss how the hypothesis of
bounded overlaps can be naturally applied to practical devices.

##  I Introduction

Quantum key distribution (QKD) [1, 2] allows two users to establish a secret
key via a quantum channel and an authenticated but public classical channel.
QKD, together with the one time pad method, provides a secure method of
communication with information-theoretical security [3]. Indeed, unlike
classical schemes, the security of QKD protocols is physical: it only relies
on some knowledge about the functioning of the devices controlled by the
communicating parties and the general laws of quantum mechanics. Nevertheless,
different approaches require different levels of detail in how the devices are
modeled [4, 5, 6, 7]. The “standard” approach presumes a full description of
different elements in the setup. Such QKD systems are available commercially
and can reach high rates over long distances.

However, relying on a detailed quantum model for characterizing the devices
may open backdoors that quantum hackers can exploit. Indeed a mathematical
model always represents (at best) an idealization of a practical device. For
example, the well-known “blinding attacks” exploit the fact that standard
models for describing photon detectors typically fail when the intensity of
the incoming light falls outside their working range [8, 9]. When a fair-
sampling type assumption is used on top of this, the door is open to attacks
where an eavesdropper Eve obtains full information about the key, without
introducing any detectable level of errors.

This motivates the investigation of the stronger, device-independent (DI)
approach. Here, devices are viewed as classically controlled black boxes, and
the security of QKD protocols can be demonstrated [10, 11, 12, 13] assuming
only that (i) the devices can be described accurately within quantum
mechanics, and (ii) no information about the secret key leaks out of the
laboratories of Alice and Bob (the two communicating parties). While this
approach represents, in principle, the perfect solution to counter any hacking
attack, its practical implementation is highly challenging, requiring the
distribution of high-quality entanglement and notably high detection
efficiencies (the best current protocol demands $68.5\%$ [14]). First proof-
of-principle experiments have recently been reported [15, 16, 14], but any
practical implementation of DI QKD is arguably still far out of reach.

Beyond the standard (device-dependent) approach and the DI one, there exists a
broad range of models that can be considered, where some of the devices are
fully (or partially) characterized, while others are treated as black boxes.
These include semi-DI [17, 18, 19], one-sided DI [20] and measurement-DI (MDI)
[21, 22] protocols. While the last approach has been extensively studied and
realized experimentally achieving record distances (see e.g. [23, 24, 25,
26]), the former two models have been less explored and, thus far, not
experimentally demonstrated.

In this work we propose a new approach, which we call “receiver-device-
independent” (RDI). A specific example of such a protocol was recently
presented, along with an experimental realisation, in the companion paper
[27]. Here, we present a more general class of RDI-QKD protocols and provide a
detailed theoretical analysis, investigating the possibilities and limits of
QKD in RDI scenarios.

We thereby consider a prepare-and-measure scenario, where the sender (Alice)
uses a partially characterized device, while the receiver (Bob) uses an
untrusted device. The protocol being black-box on Bob’s side, it is therefore
inherently secure against attacks on the receiver, notably blinding attacks
[8, 9]. On Alice’s side, the characterisation we require consists in providing
bounds on the (complex) overlaps of the prepared states (given formally by a
Gram matrix). We moreover discuss how this hypothesis can be naturally applied
to practical devices.

In practice, the RDI scenario can be quite naturally motivated. Consider for
instance a large company communicating with an end-user. The latter has
essentially no means to test their cryptographic device, which is therefore
conveniently treated as a black-box. On the other hand, the company has access
to advanced technology and technical expertise, and can therefore regularly
test and characterize their cryptographic device. We note that the MDI
approach is not applicable to this scenario, as both Alice and Bob require a
trusted device (while trust is then relaxed on an intermediate relay station).

The paper is organized as follows. In Section II we present the scenario of
RDI QKD and discuss the key assumptions that are made, before outlining the
RDI-QKD themselves in Section III. In Section IV we present a detailed
security analysis. In the noiseless case we present an analytical security
proof, showing that our protocols can achieve the maximal distance possible in
an RDI scenario. Specifically, we show that it is possible to obtain a
positive key rate for any transmission $\eta>1/n$, where $n$ denotes the
states prepared by Alice, and corresponds also to the number of measurements
performed by Bob. Hence by considering sufficiently many states, our RDI
protocol can, in principle, accommodate any amount of losses. When noise is
present, the security analysis relies on semidefinite programming, providing
lower bounds on the key rate. Then, in Section V, we discuss the practical
relevance of our RDI approach, in particular how bounds on the overlaps (Gram
matrix) can be estimated and justified in practice. Finally, in Section VI we
discuss how our protocol compares to other QKD protocols and scenarios.

##  II Scenario

Figure 1: Scenario: Alice and Bob can establish secret key based on the Gram
matrix $G$ of the set of states $\\{\ket{\psi_{x}}\\}_{x}$ prepared by Alice
and the observed data $p(b|x,y)$. Eve has a complete control on the quantum
channel, and can also have full knowledge of the functioning of the devices of
Alice and Bob.

We consider a prepare-and-measure scenario as shown in Fig. 1. Alice sends,
over a public quantum channel, one state out of a set of $n$ states
$\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$. Bob chooses among $n$ measurements
labelled by $y=0,\dots,n-1$. All measurements have binary outputs $b=0,1$.
After many rounds, Alice and Bob can estimate the probability distribution
$p(b|x,y)$. Bob’s measurement device is completely uncharacterized and can be
seen as a black box with an input $y$ and an output $b$. The black box feature
is a requirement if we aim to design a protocol robust to attacks where Eve
controls Bob’s device. The key assumption we make on the setup is about
Alice’s preparations. Namely, we assume that all inner-products
$\gamma_{ij}=\innerproduct{\psi_{i}}{\psi_{j}}$ are bounded. These assumptions
do not fix the total dimension of the Hilbert space and only partially
characterize Alice’s device.

The assumption that Alice prepares pure states with known inner-products
$\gamma_{ij}$ simplifies the presentation and analysis of the protocol, but is
evidently impossible to fulfil exactly in practice. In Sec. V we revisit this
assumption on Alice’s preparation device and show how the presence of noise,
unavoidable in experiments, can also be analyzed within our framework in
several ways. In particular, we show that the general situation where the
preparation device is subject to fluctuating noise, which remains within a
certain parameter window, can be analyzed by taking inequality constraints on
(the real and imaginary parts of) the values $\gamma_{ij}$.

Besides the assumption on Alice’s preparation device, specific to our
protocol, we also make the standard QKD assumptions, also made in the DI
scenario: (i) Alice’s input $x$ and Bob’s measurement setting $y$ are
completely uncorrelated from Eve; (ii) Eve only has access to the classical
and quantum communication specified by the protocol, she cannot gather any
additional information about $x$ and $y$; (iii) We assume the validity of
quantum physics. In the following, Eve is restricted to collective attacks.
She interacts with each round independently and can store her system in a
quantum memory.

As we will see, a lower bound on the raw secret key rate, can be computed
solely from the observed statistics $p(b|x,y)$, given that the setup satisfies
the assumptions detailed above.

##  III Protocols

In this section we describe the general structure of the RDI-QKD protocols we
consider and give a family of concrete examples. For simplicity we do not
treat the classical steps associated to parameter estimation, error
correction, key extraction and authentication. Under the assumption of
collective attacks these steps can be included easily following standard
techniques [4, 7]. The security analysis under coherent attacks is left out
for future work.

###  III.1 General structure

We begin by presenting the general structure of our RDI-QKD protocols.

Consider a given ensemble of states $\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ that
Alice is able to prepare and binary measurements
$\\{B_{0|y},B_{1|y}\\}_{y=0}^{n-1}$ that Bob can perform. We can now define
protocols with a general structure as follows.

RDI-protocol Steps to generate a sifted key between Alice and Bob.

Alice and Bob share an authenticated classical channel as well as a quantum
channel.

  1. 1.

Raw key generation

1: Alice randomly chooses a pair of integers ${\mathbf{r}}=(r_{0},r_{1})$ with
$0\leq r_{0}<r_{1}\leq n-1$ and a bit $k=0,1$. According to her choice she
sends the state $\ket{\psi_{x=r_{k}}}$ over the quantum channel to Bob.

2: Bob randomly chooses an integer $y$ with $0\leq y\leq n-1$ and performs the
binary measurement $\\{B_{0|y},B_{1|y}\\}$ on the state received from Alice.

  2. 2.

Sifting
Alice and Bob use the classical channel to communicate.

1: if $b=1$ then

2: Bob tells Alice to discard the round.

3: else if $b=0$ then

4: Bob asks Alice to reveal $\mathbf{r}$.

5: Alice reveals $\mathbf{r}$.

6: if $y=r_{0}$ or $y=r_{1}$ then

7: Bob tells Alice the round is conclusive.

8: else

9: Bob tells Alice to discard the round.

10: end if

11: end if

This structure defines a broad class of protocols specified by the choices of
$n$, the states $\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$, and the measurements
$\\{B_{0|y},B_{1|y}\\}_{y=0}^{n-1}$. In general, the idea is to choose states
and measurements such that, in Step 2.7, Bob can readily infer from the
observed outcome $b$ what the key bit $k$ of Alice is. Below we will describe
in more detail some specific such examples, which will clarify the principles
behind the RDI protocols we describe.

###  III.2 Ideal qubit protocol

We describe a class of protocols based on qubit states and measurements. These
can be considered ideal protocols in the sense of robustness to loss and
noise.

Alice prepares states from a set of $n$ single-qubit states
$\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ with

$\ket{\psi_{x}}=\cos(\theta/2)\ket{0}+e^{\frac{i2\pi}{n}x}\sin(\theta/2)\ket{1}$
(1)

for some given $\theta$. Following the general protocol outlined above, to
encode the raw key bit Alice chooses a pair of integers
$\mathbf{r}=(r_{0},r_{1})$ with $0\leq r_{0}<r_{1}\leq n-1$, among ${n\choose
2}$ possible pairs. For a key bit $k$, Alice sets $x=r_{k}$. Note that every
state $x$ can encode the bit value $0$ or $1$. Alice sends
$\ket{\psi_{x=r_{k}}}$ via the quantum channel to Bob. Bob has $y=0,\dots,n-1$
measurements and each measurement has a binary output $b=0,1$. The output
$b=1$ corresponds to a projection onto $\ket{\psi_{y}}$ while $b=0$
corresponds to the projection on the orthogonal subspace
$\mathbb{1}-\outerproduct{\psi_{y}}{\psi_{y}}$. If Bob observes $b=0$, he can
with certainty exclude the state $x=y$. We refer to the rounds where $b=0$ as
conclusive rounds. If the round is conclusive, Bob asks Alice to reveal
$\mathbf{r}$. If $y=r_{0}$ or $y=r_{1}$, Bob is able to infer the raw key bit
and announces to Alice that the round is successful; otherwise he tells Alice
to discard the round. The performance of this protocol, with respect to noise
and loss, is described below in Section IV.2. Moreover, in Section IV.3 we
show that this protocol is optimal within RDI-QKD protocols in the sense that
it yields a positive key rate for any $\eta>\frac{1}{n}$, arbitrarily close to
the threshold of $1/n$ beyond which no secret key can be established.

###  III.3 Towards practical protocols

While the above ideal qubit protocol is useful to test the limits of model,
the RDI approach can also be used quite naturally, and give good protocols, in
more realistic setups.

Firstly, the requirement that Alice prepares pure states is not necessary.
Indeed, the case of mixed states can naturally be encompassed by considering
purifications of the states Alice prepares. We discuss how to take into
account the overlap assumption on Alice’s device in this case in Section V.1.

Secondly, the qubit protocol described above can be adapted quite naturally to
an optical setup, where a dimension bound on the states Alice prepares is
unrealistic. This is because only the overlaps of the prepared states is
required (their Gram matrix), but not their Hilbert space dimension. One can
therefore consider a protocol where polarized coherent states of light are
prepared, as reported recently in the companion paper [27]. Therein a proof-
of-principle implementation of such a protocol was reported, achieving finite-
size key over a 4.8km optical fiber.

##  IV Security analysis

Eve’s information about the secret bit $k$ is bounded by assuming that the
Gram matrix $G$ of the set of encoding states is fully characterized and that
the probabilities $p(b|x,y)$ are perfectly estimated by Alice and Bob. The
Gram matrix $G$ is a Hermitian matrix whose entries are given by

$G_{ij}=\innerproduct{\psi_{i}}{\psi_{j}}.$ (2)

We do not bound the dimension of the Hilbert space associated to the system
sent by Alice. However, under the assumption that Alice prepares pure states
the rank of the Gram matrix equals the dimension of the subspace spanned by
these states. Recall that this assumption is not indispensable for our
analysis, and will be relaxed in Sec. V. Furthermore, no characterization of
the exact encoding, transmission channel nor measurement device is needed. Eve
can correlate herself to the states prepared by Alice, she can design Bob’s
measurement device by the means of an ancilla and a unitary operation, and she
can use a quantum memory to keep her ancilla until the end of the classical
post-processing (cf. Fig. 1). In fact, she can keep her ancilla until any
later time and wait until the reconciliation between Alice and Bob is over in
order to perform a measurement allowing her to extract as much information as
possible about the secret bit $k$.

The asymptotic key rate (per round) is lower bounded by [28]

$\left[H(k|\text{Eve, succ})-H(k|\text{Bob, succ})\right]p(\text{succ}),$ (3)

where $H(k|\text{Eve(Bob), succ})$ is the entropy of $k$ conditional on
Eve(Bob) and the fact that a round is not discarded, and $p$(succ) is the
probability that a round is not discarded. Bob’s entropy can be upper-bounded
as $H(k|\text{Bob},\text{succ})\leq H_{2}(\text{QBER})$, where $H_{2}(\cdot)$
is the binary entropy and QBER is the quantum bit error rate. Eve’s
conditional entropy can be lower-bounded by the conditional min entropy

$\begin{split}H(k|\text{Eve},\text{succ})&\geq
H_{\min}(k|\text{Eve},\text{succ})\\\
&=-\log_{2}\left(p_{g}(e=k|\text{succ})\right),\end{split}$ (4)

which is in a one-to-one relation with the maximal probability
$p_{g}(e=k|\text{succ})$ that Eve guesses the bit $k$ correctly [29] if the
round was not discarded. Combing the two arguments, we can lower bound the key
rate by the quantity

$R=\left[-\log_{2}\left(p_{g}(e=k|\text{succ})\right)-H_{2}(\text{QBER})\right]p(\text{succ}).$
(5)

The QBER and $p(\text{succ})$ are extracted from the observed statistics
$p(b|x,y)$ while the guessing probability $p_{g}(e=x|\text{succ})$ needs to be
upper bounded in order to give a lower bound on $R$. Note that
$p(\text{succ})>0$: if $p(\text{succ})=0$ there is no raw key generation and
hence nothing for Eve to guess. The guessing probability is given by

$\displaystyle p_{g}(e=k|\text{succ})$
$\displaystyle=\frac{p(e=k,\text{succ})}{p(\text{succ})}$ (6)
$\displaystyle=\frac{\sum_{r=0}^{{n\choose
2}-1}p_{R}(r)\sum_{k=0}^{1}p_{K}(k)\sum_{y=0}^{n-1}p_{Y}(y)\tr{(\rho_{r_{k}}^{BE}M_{1|y}E_{k|r})(\delta_{y,r_{0}}+\delta_{y,r_{1}})}}{\sum_{r=0}^{{n\choose
2}-1}p_{R}(r)\sum_{k=0}^{1}p_{K}(k)\sum_{y=0}^{n-1}p_{Y}(y)\tr{(\rho_{r_{k}}^{BE}M_{1|y}\mathbb{1})(\delta_{y,r_{0}}+\delta_{y,r_{1}})}},$

where $M_{b|y}$ are Bob’s measurement operators with $b=0,1$ and
$y=0,\dots,n-1$, and $E_{k|r}$ are Eve’s measurement operators with $k=0,1$
and $r=0,\dots,{n\choose 2}-1$. $p_{R}(r)$, $p_{Y}(y)$ and $p_{K}(k)$ are the
probabilities of choosing the inputs $r$, $y$ and $k$. Hence,
$\sum_{r}p_{R}(r)=\sum_{k}p_{K}(k)=\sum_{y}p_{Y}(y)=1$, $p_{K}(k)\geq 0$
$\forall k$, $p_{Y}(y)\geq 0$ $\forall y$ and $p_{R}(r)\geq 0$ $\forall r$.
Here we will always we take the input probabilities to be uniformly random
over all inputs. As already mentioned, the dimension of the problem is not
bounded, so without loss of generality we can, using Naimark’s dilation
theorem, assume that Bob’s and Eve’s measurements are projectors satisfying
the following properties:

$\displaystyle M_{b|y}M_{b^{\prime}|y}=\delta_{b,b^{\prime}}M_{b|y}\;\;$
$\displaystyle\forall y$ (7) $\displaystyle\sum_{b}M_{b|y}=\mathbb{1}\;\;$
$\displaystyle\forall y$ $\displaystyle
E_{e|\mu}E_{e^{\prime}|\mu}=\delta_{e,e^{\prime}}E_{e|\mu}\;\;$
$\displaystyle\forall\mu$ $\displaystyle\sum_{e}E_{e|\mu}=\mathbb{1}\;\;$
$\displaystyle\forall\mu$ $\displaystyle[M_{b|y},E_{e|\mu}]=0\;\;$
$\displaystyle\forall b,e,y,\mu.$

The last property comes from the fact that Bob and Eve act on two different
Hilbert spaces.

###  IV.1 Semidefinite programming approach

Since $p(\text{succ})$ is extracted from the observed statistics, to upper
bound $p_{g}(e=k|\text{succ})$ we need just to upper bound
$p(e=k,\text{succ})$. To do this, we will use the method presented in [30]. In
particular, we use the approach described therein which provides a
semidefinite programming (SDP) hierarchy giving increasingly tight outer
approximations of the set of quantum correlations in discrete prepare-and-
measure scenarios compatible with a given Gram matrix. The hierarchy is known
to converge to the actual set of quantum correlations, whereas for a fixed
level it provides a tractable method of bounding the guessing probability over
correlations compatible with the observed statistics. This problem would,
without the hierarchy, be computationally intractable since no bound on the
Hilbert space dimension is assumed.

Let $\\{S_{i}\\}_{i=0}^{s-1}$ be a set of measurement operators and define the
moment matrix $\Gamma$ of size $ns\times ns$ as

$\Gamma=\sum_{x,x^{\prime}=0}^{n-1}\Gamma_{xx^{\prime}}\otimes\outerproduct{\hat{e}_{x}}{\hat{e}_{x^{\prime}}},$
(8)

where $\\{\ket{\hat{e}_{x}}\\}_{x=0}^{n-1}$ is an orthonormal basis of
$\mathbb{R}^{n}$ and we recall that $n$ is the number of states prepared by
Alice. The sub-blocks $\Gamma_{xx^{\prime}}$ are defined as

$\Gamma_{xx^{\prime}}=\sum_{i,j=0}^{s-1}\bra{\psi_{x}}S_{i}^{\dagger}S_{j}\ket{\psi_{x}^{\prime}}\otimes\outerproduct*{\hat{\hat{e}}_{j}}{\hat{\hat{e}}_{j}}$
(9)

where $\\{\ket*{\hat{\hat{e}}_{i}}\\}_{i=0}^{s-1}$ is an orthonormal basis of
$\mathbb{R}^{s}$. It is easily shown that the moment matrix $\Gamma$ is
positive semidefinite. The elements of the set $\\{S_{i}\\}_{i=0}^{s-1}$ are
monomials of the operators $B_{b|y}$ and $E_{e|\mu}$. This set of operators
can be chosen arbitrarily but the aim is to have as many linearly independent
operators as possible in the moment matrix. By taking all monomials of
measurement operators up to a given order, we can define different levels of
the hierarchy. The first two levels are given, e.g., by the two following sets
of operators:

$\displaystyle\mathcal{S}_{1}$
$\displaystyle=\\{\mathbb{1},B_{b|y},E_{e|\mu}\\},$ (10)
$\displaystyle\mathcal{S}_{2}$
$\displaystyle=\mathcal{S}_{1}\cup\\{B_{b|y}B_{b^{\prime}|y^{\prime}},E_{e|\mu}E_{e^{\prime}|\mu^{\prime}},B_{b|y}E_{e|\mu}\\},$

and the levels $\mathcal{S}_{n}$ for $n>2$ can likewise be defined
inductively. Ref. [30] proved that as $n$ goes to infinity (i.e., in the
infinite level limit), the hierarchy converges to the set of quantum
correlations.

For the sake of clarity, we define
$\Gamma_{xx^{\prime}}^{ST}:=\bra{\psi_{x}}S^{\dagger}T\ket{\psi_{x^{\prime}}}$
with $S,T\in\mathcal{S}$ and $x,x^{\prime}=0,...,n-1$. The SDP upper bounding
$p(e=x,\text{succ})$ is given by

$\displaystyle\max_{\Gamma}\;\;$
$\displaystyle{\frac{1}{(n-1)n^{2}}\sum_{r=0}^{n\choose
2}\sum_{k=0}^{1}\sum_{y=0}^{n-1}\Gamma_{r_{k}r_{k}}^{B_{0|y}E_{r_{k}|r}}(\delta_{y,r_{0}}+\delta_{y,r_{1}})}$
(11a) s.t.
$\displaystyle\Gamma_{xx^{\prime}}^{\mathbb{1}\mathbb{1}}=\innerproduct{\psi_{x}}{\psi_{x^{\prime}}}=\gamma_{xx^{\prime}}\;\;\;\;\;\;\forall
x,x^{\prime}$ (11b)
$\displaystyle\Gamma_{xx}^{\mathbb{1}B_{b|y}}=p(b|x,y)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\forall
b,x,y$ (11c)
$\displaystyle\tr(\Gamma_{xx^{\prime}}F_{k})=f_{k}\;\;\;\;\;\;\;\;\;\;\;k=0,\dots,m,\forall
x,x^{\prime}$ (11d) $\displaystyle\Gamma\succeq 0.$ (11e)

The overlap constraint between the set of states is enforced by Eq. (11b). Eq.
(11c) enforces the moment matrix $\Gamma$ to be compatible with the observed
correlations $p(b|x,y)$. Eq. (11d) encodes the constraints on Bob’s and Eve’s
operators given by Eq. (7), as well as the constraints between elements of
$\Gamma_{xx^{\prime}}$ implied by the fact that
$\Gamma_{xx^{\prime}}^{ST}=\Gamma_{xx^{\prime}}^{S^{\prime}T^{\prime}}$
whenever $S^{\dagger}T={S^{\prime}}^{\dagger}T^{\prime}$ (cf. Prop. 4 of Ref.
[31]).

###  IV.2 Security analysis of the ideal qubit protocol

Here, we will analyze the security of the idealized qubit protocol presented
in Section III.2, including in the presence of loss and noise. We will model
noise by the means of a depolarizing channel with parameter $\lambda\in[0,1]$,
which replaces the transmitted state with a maximally mixed state with
probability $\lambda$ [32]. Loss is modeled by a binary erasure channel [32]
with erasure probability $(1-\eta)$, $\eta\in[0,1]$. Such a model of loss
assumes that loss is orthogonal with respect to the encoding, which is
typically the case if one considers, e.g., the polarization of photons for the
encoding of the secret bit.

The Gram matrix $G$ corresponding to the set of states (1) prepared by Alice
is given by

$G_{ij}=\cos^{2}(\theta/2)+e^{i\frac{2\pi(i-j)}{n}}\sin^{2}(\theta/2)$ (12)

with $i,j=1,...,n$. The probability distribution is then given by

$\begin{split}p(b=0|x,y)&=\eta\left(\frac{\lambda}{2}+(1-\lambda)\sin^{2}(\theta)\,\sin^{2}\left(\frac{\pi(x-y)}{n}\right)\right).\end{split}$
(13)

Given the Gram matrix $G$ of (12) and the observed probability distribution
one can upper bound the secret key rate as shown previously. Figure 2 shows
the raw key rate as a function of the transmission $\eta$ for different QBER’s
and values of $n$. For each $\eta$ we numerically optimized over $\theta$ to
obtain the optimal $R$. We notice that the lower-bound on the key rate goes
asymptotically to zero as $\eta\rightarrow 1/n$. This is optimal because at
$\eta=1/n$, Eve can break the security by intercepting the states sent by
Alice and forcing Bob’s detector according to her outcome and Bob’s input (see
Section IV.3). Therefore, for any prepare-and-measure protocol, the key rate
is null for $\eta\leq 1/n$.

Interestingly, B92 [33] is a special case of the proposed protocol with $n=2$
and a fixed $\theta=\frac{\pi}{4}$. Under the same assumptions, our protocol
outperforms B92 with respect to the transmission and the noise tolerance, see
Fig. 3. Also, BB84 [34] under the same assumptions is outrun by our protocol
with 3 states.

Figure 2: Raw key rate for our RDI-QKD protocol. The graph shows the lower
bound on the raw key rate $R$ as a function of the transmission for different
number of states and QBER’s. For $n$ states, the noiseless protocol has a
positive key rate down to $\eta=1/n$, which is the minimal transmission for
which this is possible in any prepare-and-measure scenario. The protocol is
also tolerant to noise in state preparation. Figure 3: Comparison of our RDI-
QKD protocol with other protocols under the same assumptions. The RDI protocol
with $n=2$ outperforms BB84 and B92.

###  IV.3 Analytical bounds

In this section we prove analytically that, if Alice prepares sufficiently
many states, the protocol can in principle tolerate arbitrary small
transmission $\eta$. First, with an explicit attack from Eve we lower bound
the transmission $\eta$ required to have $R>0$. (Proposition 1). Secondly, we
show that this bound is tight as long as $G$ is chosen to obey an additional
natural condition (Proposition 2). That is, for any transmission $\eta$
exceeding the threshold, Eve is unable to guess the secret bit with certainty
in all rounds, giving rise to a positive key rate.

Transmission loss in the line (scaling with distance) and finite detection
efficiency are the bottlenecks in most QKD protocols. Both effects give rise
to a loss channel and contribute to the total transmission $\eta$. In this
section we assume that this loss is the only imperfection in the setup. This
captures the main limiting factor of real QKD setups and allows us to derive
relatively simple analytical bounds. We assume that loss is orthogonal with
respect to the secret bit encoding, such that with probability $\eta$ the
system sent by Alice is lost and Bob observes a third outcome (e.g., a no-
click event $b=\emptyset$). Bob then attributes it the value $b=1$, such that
the rounds where the system sent by Alice is lost are rejected in the
protocol.

In this case any protocol with a Gram matrix
$G_{ij}=\innerproduct{\psi_{i}}{\psi_{j}}$ with $i,j=0,\dots,n-1$ and the
honest measurements ${B}_{1|y}=\outerproduct{\psi_{y}}{\psi_{y}}$ with
${B}_{0|y}=\mathbb{1}-B_{1|y}$ leads to measurement probabilities

$\begin{split}p(b=0|x,y)&=\eta(1-|G_{xy}|^{2}),\\\
p(b=1|x,y)&=1-p(b=0|x,y),\end{split}$ (14)

with $x,y=0,\dots,n-1$. One notes that with such probabilities $p(0|x=y)=0$:
Bob’s bits are perfectly correlated to Alice’s after the sifting, i.e.
$H_{2}(\textrm{QBER})=0$. For the following, we define
$\lambda_{\text{min}}(G)$ as the minimal non-zero eigenvalue of the Gram
matrix $G$.

######  Proposition 1.

Given a Gram matrix $G\in\mathbb{C}^{n\times n}$ and measurement probabilities
of Eq. (14), a necessary condition for $R>0$ is that
$\eta>\frac{1}{n-\lambda_{\mathrm{min}}(G)}$.

###### Proof.

Let us assume that with probability $q$ Eve intercepts the state sent by Alice
and makes an unambiguous state exclusion measurement
$M_{i}=\mu(\mathbb{1}-\outerproduct{\psi_{i}}{\psi_{i}})$ with
$i=0,\dots,n-1$, $\mu\in[0,1]$ and $M_{n}=\mathbb{1}-\sum_{i=0}^{n-1}M_{i}$.

If Eve obtains an outcome $i<n$, she can exclude with certainty the state
$\ket{\psi_{i}}$, whereas if she gets the outcome $n$ she cannot conclude
anything. In order to have as many conclusive outcomes as possible Eve
maximizes $\mu$ under the constraint $M_{n}\geq 0$:

$\displaystyle\max_{\mu}$ $\displaystyle\mu$ (15) s.t.
$\displaystyle\mathbb{1}\frac{(n\mu-1)}{\mu}\leq\sum_{i=0}^{n-1}\outerproduct{\psi_{i}}{\psi_{i}},$
$\displaystyle\mu\geq 0.$

The first constraint in Eq. (15) is satisfied if the eigenvalues of
$\sum_{i=0}^{n-1}\outerproduct{\psi_{i}}{\psi_{i}}$ are all larger than
$\frac{(n\mu-1)}{\mu}$. But the eigenvalues of
$\sum_{i}\outerproduct{\psi_{i}}{\psi_{i}}$ coincide with the nonzero
eigenvalues of the Gram matrix $G$. Hence, the above maximization is satisfied
if $\frac{(n\mu-1)}{\mu}\leq\lambda_{\text{min}}(G)$. This leads to an optimal
$\mu^{*}=\frac{1}{n-\lambda_{\text{min}}(G)}$ and
$p(i|x)=\mu^{*}(1-|G_{xi}|^{2})$. The result $i$ of Eve’s measurement is then
sent to Bob’s detector which only outputs $b=0$ if $y=i$, i.e.
$p(b=0|y,i)=\delta_{y,i}$. The resulting probability observed by Bob is

$\begin{split}p(b=0|x,y)&=\sum_{i=0}^{n}p(b=0|i,y)p(i|x)\\\
&=\mu^{*}(1-|G_{xy}|^{2}).\end{split}$ (16)

With probability $(1-q)$ Eve does not intercept the message, and Bob’s
detector is instructed to perform the ideal measurement
$p(b=0|x,y)=(1-|G_{xy}|^{2})$. Eve wants to remain undetected and hence needs
to reproduce the expected statistics of Eq. (14). Her attack must thus satisfy
the equality

$\eta(1-|G_{xy}|^{2})=q\mu^{*}\big{(}1-|G_{xy}|^{2})+(1-q)(1-|G_{xy}|^{2})\big{)}$
(17)

for all $x,y$. This implies that Eve can not intercept the message more often
than in a fraction $q=\frac{1-\eta}{1-\mu^{*}}$ of rounds. In particular, if
$q=\frac{1-\eta}{1-\mu^{*}}\geq 1$ or
$\eta\leq\frac{1}{n-\lambda_{\text{min}}(G)}$ she can intercept the message in
every round resulting in $p(y=i|\text{succ})=p_{g}(e=k|\text{succ})=1$ and
$R=0$. ∎

More generally, this attack gives a lower bound on Eve’s guessing probability
as

$\begin{split}p_{g}(e=k|\text{succ})&\geq q+(1-q)\frac{1}{2}\\\
&=\frac{1}{2}\left(1+\frac{1-\eta}{\eta(n-(1+\lambda_{\text{min}}(G))}\right),\end{split}$
(18)

with equality if $p_{g}(e=k|\text{succ})=\frac{1}{2}$ for the honest
implementation at $\eta=1$.

For the considered family of protocols the proposed attack allows Eve to guess
the secret bit $k$ of Alice perfectly whenever one has
$\eta\leq\frac{1}{n-\lambda_{\text{min}}(G)}$. The converse question is
whether, for any transmission exceeding this value, there exists a protocol
(with a given $n$ and $\lambda_{\text{min}}(G)$) yielding a strictly positive
key rate. We will now show that this is indeed the case by considering a qubit
protocol with rank$(G)=2$, as discussed in Sec. III.2.

######  Proposition 2.

Consider a Gram matrix $G$, with $\rank(G)=2$, leading to measurement
probabilities in Eq. (14). If the transmission exceeds
$\eta>\frac{1}{n-\lambda_{\mathrm{min}}(G)}$, then one can obtain a positive
key rate, i.e., $R>0$.

###### Proof.

Since in our case $H_{2}(\textrm{QBER})=0$, from Eq. (5) one sees that the
condition $R>0$ is equivalent to $p_{g}(e=k|\text{succ})<1$, that is Eve can
not always guess the secret bit with certainty. Thus, we want to prove
$p_{g}(e=k|\text{succ})<1$. To do so we will proceed by assuming
$p_{g}(e=k|\text{succ})=1$ and reach a contradiction.

To start, it is convenient to replace our prepare-and-measure scenario by an
equivalent entanglement-based scenario. Alice prepares an entangled state

$\ket{\Phi}_{AA^{\prime}}=\frac{1}{\sqrt{n}}\sum_{x=1}^{n}\ket{x}_{A}\ket{\psi_{x}}_{A^{\prime}},$
(19)

sends out $A^{\prime}$ and measures $A$ in the computational basis
$\\{\outerproduct{x}{x}\\}_{k=0}^{n-1}$ to obtain $x$. Since the states
$\\{\ket{\psi_{x}}\\}_{x}$ span a 2-dimensional space, by the Schmidt theorem
the state $\ket{\Phi}_{AA^{\prime}}\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ is
a two qubit state.

Without loss of generality an attack performed by Eve starts with an isometry
$U$ mapping $A^{\prime}$ onto systems $B$ and $E$ of arbitrary dimension

$U:\ket{\Phi}_{AA^{\prime}}\mapsto\ket{\Psi}_{ABE}=\mathbb{1}_{A}\otimes
U_{A^{\prime}}\ket{\Phi}_{AA^{\prime}}.$ (20)

In addition Eve chooses a set of binary measurements $\\{B_{0|y},B_{1|y}\\}$
acting on $B$. The combinations of the isometry and the measurements on $B$
define the measurements on the system $A^{\prime}$ via

$M_{b|y}=U_{A^{\prime}}^{\dagger}\left(B_{b|y}\otimes\mathbb{1}_{E}\right)U_{A^{\prime}}.$
(21)

Furthermore these measurements are constrained to satisfy
$\bra{\psi_{x}}M_{b|y}\ket{\psi_{x}}=p(b|x,y)$ by the probabilities observed
by Alice and Bob in Eq. (14). From $\bra{\psi_{y}}M_{0|y}\ket{\psi_{y}}=0$,
one concludes that
$M_{0|y}\propto\mathbb{1}-\outerproduct{\psi_{x}}{\psi_{x}}$. Any of the
remaining probabilities $\bra{\psi_{x\neq y}}M_{0|y}\ket{\psi_{x\neq y}}$
implies

$M_{0|y}=\eta(\mathbb{1}-\outerproduct{\psi_{x}}{\psi_{x}})=\eta\outerproduct{\psi_{y}^{\perp}}{\psi_{y}^{\perp}}.$
(22)

This form of $M_{0|y}$ is very restrictive for Eve. In particular, it projects
$\ket{\Phi}_{AA^{\prime}}$ into a product state

$\mathbb{1}_{A}\otimes\sqrt{M_{0|y}}\ket{\Phi}_{AA^{\prime}}=\sqrt{p(b=0|y)}\ket{\xi^{(0|y)}}_{A}\ket{\phi^{(0|y)}}_{A^{\prime}},$
(23)

with $p(b=0|y)=\frac{1}{n}\sum_{x}p(b=0|x,y)$. This identity can be put in the
form

$\sqrt{B_{0|y}}\otimes\mathbb{1}_{AE}\ket{\Psi}_{ABE}=\sqrt{p(b=0|y)}\ket{\xi^{(0|y)}}_{A}\ket{\Psi^{(0|y)}}_{BE}.$
(24)

From here we can define the marginal state of Alice and Eve conditional to Bob
measuring $y$ and obtaining $0$

$\begin{split}\rho_{AE|B}^{(0|y)}&=\outerproduct{\xi^{(0|y)}}{\xi^{(0|y)}}_{A}\otimes\rho_{E}^{(0|y)}\\\
\textrm{with}\quad&\rho_{E}^{(0|y)}=\tr_{B}\outerproduct{\Psi^{(0|y)}}{\Psi^{(0|y)}}_{BE}.\end{split}$
(25)

Remarkably, Eve’s state is no longer influenced by any manipulations done by
Alice, and in particular by her measurement result $x$. That is, conditionally
on $y$ Eve’s state is independent of $x$. This means that after the sifting
Eve can only guess $x$ perfectly ($p_{g}(e=k|\text{succ})=1$), if she can
guess $y$ perfectly. Formally,

$p_{g}(e=k|\text{succ})=1\implies\frac{1}{2}\big{\lVert}\rho_{E}^{(0|y)}-\rho_{E}^{(0|y^{\prime})}\big{\rVert}=0\quad\forall\,y\neq
y^{\prime}.$ (26)

Let us now show that this imposes some conditions on the probabilities
$p(b=0|y)$. To do so consider the trivial inequality

$\rho_{E}=p(b=0|y)\rho_{E}^{(0|y)}+(1-p(b=0|y))\rho_{E}^{(1|y)},$ (27)

where $\rho_{E}=\tr_{AB}\outerproduct{\Psi}{\Psi}_{ABE}$ and
$(1-p(b=0|y))\rho_{E}^{(1|y)}=\tr_{AB}\big{[}(B_{1|y}\otimes\mathbb{1}_{AE})\outerproduct{\Psi}{\Psi}_{ABE}\big{]}$,
which implies

$\rho_{E}-p(b=0|y=0)\rho_{E}^{(0|0)}\geq 0.$ (28)

But because the state $\rho_{E}^{(0|0)}$ and $\rho_{E}^{(0|1)}$ have
orthogonal support, we also obtain

$\rho_{E}-p(b=0|y=0)\rho_{E}^{(0|0)}-p(b=0|y=1)\rho_{E}^{(0|1)}\geq 0.$ (29)

By recursion we obtain the bound

$\begin{split}\rho_{E}-\sum_{y}p(b=0|y)\rho_{E}^{(0|y)}&\geq 0\\\
1-\sum_{y}p(b=0|y)&\geq 0\\\ \sum_{y}p(b=0|y)&\leq 1\end{split}$ (30)

on the average probability of the $b=0$ outcome. With the help of Eq. (14)
this bound can be written as

$\eta\leq\frac{1}{\frac{1}{n}\sum_{x,y}(1-|G_{xy}|^{2})}.$ (31)

This bound is, however, worse that the one in the statement of the theorem.
Let us now show how to match the two. For this we consider a thought
experiment where Alice prepares some pure state

$\ket*{\widetilde{\Phi}}_{AA^{\prime}}\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}.$
(32)

As $M_{0|y}=\eta\outerproduct{\psi_{y}^{\perp}}{\psi_{y}^{\perp}}$ is
proportional to projector on a state, one has, analogously to Eqs. (23)–(24),

$\left(\sqrt{B_{0|y}}\otimes\mathbb{1}_{AE}\right)U_{A^{\prime}}\ket{\widetilde{\Phi}}_{AA^{\prime}}\\!\\!=\sqrt{\widetilde{p}(0|y)}\ket{\widetilde{\xi}^{(0|y)}}_{A}\ket{\Psi^{(0|y)}}_{BE},$
(33)

with the same state $\ket{\Psi^{(0|y)}}_{BE}$. Hence the marginal state
$\rho_{E}^{(0|y)}$ are also the same, and satisfy

$\widetilde{\rho}_{E}=\widetilde{p}(b|y)\rho_{E}^{(0|y)}+(1-\widetilde{p}(0|y))\rho_{E}^{(1|y)}$
(34)

for
$\widetilde{\rho}_{E}=\tr_{AB}[U_{A^{\prime}}\outerproduct*{\widetilde{\Phi}}{\widetilde{\Phi}}_{AA^{\prime}}U_{A^{\prime}}^{\dagger}]$.
We can now repeat the arguments of Eqs. (29)–(30) to obtain the bound

$\sum_{y}\widetilde{p}(0|y)\leq 1,$ (35)

valid for the sum of probabilities

$\begin{split}\sum_{y}\widetilde{p}(0|y)&=\tr_{AA^{\prime}}\Big{[}\big{(}\mathbb{1}_{A}\otimes\sum_{y}M_{0|y}\big{)}\outerproduct*{\widetilde{\Phi}}{\widetilde{\Phi}}_{AA^{\prime}}\Big{]}\\\
&=\tr_{A^{\prime}}\Big{[}\big{(}\sum_{y}M_{0|y}\big{)}\,\rho_{A^{\prime}}\Big{]}\end{split}$
(36)

coming from any state $\rho_{A^{\prime}}$. Choosing the state which maximizes
the bound
$\max_{\rho_{A^{\prime}}}\tr[\rho_{A^{\prime}}(\sum_{y}M_{0|y})]=\lVert\sum_{y}M_{0|y}\rVert$,
one obtains

$\begin{split}\Big{\lVert}\sum_{y}M_{0|y}\Big{\rVert}&\leq 1\\\
\eta\Big{\lVert}\sum_{y}(\mathbb{1}-\outerproduct{\psi_{y}}{\psi_{y}})\Big{\rVert}&\leq
1\\\ \eta\big{(}n-\lambda_{\textrm{min}}(G)\big{)}&\leq 1\\\
\eta\leq\frac{1}{n-\lambda_{\textrm{min}}(G)},\end{split}$ (37)

where we used the fact that $G$ and
$\sum_{y}\outerproduct{\psi_{y}}{\psi_{y}}$ have the same eigenvalues. Hence,
having $p_{g}(e=k|\text{succ})=1$ and
$\eta>\frac{1}{n-\lambda_{\textrm{min}}(G)}$ is impossible, which concludes
the proof. ∎

Propositions 1 and 2 imply that, for any transmission $\eta$, there exists a
RDI-QKD protocol involving $n>\frac{1}{\eta}$ different measurements performed
by Bob which yields a positive key rate. In particular, as follows from the
proof of Propostion 2, this is achieved by the ideal qubit protocol of Sec.
III.2 by choosing $\lambda_{\min}(G)<n-\frac{1}{\eta}$. Conversely, in the RDI
setting where Bob can do $n$ different measurements labeled by the settings
$y$, Eve can always perform a “blinding” attack and obtain a perfect copy of
Bob’s registers. To do so she performs one of the possible measurements
$y^{\prime}$ at random, records the outcome $e$, and sends a copy of $e$ and
$y^{\prime}$ to Bob’s detector. When Bob performs his measurement with a
setting $y$, the detector reveals $b=e$ if $y=y^{\prime}$ and pretends that
the system was lost $b=\emptyset$ otherwise. Since $p(y^{\prime}=y|y)=1/n$,
for $\eta<\frac{1}{n}$ Eve is left with a perfect copy of Bob’s registers
$(b,y)$ whenever the detection is successful $b\neq\emptyset$.

###  IV.4 Importance of the choice of the Gram matrix

As we saw in the previous section, if one chooses the $n$ states
$\\{\ket{\psi_{x}}\\}_{x}$ well then one can obtain $R>0$, and thus a positive
key rate, whenever $\eta>1/n$. In this section, we show that it is indeed
important to choose the Gram matrix constraining the preparations with some
care. In particular, we show that for a seemingly natural choice of Gram
matrix the critical transmission, below which no key can be obtained, is
significantly worse: Alice and Bob will not be able to provide a nontrivial
lower bound on the key rate if there is more than $50\%$ loss, i.e. if
$\eta>1/2$.

We assume thus that Alice prepares a set of $n$ quantum states compatible with
the Gram matrix $G_{xx^{\prime}}=\innerproduct{\psi_{x}}{\psi_{x^{\prime}}}=d$
with $d\in(0,1)$ for all $x\neq x^{\prime}$ and that the observed statistics
are given by Eq. (14). Since $\rank(G)=n$, the states she prepares are
necessarily linearly independent. As a result, there exists an unambiguous
state discrimination (USD) measurement [35]. Because of the symmetry, we
consider an equiprobable USD and the probability of a conclusive
discrimination is given by the smallest eigenvalue of the Gram matrix which is
in our case equal to $1-d$ [36].

We assume that Eve performs an intercept-resend attack such that with a
probability $0\leq q\leq 1$ she performs USD and forces Bob’s detection, and
with a probability $1-q$ she leaves the state untouched and guesses at random.
Given that $x\neq y$, if Eve attacks the USD is conclusive with a probability
$1-d$ and if she does not intercept the state Bob gets $b=0$ with a
probability $\eta(1-d^{2})$. Eve wants her attack to remain unnoticed and this
fixes the probability $q$ of intercepting the state to
$q=\frac{(1+d)(1-\eta)}{d}$.

The probability that Eve successfully guesses the secret bit is then given by

$\displaystyle p_{g}(e=x|\text{succ})=\frac{1-\eta(1-d)}{2d\eta}.$ (38)

Eve thus has entire knowledge of the secret bit string, i.e.,
$p_{g}(e=k|\text{succ})=1$, for $\eta=\frac{1}{1+d}>\frac{1}{2}$. Hence,
considering identical real overlaps prevents Alice and Bob from obtaining a
positive key rate for more than $50\%$ loss.

##  V Bridging the gap between the protocols and practical implementations

Our receiver-device independent setting assumes the characterization of
Alice’s state preparation device, given by the Gram matrix

$\textrm{Alice}\simeq G.$ (39)

When Alice prepares pure states, as we have assumed so far, the Gram matrix
gives an exhaustive description of the state preparation for our purpose. That
is, in the considered RDI setting, additional information on the states does
not help restricting Eve further. In particular, any common unitary
transformation or isometry on the states can be cancelled by Eve and does not
affect the attacks she can perform.

In practice the pure state assumption is always an idealization. Here, we
discuss how a more realistic model of Alice’s setup can be analysed with our
protocols.

###  V.1 Mixed state models

Here we consider the setting where Alice’s preparation device sends out a
mixed state $\rho_{x}$ for each possible value of $x$. That is the preparation
box is modeled by a set of mixed states

$\textrm{Alice}\simeq\\{\rho_{x}\\}_{x=0}^{n-1}.$ (40)

An ensemble of mixed states of a system $A^{\prime}$ can be jointly purified
onto a larger system $A^{\prime}\otimes A_{\text{aux}}$ to obtain a set of
pure states $\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ with
$\ket{\psi_{x}}\in\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{A_{\text{aux}}}$
and

$\qquad\rho_{x}=\tr_{A_{\text{aux}}}\outerproduct{\psi_{x}}{\psi_{x}}\
\forall\,x.$ (41)

Because the system $A_{\text{aux}}$ remains inside Alice’s lab by assumption,
any security guarantee obtained for a Gram matrix $G_{\\{\ket{\psi_{x}}\\}}$
induced by the set of pure states $\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ is valid
for the original mixed states. In this case one is interested in finding the
best-case purification maximizing the key rate. This gives a straightforward
way to apply our protocols to noisy preparation devices modeled by Eq. (40).
The resulting bounds are not necessarily tight, because in the analysis the
purifying system $A_{\text{aux}}$ is given to the eavesdropper, but are
secure.

An interesting open question is whether there exists a compressed
representation of the mixed state ensemble $\\{\rho_{x}\\}_{x=0}^{n-1}$,
analogous to the Gram matrix, that specifies all the relations between the
states useful for our purpose. Notably, in the case of two states the fidelity
between them $F(\rho_{0},\rho_{1})$ precisely corresponds to the maximal
fidelity between their purifications (see e.g. [37]). However, for larger
ensembles the knowledge of pairwise fidelities is known to be insufficient to
characterize the joint purification [38]. As a simple example note that even
in the case of three pure states the pairwise fidelities disregard the complex
phases of the Gram matrix entries, which can be crucial for the security
analysis as we have seen in Section IV.4.

###  V.2 Fully characterized correlated noise models

Next, let us consider the general situation where Alice’s preparation device
is well described by pure states that are however subject to noise, e.g.,
coming from drifts and fluctuations of some parameters (laser amplitude, phase
noise etc). In such a case the preparation box is modelled by a parametric set
of states

$\textrm{Alice}\simeq\\{\ket{\phi_{x}(\lambda)}\\}_{x=0}^{n-1},$ (42)

where $p(\lambda)$ is the distribution of the noise parameter $\lambda$. In
contrast to Eq. (40), this model allows for correlated noise affecting the
preparation device for all measurement settings. Notably, the model in Eq.
(42) reduces to Eq. (40) when the hidden variable
$\lambda=(\lambda_{0},\dots,\lambda_{n-1})$ is composed of random variables
$\lambda_{x}$ that only influence the preparation for the respective setting
$x$ and are distributed independently.

Each set of pure states labeled by $\lambda$ corresponds to a Gram matrix
$G(\lambda)$. Here, it is important to realize that the correlations
$p(b|x,y)$ observed by Alice and Bob do not constrain each $\lambda$ (unless
the distribution $p(b|x,y)$ is extremal) but are only respected on average,
i.e.

$p(b|x,y)=\int\differential\lambda\,p(\lambda)\,p(b|x,y,\lambda)$ (43)

for some hidden $p(b|x,y,\lambda)$. Hence, one cannot simply verify the
security of the protocol for each $G(\lambda)$.

Instead, we recover a pure state situation by explicitly including the hidden
noise parameter $\lambda$ in the state. That is, we consider Alice preparing
states of the form

$\ket{\psi_{x}}=\int\differential\lambda\sqrt{p(\lambda)}\ket{\phi_{x}(\lambda)}\ket{\lambda},$
(44)

with the “label” states for the hidden noise parameter respecting
$\innerproduct{\lambda}{\mu}=\delta(\lambda-\mu)$. By doing so we give the
noise label $\lambda$ to Eve who can control it coherently but is bound to
respect our noisy model of the device given by $p(\lambda)$. It is
straightforward to see that the resulting Gram matrix for the states
$\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ is simply the average

$\overline{G}=\int\differential\lambda\,p(\lambda)\,G(\lambda).$ (45)

Consequently, verifying the security of the protocol for $\overline{G}$
guarantees its security for the original model.

###  V.3 Partially characterized correlated noise models

In some situations the full model with the knowledge of the distribution
$p(\lambda)$ might not be appropriate, as it requires a complete, precise
characterization of the noise mechanisms present. Instead one can only
guarantee (with the desired level of confidence) that in each round the
preparation device obeys to the model

$\textrm{Alice}\simeq\\{\ket{\phi_{x}(\lambda)}\\}_{x=0}^{n-1}\quad\textrm{with}\quad\lambda\in\Lambda,$
(46)

where $\Lambda$ specifies the range of possible $\lambda$. From there we can
recover the previous case by noting that any realization of such model
corresponds to the states $\\{\ket{\psi_{x}}\\}_{x=0}^{n-1}$ in Eq. (44) for
some probability density $p(\lambda)$ on $\Lambda$. The resulting average Gram
matrix then necessarily belongs to the set

$\begin{split}\overline{G}\,&\in\,\widehat{G}_{\Lambda}\\\
G_{\Lambda}&=\\{G(\lambda)|\lambda\in\Lambda\\},\end{split}$ (47)

where the hat $\widehat{G}_{\Lambda}$ denotes the convex hull of the set
$G_{\Lambda}$. In principle, it remains to determine the worst case
$\overline{G}$ inside the set, with respect to the key rate it implies, in
order to guarantee the security for the noise model.

Practically, this problem is however computationally hard. And instead of
solving it directly it is convenient to further relax the constraints on
$\overline{G}$ to a form that one can easily include in the security analysis
described in Section IV. This can be done by constraining each entry of the
Gram matrix $\overline{G}_{ij}$ independently. Concretely, the set
$G_{\Lambda}$ can be relaxed to a collection of constraints

$\begin{split}r_{ij}\leq&\,\textrm{Re}[G_{ij}]\,\leq R_{ij}\\\
i_{ij}\leq&\,\textrm{Im}[G_{ij}]\,\leq I_{ij},\end{split}$ (48)

on the real and imaginary parts of each entry of the matrices $G\in
G_{\Lambda}$. Being linear these constraints remain valid for the convex hull
set $\widehat{G}_{\Lambda}$. Most importantly, they are very simple to include
in the SDP. The equality constraint $\Gamma^{11}_{ij}=G_{ij}$ in Eq. (11b)
translates in two inequalities on the real and imaginary part of $\Gamma$ for
$i\neq j$

$\begin{split}r_{ij}\leq&\,\textrm{Re}[\Gamma^{\mathbb{1}\mathbb{1}}_{ij}]\,\leq
R_{ij}\\\ i_{ij}\leq&\,\textrm{Im}[\Gamma^{\mathbb{1}\mathbb{1}}_{ij}]\,\leq
I_{ij}.\end{split}$ (49)

Through the SDP the Gram matrix is constraint to be positive semidefinite.
Hence, the set of states described by the Gram matrix which maximizes
$p_{g}(e=k|\text{succ})$ remains physical.

##  VI Comparison to other QKD models

In this section we present a brief comparison of our RDI approach with other
models for partially DI QKD.

A first semi-DI (SDI) approach bearing some resemblances to our RDI approach
was proposed in Ref. [39]. There, Alice’s device is taken to be fully
characterized, while Bob’s device is, at least in principle, black-box and
requires no characterisation. While this holds true in the ideal (lossless)
case, it is unclear how their protocol would perform when losses and noise are
taken into account. Indeed, the analysis of Ref. [39] in the presence of
losses and noise relies on a fair-sampling type assumption, and hence the
protocol can no longer be considered fully black-box on Bob’s side. In
particular, blinding attacks already mean that, as for our RDI protocol, no
secret key can be obtained for a transmission $\eta\leq 1/n$.

Another SDI approach presented in Ref. [17, 18] shares more similarities with
our approach. The authors consider prepare-and-measure scenario where Alice’s
device is assumed to prepare quantum states of bounded Hilbert space dimension
(for instance qubits), while Bob’s device is completely black-box. This
represents a very different type of assumption on the preparations, which is
however arguably difficult to justify in practice; indeed a photon is not a
qubit, and has many other degrees of freedom than (say) polarisation 111More
generally, practical systems are usually described as infinite dimensional
systems, for instance when considering optical implementations based on
coherent states.. In this sense, we believe that our RDI approach is more
naturally tailored to experiments, as it can deal with systems of arbitrary
(possibly infinite) dimension. Another important advantage in practice, is the
robustness to losses. Indeed, dimension-based SDI protocols are also sensitive
to detection-loophole-type attacks and thus require detection efficiencies
comparable to Bell tests [41]. This renders their practical implementation
challenging. To the best of our knowledge, no experiment has been reported so
far. Another related approach was developed in Ref. [19], considering an
entanglement-based QDK setup assuming only the dimension of the entangled
state prepared by the source. Again, practical implementation is challenging
due to high detection efficiency requirements.

Insofar as our model considers a black-box on Bob’s side it is similar also to
the model of one-sided DI QKD [20]. The latter is based on quantum steering,
and therefore relies on entanglement. Moreover, a full characterisation of
Alice’s device is required. In practice one-sided QKD has never been
implemented, most likely due to the requirement of a high detection efficiency
($\eta>65.9\%$ [20]). We believe our RDI protocols provide a number of
advantages over the one-sided DI approach. The experimental realisation is
greatly simplified, as no source of entanglement is necessary, and much lower
detection efficiencies can be tolerated. Moreover, in our case, the
characterized party (Alice) acts as a sender, while in the one-sided model
Alice holds a measurement device. Having to trust a preparation device instead
of a measurement device is arguably an advantage.

Finally, we compare our RDI model to the MDI approach [21, 22]. Both
approaches aim at relaxing trust on the measurement device. While we do this
in the prepare-and-measure scenario, the MDI model considers an additional
party (Charlie), located in between Alice and Bob and who acts as a relay.
Charlie’s (measurement) device is then fully untrusted, while Alice’s and
Bob’s (preparation) devices must be well characterized. In practice, a strong
advantage of the MDI approach is its robustness to losses, leading to record-
distance experiments [23, 24, 25, 26]. In a scenario where both end parties,
Alice and Bob, have means to characterize and test their devices (or good
reasons to believe the devices function correctly), the MDI approach is a good
choice. However, in a scenario where one of the parties does not have the
resources (or the expertise) for testing and characterizing their device (or
reasons not to trust their devices, for instance a possible malfunctioning due
to ageing), the RDI approach provides a good solution. In contrast, the MDI
approach cannot be used here, as Bob’s (nor Alice’s) device can be described
by a black-box; some level of trust on both Alice and Bob will always be
required in the MDI case.

##  VII Conclusion

We have discussed a receiver-device-independent (RDI) approach to QKD. We
presented protocols for this model and discussed their security analysis. We
also provided a more detailed discussion concerning the relevance of our
approach in a practical context, in particular discussing how the overlap
assumption can be justified. These results complement a recent (companion)
paper, where a proof-of-principle RDI QKD experiment has been reported [27].

To conclude, we discuss a number of open questions. A first interesting
question is to derive stronger bounds on the secret key rate. This may be
possible using techniques recently developed in Ref. [42] providing lower
bounds on the conditional von Neumann entropy (instead of the conditional min-
entropy, as we consider here) from observed data. Elements from the approach
used in Ref. [43] might also be useful here.

Another question is to turn our asymptotic key rate into a finite key length
when a finite number of systems are exchanges between Alice and Bob. A natural
route towards this goal consists in using the entropy accumulation theorem
[44], although it is still unclear whether this approach can be adapted to the
prepare-and-measure scenario.

An important direction to pursue is to look for RDI protocols that can achieve
long distance and are practical. Here we presented protocols that can tolerate
the minimum possible transmission (depending on the number of measurements $n$
made by Bob) in the RDI model. In practice, the drawback of our protocols is
the sifting, which, for large $n$, renders the protocols inefficient.
Developing more efficient protocols would represent significant progress.

Finally, we note our approach shares similarities with the recent work of Ref.
[45], where the author investigates correlations in a prepare-and-measure
scenario with bounded distrust in the preparations. Specifically, the fidelity
of the prepared states with respect to some reference state is lower bounded.
Hence the distance between the actual and ideal states is bounded. In our
approach we bound the distance between the prepared states via their pairwise
overlaps.

_Acknowledgements.—_ We thank Jonathan Brask, Davide Rusca and Hugo Zbinden
for discussions. We acknowledge financial support from the EU Quantum Flagship
project QRANGE, and the Swiss National Science Foundation (BRIDGE, project
2000021_192244/1 and NCCR QSIT).

## References

  * Bennett and Brassard [1984] C. H. Bennett and G. Brassard, Quantum cryptography: public key distribution and coin tossing, in  _Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing_ (IEEE, 1984) pp. 175–179.
  * Ekert [1991] A. K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661 (1991).
  * Vernam [1926] G. S. Vernam, Cipher printing telegraph systems: For secret wire and radio telegraphic communications, J. AIEE 45, 109 (1926).
  * Scarani  _et al._ [2009] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, The security of practical quantum key distribution, Rev. Mod. Phys. 81, 1301 (2009).
  * Lo  _et al._ [2014] H.-K. Lo, M. Curty, and K. Tamaki, Secure quantum key distribution, Nature Photonics 8, 595 (2014).
  * Diamanti  _et al._ [2016] E. Diamanti, H.-K. Lo, B. Qi, and Z. Yuan, Practical challenges in quantum key distribution, npj Quantum Inf. 2, 1 (2016).
  * Xu  _et al._ [2020] F. Xu, X. Ma, Q. Zhang, H.-K. Lo, and J.-W. Pan, Secure quantum key distribution with realistic devices, Rev. Mod. Phys. 92, 025002 (2020).
  * Lydersen  _et al._ [2010] L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar, and V. Makarov, Hacking commercial quantum cryptography systems by tailored bright illumination, Nature Photonics 4, 686 (2010).
  * Gerhardt  _et al._ [2011] I. Gerhardt, Q. Liu, A. Lamas-Linares, J. Skaar, C. Kurtsiefer, and V. Makarov, Full-field implementation of a perfect eavesdropper on a quantum cryptography system, Nature Commun. 2, 349 (2011).
  * Acín  _et al._ [2007] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-independent security of quantum cryptography against collective attacks, Phys. Rev. Lett. 98, 230501 (2007).
  * Pironio  _et al._ [2009] S. Pironio, A. Acín, N. Brunner, N. Gisin, S. Massar, and V. Scarani, Device-independent quantum key distribution secure against collective attacks, New J. Phys. 11, 045021 (2009).
  * Vazirani and Vidick [2014] U. Vazirani and T. Vidick, Fully device-independent quantum key distribution, Phys. Rev. Lett. 113, 140501 (2014).
  * Arnon-Friedman  _et al._ [2018] R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, Practical device-independent quantum cryptography via entropy accumulation, Nature Commun. 9, 459 (2018).
  * Liu  _et al._ [2021] W.-Z. Liu, Y.-Z. Zhang, Y.-Z. Zhen, M.-H. Li, Y. Liu, J. Fan, F. Xu, Q. Zhang, and J.-W. Pan, High-speed device-independent quantum key distribution against collective attacks (2021), arXiv:2110.01480 [quant-ph] .
  * Nadlinger  _et al._ [2021] D. P. Nadlinger, P. Drmota, B. C. Nichol, G. Araneda, D. Main, R. Srinivas, D. M. Lucas, C. J. Ballance, K. Ivanov, E. Y.-Z. Tan, P. Sekatski, R. L. Urbanke, R. Renner, N. Sangouard, and J.-D. Bancal, Device-independent quantum key distribution (2021), arXiv:2109.14600 [quant-ph] .
  * Zhang  _et al._ [2021] W. Zhang, T. van Leent, K. Redeker, R. Garthoff, R. Schwonnek, F. Fertig, S. Eppelt, V. Scarani, C. C. W. Lim, and H. Weinfurter, Experimental device-independent quantum key distribution between distant users (2021), arXiv:2110.00575 [quant-ph] .
  * Pawłowski and Brunner [2011] M. Pawłowski and N. Brunner, Semi-device-independent security of one-way quantum key distribution, Phys. Rev. A 84, 010302 (2011).
  * Woodhead and Pironio [2015] E. Woodhead and S. Pironio, Secrecy in prepare-and-measure Clauser-Horne-Shimony-Holt tests with a qubit bound, Phys. Rev. Lett. 115, 150501 (2015).
  * Goh  _et al._ [2016] K. T. Goh, J.-D. Bancal, and V. Scarani, Measurement-device-independent quantification of entanglement for given Hilbert space dimension, New J. Phys. 18, 045022 (2016).
  * Branciard  _et al._ [2012] C. Branciard, E. G. Cavalcanti, S. P. Walborn, V. Scarani, and H. M. Wiseman, One-sided device-independent quantum key distribution: Security, feasibility, and the connection with steering, Phys. Rev. A 85, 010301 (2012).
  * Lo  _et al._ [2012] H.-K. Lo, M. Curty, and B. Qi, Measurement-device-independent quantum key distribution, Phys. Rev. Lett. 108, 130503 (2012).
  * Braunstein and Pirandola [2012] S. L. Braunstein and S. Pirandola, Side-channel-free quantum key distribution, Phys. Rev. Lett. 108, 130502 (2012).
  * Yin  _et al._ [2016] H.-L. Yin, T.-Y. Chen, Z.-W. Yu, H. Liu, L.-X. You, Y.-H. Zhou, S.-J. Chen, Y. Mao, M.-Q. Huang, W.-J. Zhang, H. Chen, M. J. Li, D. Nolan, F. Zhou, X. Jiang, Z. Wang, Q. Zhang, X.-B. Wang, and J.-W. Pan, Measurement-device-independent quantum key distribution over a 404 km optical fiber, Phys. Rev. Lett. 117, 190501 (2016).
  * Pittaluga  _et al._ [2021] M. Pittaluga, M. Minder, M. Lucamarini, M. Sanzaro, R. I. Woodward, M.-J. Li, Z. Yuan, and A. J. Shields, 600-km repeater-like quantum communications with dual-band stabilization, Nature Photonics 15, 530 (2021).
  * Chen  _et al._ [2021a] J.-P. Chen, C. Zhang, Y. Liu, C. Jiang, W.-J. Zhang, Z.-Y. Han, S.-Z. Ma, X.-L. Hu, Y.-H. Li, H. Liu, _et al._ , Twin-field quantum key distribution over a 511 km optical fibre linking two distant metropolitan areas, Nature Photonics 15, 570 (2021a).
  * Chen  _et al._ [2021b] J.-P. Chen, C. Zhang, Y. Liu, C. Jiang, D.-F. Zhao, W.-J. Zhang, F.-X. Chen, H. Li, L.-X. You, Z. Wang, Y. Chen, X.-B. Wang, Q. Zhang, and J.-W. Pan, Quantum key distribution over 658 km fiber with distributed vibration sensing (2021b), arXiv:2110.11671 [quant-ph] .
  * Ioannou  _et al._ [2021] M. Ioannou, M. A. Pereira, D. Rusca, F. Grünenfelder, A. Boaron, M. Perrenoud, A. A. Abbott, P. Sekatski, J.-D. Bancal, N. Maring, H. Zbinden, and N. Brunner, Receiver-device-independent quantum key distribution (2021), arXiv:2104.14574 [quant-ph] .
  * Devetak and Winter [2005] I. Devetak and A. Winter, Distillation of secret key and entanglement from quantum states, Proc. Roy. Soc. A461, 207 (2005).
  * Konig  _et al._ [2009] R. Konig, R. Renner, and C. Schaffner, The operational meaning of min-and max-entropy, IEEE Trans. Inf. Th. 55, 4337 (2009).
  * Wang  _et al._ [2019] Y. Wang, I. W. Primaatmaja, E. Lavie, A. Varvitsiotis, and C. C. W. Lim, Characterising the correlations of prepare-and-measure quantum networks, npj Quantum Inf. 5, 1 (2019).
  * Navascués  _et al._ [2008] M. Navascués, S. Pironio, and A. Acín, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New J. Phys. 10, 073013 (2008).
  * Nielsen and Chuang [2011] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ , 10th ed. (Cambridge University Press, USA, 2011).
  * Bennett [1992] C. H. Bennett, Quantum cryptography using any two nonorthogonal states, Phys. Rev. Lett. 68, 3121 (1992).
  * Bennett and Brassard [2014] C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Theor. Comput. Science 560, 7 (2014).
  * Chefles [1998] A. Chefles, Unambiguous discrimination between linearly independent quantum states, Phys. Lett. A 239, 339 (1998).
  * Horoshko  _et al._ [2019] D. W. Horoshko, M. M. Eskandari, and S. Y. Kilin, Equiprobable unambiguous discrimination of quantum states by symmetric orthogonalisation, Phys. Lett. A 383, 1728 (2019).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002).
  * Fannes  _et al._ [2011] M. Fannes, F. De Melo, W. Roga, and K. Zyczkowski, Matrices of fidelities for ensembles of quantum states and the Holevo quantity, Quantum Inf. Comput. 12, 472 (2011), arXiv:1104.2271 [quant-ph] .
  * Tomamichel  _et al._ [2012] M. Tomamichel, C. C. W. Lim, N. Gisin, and R. Renner, Tight finite-key analysis for quantum cryptography, Nature Commun. 3, 1 (2012).
  * Note [1] More generally, practical systems are usually described as infinite dimensional systems, for instance when considering optical implementations based on coherent states.
  * Dall’Arno  _et al._ [2015] M. Dall’Arno, E. Passaro, R. Gallego, M. Pawlowski, and A. Acin, Detection loophole attacks on semi-device-independent quantum and classical protocols, Quantum Inf. Comput. 15, 37 (2015), arXiv:1210.1272 [quant-ph] .
  * Brown  _et al._ [2021] P. Brown, H. Fawzi, and O. Fawzi, Device-independent lower bounds on the conditional von Neumann entropy (2021), arXiv:2106.13692 [quant-ph] .
  * Tan  _et al._ [2021] E. Y.-Z. Tan, R. Schwonnek, K. T. Goh, I. W. Primaatmaja, and C. C.-W. Lim, npj Quantum Inf. 7, 158 (2021).
  * Dupuis  _et al._ [2020] F. Dupuis, O. Fawzi, and R. Renner, Entropy accumulation, Commun. Math. Phys. 379, 867 (2020).
  * Tavakoli [2021] A. Tavakoli, Semi-device-independent framework based on restricted distrust in prepare-and-measure experiments, Phys. Rev. Lett. 126, 210503 (2021).